组合数学详解

__O_v_O__ · 2024-07-03 09:10:06 · 算法·理论

前置：一些定义

$n^{\overline{k}}$ 表示 $n$ 的上升幂，即 $n\times(n+1)\cdots\times(n+k-1)

组合恒等式

常用组合公式

定义式

C_n^m=\binom{n}{m}=\frac{n!}{m!(n-m)!}=\frac{n^{\underline{m}}}{m!}

递推式

\binom{n}{m}=\binom{n-1}{m-1}+\binom{n-1}{m}

证明：

相当于从 n 个物品中选择 m 个的方案数，分两种情况。

第 n 个不选，有 \binom{n-1}{m} 种情况。
第 n 个要选，有 \binom{n-1}{m-1} 种。

则 \binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}。

对称性

\binom{n}{m}=\binom{n}{n-m}

证明： 使用定义式展开即可。

吸收/相伴等式

\frac{\binom{n}{m}}{\binom{n-1}{m-1}}=\frac{n}{m}

\frac{\binom{n}{m}}{\binom{n-1}{m}}=\frac{n}{n-m}

\frac{\binom{n}{m}}{\binom{n}{m-1}}=\frac{n-m+1}{m}

证明： 同样定义式展开即可。

上指标反转

\binom{r}{k}=(-1)^k\binom{k-r-1}{k}

证明：

\begin{aligned}\binom{r}{k}=\frac{r^{\underline{k}}}{k!}&=\frac{r(r-1)(r-2)\cdots(r-k+1)}{k!}\\&=\frac{(-1)^k(-r)(1-r)\cdots(k-r-1)}{k!}\\&=\frac{(-1)^k(k-r-1)^{\underline{k}}}{k!}\\&=(-1)^k\binom{k-r-1}{k}\end{aligned}

三项式系数

\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}

证明：

\begin{aligned}\binom{n}{m}\binom{m}{k}&=\frac{n!}{(n-m)!(m-k)!k!}\\&=\binom{n}{k}\binom{n-k}{m-k}\end{aligned}

上指标求和

\sum\limits_{k=0}^n\binom{k}{m}=\binom{n+1}{m+1}

证明：

将 \binom{n+1}{m+1} 用加法公式一步步展开即可。

下指标求和

\sum\limits_{i=0}^n\binom{n}{i}=2^n

证明：

从 n 个物品中取出任意个数物品的方案数，就是大小为 n 的集合的子集个数。

下指标卷积（范德蒙德卷积）

\sum\limits_{i=0}^n\binom{a}{i}\binom{b}{n-i}=\binom{a+b}{n}

证明：

左边相当于从 a 个物品中选 i 个数的方案数，右边相当于从 b 个物品中选 n-i 个数的方案数，则求和相当于从 a+b 个数中选 n 个数的方案数，即 \binom{a+b}{n}。

上指标卷积

\sum\limits_{i=0}^n\binom{i}{a}\binom{n-i}{b}=\binom{n+1}{a+b+1}

证明：

左式的组合意义为将 n 个物品分为在左右两部分，左边选 a 个，右边选 b 个的方案数，同时等价于插入一个分隔符，共 n+1 个物品选 a+b+1 个的方案数，即 \binom{n+1}{a+b+1}。

平行求和法

\sum\limits_{k=0}^n\binom{r+k}{k}=\binom{r+n+1}{n}

证明：

把右边式子用递推式一直展开即可。

交错和

\sum\limits_{k=0}^m(-1)^k\binom{n}{k}=(-1)^m\binom{n-1}{m}

证明：

\begin{aligned}\sum\limits_{i=0}^m(-1)^k\binom{n}{k}&=\sum\limits_{i=0}^m\binom{k-n-1}{k}\\&=\binom{m-n}{m}\\&=(-1)^m\binom{n-1}{m}\end{aligned}

例题

化简：

\sum\limits_{k=0}^m\frac{\binom{m}{k}}{\binom{n}{k}}

sol:

注意到 \binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}。

则原式等于：

\begin{aligned}\sum\limits_{k=0}^m\frac{\binom{n-k}{m-k}}{\binom{n}{m}}&=\frac{1}{\binom{n}{m}}\sum\limits_{k=0}^m\binom{n-k}{m-k}\\&=\frac{1}{\binom{n}{m}}\sum\limits_{k=0}^m\binom{n-m+k}{k}\\&=\frac{\binom{n+1}{m}}{\binom{n}{m}}\\&=\frac{n+1}{n+1-m}\end{aligned}

HDU6333

**sol:** 把 $n,m$ 看成区间，使用莫队。考虑 $n\rightarrow n+1$，$m\rightarrow m+1$ 的变化即可。 3. **化简：** $$\sum\limits_{i=0}^m\binom{n}{i}\binom{m}{i}$$ **sol:** $\begin{aligned}\sum\limits_{i=0}^m\binom{n}{i}\binom{m}{i}&=\sum\limits_{i=0}^m\binom{n}{i}\binom{m}{m-i}\\&=\binom{n+m}{m}\end{aligned}

化简：

\sum\limits_{i=m}^n(-1)^i\binom{n}{i}\binom{i}{m}

sol:

&=\binom{n}{m}(-1)^m\sum\limits_{i=0}^{n-m}\binom{m-n-1+i}{i}\\&=(-1)^m[n=m]\end{aligned}

化简：

\sum\limits_{k}\binom{n+k}{2k}\binom{2k}{k}\frac{(-1)^k}{k+1}

sol:

\begin{aligned}\sum\limits_{k}\binom{n+k}{2k}\binom{2k}{k}\frac{(-1)^k}{k+1}&=\sum\limits_{k}\binom{n+k}{k}\binom{n}{k}\frac{(-1)^k}{k+1}\\&=\frac{1}{n+1}\sum\limits_{k}\binom{n+k}{k}\binom{n+1}{k+1}(-1)^k\\&=\frac{1}{n+1}\sum\limits_{k}\binom{-n-1}{k}\binom{n+1}{k+1}\\&=\frac{1}{n+1}\sum\limits_{k}\binom{-n-1}{k}\binom{n+1}{n-k}\\&=\frac{1}{n+1}\binom{0}{n}=[n=0]\end{aligned}

有标号连通图计数

sol:

设 f_n 为 n 个点连通图个数，g_n 为 n 个点无向图个数，显然 g_n＝2^{\binom{n}{2}}。

则 g_n=\sum\limits_{j=1}^n\binom{n-1}{j-1}f_jg_{n-j}。

所以 g_n=\sum\limits_{i=1}^{n-1}\binom{n-1}{j-1}f_jg_{n-j}+f_n。

所以 f_n=g_n-\sum\limits_{i=1}^{n-1}\binom{n-1}{j-1}f_jg_{n-j}，动态规划即可，复杂度 O(n^2)。

鸽巢原理

基本公式

将 (\sum\limits_{i=1}^np_i)−n+1 个物品放入 n 个盒子，一定存在一个盒子 i，使得第 i 个盒子至少装了 p_i 个物品。

例题

有十个数 a_1,a_2\cdots a_{10} 满足 \mathop{\forall}\limits_{1\le i\le 10}1\le a_i\le 60，证明能够从 a_i 中挑出两个交为空的子集，使得它们的和相等。

sol:

首先发现交为空的条件没有用，因为如果找到两个和相等的子集，将它们相交的部分同时去掉，也不影响和相等。

观察到子集总数为 2^{10}=1024 大于和的总数 60\times 10=600，则必有两个子集和相等。

证明一张有超过 1 个点的简单无向图必定有两点度数相等。

sol:

若存在两个及以上 0 度点，则成立。
若存在一个 0 度点，则剩余 n-1 个点的度数只能在 [1,n-2] 中取，故一定有两点度数相等。
若不存在 0 度点，则 n 个点的度数只能在 [1,n-1] 中取，故一定有两点度数相等

证明能从任意 11 个实数中取出 4 个满足：(ac + bd)^2\ge \frac{1}{2}(a^2+b^2)(c^2+d^2)。

sol:

显然，存在 6 个实数同号，把这 6 个实数看成 3 个向量，因为这 3 个向量均在第一或第三象限，所以一定存在两个向量夹角小于等于 45 度，利用余弦定理得 \cos 45^\circ\ge \frac{ac+bd}{\sqrt{(a^2+b^2)(c^2+d^2)}}，平方得 \frac{1}{2}\ge \frac{(ac+bd)^2}{(a^2+b^2)(c^2+d^2)}，变形即可得到原式。

错排

基本公式

记 f_n 表示长度为 n 的错排个数。

则：

f_n=(n-1)(f_{n-1}+f_{n-2})

例题

更简单的排列计数

记 cyc_{\pi} 表示把排列 \pi 看成置换，其中环的个数。

给定 n,k 和多项式 F，对 1\le m\le n 求 $\sum\limits{\pi}F(cyc{\pi})

**sol:** $\begin{aligned}\sum\limits_{\pi}F(cyc_{\pi})&=\sum\limits_{\pi}\sum\limits_{i=0}^{k-1}f_icyc_{\pi}^i\\&=\sum\limits_{\pi}\sum\limits_{i=0}^{k-1}f_i\sum\limits_{j=0}^i\begin{Bmatrix} i \\j \end{Bmatrix}\binom{cyc_{\pi}}{j}j!\\&=\sum\limits_{\pi}\sum\limits_{i=0}^{k-1}\sum\limits_{j=0}^if_i\begin{Bmatrix} i \\j \end{Bmatrix}\binom{cyc_{\pi}}{j}j!\\&=\sum\limits_{\pi}\sum\limits_{j=0}^{k-1}\sum\limits_{i=j}^{k-1}f_i\begin{Bmatrix} i \\j \end{Bmatrix}\binom{cyc_{\pi}}{j}j!\\&=(\sum\limits_{j=0}^{k-1}j!)(\sum\limits_{\pi}\binom{cyc_{\pi}}{j})(\sum\limits_{i=j}^{k-1}f_i\begin{Bmatrix} i \\j \end{Bmatrix})\end{aligned}

记 c_{t,i} 表示 |\pi|=t 且 cyc_{\pi}=i 的错排 \pi 个数。

考虑递推，设 1 在序列中的位置为 k，分两种情况：

这里其实和错排的递推差不多。

而 k 有 t-1 种选法，则 c_{t,i}=(t-1)(c_{t-2,i-1}+c_{t-1,i})。

又记 p_{t,i} 表示 \sum\limits_{|\pi|=t}\binom{cyc_{\pi}}{i} 的值。

将式子转换为枚举 cyc_{\pi}，可得：

\begin{aligned}p_{t,i}&=\sum\limits_{j=1}^t\binom{j}{i}c_{t,j}\\&=\sum\limits_{j=1}^t\binom{j}{i}(t-1)(c_{t-2,j-1}+c_{t-1,j})\\&=(t-1)\sum\limits_{j=1}^t\binom{j}{i}(c_{t-2,j-1}+c_{t-1,j})\\&=(t-1)[\sum\limits_{j=1}^t\binom{j}{i}c_{t-2,j-1}+\sum\limits_{j=1}^t\binom{j}{i}c_{t-1,j}]\\&=(t-1)[\sum\limits_{j=1}^t[\binom{j-1}{i}c_{t-2,j-1}+\binom{j-1}{i-1}c_{t-2,j-1}]+\sum\limits_{j=1}^t\binom{j}{i}c_{t-1,j}]\\&=(t-1)(p_{t-2,i}+p_{t-2,i-1}+p_{t-1,i})\end{aligned}

而由于 t\le n,i<k，则 p 数组可以在 O(nk) 时间复杂度内递推处理。

再看求得的答案式子：

(\sum\limits_{j=0}^{k-1}j!)(\sum\limits_{\pi}\binom{cyc_{\pi}}{j})(\sum\limits_{i=j}^{k-1}f_i\begin{Bmatrix} i \\j \end{Bmatrix})

我们发现：前面一部分和后面一部分可以 O(k^2) 预处理，中间一部分已经被 O(nk) 递推，则枚举要计算的 m，式子就能 O(1) 算了。

容斥原理

基本容斥

对于一个集合 S 的一部分子集构成的簇 P 有：|\mathop{\bigcup}\limits_{T\in P}T| =\sum\limits_{Q\subset P}(−1)^{|Q|−1}|\mathop{\bigcap}\limits_{T\in Q}T|

证明：

考虑每个元素 x，假设它被 k 个元素包含，那么它的贡献就是 \sum\limits_{i=1}^k(-1)^{i-1}\binom{k}{i}。

若 k=0，显然原式等于 0。

若 k>0，则：

则 $x$ 的贡献为 $[k>0]$，可得原式。 ### $\min/\max$ 容斥 $$\max(S)=\sum\limits_{T\subseteq S}(-1)^{|T|+1}\min(T)$$ $$\max\limits_{kth}(S)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min(T)$$ **证明：** $\begin{aligned}\max\limits_{k_{th}}{S}&=\sum\limits_{T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}\min T}\\&=\sum\limits_{x\in S}x\sum\limits_{x\in T\subseteq S}{(-1)^{|T|-k}\dbinom {|T|-1}{k-1}[\min{T}=x]}\end{aligned}

令 f(x) 表示 S 中大于 x 的元素构成的集合。

\begin{aligned}=\sum\limits_{x\in S}{x}\sum\limits_{x\in T\subseteq f(x)}{(-1)^{|T|-k}\dbinom{|T|-1}{k-1}}\end{aligned}

枚举 |T|:

\begin{aligned}&=\sum\limits_{x\in S}{x\sum\limits_{l=1}^{|f(x)|}{(-1)^{l-k}\dbinom{|f(x)|-1}{l-1}\dbinom{l-1}{k-1}}}\\&=\sum\limits_{x\in S}{x\sum\limits_{l=1}^{|f(x)|}{(-1)^{l-k}\dbinom {|f(x)|-1}{k-1}\dbinom{|f(x)|-k}{l-k}}}\\&=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}\sum\limits_{l=1} ^{|f(x)|}{(-1)^{l-k}\dbinom {|f(x)|-k}{l-k}}}\end{aligned}

易知 |f(x)|<k 时无贡献。

\begin{aligned}&=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}\sum\limits_{l=0}^{|f(x)|-k}(-1)^l\dbinom{|f(x)|-k}{l}}\\&=\sum\limits_{x\in S}{x\dbinom {|f(x)|-1}{k-1}[|f(x)|=k]}=\max\limits_{k_{th}}{S}\end{aligned}

例题1

硬币购物

共有 4 种硬币。面值分别为 c_1,c_2,c_3,c_4。

某人去商店买东西，去了 n 次，对于每次购买，他带了 d_i 枚 i 种硬币，想购买 s 的价值的东西。请问每次有多少种付款方法。

sol:

设 A_1,A_2,A_3,A_4 分别为每种硬币取超限的方案数。

则答案为总情况数减去 A_1\cup A_2\cup A_3\cup A_4。

显然，总情况数做一个完全背包即可求出。

现在考虑第 1 种硬币超限的方案数，它其实相当于先取 d_1+1 个第 1 种硬币，再对剩下的硬币做一次完全背包。

同理，可以用以上方法算出所有方案数，此题得解。

卡农

在集合 S=\{1,2,\cdots,n\} 中，选出 m 个无序的互不相同的非空子集，使得每个元素的出现次数均为偶数，求选择方案数。

sol:

设 f_i 表示选出 i 个集合满足条件的方案数。

先考虑出现次数为偶数的限制：前 i-1 个集合确定了，第 i 个集合也确定了，方案数为 (2^n-1)^{\underline{i-1}}。

再减去不满足另外两个限制的方案数：

第 i 个集合为空集。此时前 i-1 个集合构成合法方案，数量为 f_{i-1}。
第 i 个集合和第 j 个集合相同。此时剩下 i-2 个集合构成合法方案，且 j 有 i-1 种选法，集合 i 有 2^n-1-(i-2) 种选法。故数量为 f_{i-2}(i-1)(2^n-i+1)。

综上，递推式为 f_i=(2^n-1)^{\underline{i-1}}-f_{i-1}-f_{i-2}(i-1)(2^n-i+1)。

如何正确地排序

给定数列 a,b,c，求 \sum\limits_{i=1}^n\sum\limits_{j=1}^n\max\{a_i+a_j,b_i+b_j,c_i+c_j\}-\min\{a_i+a_j,b_i+b_j,c_i+c_j\}。

sol:

考虑 min-max 容斥。

\begin{aligned}\max\{a_i+a_j,b_i+b_j,c_i+c_j\}-\min\{a_i+a_j,b_i+b_j,c_i+c_j\}\end{aligned}

\begin{aligned}=a_i+a_j+b_i+b_j+c_i+c_j-\min\{a_i+a_j,b_i+b_j\}-\min\{a_i+a_j,c_i+c_j\}-\min\{b_i+b_j,c_i+c_j\}\end{aligned}

考虑如何求出 \sum\limits_{i=1}^n\sum\limits_{j=1}^n-\min\{a_i+a_j,b_i+b_j\}。

把式子变成 (a_i+a_j)[a_i+a_j<b_i+b_j]，移一下项可得：(a_i+a_j)[a_i-b_i<b_j-a_j]，发现就是一个逆序对，树状数组或二维偏序即可。

Card Collector

给 n 个元素，每次随机选择一个，有 p_i 的概率选择第 i 个，问所有元素都被选择的期望时间。

sol1:

假设全集为 S，则答案为 E(\max(S))。

考虑 min-max 容斥：

而 $E(\min(T))$ 第一次抽出集合 $T$ 中元素的期望时间，显然是 $\frac{1}{\sum\limits_{i\in S}p_i}$。（概率是 $\sum\limits_{i\in S}p_i$，则期望是它的倒数，可证明） **sol2:** 设 $f_S$ 表示现在已经有了集合 $S$ 中的元素，集齐全部的时间期望。则 $f_{S}=1+(\sum\limits_{i\in S}p_i)f_{S}+(\sum\limits_{i\notin S}p_i)f_{S+\{i\}}$。化简得 $f_{S}=\frac{1+(\sum\limits_{i\notin S}p_i)f_{S+\{i\}}}{1-\sum\limits_{i\in S}p_i}$，dp 即可。 5. **重返现世** 给 $n$ 个元素，每次随机选择一个，有 $\frac{p_i}{m}$ 的概率选择第 $i$ 个，问第一次有 $k$ 个元素被选择的期望时间。 **sol:** 设全集为 $S$，显然答案为 $E(\max\limits_{kth}(S))$。由 min-max 容斥： $\begin{aligned}E(\max\limits_{kth}(S))&=\sum\limits_{T\subset S}(-1)^{|T|-k}\binom{|T|-1}{k-1}E(\min(S))\\&=\sum\limits_{T\subset S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\frac{m}{\sum\limits_{i\in T}p_i}\end{aligned}

转为枚举 \frac{m}{\sum\limits_{i\in T}p_i}，则答案为：

\sum\limits_{h=0}^m\frac{m}{h}\cdot \sum\limits_{T\subset S\land \sum\limits_{i\in T}p_i=h}(-1)^{|T|-k}\binom{|T|-1}{k-1}

设 \frac{m}{h} 后面一部分为 f_{n,h}，则答案为：\sum\limits_{h=0}^m\frac{m}{h}\cdot f_{n,h}。

考虑转移，有两种情况：

不选 n，则贡献为 f_{n-1,h}。

选 n，对于 i,j 这两维，必定分别由 i-1,j-p_i 转移而来，但如果直接转移，转移后的所有 |T| 都比转移前大 1（塞了个 p_i 进去），考虑其影响：

式子里的 (-1)^{|T|-k} 正负相反，所以应该给转移的 f 取相反数。
观察 C_{|T|-1}^{k-1}，如果 |T| 大 1，它可以拆成 C_{|T|-1}^{k-1} + C_{|T|-1}^{k-2}。

把它们综合起来，可得 f_{i,j,k}=f_{i-1,j,k}-f_{i-1,j-p_i,k}+f_{i-1,j-p_i,k-1}。

### 二项式反演 #### 基本公式 $$F(n)=\sum\limits_{i=m}^n\binom{n}{i}G(i)\Leftrightarrow G(n)=\sum\limits_{i=m}^n(-1)^{n-i}\binom{n}{i}F(i)$$ $$F(n)=\sum\limits_{i=m}^n\binom{i}{m}G(i)\Leftrightarrow G(n)=\sum\limits_{i=m}^n(-1)^{n-i}\binom{i}{m}F(i)$$ **证明：** 这里只证明第一个，第二个同理。要证明第一个式子等价于第二个式子，相当于把 $F(n)$ 代入第二个式子后，第二个式子是恒等式。代入得： $\begin{aligned}G(n)&=\sum\limits_{i=m}^n(-1)^{n-i}\binom{n}{i}\sum\limits_{j=m}^i\binom{i}{j}G(j)\\&=\sum\limits_{i=m}^n\sum\limits_{j=m}^i(-1)^{n-i}\binom{n}{i}\binom{i}{j}G(j)\\&=\sum\limits_{j=m}^n\sum\limits_{i=j}^n(-1)^{n-i}\binom{n}{j}\binom{n-j}{i-j}G(j)\\&=\sum\limits_{j=m}^n\binom{n}{j}\sum\limits_{i=j}^n(-1)^{n-i}\binom{n-j}{i-j}G(j)\\&=\sum\limits_{j=m}^n\binom{n}{j}\sum\limits_{i=0}^{n-j}(-1)^{n-j-i}\binom{n-j}{i}G(j)\\&=\sum\limits_{j=m}^n\binom{n}{j}(1-1)^{n-j}G(j)\\&=\sum\limits_{j=m}^n\binom{n}{j}G(j)[n=j]\\&=\binom{n}{n}G(n)=G(n)\end{aligned}

例题2

集合计数

一个有 n 个元素的集合，现在要取出此集合的若干子集（至少一个），使得它们的交集的元素个数为 k，求取法的方案数。

sol:

记 F_i 为答案，G_i 表示「至少」i 个元素是集合的交集，即钦定 i 个元素作为集合的交集，剩余不做限制的方案数，会有重复。

而另外 n−i 个元素都可以选或不选，所以共有 2^{n−i} 个集合，在其中选若干个集合有 2^{2^{n−i}} 种情况，再去掉一个空集，所以是 2^{2^{n−i}}-1 种方案。

则 G_i=\binom{n}{k}(2^{2^{n-i}}-1)。

观察到 G_i=\sum\limits_{j=i}^n\binom{j}{i}F_j。解释一下：我们枚举 j 表示实际交集的元素数，而 G_i 统计了 \binom{j}{i} 次 F_j（从 j 个元素里选出 i 个钦定），所以上式成立。

二项式反演得：

\begin{aligned}F_k&=\sum\limits_{i=k}^n(-1)^{i-k}\binom{i}{k}G_i\\&=\sum\limits_{i=k}^n(-1)^{i-k}\binom{i}{k}\binom{n}{k}(2^{2^{n-i}}-1)\end{aligned}

已经没有什么好害怕的了

有两个序列 a_i,b_i 保证所有元素互不相同。

你需要重排 b 序列，使得恰好有 k 个 i 满足 a_i>b_i，求方案数。

sol:

先将 a 序列排序。

考虑设 dp_{i,j} 表示考虑了前 i 对数，钦定有 j 对数满足 a_x>b_x。

则 dp_{i,j}=dp_{i-1,j}+dp_{i-1,j-1}\times(cnt_{a_i}-j+1)。

设 $f(i)$ 表示钦定 $i$ 对的方案数，$g(i)$ 表示恰好 $i$ 对的方案数。观察可得：$f_i=(n-i)!dp_{n,i}$。又有：$f_i=\sum\limits_{j=i}^n\dbinom ji g_j

二项式反演得：g_k=\sum\limits_{i=k} ^n{(-1)^{n-i}\dbinom ik(n-i)!dp_{n,i}}。

Sky Full of Stars

有一个 n\times n 的矩阵，将其三染色，使得至少有一行或一列同色，问方案数。

sol:

记 f_{i,j} 为恰好 i 行 j 列同色的方案数，g_{i,j} 为钦定 i 行 j 列同色的方案数。

显然，g_{i,j} 有四种情况：

观察到：

\begin{aligned}g_{i,j}&=\sum\limits_{k=i}^n\sum\limits_{l=j}^n \binom{k}{i}\binom{l}{j}f_{k,l}\\&=\sum\limits_{k=i}^n\binom{k}{i}\sum\limits_{l=j}^n\binom{l}{j}f_{k,l}\end{aligned}

记 h_{k,j}=\sum\limits_{l=j}^n\binom{l}{j}f_{k,l}，则 g_{i,j}=\sum\limits_{k=i}^n\binom{k}{i}h_{k,j}。

二项式反演得：

h_{i,j}=\sum\limits_{k=i}^n\binom{k}{i}(-1)^{n-k}g_{k,j}

又 h_{i,j}=\sum\limits_{l=j}^n\binom{l}{j}f_{i,l}。

二项式反演得：

f_{i,j}=\sum\limits_{l=j}^n(-1)^{n-l}\binom{l}{j}h_{i,l}

将 h_{i,l} 代入得：

f_{i,j}=\sum\limits_{l=j}^n(-1)^{n-l}\binom{l}{j}\sum\limits_{k=i}^n(-1)^{n-k}\binom{k}{i}g_{k,l}

注意到我们只需要求出 f_{0,0}，答案就是总方案数减去 f_{0,0}。

所以 f_{0,0}=\sum\limits_{k=0}^n\sum\limits_{l=0}^n(-1)^{l+k}g_{k,l}。

把 g_{k,l} 分类可得：

f_{0,0}=g_{0,0}+\sum\limits_{j=1}^n(-1)^jg_{0,j}+\sum\limits_{i=1}^n(-1)^ig_{i,0}+\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{i+j}g_{i,j}

其中前三部分都能 O(n) 求出，问题来到第四部分。

\begin{aligned}\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^{i+j}g_{i,j}&=3\sum\limits_{i=1}^n\sum\limits_{j=1}^n(-1)^i(-1)^j\binom{n}{i}\binom{n}{j}3^{(n-i)(n-j)}\\&=3\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^{n-1}(-1)^i(-1)^j\binom{n}{i}\binom{n}{j}3^{ij}\\&=3\sum\limits_{i=0}^{n-1}(-1)^i\binom{n}{i}\sum\limits_{j=0}^{n-1}(-1)^j3^{ij}\binom{n}{j}\\&=3\sum\limits_{i=0}^{n-1}(-1)^i\binom{n}{i}\sum\limits_{j=0}^{n-1}(-3^i)^j\binom{n}{j}\\&=3\sum\limits_{i=0}^{n-1}(-1)^i\binom{n}{i}[(-3^i+1)^n-(-3^{in})]\end{aligned}

这样就能 O(n) 算出了，此题得解。

特殊数

卡特兰数

斯特林数

第二类斯特林数

第二类斯特林数 \begin{Bmatrix} n \\m \end{Bmatrix} 表示把 n 个不同元素划分成 m 个相同的集合中（不能有空集）的方案数。

求法：

递推式

\begin{Bmatrix} n \\m \end{Bmatrix}=m\begin{Bmatrix} n-1 \\m \end{Bmatrix}+\begin{Bmatrix} n-1 \\m-1 \end{Bmatrix}

证明：

考虑第 n 个元素放在哪个集合。它要么在已经有的 k 个非空集合里选一个放进去，要么自己单开一个新的集合。

通项公式

\begin{Bmatrix} n \\m \end{Bmatrix}=\sum\limits_{i=0}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}

证明：

记 f_{n,m}=\begin{Bmatrix} n \\m \end{Bmatrix}，g_{n,m} 表示允许空集的方案数。

显然，g_{n,m}=\frac{n^m}{m!}。

钦定非空集合个数知：

g_{n,m}=\sum\limits_{i=1}^m\binom{m}{i}f_{n,i}

对其二项式反演可得：

f_{n,m}=\sum\limits_{i=1}^m(-1)^{m-i}\binom{m}{i}g_{n,i}

带入 g_{n,i} 可得：

\begin{aligned}\begin{Bmatrix} n \\m \end{Bmatrix}&=f_{n,m}\\&=\sum\limits_{i=1}^m(-1)^{m-i}\binom{m}{i}\frac{m^n}{m!}\\&=\sum\limits_{i=1}^m\frac{(-1)^{m-i}i^n}{i!(m-i)!}\end{aligned}

第一类斯特林数

第一类斯特林数 \begin{bmatrix} n \\k \end{bmatrix} 表示将 n 个元素排成 k 个轮换的方案数。也即所有 n! 个排列中，构成的置换有 k 个环的排列数。

递推式：

{n\brack k}=(n-1){n-1\brack k}+{n-1\brack k-1}

证明：

考虑第 n 个元素放在哪个轮换里。要么在已经有的 k 个轮换里选一个位置插进去，方案数是 n-1；要么自己单开一个新的轮换。

注意：第一类斯特林数无实用通项公式。

基本应用

斯特林数的特殊值

第二类

{n\brace 0}=[n=0]\ ,\ {n\brace 1}={n\brace n}=1(n>0)

{n\brace 2}=2^{n-1}-1(n>0)\ ,\ {n\brace n-1}=\binom{n}{2}

第一类

{n\brack 0}=[n=0]\ ,\ {n\brack n}=1(n>0)

{n\brack 1}=(n-1)!(n>0)\ ,\ {n\brack n-1}=\binom{n}{2}

一些恒等式

{n+1\brace m+1}=\sum\limits_{k}\binom{n}{k}{k\brace m}

证明：

使用组合意义：枚举 k 表示 n+1 号节点所在的集合之外剩下了 k 个节点，这 k 个节点构成了 m 个集合。

{n\brace m}=\sum\limits_k\binom{n}{k}{k+1\brace m+1}(-1)^{n-k}

证明：

把 1 中的式子二项式反演即可。

{m+n+1\brace m}=\sum\limits_{k=0}^mk{n+k\brace k}

证明：

\begin{aligned}\sum\limits_{k=0}^mk{n+k\brace k}&=\sum\limits_{k=0}^m\left({n+k+1\brace k}-{n+k\brace k-1}\right)\\&={m+n+1\brace m}\end{aligned}

同理可得：

{m+n+1\brack m}=\sum\limits_{k=0}^m(n+k){n+k\brack k}

\sum\limits_{k=0}^n{n\brack k}=n!

证明：

一个有 n 个元素的排列和一个 n 个元素的置换一一对应，于是枚举所有置换中的轮换个数，求和即为排列个数 n!。

斯特林数与上升幂、下降幂

普通幂转下降幂 x^n=\sum\limits_{k=0}^n\begin{Bmatrix} n \\k\end{Bmatrix}x^{\underline{k}}=\sum_{k=0}^n{{n\brace k}\binom xkk!}

证明（组合意义）：

那么先从 $x$ 个集合中选 $i$ 个，然后再把 $n$ 个元素有序划分为 $i$ 个部分，每个部分依次放进每个集合，组合意义与 $x^n$ 相同。 **证明（代数）：** 一个重要的观察：$x^{\underline{k+1}}=x^{\underline{k}}(x-k)$，$x\cdot x^{\underline{k}}=x^{\underline{k+1}}+k\cdot x^{\underline{k}}$。使用数学归纳法： $\begin{aligned}x\cdot x^{n-1}&=x\cdot \sum\limits_{k=0}^{n-1}{n-1\brace k}x^{\underline{k}}\\&=\sum\limits_{k=0}^{n-1}{n-1\brace k}x^{\underline{k+1}}+\sum\limits_{k=0}^{n-1}{n-1\brace k}k\cdot x^{\underline{k}}\\&=\sum\limits_{k=1}^n{n-1\brace k-1}x^{\underline{k}}+\sum\limits_{k=1}^{n-1}{n-1\brace k}k\cdot x^{\underline{k}}\\&=\sum\limits_{k=1}^n\left(k{n-1\brace k}+{n-1\brace k-1}\right)x^{\underline{k}}\\&=\sum\limits_{k=1}^n{n\brace k}x^{\underline{k}}\end{aligned}

故得证。

上升幂转普通幂

x^{\overline{n}}=\sum\limits_{i=0}^n{n\brack k}x^k

证明：

同样使用数学归纳法即可。

注意此时的观察为 (x+n-1)x^k=x^{k+1}+(n-1)x^k。

下降幂转普通幂

x^{\underline{n}}=\sum\limits_{k=0}^n(-1)^{n-k}{n\brack k}x^k

证明：

观察可知，上升和下降幂有交错的符号，如：

x^{\underline{4}}=x^4-6x^3+11x^2-6x

x^{\overline{4}}=x^4+6x^3+11x^2+6x

则根据上升幂转普通幂公式可得，原式成立。

普通幂转上升幂

x^n=\sum\limits_{k=0}^n{n\brace k}(-1)^{n-k}x^{\overline{k}}

证明：

在 x^n=\sum\limits_{k=0}^n{n\brace k}x^{\underline{k}} 中两边带入 -x，得：

(-1)^nx^n=\sum\limits_{k=0}^n{n\brace k}(-x)^{\underline{k}}

同时：

x^{\underline{n}}=(-1)^n(-x)^{\overline{n}}

故得证。

反转公式

\sum\limits_{k=m}^n{n\brace k}{k\brack m}(-1)^{k-m}=[m=n]

证明：

普通幂转下降幂，再下降幂转普通幂，得到：

x^n=\sum\limits_{k=0}^n{n\brace k}x^{\underline{k}}=\sum\limits_{k=0}^n{n\brace k}\sum\limits_{j=0}^k(-1)^{k-j}{k\brack j}x^j=\sum\limits_{j=0}^n\sum\limits_{k=j}^n{n\brace k}(-1)^{k-j}{k\brack j}x^j

对比两侧多项式的系数，即可得到原式。

类似地，下降幂转普通幂，再普通幂转下降幂，可以得到：

\sum\limits_{k=m}^n{n\brack k}{k\brace m}(-1)^{n-k}=[m=n]

斯特林反演

f(n)=\sum\limits_{k=0}^n{n\brace k}g(k)\Leftrightarrow g(n)=\sum\limits_{k=0}^n(-1)^{n-k}{n\brack k}f(k)

f(n)=\sum\limits_{k=m}^n{k\brace m}g(k)\Leftrightarrow g(n)=\sum\limits_{k=m}^n(-1)^{k-m}{k\brack m}f(k)

这里证明第一个式子，与二项式反演相似：

\begin{aligned}f(n)&=\sum\limits_{k=0}^n{n\brace k}\sum\limits_{j=0}^k(-1)^{k-j}{k\brack j}f(j)\\&=\sum\limits_{j=0}^nf(j)\sum\limits_{k=j}^n{n\brace k}{k\brack j}(-1)^{k-j}\\&=\sum\limits_{j=0}^nf(j)[j=n]=f(n)\end{aligned}

故得证。

例题

Team Work

给定 n,k，求：\sum\limits_{i=1}^n\binom{n}{i}i^k。

sol:

\begin{aligned}\sum\limits_{i=1}^n\binom{n}{i}i^k&=\sum\limits_{i=0}^n\binom{n}{i}\sum\limits_{j=1}^k{k\brace j}i^{\underline{j}}\\&=\sum\limits_{j=1}^k{k\brace j}j!\sum\limits_{i=0}^n\binom{n}{i}\binom{i}{j}\\&=\sum\limits_{j=1}^k{k\brace j}j!\binom{n}{j}\sum\limits_{i=0}^n\binom{n-j}{i-j}\\&=\sum\limits_{j=1}^k{k\brace j}j!\binom{n}{j}\sum\limits_{i=0}^{n-j}\binom{n-j}{i}\\&=\sum\limits_{j=1}^k{k\brace j}\binom{n}{j}2^{n-j}j!\end{aligned}

预处理斯特林数，即可 O(k^2) 计算。

组合数问题

给定多项式 f(k)=a_0+a_1k+a_2k^2+\cdots+a_mk^m 以及 n,x,p，求：

\sum\limits_{k=0}^nf(k)x^k\binom{n}{k}

sol:

首先把 f(k) 转下降幂多项式 f(k)=b_0+b_1k^{\underline{1}}+\cdots+b_mk^{\underline{m}}：

\sum\limits_{i=0}^ma_ik^i=\sum\limits_{i=0}^ma_i\sum\limits_{j=0}^i{i\brace j}k^{\underline{j}}=\sum\limits_{i=0}^m\left(\sum\limits_{j=i}^m{j\brace i}a_j\right)k^{\underline{i}}

则取 b_i=\sum\limits_{j=i}^m\begin{Bmatrix}j\\i\end{Bmatrix}a_j 即可。

则原式化为：

\sum\limits_{k=0}^n\sum\limits_{i=0}^mb_ik^{\underline{i}}x^k\binom{n}{k}

观察到：

k^{\underline{i}}\binom{n}{k}=n^{\underline{i}}\binom{n-i}{k-i}

带入原式得到：

\begin{aligned}\sum\limits_{k=0}^n\sum\limits_{i=0}^mb_ik^{\underline{i}}x^k\binom{n}{k}&=\sum\limits_{k=0}^n\sum\limits_{i=0}^mb_ix^kn^{\underline{i}}\binom{n-i}{k-i}\\&=\sum\limits_{i=0}^mb_in^{\underline{i}}\sum\limits_{k=0}^n\binom{n-i}{k-i}x^k\\&=\sum\limits_{i=0}^mb_in^{\underline{i}}x^i\sum\limits_{k=0}^{n-i}\binom{n-i}{k}x^k\\&=\sum\limits_{i=0}^mb_in^{\underline{i}}x^i(x+1)^{n-i}\end{aligned}

即可 O(m^2) 计算。

Crash 的文明世界

给定一棵 n 个点的树，以及一个常数 k，对每个 i=1,2,\cdots,n，求：

S(i)=\sum\limits_{j=1}^n\operatorname{dist}(i,j)^k

sol:

利用普通幂转下降幂，原式即为：

\begin{aligned}S(u)&=\sum\limits_{v=1}^n\sum\limits_{i=0}^k{k\brace i}\binom{\operatorname{dist}(u,v)}{i}i!\\&=\sum\limits_{i=0}^k{k\brace i}i!\sum\limits_{v=1}^n\binom{\operatorname{dist}(u,v)}{i}\end{aligned}

考虑使用树形 dp，设 f_{u,i} 表示 u 子树内所有点 v 的 \binom{\operatorname{dist}(u,v)}{i} 之和。

转移方程：

\begin{aligned}f_{u,i}&=\sum\limits_{v\in \operatorname{sub}(u)}\binom{\operatorname{dist}(u,v)}{i}\\&=\sum\limits_{v\in \operatorname{sub}(u)}\left(\binom{\operatorname{dist}(u,v)-1}{i-1}+\binom{\operatorname{dist}(u,v)-1}{i}\right)\\&=\sum\limits_{v\in \operatorname{sub}(u)}f_{v,i-1}+f_{v,i}\end{aligned}

做换根 dp 即可得到每个点的答案。

幼儿园篮球题

给定 L，T 次询问，每次给 n,m,k，求 \sum\limits_{i=0}^k\binom{m}{i}\binom{n-m}{k-i}i^L。

sol:

因为 x^L=\sum\limits_{i=0}^x\binom{x}{i}i!\begin{Bmatrix} L \\j \end{Bmatrix}。

所以：

\begin{aligned}\sum\limits_{i=0}^k\binom{m}{i}\binom{n-m}{k-i}i^L&=\sum\limits_{i=0}^k\binom{m}{i}\binom{n-m}{k-i}\sum\limits_{j=0}^i\binom{i}{j}j!\begin{Bmatrix} L \\j \end{Bmatrix}\\&=\sum\limits_{j=0}^k\sum\limits_{i=j}^k\binom{m}{i}\binom{n-m}{k-i}\binom{i}{j}j!\begin{Bmatrix} L \\j \end{Bmatrix}\\&=\sum\limits_{j=0}^kj!\begin{Bmatrix} L \\j \end{Bmatrix}\sum\limits_{i=j}^k\binom{m}{i}\binom{n-m}{k-i}\binom{i}{j}\\&=\sum\limits_{j=0}^kj!\begin{Bmatrix} L \\j \end{Bmatrix}\binom{m}{j}\sum\limits_{i=j}^k\binom{m-j}{i-j}\binom{n-m}{k-i}\\&=\sum\limits_{j=0}^kj!\begin{Bmatrix} L \\j \end{Bmatrix}\binom{m}{j}\sum\limits_{i=0}^{k-j}\binom{m-j}{k-i-j}\binom{n-m}{i}\end{aligned}

发现可以使用范德蒙德卷积，化简得：

=\sum\limits_{j=0}^kj!\begin{Bmatrix} L \\j \end{Bmatrix}\binom{m}{j}\binom{n-j}{k-j}

求出一行第二类斯特林数，即可 O(L) 计算。

生成函数

普通生成函数

将数列 \{a_i\} 写成一个函数 F(x)=\sum{a_ix^i} 的形式叫做普通生成函数。

对于生成函数来说，绝大数运算法则都是同平常所说的函数一样的，例如 A(x)+B(x)=\sum\limits{(a_i+b_i)x^i} 和 A(x)B(x)=\sum\limits_i\sum\limits_j(a_ib_j)x^{i+j}。

一些常见的数列都可以写作生成函数的形式，而且往往都有较为简单的形式：

\{1,1,1,\cdots\}\rightarrow 1+x+x^2+x^3+\cdots=\frac{1}{1-x}
\{1,2,3,\cdots\}\rightarrow 1+2x+3x^2+4x^3+\cdots=(1+x+x^2+x^3+\cdots)^\prime=(\frac{1}{1-x})^\prime=\frac{1}{(1-x)^2}
\{\binom{0}{n},\binom{1}{n},\binom{2}{n},\cdots\}=\binom{0}{n}+\binom{1}{n}x+\binom{2}{n}x^2+\cdots=(1+x)^n
\{1,p,p^2\dots\}\rightarrow1+px+(px)^2+\dots=\frac1{1-px}

注意我们这里的 x 只是一个占位符，我们要关注的是数列 a_i，写成多项式形式的目的是利用多项式的运算帮助我们处理关于 a_i 的操作，并更直观地观察数列的性质。所以多项式的运算对于系数 a_i 都有一定的组合意义，如加法可以代表两个方案数列的加法原理。

例题

食物

sol:

先计算出每一种食物的生成函数：

承德汉堡：能选的数列为 \{1,0,1,0,\cdots\}，生成函数为 \sum\limits_{i=0}^{\infty}x^{2i}，用等比数列求和公式计算，它等于 \frac{1}{1-x^2}。
可乐：能选的数列为 \{1,1,0,0,\cdots\}，生成函数为 1+x。
鸡腿：能选的数列为 \{1,1,1,0,\cdots\}，生成函数为 1+x+x^2。
蜜桃多：能选的数列为 \{0,1,0,1,\cdots\}，生成函数为 \sum\limits_{i=0}^{\infty}x^{2i+1}=\frac{x}{1-x^2}。
鸡块：能选的数列为 \{1,0,0,0,1,\cdots\}，生成函数为 \sum\limits_{i=0}^{\infty}x^{4i}=\frac{1}{1-x^4}。
包子：能选的数列为 \{1,1,1,1,0,\cdots\}，生成函数为 1+x+x^2+x^3。
土豆片炒肉：能选的数列为 \{1,1,0,0,\cdots\}，生成函数为 1+x。
面包：能选的数列为 \{1,0,0,1,\cdots\}，生成函数为 \sum\limits_{i=0}^{\infty}x^{3i}=\frac{1}{1-x^3}。

两个生成函数 a 和 b 的乘积 c 是加法卷积：

c_k=\sum\limits_{i+j=k}a_ib_j

考虑它的组合意义，假设 a_i 是某种物品取 i 个的方案数（b 同理），那么 c 的 n 次项系数即为对应的两种物品共取 n 个的方案数。

回到原题，显然直接把生成函数乘起来就是答案，化简得到：F(x)=\frac{x}{(x-1)^4}。

使用广义二项式定理化简得到：

\begin{aligned}\frac{x}{(x-1)^4}&=x(x-1)^{-4}\\&=x\sum\limits_{i=0}^{\infty}\binom{-4}{i}x^i(-1)^{-4-i}\\&=x\sum\limits_{i=0}^{\infty}\binom{i+3}{i}(-1)^{i}x^i(-1)^{-4-i}\\&=\sum\limits_{i=0}^{\infty}\binom{i+3}{i}x^{i+1} \end{aligned}

题目要求第 n 项的系数，所以把 i+1 换成 n，原式变为 \sum\limits_{n=1}^{\infty}\binom{n+2}{n-1}x^n。

显然，第 n 项的系数为 \binom{n+2}{n-1}=\binom{n+2}{3}=\frac{1}{6}n(n+1)(n+2)，这就是答案。

指数生成函数

对于数列 \{a_i\}，它的指数生成函数 F(x)=\sum{\frac{a_i}{i!}x^i}。

常用的指数生成函数：

\{1,1,1,\cdots\}\rightarrow e^x
\{1,-1,1,-1,\cdots\}\rightarrow e^{-x}
\{c^0,c^1,c^2,\cdots\}\rightarrow e^{cx}
\{1,0,1,0,1,\cdots\}\rightarrow \frac{e^x+e^{-x}}{2}
\{1,a^{\underline{1}},a^{\underline{2}},a^{\underline{3}},\cdots\}\rightarrow (1+x)^a