杨辉三角

杨辉三角把组合数 $(\binom{n}{k})$ 按 $n = 0, 1, 2, \dots$ 排成三角形：第 $n$ 行从 $(\binom{n}{0})$ 写到 $(\binom{n}{n})$ 。前六行依次为 $\begin{matrix} 1 \\ 1 1 \\ 1 2 1 \\ 1 3 3 1 \\ 1 4 6 4 1 \\ 1 5 10 10 5 1. \end{matrix}$ 行号从 0 开始；若把顶端称为“第一行”，下面的下标就会整体错一位。

上方相邻两数相加

看第 5 行中间的 10，它等于上行相邻的 4 与 6。这是排列与组合中的分类恒等式： $(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) (1 \leq k \leq n - 1) .$ 固定一名对象，所选的 $k$ 人组要么含他、要么不含他；两类互斥而且穷尽。边缘的 1 则来自“一个都不选”或“全部选中”。图中两条箭头落在同一个 10 上，标出的是这两类来源，不是神秘的数字巧合。

杨辉三角零至五行，第四行的四和六分别用箭头指向第五行中间的十，左右边缘都是一 — 中间的 10 由上一行相邻的 4 与 6 相加；行号从 0 开始。

对称与一整行的和

选出 $k$ 个对象同时也决定留下 $n - k$ 个对象，因此 $(\binom{n}{k}) = (\binom{n}{n - k})$ ，每一行左右对称。第 5 行的两个 10 分别是 $(\binom{5}{2})$ 与 $(\binom{5}{3})$ 。

一行相加是在按所选人数分类统计所有子集。每个对象可选或不选，共 $2^{n}$ 个子集，所以 $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n} .$ 第 4 行 $1 + 4 + 6 + 4 + 1 = 16 = 2^{4}$ 。这也可在二项式定理中令 $x = y = 1$ 得到，但“每个元素两种选择”解释了式子的计数含义。

令 $x = 1, y = - 1$ ，当 $n \geq 1$ 时还得到 $\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0.$ 把普通和与交替和相加、相减可知：偶数下标的系数之和与奇数下标的系数之和各为 $2^{n - 1}$ 。 $n = 0$ 时只有一个偶数下标项，不能套这个结论。

名称与文献

杨辉在《详解九章算法》中记述相关数表，并引用更早的贾宪方法；贾宪原书已散佚。这个数表在不同传统中也有其他名称。历史名称说明传承与记载，不改变组合数的定义和证明。

试算。求第 6 行的中间一项。用组合公式 $(\binom{6}{3}) = 20$ ；也可由第 5 行两个相邻的 10 相加得到 20。若有人把 $(\binom{6}{3})$ 写成第 3 行的数，检查“第 $n$ 行对应 $(x + y)^{n}$ 的系数”即可发现错位。

参考资料

MIT 6.042J《Mathematics for Computer Science》组合恒等式章节。
圣安德鲁斯大学 MacTutor：杨辉：数表的文献关系。