Pascal triangle · 二项式定理

Pascal 三角与二项式定理

把组合数 $C(n, k)$ 按 $n$ 逐行、 $k$ 逐列排成一个三角形，行号 $n \ge 0$ 、每行列号 $k$ 取遍 $0 \le k \le n$ ，就是 Pascal 三角。它有一条极简的递推：两腰即 $k = 0$ 与 $k = n$ 处恒为 $1$ ，其余每个内部数都等于它上方紧邻两数之和。而每一行的数恰是二项式定理 $(a+b)^n$ 展开后各项的系数。

1 · 上方两数之和

0 < k < n : C(n, k) = C(n−1, k−1) + C(n−1, k)

C(n, k) = C(n-1,\, k-1) + C(n-1,\, k), \qquad 0 < k < n

图 1-1 · Pascal 三角与它的递推。可拖动滑块决定显示到第几行，点击任一格看它高亮为选中、上一行的两个父格高亮为绿，三者相加相等。

递推只对内部格 $0 < k < n$ 成立。两腰处两个父格 $C(n-1, k-1)$ 与 $C(n-1, k)$ 中恰有一个的列号越出上一行范围，约定越界的组合数记为 $0$ ，于是只剩一个父格；而剩下的那个就是上一行的腰，其值为 $1$ ，故 $C(n, 0) = C(n, n) = 1$ 逐行传递下来。

2 · 展开式的系数

binomial theorem · (a+b)ⁿ = Σ C(n,k)·aⁿ⁻ᵏ·bᵏ

把 $(a+b)^n$ 乘开：每个因子 $(a+b)$ 都要么出 $a$ 、要么出 $b$ ， $n$ 个因子里恰好选 $k$ 个出 $b$ 就得到 $a^{n-k} b^k$ ，而「从 $n$ 个里选 $k$ 个」的方案数即 $C(n, k)$ ，这就是该项的系数：

(a+b)^n = \sum_{k=0}^{n} C(n, k)\, a^{n-k} b^{k}

图 2-1 · Pascal 三角某一行与

(a+b)^n

展开式各项的对应。选中某格时下方高亮它对应的那一项。

两个可直接读出的事实：把第 $n$ 行所有数相加得 $2^n$ ，即令 $a = b = 1$ ，也就是 $n$ 个元素的全部子集数；每一行（ $n \ge 1$ ）交替加减得 $0$ ，即令 $a = 1$ 、 $b = -1$ 得 $(1-1)^n = 0$ ，顶点行 $n = 0$ 只有单个 $1$ 是例外。

3 · 递推与归纳步骤的同一性

induction step · C(n+1, k) = C(n, k−1) + C(n, k)

§2 的「从 $n$ 个因子里选 $k$ 个出 $b$ 」是二项式定理的组合证明，直接读出系数。若改走对指数 $n$ 做数学归纳法这条路，会发现 §1 那条递推恰好是归纳步骤的核心。

图 3-1 · 归纳步骤的逐行整理。两边乘

(a+b)

之后每一步做了什么，由右侧注解标出。

关键在合并那一步。同幂项 $a^{n+1-k} b^{k}$ 从两处汇合：左边和式里原第 $k$ 项乘 $a$ ，系数 $C(n, k)$ ；右边和式换元 $k \to k-1$ 后原第 $k-1$ 项乘 $b$ ，系数 $C(n, k-1)$ 。相加得该项系数 $C(n, k-1) + C(n, k)$ ，而要它恰好等于目标系数 $C(n+1, k)$ ，需要的正是 §1 的递推（把其中的 $n$ 换成 $n+1$ ）。

沿用 §1「越界的组合数记为 $0$ 」的约定，上面求和范围可统一取 $0 \le k \le n+1$ ：两个端点 $k = 0$ 与 $k = n+1$ 处，两个来源里恰有一个的组合数越界记 $0$ ，系数自动落到 $1 = C(n+1, 0) = C(n+1, n+1)$ ，不必单列。于是三角里「每个数等于上方两数之和」这个动作，与归纳证明里「合并同类项、两个父项系数相加」那一步是同一件事；三角形逐行往下生长，就是归纳法从 $n$ 推到 $n+1$ 的可视化。

4 · 参考文献

Pascal's triangle. Wikipedia. Pascal 三角的递推、对称性与诸多规律。https://en.wikipedia.org/wiki/Pascal%27s_triangle
Binomial theorem. Wikipedia. $(a+b)^n$ 的展开、二项式系数与推广。https://en.wikipedia.org/wiki/Binomial_theorem