多项式系数 | Codeboy's Blog

形式陈述

若 $n_1+\cdots+n_k=n$ 且各 $n_i\ge0$ ，多项式系数为

\binom{n}{n_1,\ldots,n_k}=\frac{n!}{n_1!\cdots n_k!}.

它计数把 $n$ 个互异对象分入 $k$ 个有标号组且第 $i$ 组大小为 $n_i$ 的方法，也是 $(x_1+\cdots+x_k)^n$ 中 $x_1^{n_1}\cdots x_k^{n_k}$ 的系数。

直觉

把 $n$ 个互异元素依次排成一列有 $n!$ 种，但同一分组内部的排列不改变各组成员，因此每组分别除以 $n_i!$ 。等价地，也可先从 $n$ 个中选第一组，再从剩余者选第二组，连续二项式系数会望远镜成多项式系数。组标签是否有区别决定还要不要再除去组之间的对称。

例子与边界

多项式系数在各盒容量 $n_1,\ldots,n_k$ 已指定且盒有标签时计数分配；第二类 Stirling 数只指定非空块数，块本身无标签且大小可变。两者都涉及集合分组，却除去了不同的对称性。

把 5 人分为大小 2、2、1 的三个有标号小组有 $5!/(2!2!1!)=30$ 种。若小组无标号且大小重复，还要再除以交换同型组的对称因子。二项式系数是 $k=2$ 的特例；当下标和不为 $n$ 时通常定义系数为 0。

把十名学生分到标号为 A、B、C 的三组，大小分别为 $3,3,4$ ，方案数为

\binom{10}{3,3,4}=\frac{10!}{3!3!4!}.

若 A、B 两组三人组没有标签，交换它们不产生新方案，还需再除以 $2!$ 。当某个 $n_i=0$ 时以 $0!=1$ 处理空组；各 $n_i$ 之和不为 $n$ 时系数通常定义为零。

推论与应用

阶乘与组合给出分组公式，乘法原理解释逐组选取。它是 $(x_1+\cdots+x_k)^n$ 展开中的系数，也描述多类别样本计数与 multinomial 分布；若组本身不带标签，则问题转向集合划分而非直接使用该系数。

参考资料

Eric Lehman, F. Thomson Leighton, and Albert R. Meyer, Mathematics for Computer Science, rev. 2018，Parts I–V。
Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th ed., McGraw-Hill, 2019，Chs. 1–8。