组合数学
_Ch1F4N_
·
·
个人记录
我已经忘了组合是啥了。
公式
递推公式：{n \choose m} = {n-1 \choose m} + {n-1 \choose m-1}。
吸收恒等式：{n \choose m} = \frac{n}{m} {n-1 \choose m-1}。
上指标求和：\sum_{i=m}^{n} {i \choose m} = {n+1 \choose m+1}。
平行恒等式：\sum_{i=0}^{n} {m+i \choose i} = {n + m + 1 \choose n}。
范德蒙德卷积：\sum_{i=0}^{k} {n \choose i}{m \choose k - i} = {n+m \choose k}。
二项式定理：\sum_{i=0}^{k} {k \choose i} a^{i}b^{n-i} = (a+b)^n。
一般而言，下指标求和使用二项式定理，上指标求和使用范德蒙德卷积或上指标求和公式。
第一类斯特林数
$\begin{bmatrix}n \\ m \end{bmatrix} = \begin{bmatrix}n-1 \\ m-1 \end{bmatrix} + {(n-1)} \times \begin{bmatrix}n-1 \\ m \end{bmatrix}
边界是 \begin{bmatrix}0 \\ 0 \end{bmatrix} = 1 其余含有 0 时值为 0。
第二类斯特林数
$\begin{Bmatrix}n \\ m \end{Bmatrix} = \begin{Bmatrix}n-1 \\ m-1 \end{Bmatrix} + {m} \times \begin{Bmatrix}n-1 \\ m \end{Bmatrix}
边界是 \begin{Bmatrix}0 \\ 0 \end{Bmatrix} = 1 其余含有 0 时值为 0。
普通幂转下降幂
有人会问这公式形式这么逆天有啥用，接下来给出几个基本事实。
$i > m$ 时 $\begin{Bmatrix}m \\ i \end{Bmatrix} = 0$。
$ x^{\underline{i}} = {x \choose i} \times i!$。
# 关于插板
对于相同的球不考虑时间关系，排在一排考虑位置关系。
简单的，容易计算的，看成球，有奇怪限制的看成板。
# 例题
## CF622F
$\sum_{i=1}^n i^k = \sum_{i=1}^n \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} i^{\underline{j}} = \sum_{i=1}^n \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} {i \choose j} j! = \sum_{i=1}^{n} \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} {i \choose j} j! = \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{i=1}^{n} {i \choose j} = \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! {n+1 \choose j+1}$。
注意到 ${n+1 \choose{j+1}}$ 直接算是 $O(j)$ 的，总复杂度就是 $O(k^2)$ 的。然后第二类斯特林数可以递推。
## CF1278F
回到期望最原本的定义：
$E(x^k) = \sum_{i=0}^{n} {\frac{1}{m}}^i {\frac{m-1}{m}}^{n-i}{n \choose i} i^k = \frac{1}{m^n} \sum_{i=0}^n {n \choose i} i^k {(m-1)}^{n-i} = \frac{1}{m^n} \sum_{i=0}^n {n \choose i} \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} i^{\underline{j}} {(m-1)}^{n-i} = \frac{1}{m^n} \sum_{i=0}^n {n \choose i} {(m-1)}^{n-i} \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} {i \choose j} j! = \frac{1}{m^n} \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{i=0}^{n} {n \choose i}{(m-1)}^{n-i}{i \choose j}$。
随后我们注意到 ${n \choose i}{i \choose j}$ 表示从 $n$ 个里面选 $i$ 个再从 $i$ 个里面选 $j$ 个，等价于先从 $n$ 个里面选出 $j$ 个再从剩下的 $n-j$ 个中选出 $i-j$ 个，即 ${n \choose i}{i \choose j} = {n \choose j}{n-j \choose i-j}$，这个式子好处在于在第一个组合数中去除了 $i$ 这个枚举范围特别大的变量。
$\frac{1}{m^n} \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{i=0}^{n} {n \choose i}{(m-1)}^{n-i}{i \choose j} = \frac{1}{m^n} \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{i=0}^{n} {(m-1)}^{n-i}{n \choose i}{i \choose j} = \frac{1}{m^n} \sum_{j=0}^{k} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{i=0}^{n} {(m-1)}^{n-i}{n \choose j}{n-j \choose i-j} = \frac{1}{m^n} \sum_{j=0}^{k} {n \choose j} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{i=0}^{n} {(m-1)}^{n-i}{n-j \choose i-j}$。
然后你注意到们需要对下指标求和，考虑二项式定理，先换元令 $t = i-j$。
$\frac{1}{m^n} \sum_{j=0}^{k} {n \choose j} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{i=0}^{n} {(m-1)}^{n-i}{n-j \choose i-j} = \frac{1}{m^n} \sum_{j=0}^{k} {n \choose j} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{i=j}^{n} {(m-1)}^{n-i}{n-j \choose i-j} = \frac{1}{m^n} \sum_{j=0}^{k} {n \choose j} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{t=0}^{n} {(m-1)}^{n-t-j}{n-j \choose t} = \frac{1}{m^n} \sum_{j=0}^{k} {n \choose j} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! \sum_{t=0}^{n} 1^t{(m-1)}^{n-t-j}{n-j \choose t} = \frac{1}{m^n} \sum_{j=0}^k {n \choose j} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! {(m-1+1)}^{n-j} = \frac{1}{m^n} \sum_{j=0}^k {n \choose j} {\begin{Bmatrix}k \\ j \end{Bmatrix}} j! m^{n-j}$。
注意到 ${n \choose j} = \frac{n^{\underline{j}}}{j!}$ 而下降幂只有 $j$ 项可以暴力，预处理处 $1 \to k$ 的阶乘逆即可做到 $O(k^2)$。
# 计数 dp
[参见寒假内容](https://www.luogu.com.cn/article/1akxk0n9)