组合数学

一些模板

预处理阶乘+阶乘逆元计算组合数。

typedef long long ll;
ll fact[N],inv_fact[N];
void init(){
    fact[0]=1;
    for(int i=1;i<=n;i++)
        fact[i]=fact[i-1]*i%mod;
    inv_fact[n]=qpow(fact[n],mod-2);
    for(int i=n-1;i>=0;i++)
        inv_fact[i]=inv_fact[i+1]*(i+1)%mod;
}
ll C(int n,int m){return fact[n]*inv_fact[m]%mod*inv_fact[n-m]%mod;}

插板法

现有 \(n\) 个完全相同的球，将其分至 \(k\) 个盒子中，每个盒子至少 \(1\) 个球，共有多少种分法？
问题等价于用 \(k-1\) 个板子插入到 \(n-1\) 个空隙中，将其分为 \(k\) 组的方案数。答案就是 \[\binom{n-1}{k-1}\] 若每个盒子允许为空，就会出现多个板子插入同一空隙的情况。我们假设所有盒子中已有 \(1\) 个球，那么总共有 \(n+k\) 个球，答案就是 \[\binom{n+k-1}{k-1}=\binom{n+k-1}{n}\]

二项式定理

\[(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}\]

范德蒙德卷积

\[\sum_{i=0}^k\binom{n}{i}\binom{m}{k-i}=\binom{n+m}{k}\] 组合意义：在 \(n+m\) 中选 \(k\) 个，相当于先在 \(n\) 中选 \(i\) 个，再在 \(m\) 中选 \(k-i\) 个。

多重集的排列数

设 \(S=\{n_1\cdot a_1,n_2\cdot a_2,\cdots,n_k\cdot a_k\}\) 表示由 \(n_1\) 个 \(a_1\)，\(n_2\) 个 \(a_2\)，…，\(n_k\) 个 \(a_k\) 组成的多重集，则 \(S\) 的全排列个数为 \[\frac{n!}{\prod_{i=1}^k n_i!}=\frac{n!}{n_1!n_2!\cdots n_k!}\]

错排列

记 \(D_n\) 表示 \(n\) 个元素的错排列数，则有 \[D_n=(n-1)\cdot(D_{n-1}+D_{n-2})\] 其中 \(D_0=1,D_1=0,D_2=1\)。
对于第 \(n\) 个元素，其可以与前 \(n-1\) 个元素中任意一个交换位置。设与它交换的元素所在位置为 \(k\)，交换后分为两种情况：
- 第 \(k\) 个元素被交换到第 \(n\) 个位置，则剩下的 \(n-2\) 个元素构成错排列。 - 第 \(k\) 个元素没有交换到第 \(n\) 个位置，则剩下的 \(n-1\) 个元素构成错排列。

圆排列

设 \(n\) 个元素的圆排列数为 \(Q_n^n\)。考虑其中一种情况，从不同的位置断开就变为不同的排列，所以有 \[Q_n^n=\frac{A_n^n}{n}=(n-1)!\] 部分圆排列的公式： \[Q_n^r=\frac{A_n^r}{r}=\frac{n!}{r\cdot (n-r)!}\]

常用公式

(1)

\[\binom{n}{m}=\binom{n}{n-m}\] 显然。

(2)

\[\binom{n}{m}=\frac{n}{m}\binom{n-1}{m-1}\] 代数推导显然。

(3)

\[\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\] 组合意义：杨辉三角递推过程。

(4)

\[\sum_{i=0}^n\binom{n}{i}=2^n\] 代数推导： \[\sum_{i=0}^n\binom{n}{i}=(1+1)^n\]

(5)

\[\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]\] 代数推导： \[\sum_{i=0}^n(-1)^i\binom{n}{i}=(1-1)^n\]

(6)

\[\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\] 快拿这个式子去诈骗，一骗一个准。
代数推导： \[\sum_{i=0}^n\binom{n}{i}^2=\sum_{i=0}^n\binom{n}{i}\binom{n}{n-i}=\binom{2n}{n}\]

(7)

\[\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\] 代数推导：
首先处理 \(i\dbinom{n}{i}\)： \[i\binom{n}{i}=i\cdot \frac{n!}{i!(n-i)!}=n\cdot \frac{(n-1)!}{(i-1)!(n-i)!}=n\binom{n-1}{i-1}\] 设 \(j=i-1\)，代入： \[\sum_{i=0}^ni\binom{n}{i}=n\sum_{j=0}^{n-1}\binom{n-1}{j}=n2^{n-1}\]

(8)

\[\sum_{i=0}^n\binom{i}{m}=\binom{n+1}{m+1}\] 组合意义：
本质上是求杨辉三角某一列的和。我们可以发现，开头的 \(\dbinom{m}{m}\) 等于 \(\dbinom{m+1}{m+1}\)，也就是杨辉三角 \(\dbinom{m+1}{m}\) 的右侧，二者求和可以再次传递到右侧，如此不断直到 \(\dbinom{n+1}{m+1}\)。

(9)

\[\binom{n}{r}\binom{r}{k}=\binom{n}{k}\binom{n-k}{r-k}\] 代数推导和组合意义都易证。

容斥原理

\[\left|\bigcup_{i=1}^{n}S_i\right|=\sum_{m=1}^n(-1)^{m-1}\sum_{a_i<a_{i+1} }\left|\bigcap_{i=1}^mS_{a_i}\right|\]

min-max 容斥

高大上的东西，我觉得我用不上。现有长度为 \(n\) 的序列 \(\{x_i\}\)，设 \(S=\{1,2,3,\cdots,n\}\)，则有 \[\max_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\min_{j\in T}{x_j}}\] \[\min_{i\in S}{x_i}=\sum_{T\subseteq S}{(-1)^{|T|-1}\max_{j\in T}{x_j}}\]