组合计数 学习笔记

其实不是什么学习笔记，只是稍微整理一下。

排列组合

排列

从 $n$ 个元素中有序的选择 $k$ 个元素的方案数： $$n(n-1)(n-2)\cdots(n-k+1) = \frac{n!}{(n-k)!} = n^{\underline{k}}$$

组合

从 $n$ 个元素中选出无序的 $k$ 个元素的方案数： $$\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!} = \frac{n!}{(n-k)!k!} = \binom{n}{k}$$

计算组合数的方法

1. 根据杨辉三角递推，时间复杂度 $\mathcal O(n^2) - \mathcal O(1)$。

2. 预处理阶乘、逆元、阶乘逆元，时间复杂度 $\mathcal O(n) - \mathcal O(1)$。

3. Lucas 定理：
   当 $p$ 为质数时，有： $$\binom nm \equiv \binom {n \bmod p}{m \bmod p} \cdot \binom{\lfloor \frac np \rfloor}{\lfloor \frac mp \rfloor} \pmod p$$ 时间复杂度 $\mathcal O(p) - \mathcal O(\log_pn)$。

隔板法

将 $n$ 个一样的小球放进 $m$ 个不同的盒子内的方案数，
等价于将 $n$ 个小球划分成 $m$ 段，段可以为空的方案数，
等价于将 $n+m$ 个小球划分成 $m$ 段，段不能为空的方案数，
等价于从 $n+m-1$ 个空隙中选 $m-1$ 个空隙作为划分点的方案数： $$\binom {n+m-1}{m-1}$$

二项式定理

一般二项式定理

$n$ 为非负整数： $$(x+y)^n = \sum_{k=0}^n \binom nk x^ky^{n-k}$$

扩展二项式定理

$n$ 为非负整数： $$\left(\sum_{i=1}^t x_i\right)^n = \sum_{\sum_{i=1}^tn_i = n} \left(\binom{n}{n_1,n_2,\cdots,n_t} \prod_{j=1}^t x_j^{n_j}\right)$$

广义二项式定理

$n$ 为实数： $$(x+y)^n = \sum_{k} \frac{n^{\underline{k}}}{k!} x^ky^{n-k}$$

特殊数列

$\text{Fibonacci}$ 数

A000045
递推公式： $$F_{n} = \begin{cases}n & n \le 1 \\\\ F_{n-1} + F_{n-2} & n \ge 2 \end{cases}$$ 通项公式： $$F_n = \frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n}-\left(\frac{1-\sqrt{5}}{2}\right)^{n}}{\sqrt{5}}$$ OGF： $$F(x) = \frac x{1-x-x^2} = \frac{\left(\frac{1}{1-\frac{1+\sqrt5}{2}x} - \frac{1}{1-\frac{1-\sqrt5}{2}x}\right)}{\sqrt5}$$ 性质：

• $F_{n-1}F_{n+1} - F_n^2 = (-1)^n$。
• $\gcd(F_n, F_m) = F_{\gcd(n,m)}$。
• $\sum_{i=0}^n F_i = F_{n+2}-1$。
• $\text{Fibonacci}$ 数列模 $m$ 意义下循环节长度 $\le 6m$。

$\text{Catalan}$ 数

A000108

意义：$C_n$ 表示 $n$ 对括号的合法括号序列数，以及延伸出来的无数种意义。

递推公式： $$C_{n} = \begin{cases}1 & n = 0 \\\\ \sum_{i=0}^{n-1} C_{i}C_{n-1-i} & n \ge 1 \end{cases}$$ 通项公式： $$C_{n} = \binom {2n}{n} - \binom {2n}{n-1} = \frac{\binom{2n}{n}}{n+1} = \frac{C_{n-1}(4n-2)}{n+1}$$ OGF： $$C(x)=\frac{1 - \sqrt{1-4 x}}{2 x}$$

第一类 $\text{Stirling}$ 数

意义：$S_1(n,m)$ 表示 $n$ 个元素构成恰好 $m$ 个圆排列的方案数。

递推公式： $$S_1(n,m) = S_1(n-1,m-1)+(n-1) \cdot S_1(n-1,m)$$ 性质：

• $n! = \sum_{i=0}^n S_1(n,i)$。
• 上升幂 $\to$ 常幂：$x^{\bar{n}}=\sum_{i=0}^{n} S_1(n, i) x^{i}$。
• 下降幂 $\to$ 常幂：$x^{\underline{n}}=\sum_{i=0}^{n}(-1)^{n-i} S_1(n, i) x^{i}$。
• 上面两个同时成立是因为：$(-x)^{\underline{n}}=(-1)^{n} x^{\bar{n}}$。

第二类 $\text{Stirling}$ 数

意义：$S_2(n,m)$ 表示 $n$ 个元素构成恰好 $m$ 个非空集合的方案数。

递推公式： $$S_2(n,m) = S_2(n-1,m-1) + m \cdot S_2(n-1,m)$$ 通项公式： $$S_2(n,m) = \frac{\sum_{k=0}^m (-1)^k \binom mk (m-k)^n}{m!}$$

性质：

• 常幂 $\to$ 下降幂：$x^{n}=\sum_{i=0}^{n} S_2(n,i) x^{\underline{i}}$。
• 常幂 $\to$ 上升幂：$x^n = \sum_{i=0}^n (-1)^{n-i}S_2(n,i)x^{\bar{i}}$。
• 广义上：$S_2(n,m) = S_1(-m,-n)$。

$\text{Bell}$ 数

A000110

意义：$B_n$ 表示将 $n$ 个集合划分成若干个非空集合的方案数。

递推公式： $$B_{n} = \sum_{i=0}^{n-1} \binom {n-1}{i} B_i$$ 通项公式： $$B_n = \frac 1e \sum_{i \ge 0} \frac{i^n}{i!}$$ 性质：

• $B_n = \sum_{i=0}^n S_2(n,i)$。
• 对于质数 $p$，$B_{p^m+n} = mB_{n}+B_{n+1}$。
• $\text{Bell}$ 数列模质数 $p$ 意义下循环节长度为 $\frac {p^p-1}{p-1}$。

EGF： $$B(x) = e^{e^x-1}$$ $\text{Bell}$ 三角 A011971：

• $b_{0,0} = 1$。
• 对于 $n > 0$，$a_{n,1} = a_{n-1,n-1}$。
• 对于 $n,m > 0$，$a_{n,m} = a_{n,m-1} + a_{n-1,m-1}$。
• $B_{n} = b_{n,0}$。

分拆数

A000041 LOJ6268

意义：将 $n$ 进行整数分拆的方案数。

递推公式： $$F_{n} = \begin{cases} 0 & n < 0 \\\\ 1 & n = 0 \\\\ \sum_{k \ge 1} -(-1)^k (F_{n-\frac{k(3k-1)}{2}} + F_{n-\frac{k(3k+1)}{2}}) & n > 0 \end{cases}$$ 按照递推公式求分拆数是 $\mathcal O(n \sqrt n)$ 的。

OGF： $$F(x) = \prod_{n > 0} \frac{1}{1-x^n} = \frac1{\sum_{k\ge 1}(-1)^k(x^{k(3k-1)} + x^{k(3k+1)})}$$

$\text{Bernoulli}$ 数

设等幂和 $S_m(n) = \sum_{k=1}^n k^m$，有公式： $$S_m(n) = \frac1{m+1} \sum_{k=0}^m \binom {m+1}{k} B^+_k n^{m+1-k}$$ 其中 $B^+_k$ 为 $\text{Bernoulli}$ 数，$B^+_n$ 与 $B^-_n$ 为两种不同的定义，仅在 $n=1$ 时有区别：$B^+_1 = \frac 12$，$B^-_1 = -\frac 12$。

递推公式： $$\sum_{k=0}^m \binom {m+1}{k} B^-_k = 0$$ 边界为 $B^-_0 = 1$。

EGF： $$B(x) = \frac x{e^x-1}$$