二项式系数 Binomial Coefficients

yzxoi

2021-12-02 (Updated: 2022-06-23)

数学

二项式定理, 卷积, 生成函数

1.1 基本恒等式 Basic Identities

1.1.1 定义 Definition

$\binom nk$ 表示二项式系数，其中 $n$ 称作上指标 (upper index)，而称 $k$ 为下指标 (lower index)。

$$
\binom rk=
\begin{cases}
\frac{r^{\underline{k}}}{k!} ,& k\ge0\\
0, & k<0
\end{cases}

\quad (k\in \Z)
$$

1.1.2 对称恒等式 Symmetric Identity

$$
\binom nk=\binom n{n-k}\quad n\in \N
$$

证明：
$$
\binom nk=\frac{n!}{k!(n-k)!}=\frac{n!}{(n-(n-k))!(n-k)!}=\binom n{n-k}
$$

1.1.3 吸收恒等式 Absorption Identity

$$
\binom rk=\frac rk\binom {r-1}{k-1}
$$

证明：

$k> 0$
$$
\binom rk=\frac{r^{\underline k}}{k!}=\frac{r{(r-1)}^{\underline {k-1}}}{k(k-1)!}=\frac rk\binom {r-1}{k-1}
$$
$k<0$

$$
\binom rk = 0 = \binom {r-1}{k-1}
$$

1.1.3+ 相伴恒等式 Companion Identity

$$
(r-k)\binom rk=r\binom {r-1}k
$$

证明：
$$
\begin{aligned}
(r-k)\binom rk & =(r-k)\binom r {r-k}\\
& = r\binom {r-1}{r-k-1}\\
& = r\binom {r-1}k
\end{aligned}
$$
容易发现上述证明过程仅当 $r\in \Z$ 时成立，但其实相伴恒等式对于所有 $r\in \R$ 均成立。具体证明需要用到多项式推理法。

1.1.4 加法公式 Addition Formula

$$
\binom rk = \binom {r-1}k+\binom {r-1}{k-1}
$$

证明：
$$
r\binom rk=(r-k)\binom rk +k\binom rk=r\binom {r-1}k+r\binom {r-1}{k-1}
$$

1.1.5 上指标求和 Summation of Upper Indicators

$$
\begin{align}
\sum_{0\leq k\leq n}\binom km =\binom{n+1}{m+1}\quad m,n\in \N \tag1
\end{align}
$$

证明：

利用数学归纳法。

$n=0$ 时，左边 $=\binom 0m=[m=0]=\binom 1{m+1}=$ 右边

设 $n=N \ (N\in \N_+)$ 时 $(1)$ 成立，那么 $n=N+1$ 时，
$$
\begin{aligned}
\sum_{0\leq k\leq n+1}\binom km & =\sum_{0\leq k\leq n}\binom km+\binom {n+1}m\\
& = \binom {n+1}{m+1} +\binom {n+1}m\\
& = \binom {n+2}{m+1}
\end{aligned}
$$

所以对一切 $n\in \N$，$(1)$ 成立。

1.1.6 平行求和法 Parallel Summation

$$
\sum_{k\leq n}\binom {r+k}k=\binom{r+n+1}n \quad n\in \Z
$$

证明：
$$
\begin{aligned}
\sum_{k\leq n}\binom {m+k}k & =\sum_{-m\leq k\leq n}\binom {m+k}k\\
& = \sum_{-m\leq k\leq n}\binom {m+k}m\\
& = \sum_{0\leq k\leq m+n}\binom km\\
& = \binom {m+n+1}{m+1}
\end{aligned}
$$

注意到以上证明当且仅当 $m+k\ge 0$ 才可以这么做（第二行运用到对称法则），因此我们在第一步去掉了 $k<-m$ 的项。

1.1.7 上指标反转 Upper Negation

$$
\binom rk=(-1)^k \binom {k-r-1}k \quad k\in \Z
$$

证明：

$k\ge 0$
$$
\binom rk=\frac{r^{\underline k}}{k!}=\frac{(-1)^k (-r)(1-r)\cdots (k-1-r)}{k!}=\frac {(-1)^k(k-r-1)^{\underline k}}{k!}=(-1)^k\binom {k-r-1}k
$$
$k<0$

$$
\binom rk = 0 = (-1)^k\binom {k-r-1}k
$$

1.1.8 三项式版恒等式 Trinomial Version of Identity

$$
\binom rm\binom mk=\binom rk\binom {r-k}{m-k} \quad m,k\in \Z
$$

证明：

若 $r\ge m\ge k\ge 0$，
$$
\begin{aligned}
\binom rm\binom mk & = \frac{r!}{m!(r-m)!}\frac{m!}{k!(m-k)!} \\
& = \frac{r!}{k!(m-k)!(r-m)!}\\
& = \frac{r!}{k!(r-k)!}\frac{(r-k)!}{(m-k)!(r-m)!}\\
& = \binom rk \binom {r-k}{m-k}
\end{aligned}
$$

若 $m<k$ 或 $k<0$ 等式两边都是 $0$。

1.1.9 范德蒙德卷积 Vandermonde Convolution

$$
\sum_k \binom r{m+k}\binom s{n-k}=\binom {r+s}{m+n} \quad m,n\in \Z
$$

证明：

这里可以暂时通过组合意义来简单证明：

先从 $r$ 个球中取 $m+k$ 个，再从 $s$ 个球中取 $n-k$ 个，就相当于在 $r+s$ 个球中取 $m+n$ 个。

具体严谨证明见下文——生成函数。

1.1.10 二项式定理 Binomial Theorem

$$
(x+y)^n=\sum_{k=0}^n\binom nky^kx^{n-k}\quad n\in Z_+
$$

特别地，

$$
(1+x)^n=\sum_{k=0}^n\binom nkx^k\quad n\in Z_+
$$

1.1.11 其他基本组合恒等式 Other Basic Combination Identities

$$
\sum_{k=0}^n \binom nk=2^n \tag 1
$$

$$
\sum_{k=0}^n (-1)^k\binom nk=0 \tag 2
$$

1.2 生成函数 Generating Function

1.2.1 卷积 Convolution

$$
c_n=\sum_{k=0}^na_kb_{n-k} \tag1
$$

由 $(1)$ 所定义的序列 $\langle c_n\rangle$ 称为序列 $\langle a_n\rangle$ 和 $\langle b_n \rangle$ 的卷积。

1.2.2 二项式定理与生成函数 Binomial Theorem and Generating Function

$$
(1+z)^r=\sum_{k\ge 0}\binom rkz^k \tag1
$$

类似地，

$$
(1+z)^s=\sum_{k\ge 0}\binom skz^k \tag2
$$

将 $(1)(2)$ 相乘，我们可以得到另外一个生成函数：

$$
(1+z)^r(1+z)^s=(1+z)^{r+s}
$$

让这个等式两边 $z^n$ 的系数相等就给出：

$$
\sum_{k=0}^n\binom rk\binom s{n-k}=\binom {r+s}n
$$

我们就发现了范德蒙德卷积。

此外我们还有一系列重要的恒等式：

$$
(1-z)^r=\sum_{k\ge 0}(-1)^k\binom rk\tag 3
$$

$$
\frac 1{(1-z)^{n+1}}=\sum_{k\ge 0}\binom {n+k}nz^k \quad n\in \N \tag 4
$$

当 $n=0$ 时，我们就得到了 $(4)$ 的特例，即几何级数：

$$
\frac 1{1-z}=1+z+z^2+z^3+\cdots =\sum_{k\ge 0}z^k
$$

这就是序列 $\langle 1,1,1,\cdots \rangle$ 的生成函数。

1.3 基本练习 Basic Practice

1.3.1 利用基本组合恒等式 Use Basic Combinatorial Identities

证明：$\sum_{k=1}^n (-1)^{k-1}k\binom nk=0 \ (n\ge2)$

$$
\begin{aligned}
LHS & = \sum_{k=1}^n(-1)^{k-1}n\binom {n-1}{k-1} \\
& = n\sum_{k}(-1)^k\binom nk\\
& = n\binom 0n\\
& = n[n=0]\\
& = 0 = RHS
\end{aligned}
$$

证明：$\sum_{k=p}^n\binom nk\binom kp=\binom np2^{n-p}$

$$
\begin{aligned}
LHS & = \sum_{k=p}^n\binom np\binom {n-k}{k-p}\\
& = \binom np\sum_{k=0}^{n-p}\binom {n-p-k}k\\
& = \binom np 2^{n-p} = RHS
\end{aligned}
$$

1.3.2 利用生成函数 Use Generating Functions

证明：
$\sum_{k=0}^n{\binom nk}^2=\binom n{2n}$
$\sum_{k=1}^{2n-1}\binom {2n}k[2 (k-1)]=\frac 12{\binom {4n}{2n}+(-1)^{n-1}\binom {2n}n}$

[collapse title=”解答”] 1. 首先有： $$ \begin{aligned} [z^n](1+z)^{2n} & =\sum_{k=0}^{2n}\binom {2n}kz^k\\ & =\binom {2n}n \end{aligned} $$ 注意到： $$ \begin{aligned} [z^n](1+z)^{2n} & =[z^n]((1+z)^n)^2\\ & = [z^n](\sum_{i=0}^n\binom niz^i)\cdot (\sum_{j=0}n\binom njz^j)\\ & =\sum_{k=0}^n\binom nk\binom n{n-k}\\ & =\sum_{k=0}^n{\binom nk}^2 \end{aligned} $$ 因此： $$ \sum_{k=0}^n{\binom nk}^2=\binom {2n}n $$ 2. 由小题 $1$ 得： $$ \sum_{k=0}^{2n}\binom {2n}k^2=\binom {4n}{2n}\tag1 $$ 其次： $$ \begin{aligned} [z^{2n}](1-z^2)^{2n} & =[z^{2n}]\sum_{k=0}^{2n}(-1)^k\binom {2n}kz^{2k}\\ & =(-1)^n\binom {2n}n \end{aligned} $$ 注意到： $$ \begin{aligned} [z^{2n}](1-z^2)^{2n} & =(1-z)^{2n}(1+z)^{2n}\\ & = [z^{2n}](\sum_{k=0}^{2n}(-1)^k\binom {2n}kz^k)(\sum_{j=0}^{2n}\binom {2n}jz^j)\\ & = \sum_{k=0}^{2n}(-1)^k\binom {2n}k\binom {2n}{2n-k}\\ & = \sum_{k=0}^{2n}(-1)^k\binom {2n}k^2 \end{aligned} $$ 所以有： $$ (-1)^n\binom {2n}n=\sum_{k=0}^{2n}(-1)^k\binom {2n}k^2 \tag 2 $$ 由 $((1)-(2))\div 2$ 得： $$ \sum_{k=1}^n\binom {2n}{2k-1}^2=\frac 12\{\binom {4n}{2n}+(-1)^{n-1}\binom {2n}n\} $$ [/collapse]