首页 学习笔记

# 二项式系数

# 定义

符号：(nk)\dbinom{n}{k}，读作：“nn 选 kk”。

组合意义：从有 nn 个元素的集合中选出 kk 个元素作为子集的方案数。

我们称 nn 是 上指标，称 kk 是下指标。

(nk)={n(n−1)⋯(n−k+1)k(k−1)⋯1=nk‾k!,k≥0;0,k<0.\dbinom{n}{k}=\left\{ \begin{aligned} & \frac {n(n - 1)\cdots(n - k + 1)}{k(k - 1)\cdots1} = \frac {n^{\underline{k}}}{k!}, && k \geq 0; \\ & 0, && k < 0. \end{aligned} \right.

需要注意的是：nn 为任意实数，kk 为任意整数。

# 基本恒等式

(nk)=n!k!(n−k)!,n,k∈Z且n≥k≥0\dbinom{n}{k} = \frac {n!}{k!(n - k)!},\ \ n, k \in \mathbb{Z}\ 且\ n \geq k \geq 0

证明：只需要把定义式中的分子分母同时乘上 (n−k)!(n - k)! 即可。

对称恒等式：

(nk)=(nn−k),n,k∈X且n≥0\dbinom{n}{k} = \dbinom{n}{n -k},\ \ n, k \in \mathbb{X} \ 且\ n \geq 0

证明：可以通过组合意义理解，从 nn 个元素中选 kk 个元素相当于指定 n−kn - k 个元素不被选取。

吸收恒等式：

(rk)=rk(r−1k−1),k∈Z且k≠0\dbinom{r}{k} = \frac rk\dbinom{r - 1}{k - 1},\ \ k \in \mathbb{Z}\ 且\ k \neq 0

证明：由定义式，rk‾=r(r−1)k−1‾r^{\underline k} = r(r - 1)^{\underline{k - 1}} 并且 k!=k(k−1)!k! = k(k -1 )!。

条件中 k≠0k \neq 0 是为了避免除数中出现 0，如果我们对两边同时乘上 kk，那么就有了一个 kk 等于 0 时也成立的吸收恒等式：

k(rk)=r(r−1k−1)k\dbinom{r}{k} = r\dbinom{r - 1}{k - 1}

这个恒等式也有一个保持下指标不变的伴恒等式：

(r−k)(rk)=r(r−1k)(r - k)\dbinom{r}{k} = r\dbinom{r - 1}{k}

证明：

(r−k)(rk)=(r−k)(rr−k)=(r−k)rr−k(r−1r−k−1)=r(r−1r−k−1)=r(r−1k)\begin{aligned} (r - k)\dbinom{r}{k} =& (r - k)\dbinom{r}{r - k} \\ =& (r - k)\frac {r}{r - k}\dbinom{r - 1}{r - k - 1} \\ =& r\dbinom{r - 1}{r - k - 1} \\ =& r\dbinom{r - 1}{k} \end{aligned}

先对称，再吸收，再对称。

加法公式：

(rk)=(r−1k)+(r−1k−1),k∈Z\dbinom{r}{k} = \dbinom{r - 1}{k} + \dbinom{r - 1}{k - 1}, \ \ k \in \mathbb{Z}

证明：依旧使用组合意义。从 rr 个元素中选择 kk 个元素，可以分为两种情况，第 rr 个元素不选，从前 r−1r - 1 个元素中选 kk 个，即 (r−1k)\dbinom{r - 1}{k}，或选择第 rr 个元素，然后从前 r−1r - 1 个元素中选 kk 个元素，即 (r−1k−1)\dbinom{r - 1}{k - 1}。

我们也可以使用两个吸收恒等式或者把二项式拆开计算来证明。

上指标求和法：

∑k=0n(km)=(n+1m+1),n,m∈Z且n,m≥0\sum_{k = 0}^n\dbinom{k}{m} = \dbinom{n + 1}{m + 1},\ \ n, m \in \mathbb{Z}\ 且\ n, m \geq 0

证明：这个式子有一个有趣的组合意义，假设我们想从 n+1n + 1 个数（编号为 0 到 n+1n + 1）选择 m+1m + 1 个数，当选取的数中最大的数为 kk 时就有 (km)\dbinom{k}{m} 种选法。

平行求和法：

∑k≤n(m+kk)=(m+n+1n),n∈Z\sum_{k \leq n}\dbinom{m + k}{k} = \dbinom{m + n + 1}{n}, \ \ n \in \mathbb{Z}

证明：我们可以通过刚提到的上指标求和法来证明，

∑k≤n(m+kk)=∑−m≤k≤n(m+kk)=∑−m≤k≤n(m+km)=∑0≤k≤m+n(km)=(m+n+1m+1)=(m+n+1n)\begin{aligned} \sum_{k \leq n}\dbinom{m + k}{k} =& \sum_{-m \leq k \leq n}\dbinom{m + k}{k} \\ =& \sum_{-m \leq k \leq n}\dbinom{m + k}{m} \\ =& \sum_{0 \leq k \leq m + n}\dbinom{k}{m} \\ =& \dbinom{m + n + 1}{m + 1} \\ =& \dbinom{m + n + 1}{n} \end{aligned}

  • 第一个等号，我们去掉了 k<−mk < -m 的项，这是合法的，因为那些项值都为 0。
  • 第二个等号使用了对称性。
  • 第三个等号，把 k−mk - m 代替 kk 并整理求和范围。
  • 第四个等号使用上指标求和法。
  • 最后一个等号再次使用对称性。

上指标反转：

(rk)=(−1)k(k−r−1k)\dbinom{r}{k} = (-1)^k\dbinom{k - r - 1}{k}

证明：

rk‾=r(r−1)⋯(r−k+1)=(−1)k(−r)(−r+1)⋯(−r+k−1)=(−1)k(k−r−1)k‾\begin{aligned} r^{\underline{k}} =& r(r - 1)\cdots(r - k + 1) \\ =& (-1)^k(-r)(-r + 1)\cdots(-r + k - 1) \\ =& (-1)^k(k - r - 1)^{\underline{k}} \end{aligned}

这个恒等式有一个对称的表达式：

(−1)m(−n−1m)=(−1)n(−m−1n)(-1)^m\dbinom{-n - 1}{m} = (-1)^n\dbinom{-m - 1}{n}

这是因为两边都等于 (m+nn)\dbinom{m + n}{n}。

我们还能推出如下的和式：

∑k≤m(rk)(−1)k=(−1)m(r−1m)\begin{aligned} \sum_{k \leq m}\dbinom{r}{k}(-1)^k =& (-1)^m\dbinom{r - 1}{m} \end{aligned}

证明：

∑k≤m(rk)(−1)k=∑k≤m(k−r−1k)=(m−rm)=(−1)m(r−1m)\begin{aligned} \sum_{k \leq m}\dbinom{r}{k}(-1)^k =& \sum_{k \leq m}\dbinom{k - r - 1}{k} \\ =& \dbinom{m - r}{m} \\ =& (-1)^m\dbinom{r - 1}{m} \end{aligned}

  • 第一个等号，上指标反转。
  • 第二个等号，对 −r−1-r - 1 换元并使用平行求和法。
  • 第三个等号，再次上指标反转。

三项式版恒等式：

(nm)(mk)=(nk)(n−km−k),m,k∈Z\dbinom{n}{m}\dbinom{m}{k} = \dbinom{n}{k}\dbinom{n - k}{m - k},\ \ m, k \in \mathbb{Z}

证明：把等号左边的两个二项式全部拆开重组即可。

范德蒙德卷积：

∑k(rk)(sn−k)=(r+sn),n∈Z\sum_k\dbinom{r}{k}\dbinom{s}{n - k} = \dbinom{r + s}{n},\ \ n \in \mathbb{Z}

证明；有一个很好的组合解释，等号右边为从 r+sr + s 个元素中选出 nn 个元素的方案数，等号左边为分别从 rr 个元素中选 kk 个，再从 ss 个元素中选 n−kn - k 个。

# 二项式定理

(a+b)n=∑i=0n(ni)an−ibi(a + b)^n = \sum_{i = 0}^n\dbinom{n}{i}a^{n - i}b^i

# 生成函数

二项式系数也存在于生成函数中。

当 a=1a = 1 时，我们的二项式定理变为了：

(1+z)n=∑k≥0(nk)zk(1 + z)^n = \sum_{k \geq 0}\dbinom{n}{k}z^k

等式的左右分别是数列 ⟨(n0),(n1),(n2),⋯⟩\left\langle\dbinom{n}{0}, \dbinom{n}{1}, \dbinom{n}{2},\cdots\right\rangle 的封闭形式以及生成函数。

当二项式的幂为负数时同样有生成函数：

1(1−z)n+1=∑k≥0(n+kn)zkzn(1−z)n+1=∑k≥0(kn)zk\frac 1{(1 - z)^{n + 1}} = \sum_{k \geq 0}\dbinom{n + k}{n}z^k \\ \frac {z^n}{(1 - z)^{n + 1}} = \sum_{k \geq 0}\dbinom{k}{n}z^k

（上面两个式子中 n∈Zn \in \mathbb{Z} 且 n≥0n \geq 0）

  • 第一个等式是二项式定理中幂为负数的情形，展开 (1−z)−n−1(1 - z)^{-n-1}，则 zkz^k 的系数是 (−n−1k)(−1)k\dbinom{-n - 1}{k}(-1)^k，它可以通过上指标反转改写成 (n+kk)\dbinom{n + k}{k} 或者 (n+kn)\dbinom{n + k}{n}。

    这就是 ⟨1,(n+11),(n+22),(n+33),⋯⟩\left\langle 1, \dbinom{n + 1}{1}, \dbinom{n + 2}{2}, \dbinom{n + 3}{3},\cdots\right\rangle 的生成函数。

  • 第二的等式为第一个等式乘上 znz^n，也就是向右移动了 nn 位。