《组合数学》 §1.4 学习笔记

前言：本章节标题叫组合恒等式，那我就一个证明都不写了。

定理 1.4.1 （二项式定理）

参考 广义二项式定理 （什么垃圾作者怎么这么推荐的？原来是我啊那没事了）

性质 1.4.2

设 $n \ge k \ge 0$ ，则

$$\binom{n}{n-k}$$

性质 1.4.3

设 $n \ge 0$ ，则

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

性质 1.4.4

设 $n \ge 1$ ，则

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

推论 1.4.5

设 $n \ge 1$ ，则

$$\sum_{2k + 1}\binom{n}{2k+1} = \sum_{2k} \binom{n}{2k} \quad(k > 0)$$

性质 1.4.6 （Vandermonde 恒等式）

设 $n,m \ge 0$ ，则

$$\binom{m+n}{k} = \sum_{i=1}^k\binom{m}{i}\binom{n}{k-i}$$

推论 1.4.7

在 Vandermonde 恒等式中，令 $m=n=k$ ，则有

$$\binom{2n}{n} = \sum_{i=0}^n\binom{n}{i}^2$$

推论 1.4.8 （Pascal 恒等式）

在 Vandermonde 恒等式中，令 $m=1$ ，则有

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

性质 1.4.9 （朱世杰恒等式）

设 $n,m \ge 0$ ，则

$$\binom{m+n+1}{n+1} = \sum_{i=0}^{m} \binom{n+i}{n}$$

推论 1.4.10

在朱世杰恒等式中，令 $n=k,\,m=n-k$ ，则有

$$\binom{n+1}{k+1} = \sum_{i=0}^{n-k}\binom{k+i}{k} = \sum_{i=k}^n\binom{i}{k}$$

定理 1.4.11 （Lucas 定理）

设 $p$ 是一个素数，将 $m$ 和 $n$ 写成 $p$ 进制数

$$m=a_0 + a_1p + \cdots a_kp^k \\ n =b_0 + b_1p + \cdots b_kp^k$$

其中 $0 \le a_i,b_i < p(i = 0,1,\cdots,k)$ ，则

$$\binom{m}{n} \equiv \prod_{i=0}^k \binom{a_i}{b_i} \pmod{p}$$

不过 OI 中更为熟悉的形式是

$$\binom{n}{m} \bmod p=\binom{\lfloor n / p\rfloor}{\lfloor m / p\rfloor} \times\binom{ n \bmod p}{m \bmod p} \bmod p$$

注 1.4.12

略。讲的 Lucas 定理的应用。

定理 1.4.13 （多项式定理）

设 $n$ 为正整数，则

$$(x_1 + x_2 + \cdots x_k)^n = \sum_{n_1 + n_2 + \cdots + n_k = n} \binom{n}{n_1,n_2,\cdots,n_k}x_1^{n_1}x_2^{n_2}\cdots x_k^{n_k}$$

这个 $\binom{n}{n_1,n_2,\cdots,n_k}$ 是多重选取数，前面讲过，也称为多项式系数（相对于二项式系数）。

例 1.4.14

略。简单例题。