帕斯卡恒等式

帕斯卡恒等式把一次选取拆成两种互斥情形： $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}), 1 \leq k \leq n .$ 它是杨辉三角中“下方一数等于上方相邻两数之和”的精确形式，也能作为递推计算组合数的依据。

固定一个元素后分类

从 $n$ 个不同元素中选 $k$ 个，先指定其中一个元素 $u$ 。若选 $u$ ，剩余 $k - 1$ 个从其余 $n - 1$ 个中选，有 $(\binom{n - 1}{k - 1})$ 种；若不选 $u$ ，全部 $k$ 个从其余元素中选，有 $(\binom{n - 1}{k})$ 种。两类不重不漏，故相加。

例如从五人中选两人，预先指定甲：含甲的组合有 $(\binom{4}{1}) = 4$ 个，不含甲的有 $(\binom{4}{2}) = 6$ 个，总数 $4 + 6 = 10 = (\binom{5}{2})$ 。若把两类当作独立步骤相乘，会把“是否含甲”误当作还要再选一次，得出错误数量。

与二项式系数的联系

将 $(1 + t)^{n - 1}$ 乘 $(1 + t)$ 。得到 $t^{k}$ 的途径也恰有两种：前一个因子提供 $t^{k}$ 或 $t^{k - 1}$ 。因此二项式定理的代数展开也给出同一递推。两种证明分别解释“选人”与“取项”，说明公式并非只属于某一种题型。

参考资料

MIT，Mathematics for Computer Science，Counting 章节。
MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
继续阅读：二项式定理、递推关系、组合数学。