组合计数 学习笔记
Visits: 1063
其实不是什么学习笔记，只是稍微整理一下。
排列组合
排列
从 $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}
$$
计算组合数的方法
- 根据杨辉三角递推，时间复杂度 $\mathcal O(n^2) – \mathcal O(1)$。
-
预处理阶乘、逆元、阶乘逆元，时间复杂度 $\mathcal O(n) – \mathcal O(1)$。
-
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}$ 数
意义：$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}$ 数
意义：$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}$。
分拆数
意义：将 $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}
$$
