帕斯卡恒等式

第一步(固定一个元素,按是否包含分类):在 $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$。