组合公式定理

第一步(把选排按其基础子集分组):从 $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)!}$。