aiwiki.page
中文
数学 / 离散数学与逻辑 / multinomial-coefficient

多项式系数

多项式系数用于计算各类别数量给定时的排列数,也是和的幂展开式中相应项的系数。

20 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
二项式系数组合数学概率阶乘集合划分置换多项式二项式定理多项式系数

多项式系数是一个非负整数,表示将 nn 个不同对象分配到大小指定、带有标号的各组中的方法数,也表示每种符号出现次数指定时不同序列的数量。它将二项式系数从两组的情形推广到了任意有限组的情形。多项式系数出现在组合数学、和的幂的展开式,以及涉及多种可能结果的概率计算中。

定义与记号

对于满足

n1+⋯+nk=n,n_1+\cdots+n_k=n,

的非负整数 n1,…,nkn_1,\ldots,n_k,多项式系数定义为

(nn1,n2,…,nk)=n!n1!n2!⋯nk!,\binom{n}{n_1,n_2,\ldots,n_k} =\frac{n!}{n_1!n_2!\cdots n_k!},

其中 m!m! 表示 mm 的阶乘,并规定 0!=10!=1。

上方参数表示对象或位置的总数,下方参数表示各类别的数量。有些记号省略上方参数,因为它可以由下方参数确定。

对于两个类别,

(nr,n−r)=(nr).\binom{n}{r,n-r}=\binom{n}{r}.

对于一个类别,系数为 11。若 n=0n=0,则所有类别的数量均为零,系数也为 11,对应唯一的空排列。

阶乘形式的定义要求所有下方参数均为非负数,且其和等于上方参数。在递推式和系数公式中,常将不满足这些条件的整数参数组所对应的值定义为零,以便使用。

计数解释

将不同对象分配到带标号的组中

设将 nn 个不同对象分配到 kk 个带标号的组中,要求第 ii 组恰好包含 nin_i 个对象。分配方法数为

(nn1,…,nk).\binom{n}{n_1,\ldots,n_k}.

为说明这一点,可以先将全部 nn 个对象排成一行,再依次切分为长度为 n1,…,nkn_1,\ldots,n_k 的连续区块。最初共有 n!n! 种排列。任一区块内部对象的重新排列不会改变分组结果,因此每种分配方法都被重复计算了 n1!⋯nk!n_1!\cdots n_k! 次。

组的标号至关重要。若各组不带标号,计数问题就变成了集合划分问题,可能需要额外调整。例如,将 n=krn=kr 个不同对象分成 kk 个不带标号的组,且每组的大小均为正整数 rr,其方法数为

n!(r!)kk!.\frac{n!}{(r!)^k k!}.

含重复符号的排列

同一个系数也表示长度为 nn、其中符号 ii 出现 nin_i 次的不同序列的数量。这通常称为多重集的置换计数。

例如,单词 BANANA 包含三个 A、两个 N 和一个 B。其不同字母排列的数量为

(63,2,1)=6!3! 2! 1!=60.\binom{6}{3,2,1} =\frac{6!}{3!\,2!\,1!} =60.

尽管相同符号的各个副本无法区分,但它们在序列中的位置是可以区分的。选择每种符号占据哪些位置,等价于将这些位置分配到带标号的组中。

格路径

考虑整数格中从原点到 (n1,…,nk)(n_1,\ldots,n_k) 的路径,其中每一步恰好使一个坐标增加 11。每条路径都包含沿第 ii 个坐标方向的 nin_i 步,因此路径数为

(n1+⋯+nkn1,…,nk).\binom{n_1+\cdots+n_k}{n_1,\ldots,n_k}.

这一解释适用于没有禁止经过的顶点或边界约束等额外限制的情形。

多项式定理

多项式定理指出,

(x1+⋯+xk)n=∑n1,…,nk≥0n1+⋯+nk=n(nn1,…,nk)x1n1⋯xknk.(x_1+\cdots+x_k)^n = \sum_{\substack{n_1,\ldots,n_k\geq0\\ n_1+\cdots+n_k=n}} \binom{n}{n_1,\ldots,n_k} x_1^{n_1}\cdots x_k^{n_k}.

因此,多项式系数就是展开后的多项式中相应单项式的系数。当 k=2k=2 时,这就是二项式定理。

将这个幂看成 nn 个相同的和式的乘积,即可得到该公式。要得到 x1n1⋯xknkx_1^{n_1}\cdots x_k^{n_k},必须恰好从 nin_i 个因式中选取 xix_i。这样的选择方法数就是多项式系数。

例如,

(x+y+z)3=x3+y3+z3+3x2y+3x2z+3xy2+3y2z+3xz2+3yz2+6xyz.(x+y+z)^3 =x^3+y^3+z^3 +3x^2y+3x^2z+3xy^2 +3y^2z+3xz^2+3yz^2+6xyz.

其中 xyzxyz 的系数为

(31,1,1)=6.\binom{3}{1,1,1}=6.

该定理适用于彼此可交换的变量,包括交换环中的元素。对于任意不可交换的量,这一形式并不适用,因为 xyxy 和 yxyx 这样的项未必相等。

恒等式与递推式

对称性与逐次选取

任意重排下方参数,系数都保持不变:

(nn1,…,nk)=(nnσ(1),…,nσ(k))\binom{n}{n_1,\ldots,n_k} = \binom{n}{n_{\sigma(1)},\ldots,n_{\sigma(k)}}

其中 σ\sigma 是类别下标的任意一个置换。

多项式系数也可以写成二项式系数的乘积:

(nn1,…,nk)=∏i=1k(n−∑j<injni).\binom{n}{n_1,\ldots,n_k} = \prod_{i=1}^{k} \binom{n-\sum_{j<i}n_j}{n_i}.

这对应于先选出第一组,再从剩余对象中选出第二组,如此继续。这也证明了阶乘之比是整数。

帕斯卡型递推式

对于 n≥1n\geq1,

(nn1,…,nk)=∑1≤i≤kni>0(n−1n1,…,ni−1,…,nk).\binom{n}{n_1,\ldots,n_k} = \sum_{\substack{1\leq i\leq k\\n_i>0}} \binom{n-1}{n_1,\ldots,n_i-1,\ldots,n_k}.

按照序列的最后一个符号分类,即可得到这一递推关系。它推广了二项式系数的帕斯卡递推式。

所有系数之和

在多项式定理中令每个变量都等于 11,可得

∑n1+⋯+nk=nni≥0(nn1,…,nk)=kn.\sum_{\substack{n_1+\cdots+n_k=n\\n_i\geq0}} \binom{n}{n_1,\ldots,n_k} =k^n.

从组合计数的角度看,两边都表示由 kk 种符号组成的所有长度为 nn 的序列的数量。

该求和式中计数向量的数量为

(n+k−1k−1).\binom{n+k-1}{k-1}.

它计算的是各类别数量的可能组合,而不是序列数,不应将其与单个多项式系数混淆。

概率与统计

设进行 nn 次统计独立的试验,每次试验都有 kk 种可能结果,各结果的概率固定为 p1,…,pkp_1,\ldots,p_k,且满足

pi≥0,∑i=1kpi=1.p_i\geq0,\qquad \sum_{i=1}^{k}p_i=1.

令随机变量 NiN_i 表示结果 ii 出现的次数。该计数向量服从多项分布,其概率质量函数为

Pr⁡(N1=n1,…,Nk=nk)=(nn1,…,nk)∏i=1kpini.\Pr(N_1=n_1,\ldots,N_k=n_k) = \binom{n}{n_1,\ldots,n_k} \prod_{i=1}^{k}p_i^{n_i}.

当某个类别的概率和出现次数均为零时,将其对应的因子解释为 11。

满足这些计数的每个特定结果序列,其概率均为 ∏ipini\prod_i p_i^{n_i}。多项式系数给出了构成该事件的这类序列的数量。

例如,独立投掷一枚均匀骰子六次,每一面恰好出现一次的概率为

(61,1,1,1,1,1)(16)6=6!66.\binom{6}{1,1,1,1,1,1}\left(\frac16\right)^6 =\frac{6!}{6^6}.

当只有两种结果时,多项分布就化为二项分布。根据固定计数向量进行最大似然估计时,多项式系数不随未知概率而变化。因此,在寻找使似然最大的参数时,可以将它省略,但它仍然是概率质量函数的一部分。

计算与渐近大小

直接计算阶乘可能产生非常大的中间值。精确计算时,可以改用逐次选取所对应的二项式系数乘积,必要时采用任意精度整数运算。

对于近似计算,特别是在只需要对数值时,可以使用

log⁡(nn1,…,nk)=log⁡Γ(n+1)−∑i=1klog⁡Γ(ni+1),\log\binom{n}{n_1,\ldots,n_k} = \log\Gamma(n+1)-\sum_{i=1}^{k}\log\Gamma(n_i+1),

其中 Γ\Gamma 为伽马函数。采用对数计算可避免直接计算巨大阶乘所导致的溢出,不过相消和舍入仍可能影响精度。

斯特林近似描述了系数的增长规律。记 qi=ni/nq_i=n_i/n。当 kk 固定,且随着 nn 增大,所有比例始终与零保持一定距离时,

(nn1,…,nk)∼exp⁡ ⁣(nH(q))(2πn)(k−1)/2q1⋯qk,\binom{n}{n_1,\ldots,n_k} \sim \frac{\exp\!\bigl(nH(q)\bigr)} {(2\pi n)^{(k-1)/2}\sqrt{q_1\cdots q_k}},

其中

H(q)=−∑i=1kqilog⁡qiH(q)=-\sum_{i=1}^{k}q_i\log q_i

是以自然对数定义的信息熵。

这一公式将给定类别数量的排列与信息论联系起来:其主要的指数增长率由熵决定。若某些类别的数量始终很小或为零,上述近似就不能直接用于这些类别。

对于固定的 nn 和 kk,当各类别数量相差不超过一时,系数最大。事实上,若 ni≥nj+2n_i\geq n_j+2,将 nin_i 减少一、同时将 njn_j 增加一,会使系数乘以

ninj+1>1.\frac{n_i}{n_j+1}>1.

因此,反复调整不均衡的类别数量会使系数不断增大,直至各类别数量尽可能相等。