《组合数学》 §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

略。简单例题。