maththeorem

二项式定理的研究

杨辉三角

我国南宋数学家杨辉使用了如下三角形解释二项式展开的规律：

在这个三角形中，第 $i$ 行有 $i$ 个数。第 $1$ 行的数字为 $1$ ，第 $i(i \ne 1)$ 行的第 $j(1<j<i)$ 个数字为其上方两个数字之和，即，第 $i-1$ 行第 $j$ 个数字和第 $i-1$ 行第 $j-1$ 个数字之和。第 $i$ 行第一个数字和最后一个数字为 $1$ 。

杨辉认为，这个三角形中第 $i$ 行第 $j$ 个数字为 $(a+b)^{i-1}$ 中 $a^{j-1}b^{i-j}$ 的系数。

二项式展开

二项式是形如 $(a+b)^n$ 的式子。这类式子可以使用多项式乘法将其展开成几个只与 $a,b$ 有关的式子。

比如， $a+b=a+b$ ， $(a+b)^2=(a+b)(a+b)=a^2+2ab+b^2$ 。

一般的，我们可以将二项式展开为如下形式：

$$\sum_i\sum_j c_{i,j}a^ib^j$$

其中 $c_{i,j}$ 为未知实数。

二项式定理

二项式定理内容

二项式定理的基本内容如下：

$$(a+b)^n=\sum_{i=0}^n C_n^ia^ib^{n-i}$$

其中 $C_n^i$ 为组合数，即 $\begin{pmatrix}n \\ i\end{pmatrix}$ 。

证明

设二项式形式为 $(a+b)^n=\displaystyle\prod_{i=1}^n (a+b)$

根据多项式乘法的规律，二项式展开后不化简的每一项均为每一个单独的多项式中的一项的乘积。

而二项式中的每一项均为 $(a+b)$ ，设不化简的其中一项共选择了 $w(0 \le w \le n)$ 个多项式中的项 $a$ ，则该项的值为 $a^wb^{n-w}$ 。

所以， $(a+b)^n=\displaystyle\sum_{i=0}^n c_ia^ib^{n-i}$ ，其中 $c_i$ 为未知实数。

回顾我们刚才的过程，我们发现对于某一个 $x(0 \le x \le n)$ ， $a^xb^{n-x}$ 是在 $n$ 个多项式中，选择了 $x$ 次 $a$ 所得到的项。而在 $n$ 个多项式中，如果把选 $a$ 当作取走这个数，不选 $a$ 当作不取这个数，则在 $2^n$ 种选择中，共有 $C_n^x$ 中选择方法，即，在二项式 $(a+b)^n$ 中，共有 $C_n^x$ 个项为 $a^xb^{n-x}$ 。所以， $a^xb^{n-x}$ 的系数为 $C_n^x$ 。

综上， $(a+b)^n$ 的展开式为：

$$\sum_{i=0}^n C_n^ia^ib^{n-i}$$

二项式定理与杨辉三角

由上述内容可知，杨辉的解释等价于杨辉三角中第 $i$ 行第 $j$ 个数字为 $C_{i-1}^{j-1}$ 。

由杨辉三角的性质，这同时等价于如下命题：

$$C_n^k=C_{n-1}^{k-1}+C_{n-1}^k, C_n^0=C_n^n=1$$

其中 $n \ge 1,0 < k < n$ 。

这里面第二条是显然的，由组合数定义可知，从 $n$ 个不同的数里一个都不选的方案数显然是 $1$ ，选 $n$ 个的方案数也只能是 $1$ 。

而第一条，我们仍可以使用二项式定理证明。

注意到 $(a+b)^n=\sum_{i=0}^n C_n^ia^ib^{n-i}$ ，

同时， $(a+b)^n=(a+b)^{n-1}\times (a+b)=(\displaystyle\sum_{i=0}^{n-1} C_{n-1}^ia^ib^{n-i-1})\times(a+b)$ 。

所以 $\displaystyle\sum_{i=0}^n C_n^ia^ib^{n-i}=(\displaystyle\sum_{i=0}^{n-1} C_{n-1}^ia^ib^{n-i-1})\times(a+b)$ 。

设 $p$ 为 $(a+b)^n$ 中 $a^kb^{n-k}$ 的系数 $C_n^k$ ， $q$ 为$(a+b)^{n-1}$ 中 $a^kb^{n-k-1}$ 的系数 $C_{n-1}^k$ ， $r$ 为 $(a+b)^{n-1}$ 中 $a^{k-1s}b^{n-k}$ 的系数 $C_{n-1}^{k-1}$ 。

由多项式乘法得， $(a+b)^n=(a+b)^{n-1} \times (a+b)$ 中的不化简的系数是由 $(a+b)^{n-1}$ 中选择一项，与 $(a+b)$ 中的一项相乘得到的。

所以 $(a+b)^n$ 中项 $p \times a^kb^{n-k}$ 应该为 $(a+b)^{n-1}$ 中项 $q \times a^kb^{n-k-1}$ 乘上 $b$ 加上 $(a+b)^{n-1}$ 中项 $r \times a^{k-1}b^{n-k}$ 乘上 $a$ 得到。

换句话说， $p \times a^kb^{n-k}=q \times a^kb^{n-k-1} \times b+ r \times a^{k-1}b^{n-k} \times a$ ，

也就是 $p \times a^kb^{n-k}=q\times a^kb^{n-k}+r\times a^kb^{n-k}$ ，

所以， $p=q+r$ ，即：

$$C_n^k=C_{n-1}^{k-1}+C_{n-1}^k$$

于是以上两个命题均得证，杨辉的解释是正确的，杨辉三角的各种性质也都可以由组合数解释。

二项式定理与普通型生成函数

二项式定理与组合数的关系

如果定义当 $k>n$ 时， $C_n^k=0$ ，那么二项式定理又可以写作如下形式：

$$(a+b)^n=\sum_{i=0}^{\infty}C_n^ia^ib^{n-i}$$

再令 $a=x$ ， $b=1$ ，则有：

$$(1+x)^n=\sum_{i=0}^{\infty}C_n^ix^i$$

这正是普通型生成函数的形式。也就是说， $(1+x)^n$ 是 $C_n^i$ 的普通型生成函数。

二项式定理的用途

求组合数

我们可以利用生成函数得到一种可以绕开 Lucas 定理求组合数的方法：

1. 选定三个模数 $p_1,p_2,p_3$ ，一般选择 $2^{23} \times 119+1$ ， $2^{21} \times 479+1$ 和 $2^{26} \times 7+1$ 。
2. 对于所有需要的单位根为 $\omega$ ，计算 $(1+\omega)^n$ 分别模 $p_1,p_2,p_3$ 的值。
3. 得到后使用逆 NTT 算三次，分别对应三个模数。
4. 使用 CRT 对答案进行合并。

这样就可以 $O(n\log n)$ 的计算组合数了。

对比 Lucas 定理，这种方法适合模数较大时（一般至少有 $10^9$ 量级）的快速计算。

关于一些组合数公式的推导

我们可以利用生成函数完成一些组合数公式的推导。

例如如下公式：

$$\sum_{i=0}^n{\begin{pmatrix}n \\ i\end{pmatrix}}^2=\begin{pmatrix}2n \\ n\end{pmatrix}$$

证明：

对于两个多项式 $A(x),B(x)$ ，若 $A(x)=\displaystyle\sum_{i=0}^na_ix^i$ ， $B(x)=\displaystyle\sum_{i=0}^nb_ix^i$ ， $A(x) \times B(x)=\displaystyle\sum_{i=0}^{2n}c_ix^i$ ，则对于任意 $0 \le k \le 2n$ ，有：

$$c_k=\sum_{i=0}^k a_ib_{k-i}$$

设 $A(x)=(1+x)^n$ ， $B(x)=(1+x)^n$ ，则有 $A(x)\times B(x)=(1+x)^{2n}$ ， $c_n=\displaystyle\sum_{i=0}^n \begin{pmatrix}n \\ i\end{pmatrix} \begin{pmatrix}n \\ n-i\end{pmatrix}$ 。

由于 $\begin{pmatrix}n \\ i\end{pmatrix}=\begin{pmatrix}n \\ n-i\end{pmatrix}$ ，所以有　$c_n=\displaystyle\sum_{i=0}^n \begin{pmatrix}n \\ i\end{pmatrix}^2$ 。

同时，由二项式定理得 $(1+x)^{2n}=\displaystyle\sum_{i=0}^{2n}\begin{pmatrix}2n \\ i\end{pmatrix}x^i$ ，也就是说 $c_i=\begin{pmatrix}2n \\ i\end{pmatrix}$ ，那么 $c_n=\begin{pmatrix}2n \\ n\end{pmatrix}$ ，代入上式，得：

$$c_n=\sum_{i=0}^n{\begin{pmatrix}n \\ i\end{pmatrix}}^2=\begin{pmatrix}2n \\ n\end{pmatrix}$$

公式得证。

再比如下面的公式：

$$\sum_{i=0}^n \begin{pmatrix}n\\ i\end{pmatrix} \begin{pmatrix}m+i\\ n\end{pmatrix}=\sum_{i=0}^n\begin{pmatrix}n\\ i\end{pmatrix}\begin{pmatrix}m\\ i\end{pmatrix}2^i$$

证明：

我们有一个组合数公式：

$$\begin{pmatrix}m+i\\ n\end{pmatrix}=\displaystyle\sum_{j=0}^n {\begin{pmatrix}i\\ j\end{pmatrix}\begin{pmatrix}m\\ n-j\end{pmatrix}}$$

原理也好理解，从 $m+i$ 个数中选 $n$ 个等价于对于每一个 $0 \le j \le n$ ，从 $i$ 个数中选 $j$ 个，从另外 $m$ 个数中选 $n-j$ 个。

那么， $\displaystyle\sum_{i=0}^n \begin{pmatrix}n\\ i\end{pmatrix} \begin{pmatrix}m+i\\ n\end{pmatrix}=\displaystyle\sum_{i=0}^n \begin{pmatrix}n\\ i\end{pmatrix} \displaystyle\sum_{j=0}^n {\begin{pmatrix}i\\ j\end{pmatrix}\begin{pmatrix}m\\ n-j\end{pmatrix}}$ ，交换求和顺序，可以得到：

$$\displaystyle\sum_{j=0}^n \begin{pmatrix}m\\ n-j\end{pmatrix} \displaystyle\sum_{i=0}^n \begin{pmatrix}i\\ j\end{pmatrix}\begin{pmatrix}n\\ i\end{pmatrix}$$

我们注意到 $\begin{pmatrix}i\\ j\end{pmatrix}\begin{pmatrix}n\\ j\end{pmatrix}=\begin{pmatrix}n\\ j\end{pmatrix}\begin{pmatrix}n-j\\ i-j\end{pmatrix}$ ，因为左式利用组合数基本公式 $\begin{pmatrix}i\\ j\end{pmatrix}=\displaystyle\frac{i!}{j!(i-j)!}$ 可以得到 $\displaystyle\frac{n!}{j!(i-j)!(n-i)!}$ ，而右式也可以得到这个结果。

那么原式又可以利用这个式子变换成如下形式：

$$\displaystyle\sum_{j=0}^n \begin{pmatrix}m\\ n-j\end{pmatrix} \begin{pmatrix}n\\ j\end{pmatrix}\displaystyle\sum_{i=0}^n \begin{pmatrix}n-j\\ i-j\end{pmatrix}$$

观察 $i$ 的求和式中，设 $N=n-j,I=i-j$ ，那么求和式变为 $\displaystyle\sum_{I=0}^N \begin{pmatrix}N\\ I\end{pmatrix}$ 。

设 $A(x)=\displaystyle\sum_{I=0}^N \begin{pmatrix}N\\ i\end{pmatrix}x^I$ ，利用二项式定理知 $A(x)=(1+x)^N$ 。代入 $x=1$ ，得 $A(1)=(1+1)^N=2^N=\displaystyle\sum_{I=0}^N \begin{pmatrix}N\\ i\end{pmatrix}$ 。

将这一结果代入原式，得到如下式子：

$$\displaystyle\sum_{j=0}^n \begin{pmatrix}m\\ n-j\end{pmatrix} \begin{pmatrix}n\\ j\end{pmatrix}2^{n-j}$$

又由组合数基本公式 $\begin{pmatrix}n \\ i\end{pmatrix}=\begin{pmatrix}n \\ n-i\end{pmatrix}$ ，我们可将原式变换成 $\displaystyle\sum_{j=0}^n \begin{pmatrix}m\\ n-j\end{pmatrix} \begin{pmatrix}n\\ n-j\end{pmatrix}2^{n-j}$ 。

设 $k=n-j$ ，使用 $k$ 代换原式中的变量 $j$ ，得到如下式子：

$$\displaystyle\sum_{k=0}^n \begin{pmatrix}m\\ k\end{pmatrix} \begin{pmatrix}n\\ k\end{pmatrix}2^k$$

这恰是我们要证明的东西，于是公式得证。

参考资料

1. 必应图片， https://pic2.zhimg.com/v2-49147aa82c0a2340643d7fa988f5fc5d_r.jpg 。