- 推导多项式系数(multinomial coefficient)的公式 \(\binom{n}{n_1,n_2,\ldots,n_r}=\dfrac{n!}{n_1!n_2!\cdots n_r!}\)，说明它是组合数向 "\(r\) 个组"的推广；
- 叙述多项式定理(multinomial theorem)并用"从 \(n\) 个因子中分组取变量"的组合论证证明之；
- 说明 \(r=2\) 时多项式系数退化为二项式系数 \(\binom{n}{k}\)，并解释行和恒等式 \(\sum \binom{n}{n_1,\ldots,n_r}=r^n\)；
- 运用多项式系数解决字母重排、图书分配、放球入盒与席位划分等经典计数问题；
- 辨析"组可区分"与"组不可区分"、"对象互异"与"对象相同"这两类易混情形。
1. 从组合到多项式系数：分成 r 个组
1.4 节的组合回答的是"从 \(n\) 个不同对象中不计次序地取出 \(k\) 个"的计数问题。换一个角度看，它其实是一个分成两组的问题：\(k\) 个对象"入选"、\(n-k\) 个对象"落选"，故 \(\binom{n}{k}=\dfrac{n!}{k!(n-k)!}\)。然而现实中的分配问题常常不止两个去向：9 本不同的书要分给 3 个孩子；11 个字母要填进 11 个位置，其中 4 个位置留给 S；一间办公室的人要分派到若干个项目组。这时"入选/落选"的二分法不够用了，需要把对象一次分进 \(r\) 个组，各组大小预先指定。本节的核心概念多项式系数(multinomial coefficient)正是为此而生。
设 \(n_1,n_2,\ldots,n_r\) 为非负整数，\(n_1+n_2+\cdots+n_r=n\)。记 \[ \binom{n}{n_1,\,n_2,\,\ldots,\,n_r}\;=\;\frac{n!}{n_1!\,n_2!\cdots n_r!}\,, \] 也写作 \(C(n;\,n_1,n_2,\ldots,n_r)\)，称为多项式系数(multinomial coefficient)。
分母中 \(n_i=0\) 时约定 \(0!=1\)，该项不产生任何影响。当 \(r=2\) 时 \(\binom{n}{k,\,n-k}=\dfrac{n!}{k!(n-k)!}\) 恰是二项式系数——多项式系数是组合数的直接推广。
定义只给出了记号与公式，它凭什么数出"分组数"？下面的定理给出组合解释，证明完全依赖 1.2 节的计数基本原理与 1.4 节的组合数公式。
把 \(n\) 个互不相同的对象划分成 \(r\) 个可区分（有编号 \(1,2,\ldots,r\)）的组，要求第 \(i\) 组恰含 \(n_i\) 个对象（\(n_1+\cdots+n_r=n\)），则分法总数为 \[ \binom{n}{n_1,\,n_2,\,\ldots,\,n_r}=\frac{n!}{n_1!\,n_2!\cdots n_r!}\,. \]
思路一（依次选取）：第 1 组从 \(n\) 个对象中选 \(n_1\) 个，有 \(\binom{n}{n_1}\) 种；选定后第 2 组从剩下 \(n-n_1\) 个中选 \(n_2\) 个，有 \(\binom{n-n_1}{n_2}\) 种；……；最后一组把余下的 \(n_r\) 个全部收入，有 \(\binom{n_r}{n_r}=1\) 种。由计数基本原理连乘，并注意到相邻两项的阶乘逐个相消： \[ \binom{n}{n_1}\binom{n-n_1}{n_2}\cdots\binom{n_r}{n_r} =\frac{n!}{n_1!(n-n_1)!}\cdot\frac{(n-n_1)!}{n_2!(n-n_1-n_2)!}\cdots =\frac{n!}{n_1!n_2!\cdots n_r!}\,. \] 思路二（先排后消序）：把 \(n\) 个对象排成一列，共 \(n!\) 种排列；规定排列的前 \(n_1\) 个进第 1 组、接着 \(n_2\) 个进第 2 组、……。同一个分组里，各组内部的对象任意换序会给出不同排列，却对应同一个分组，故每个分组恰被数了 \(n_1!\,n_2!\cdots n_r!\) 次。于是分组数为 \(\dfrac{n!}{n_1!\,n_2!\cdots n_r!}\)。
思路二把 1.4 节"排列数 = 组合数 \(\times\, k!\)"的消序思想推广到了 \(r\) 个组：分母里的每一个阶乘 \(n_i!\) 都在为第 \(i\) 组"擦掉"组内次序。做题时只要能确认"对象互异、组有编号、各组大小指定"，就可以直接套用定理 1。
2. 多项式定理
与二项式系数一样，多项式系数也有一个代数出身。1.4 节把 \((x+y)^n\) 展开式的系数叫二项式系数；现在把底数换成 \(r\) 个变量的和，展开式的系数恰为多项式系数。
对任意正整数 \(r\) 与 \(n\)， \[ (x_1+x_2+\cdots+x_r)^n \;=\;\sum_{n_1+n_2+\cdots+n_r=n}\frac{n!}{n_1!\,n_2!\cdots n_r!}\; x_1^{n_1}x_2^{n_2}\cdots x_r^{n_r}\,, \] 其中求和遍历一切满足 \(n_1+\cdots+n_r=n\) 的非负整数组 \((n_1,\ldots,n_r)\)。
例如取 \(r=3,\ n=2\)，直接相乘可验证 \[ (x_1+x_2+x_3)^2=x_1^2+x_2^2+x_3^2+2x_1x_2+2x_1x_3+2x_2x_3\,, \] 交叉项的系数 \(2=\binom{2}{1,1,0}\)，平方项的系数 \(1=\binom{2}{2,0,0}\)。当 \(r=2\) 时定理 2 退化为 1.4 节的二项式定理(binomial theorem)，这也再次说明 \(\binom{n}{k}\) 是多项式系数的特例。
在定理 2 中令 \(x_1=x_2=\cdots=x_r=1\)，得到行和恒等式 \[ \sum_{n_1+\cdots+n_r=n}\binom{n}{n_1,\,n_2,\,\ldots,\,n_r}=r^{\,n}\,, \] 其组合意义一目了然：把 \(n\) 个互异的球放入 \(r\) 个有编号的盒子，一切放法按"各盒占用数 \((n_1,\ldots,n_r)\)"分类计数得左边；而每个球独立地面对 \(r\) 个盒子各选其一，由乘法原理得右边 \(r^n\)。同一个量、两种数法——这与 1.4 节 \(\sum_k\binom{n}{k}=2^n\) 的处理如出一辙。
| 项目 | \(r=2\)（1.4 节） | 一般 \(r\)（本节） |
|---|---|---|
| 分组计数 | \(\binom{n}{k}=\dfrac{n!}{k!(n-k)!}\) | \(\binom{n}{n_1,\ldots,n_r}=\dfrac{n!}{n_1!\cdots n_r!}\) |
| 代数定理 | \((x+y)^n=\sum\limits_k\binom{n}{k}x^k y^{\,n-k}\) | \((x_1+\cdots+x_r)^n=\sum\limits_{n_1+\cdots+n_r=n}\binom{n}{n_1,\ldots,n_r}\prod x_i^{n_i}\) |
| 令所有变量 \(=1\) | \(\sum\limits_k\binom{n}{k}=2^n\) | \(\sum\limits_{n_1+\cdots+n_r=n}\binom{n}{n_1,\ldots,n_r}=r^n\) |
| 组合情境 | 入选 / 落选；分 2 组 | 分配给 \(r\) 个孩子、盒子、选区…… |
3. 例题选讲
单词 MISSISSIPPI 的 11 个字母共有多少种不同的排列方式（不必是英文单词）？
把 9 本互不相同的书分给甲、乙、丙三个孩子，每人恰好分得 3 本，共有多少种分法？
把 \(n\) 个彼此不同的球放入编号为 \(1,2,3\) 的三个盒子，要求盒 \(i\) 恰放入 \(n_i\) 个球（\(n_1+n_2+n_3=n\)）。共有多少种放法？又：\(n=5\)、\((n_1,n_2,n_3)=(2,2,1)\) 时是多少？
某议会共有 6 个席位（席位可区分，例如来自 6 个不同选区），全部在 A、B 两党之间分配，且每党至少占 1 席。共有多少种分配格局？
4. 使用要点与两类易混情形
使用定理 1 之前，必须核对两个前提：对象互异、组可区分。例 2 中三个孩子是不同的人，组天然有编号；但若问题改成"把 12 人分成 3 个不挂任何标签、大小均为 4 的小组"，小组之间彼此无法区别，同样的分法会在"哪组算第 1 组"上被重复计算，须再除以 \(3!\)（见练习 3）。此外，字母重排问题（例 1）表面没有"组"，其实只要把位置看作对象、把"留给哪个字母"看作组，它就是标准的分组问题——多项式系数的题目大多可以还原成"互异对象 + 编号组 + 指定大小"的骨架。
其一，组可区分与否。\(\binom{n}{n_1,\ldots,n_r}\) 默认 \(r\) 个组有编号。若若干组大小相同且实际问题中这些组不加区分，应再除以同大小组之间的阶乘。例如 12 人分入甲、乙、丙三个（有名称的）项目组各 4 人有 \(\frac{12!}{4!4!4!}\) 种；若只是"分成三个无名小组"，则为 \(\frac{12!}{4!4!4!\,3!}\) 种。
其二，对象互异与否。本节处理的对象两两不同（不同的书、不同的球、不同的席位）。若对象彼此相同，计数工具就完全不同：把 9 本不同的书分给 3 个孩子各 3 本有 \(\frac{9!}{3!3!3!}=1{,}680\) 种；而把 9 本相同的书同样分配则只有 1 种——书无差异，"各拿 3 本"别无选择。1.6 节将系统研究"相同对象"的分配（相同球入盒、不定方程的整数解），使用的工具是隔板法(stars and bars)。学完 1.6 后请回看本注记：分清"对象是否互异"是第 1 章收尾阶段最重要的判断力。
5. 本节小结
- 多项式系数：\(\binom{n}{n_1,\ldots,n_r}=\dfrac{n!}{n_1!\cdots n_r!}\)（\(n_1+\cdots+n_r=n\)），数出把 \(n\) 个互异对象分成 \(r\) 个可区分、大小指定的组的分法数；证明可循"依次选取连乘"或"全排列消序"两条路线。
- 多项式定理：\((x_1+\cdots+x_r)^n=\sum\frac{n!}{n_1!\cdots n_r!}x_1^{n_1}\cdots x_r^{n_r}\)，系数来自"从 \(n\) 个因子中分组取变量"的计数。
- \(r=2\) 时退化为二项式系数与二项式定理；令各变量为 1 得行和恒等式 \(\sum\binom{n}{n_1,\ldots,n_r}=r^n\)，即"\(n\) 个互异球入 \(r\) 个编号盒"的两种数法。
- 典型应用：含重复字母的重排（MISSISSIPPI \(\to 34{,}650\)）、图书/人员分配、放球入盒、席位划分；"每组一个多项式系数再求和"是常见节奏（例 4 的 \(62=2^6-2\)）。
- 两个前提别忘核对：对象互异、组可区分；组不可区分时须补除组间阶乘，对象相同时本节公式失效，那是 1.6 节隔板法的领地。
练习
练习 1-5-1
单词 PERMUTATION 的 11 个字母共有多少种不同的排列方式？
答案与提示清点字母：P、E、R、M、U、T、A、T、I、O、N——除 T 出现 2 次外，其余 9 个字母各出现 1 次。由定理 1， \[ \frac{11!}{2!\,1!\,\cdots\,1!}=\frac{11!}{2}=\frac{39{,}916{,}800}{2}=19{,}958{,}400\,. \] 只有字母 T 的内部换位不产生新排列，故只除以 \(2!\)。
练习 1-5-2
一副 52 张的扑克牌发给 4 名玩家，每人 13 张，共有多少种发法？
答案与提示牌互异、玩家可区分、各得 13 张，正是 \((n;n_1,n_2,n_3,n_4)=(52;13,13,13,13)\)： \[ \frac{52!}{(13!)^4}\approx 5.36\times 10^{28}\,. \] 这是天文级数字——作为对照，阿伏伽德罗常数约 \(6.02\times 10^{23}\)，还不及它的十万分之一。凭直觉感受阶乘之快：把 52! 与 \((13!)^4\) 直接展开相除并不现实，计数公式的价值正在于用一个紧凑的分式给出答案。
练习 1-5-3
把 12 名成员分成 3 个组、每组 4 人：(a) 若三组分别派往甲、乙、丙三个（不同的）项目组；(b) 若三组只是三个不加任何标签的小组。各有多少种分法？
答案与提示(a) 组可区分：\(\dfrac{12!}{4!\,4!\,4!}=34{,}650\)。巧的是它与例 1 的 MISSISSIPPI 重排数相同，因为 \(\dfrac{12!}{4!}=\dfrac{11!}{2!}\)。(b) 组不可区分：三个大小相同的组互换仍是同一分法，须再除以 \(3!\)：\(\dfrac{12!}{4!\,4!\,4!\,3!}=\dfrac{34{,}650}{6}=5{,}775\)。对照 (a)(b) 即"组可区分与否"的差别所在。
练习 1-5-4
求 \((x_1+x_2+x_3)^4\) 展开式中 \(x_1^2x_2x_3\) 项的系数，并写出该展开式的项数。
答案与提示系数为 \(\binom{4}{2,\,1,\,1}=\dfrac{4!}{2!\,1!\,1!}=12\)。项数等于满足 \(n_1+n_2+n_3=4\) 的非负整数解个数，枚举 \((4,0,0)\) 型 3 个、\((3,1,0)\) 型 6 个、\((2,2,0)\) 型 3 个、\((2,1,1)\) 型 3 个，共 15 项——"解的个数"如何不靠枚举得到，正是 1.6 节的主题。