组合学/二项式定理

二项式定理

二项式定理确定了不同和的幂的展开式；写出来，它就是

$(x+y)^{n}=\sum _{i=0}^{n}{n \choose i}x^{n-i}y^{i}$

这里，${\tbinom {n}{i}}$ 是n 和i 的二项式系数，它在上一章中被定义为一个计数从n 个元素的集合中选择i 个元素的方法的数量，读作“从n 个元素中选择i 个”，它的值可以计算为

${\binom {n}{i}}={\frac {n!}{i!(n-i)!}}$

因此，$(x+2)^{2}=1x^{2}+2x^{1}2^{1}+2^{2}=x^{2}+4x+4\,$

以及 $(x+y)^{5}=x^{5}+5x^{4}y+10x^{3}y^{2}+10x^{2}y^{3}+5xy^{4}+y^{5}\,$

展开式中的系数是帕斯卡三角形中一行中的项。即 $(x+y)^{5}$ 给出了帕斯卡三角形第五行的系数。

组合证明

二项式定理有很多可能的证明。组合证明如下

考虑两边 $x^{n-k}y^{k}\,$ 的系数，其中k为固定值。左边即 $(x+y)^{n}=(x+y)(x+y)\cdots (x+y)$ 展开后，只有 $x^{n-i}y^{i}\,$ 类型项，其中i从0到n。 $x^{n-k}y^{k}\,$ 出现的次数恰好等于从n个数中选出k个数的方法数。这是因为，从每个因子 (x+y) 中，总共有n个因子，我们需要选择k个y（剩下的就是x）。因此，左边 $x^{n-k}y^{k}\,$ 的系数将是 ${n \choose k}$。这与右边系数相符，证明完成。证明应该是逻辑性的，不是陈述句。

推论

二项式定理有许多推论。

首先，在定理中令x = y = 1，我们得到 $2^{n}=\sum _{i=0}^{n}{n \choose i}$。这意味着，一个包含n个元素的集合的子集总数（即 $2^{n}$，我们已经得到了这个结果）等于从n个元素中选择i个有序集合的方法数的总和，对所有i来说。

其次，在定理中令x = 1，y = -1，我们得到 $0=\sum _{k=0}^{n}(-1)^{k}{n \choose k}$。等价地，这意味着，

$\sum _{k\ odd}{n \choose k}=\sum _{k\ even}{n \choose k}$,

也就是说，对于任何n阶集合，其奇数阶子集的数量等于其偶数阶子集的数量。

第三，通过比较 $x^{k}$ 在 $(1+x)^{m+n}$ 中的系数，我们得到了范德蒙德恒等式。

${\begin{aligned}\sum _{k=0}^{m+n}{m+n \choose k}x^{k}&=(1+x)^{m+n}\\&=(1+x)^{m}(1+x)^{n}\\&={\biggl (}\sum _{k=0}^{m}{m \choose k}x^{k}{\biggr )}{\biggl (}\sum _{k=0}^{n}{n \choose k}x^{k}{\biggr )}\\&=\sum _{k=0}^{m+n}{\biggl (}\sum _{i=0}^{k}{m \choose i}{n \choose k-i}{\biggr )}x^{k},\end{aligned}}$

注意，这里我们使用的是两个多项式相乘的定义，它们的次数分别为 *m* 和 *n*，即

${\biggl (}\sum _{i=0}^{m}a_{i}x^{i}{\biggr )}{\biggl (}\sum _{j=0}^{n}b_{j}x^{j}{\biggr )}=\sum _{r=0}^{m+n}{\biggl (}\sum _{k=0}^{r}a_{k}b_{r-k}{\biggr )}x^{r},$

其中我们使用约定 *a_s* = 0 对于所有整数 *s* > *m* 和 *b_t* = 0 对于所有整数 *t* > *n*。

比较 $x^{k}$ 的系数，我们得到了范德蒙恒等式

${m+n \choose k}=\sum _{i=0}^{k}{m \choose i}{n \choose k-i},\qquad m,n,k\in \mathbb {N}$

注意，在范德蒙恒等式中将 m 设为 1，我们可以得到上一章中讨论的帕斯卡关系，尽管形式略有不同

${n+1 \choose k}={n \choose k}+{n \choose k-1}$

范德蒙德恒等式也有一个组合证明。二项式系数 ${m+n \choose k}$ 代表从 m + n 个元素的集合 $A\bigcup B$ 中选取 k 个子集的个数，其中 $A=\{1,2\cdots m\}$ 和 $B=\{m+1,m+2\cdots m+n\}$。包含 i 个 A 中元素的 k-子集的个数将是 ${m \choose i}{n \choose k-i}$（从 A 中选取 i 个元素，并且从 B 中选取剩下的 k-i 个元素）。求和 $\sum _{i=0}^{k}{m \choose i}{n \choose k-i}$ 计算了所有 i 的这些子集。

范德蒙德恒等式另一个有用的结果是在恒等式中令 m = k = n。这将得到：

${2n \choose n}=\sum _{i=0}^{n}{n \choose i}^{2}$

让我们看看另一个结果，第四个结果。考虑$(1+x)^{m+n+1}=(1+x)\cdots (1+x)$，其中有$m+n+1$ 个 $(1+x)$ 项在等式右边。左侧 $x^{n+1}$ 的系数是 ${m+n+1 \choose n+1}$。在等式右侧，该系数可以通过查看从 m+n+1 个 (1+x) 类型的项中挑选出 n+1 个 x 和剩下的 1 的方法数量来获得，这与我们在二项式定理证明中所做的方法类似。假设最右边的 x 来自第 n+i+1 项，其中 i 显然从 0 变化到 m。这给了我们从剩下的 n+i 项中选择 n 个 x 的选择，这可以在 ${n+i \choose n}$ 种方法中完成。方法总数显然可以通过对所有可能的 i 求和来获得。所以 $x^{n+1}$ 的系数将是 $\sum _{i=0}^{m}{n+i \choose n}$，因此我们有关系

${m+n+1 \choose n+1}=\sum _{i=0}^{m}{n+i \choose n}$

与范德蒙德恒等式一样，该恒等式也可以用组合方法证明。左侧表示从 m+n+1 个集合中选择 n+1 个有序集合的方法数，比如 $\{1,2,\cdots m+n+1\}$。假设对于任何给定的 n+1 个有序集合，最大元素在 n+i+1 中，其中 i 从 0 变化到 m。那么剩下的 n 个元素必须从 n+i 个元素中选择，并且这样做的选择方法数正好是 ${n+i \choose n}$。对所有 i 求和，我们得到了方法总数，该总数已被确定为左侧。只需要将这两个项等同起来。

在上述恒等式中改变变量，我们得到

${n+1 \choose k+1}=\sum _{i=k}^{n}{i \choose k}$

这也意味着

${n+1 \choose k+1}-{m+1 \choose k+1}=\sum _{i=m+1}^{n}{i \choose k}$