多项式系数是一个非负整数,表示将 n 个不同对象分配到大小指定、带有标号的各组中的方法数,也表示每种符号出现次数指定时不同序列的数量。它将二项式系数从两组的情形推广到了任意有限组的情形。多项式系数出现在组合数学、和的幂的展开式,以及涉及多种可能结果的概率计算中。
定义与记号
对于满足
n1+⋯+nk=n,
的非负整数 n1,…,nk,多项式系数定义为
(n1,n2,…,nkn)=n1!n2!⋯nk!n!,
其中 m! 表示 m 的阶乘,并规定 0!=1。
上方参数表示对象或位置的总数,下方参数表示各类别的数量。有些记号省略上方参数,因为它可以由下方参数确定。
对于两个类别,
(r,n−rn)=(rn).
对于一个类别,系数为 1。若 n=0,则所有类别的数量均为零,系数也为 1,对应唯一的空排列。
阶乘形式的定义要求所有下方参数均为非负数,且其和等于上方参数。在递推式和系数公式中,常将不满足这些条件的整数参数组所对应的值定义为零,以便使用。
计数解释
将不同对象分配到带标号的组中
设将 n 个不同对象分配到 k 个带标号的组中,要求第 i 组恰好包含 ni 个对象。分配方法数为
(n1,…,nkn).
为说明这一点,可以先将全部 n 个对象排成一行,再依次切分为长度为 n1,…,nk 的连续区块。最初共有 n! 种排列。任一区块内部对象的重新排列不会改变分组结果,因此每种分配方法都被重复计算了 n1!⋯nk! 次。
组的标号至关重要。若各组不带标号,计数问题就变成了集合划分问题,可能需要额外调整。例如,将 n=kr 个不同对象分成 k 个不带标号的组,且每组的大小均为正整数 r,其方法数为
(r!)kk!n!.
含重复符号的排列
同一个系数也表示长度为 n、其中符号 i 出现 ni 次的不同序列的数量。这通常称为多重集的置换计数。
例如,单词 BANANA 包含三个 A、两个 N 和一个 B。其不同字母排列的数量为
(3,2,16)=3!2!1!6!=60.
尽管相同符号的各个副本无法区分,但它们在序列中的位置是可以区分的。选择每种符号占据哪些位置,等价于将这些位置分配到带标号的组中。
格路径
考虑整数格中从原点到 (n1,…,nk) 的路径,其中每一步恰好使一个坐标增加 1。每条路径都包含沿第 i 个坐标方向的 ni 步,因此路径数为
(n1,…,nkn1+⋯+nk).
这一解释适用于没有禁止经过的顶点或边界约束等额外限制的情形。
多项式定理
多项式定理指出,
(x1+⋯+xk)n=n1,…,nk≥0n1+⋯+nk=n∑(n1,…,nkn)x1n1⋯xknk.
因此,多项式系数就是展开后的多项式中相应单项式的系数。当 k=2 时,这就是二项式定理。
将这个幂看成 n 个相同的和式的乘积,即可得到该公式。要得到 x1n1⋯xknk,必须恰好从 ni 个因式中选取 xi。这样的选择方法数就是多项式系数。
例如,
(x+y+z)3=x3+y3+z3+3x2y+3x2z+3xy2+3y2z+3xz2+3yz2+6xyz.
其中 xyz 的系数为
(1,1,13)=6.
该定理适用于彼此可交换的变量,包括交换环中的元素。对于任意不可交换的量,这一形式并不适用,因为 xy 和 yx 这样的项未必相等。
恒等式与递推式
对称性与逐次选取
任意重排下方参数,系数都保持不变:
(n1,…,nkn)=(nσ(1),…,nσ(k)n)
其中 σ 是类别下标的任意一个置换。
多项式系数也可以写成二项式系数的乘积:
(n1,…,nkn)=i=1∏k(nin−∑j<inj).
这对应于先选出第一组,再从剩余对象中选出第二组,如此继续。这也证明了阶乘之比是整数。
帕斯卡型递推式
对于 n≥1,
(n1,…,nkn)=1≤i≤kni>0∑(n1,…,ni−1,…,nkn−1).
按照序列的最后一个符号分类,即可得到这一递推关系。它推广了二项式系数的帕斯卡递推式。
所有系数之和
在多项式定理中令每个变量都等于 1,可得
n1+⋯+nk=nni≥0∑(n1,…,nkn)=kn.
从组合计数的角度看,两边都表示由 k 种符号组成的所有长度为 n 的序列的数量。
该求和式中计数向量的数量为
(k−1n+k−1).
它计算的是各类别数量的可能组合,而不是序列数,不应将其与单个多项式系数混淆。
概率与统计
设进行 n 次统计独立的试验,每次试验都有 k 种可能结果,各结果的概率固定为 p1,…,pk,且满足
pi≥0,i=1∑kpi=1.
令随机变量 Ni 表示结果 i 出现的次数。该计数向量服从多项分布,其概率质量函数为
Pr(N1=n1,…,Nk=nk)=(n1,…,nkn)i=1∏kpini.
当某个类别的概率和出现次数均为零时,将其对应的因子解释为 1。
满足这些计数的每个特定结果序列,其概率均为 ∏ipini。多项式系数给出了构成该事件的这类序列的数量。
例如,独立投掷一枚均匀骰子六次,每一面恰好出现一次的概率为
(1,1,1,1,1,16)(61)6=666!.
当只有两种结果时,多项分布就化为二项分布。根据固定计数向量进行最大似然估计时,多项式系数不随未知概率而变化。因此,在寻找使似然最大的参数时,可以将它省略,但它仍然是概率质量函数的一部分。
计算与渐近大小
直接计算阶乘可能产生非常大的中间值。精确计算时,可以改用逐次选取所对应的二项式系数乘积,必要时采用任意精度整数运算。
对于近似计算,特别是在只需要对数值时,可以使用
log(n1,…,nkn)=logΓ(n+1)−i=1∑klogΓ(ni+1),
其中 Γ 为伽马函数。采用对数计算可避免直接计算巨大阶乘所导致的溢出,不过相消和舍入仍可能影响精度。
斯特林近似描述了系数的增长规律。记 qi=ni/n。当 k 固定,且随着 n 增大,所有比例始终与零保持一定距离时,
(n1,…,nkn)∼(2πn)(k−1)/2q1⋯qkexp(nH(q)),
其中
H(q)=−i=1∑kqilogqi
是以自然对数定义的信息熵。
这一公式将给定类别数量的排列与信息论联系起来:其主要的指数增长率由熵决定。若某些类别的数量始终很小或为零,上述近似就不能直接用于这些类别。
对于固定的 n 和 k,当各类别数量相差不超过一时,系数最大。事实上,若 ni≥nj+2,将 ni 减少一、同时将 nj 增加一,会使系数乘以
nj+1ni>1.
因此,反复调整不均衡的类别数量会使系数不断增大,直至各类别数量尽可能相等。