排列与组合

排列与组合都从不同对象中选出若干个；区别是交换选出对象的位置后，是否成为新结果。把 6 位学生中的 3 位安排为第一、第二、第三名，是排列；只选 3 位组成小组，是组合。先辨认结果的身份，再写公式。

排列数来自连续的选择

设 $n$ 个对象各不相同，从中不重复地取 $k$ 个并排成一列，要求整数 $0 \leq k \leq n$ 。第一位有 $n$ 种选择，第二位剩 $n - 1$ 种，直至第 $k$ 位剩 $n - k + 1$ 种，因此 $A_{n}^{k} = n (n - 1) \dots (n - k + 1) = \frac{n!}{(n - k)!} .$ 符号 $n! = n (n - 1) \dots 1$ 称为阶乘，约定 $0! = 1$ ，于是“不选任何对象并排成空列”有 $A_{n}^{0} = 1$ 种。六人争前三名，数量为 $A_{6}^{3} = 6 \cdot 5 \cdot 4 = 120$ 。

组合数为何要除以 k!

不计顺序地选出 $k$ 个对象后，这一组选中的对象可以排成 $k!$ 种列。每组都恰好对应这么多排列，故组合数为 $C_{n}^{k} = (\binom{n}{k}) = \frac{A_{n}^{k}}{k!} = \frac{n!}{k! (n - k)!} .$ 六人选三人的小组只有 $C_{6}^{3} = 20$ 个；每个小组又能排出 $3! = 6$ 个前三名次序， $20 \cdot 6 = 120$ ，和排列数核对一致。

这个除法成立是因为每个无序三人组都被同样多地重复计算。若某些位置另有资格限制，重复次数可能不一样，不能先随意排列再一律除以阶乘。最稳妥的是把一个完整结果写成“哪些人＋是否分角色”的具体对象。

用互补选择与分类求组合数

从 $n$ 人中选 $k$ 人，与指定留下的 $n - k$ 人一一对应，所以 $(\binom{n}{k}) = (\binom{n}{n - k})$ 。从 6 人选 5 人不必逐组列出：等价于决定唯一没选中的人，结果为 $(\binom{6}{5}) = 6$ 。

若固定其中一位甲，从 $n$ 人选 $k$ 人，可按“含甲”和“不含甲”分类，得到 $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) .$ 第一项先选甲、再选余下 $k - 1$ 人；第二项从其余 $n - 1$ 人中直接选 $k$ 人。这个等式既是杨辉三角的逐行生成规则，也是二项式定理系数之间的关系。

条件变化后重新判断对象

若从 4 个数字中选 3 个组成无重复的三位号码，选中的是有序数字列，共 $A_{4}^{3} = 24$ 个，前提是数字都可以放在百位。若数字中含 0，首位不能为 0，应先按首位另算，不能照搬 24。若允许数字重复，每位有 4 种，结果为 $4^{3}$ （仍须另外处理首位限制）。

相同物品的排列又是另一题。例如字母 A、A、B、B 的不同排法有 $4! / (2! 2!) = 6$ 种，因为交换两个 A 或两个 B 不会形成新字串。这里分母去掉的是相同物品内部的重复，不是把四个位置的全部顺序抹去。

试算。7 人中选 2 位代表并指定其中一位发言。先选代表再指定发言者，有 $(\binom{7}{2}) \cdot 2 = 42$ 种；先选发言者再选另一位，有 $7 \cdot 6 = 42$ 种。两种算法数的是同一组结果，互相校验。

参考资料

MIT 6.042J《Mathematics for Computer Science》计数与二项式系数章节。
更广的分配、隔板和容斥问题见组合数学。