二项式定理

二项式定理展开两个可交换量的整数次幂： $(x + y)^{n} = \sum_{k = 0}^{n} (\binom{n}{k}) x^{n - k} y^{k}, n \in ℕ_{0} .$ 系数 $(\binom{n}{k})$ 表示从 $n$ 个位置中选 $k$ 个的位置数。这里 $x, y$ 可以是实数、复数或可交换的代数元素；若乘法不交换，不能不加修改地套用同一展开式。

系数从选择位置得到

把 $(x + y)^{n}$ 看成 $n$ 个括号相乘。要得到 $x^{n - k} y^{k}$ ，恰需从其中 $k$ 个括号取 $y$ ，其余取 $x$ 。每种选择都贡献同一个单项式，因此其系数为 $(\binom{n}{k})$ 。例如 $(1 + t)^{4} = 1 + 4 t + 6 t^{2} + 4 t^{3} + t^{4} .$ 中间的 6 是从四个括号中选两个取 $t$ 的方案数，不是碰巧的数列。

两种快速核对

令 $x = y = 1$ ，得到 $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$ ：左边按选中元素数量分组统计所有子集，右边按每个元素收或不收统计。令 $x = 1, y = - 1$ 且 $n \geq 1$ ，得到交替和 $\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = 0$ 。这些代入可检验一行系数是否漏项，却不替代上面的组合证明。

参考资料

MIT，Mathematics for Computer Science，Binomial Theorem 章节。
MIT 6.042J Fall 2010，Mathematics for Computer Science 课程讲义。
继续阅读：组合数学、帕斯卡恒等式、幂集。