排列与组合

依次填入 k 个有序位置,每填一个位置后剩余合格对象数就减少一个,这正是独立相继步骤的乘法原理所描述的情形。

第一步(设置位置):把要填的 $k$ 个位置依次记为位置1到位置 $k$。用 $n$ 个对象之一填每个位置,且不重复使用已放置的对象,这是一项由 $k$ 个相继步骤组成的工作。

第二步(应用乘法原理):位置1有 $n$ 种填法。填完后已用掉一个对象,所以无论位置1选了哪个对象,位置2都有 $n-1$ 种填法。依此类推,位置 $k$ 有 $n-k+1$ 种填法,因为已经用掉了 $k-1$ 个对象。由乘法原理,总数为乘积 $n(n-1)\cdots(n-k+1)$。

第三步(改写为阶乘之商):乘以再除以缺失的尾部 $(n-k)!$,得到 $n(n-1)\cdots(n-k+1) = \frac{n(n-1)\cdots(n-k+1)\cdot (n-k)!}{(n-k)!} = \frac{n!}{(n-k)!}$,这正是 $A_n^k = \frac{n!}{(n-k)!}$。

第四步(特殊情形 $k=n$):代入 $k=n$,利用 $0! = 1$ 得到 $A_n^n = \frac{n!}{0!} = \frac{n!}{1} = n!$,恢复排列数 $P_n = n!$。

每个大小为 k 的无序子集恰好能以 k! 种方式变成有序的选排,所以有序计数把每个子集都重复计数了相同的因子 k!;除以 k! 就消除了这种重复计数。

第一步(把选排按其基础子集分组):从 $n$ 个对象中选 $k$ 个的每一个选排,都是先选定某个 $k$ 元子集,再对其排序而得到的。把 $A_n^k$ 个选排按可能的 $k$ 元子集分成若干组,使得两个选排属于同一组当且仅当它们使用相同的对象集合。

第二步(每组的大小):固定一个 $k$ 元子集,由它构成的选排恰好对应该子集的各种排序方式,这样的排序方式共有 $k!$ 种($k$ 个对象的一个排列)。因此每一组恰好有 $k!$ 个选排。

第三步(对各组用加法原理):各组两两不相交(一个选排恰好属于一组),按定义共有 $C_n^k$ 组,每组大小为 $k!$。加法原理($k!$ 自加 $C_n^k$ 次)给出 $A_n^k = C_n^k \cdot k!$。

第四步(解出组合数):两边除以 $k!$ 并代入 $A_n^k = \frac{n!}{(n-k)!}$,得到 $C_n^k = \dfrac{A_n^k}{k!}$,即 $C_n^k = \frac{n!}{k!(n-k)!}$。

这正是加法原理的又一体现:按是否包含某个固定元素,把所有大小为 k 的子集分成两种互斥情形,数目相加即可。

第一步(固定一个元素,按是否包含分类):在 $n$ 个对象中固定一个对象 $x$。每个 $k$ 元子集要么包含 $x$,要么不包含;这两种情形互斥,且合起来穷尽全部 $C_n^k$ 个子集。

第二步(数包含x的子集):包含 $x$ 的子集是从其余 $n-1$ 个对象中再选 $k-1$ 个而构成的,这样的子集共有 $C_{n-1}^{k-1}$ 个。

第三步(数不包含x的子集):不包含 $x$ 的子集是从其余 $n-1$ 个对象中选出全部 $k$ 个而构成的,这样的子集共有 $C_{n-1}^k$ 个。

第四步(应用加法原理):由于这两种情形互斥且穷尽了所有大小为 k 的子集,加法原理给出 $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$。