二项式反演
形式
形式 \(1\)：
\[f(n)=\sum\limits_{i=0}^{n}(-1)^i\binom{n}{i}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^{n}(-1)^i\binom{n}{i}f(i) \]形式 \(2\)：
\[f(n)=\sum\limits_{i=0}^{n}\binom{n}{i}g(i)\Leftrightarrow g(n)=\sum\limits_{i=0}^{n}(-1)^{n-i}\binom{n}{i}f(i) \]形式 \(3\)：
\[f(n)=\sum\limits_{i=n}(-1)^i\binom{i}{n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}(-1)^{i}\binom{i}{n}f(i) \]形式 \(4\)：
\[f(n)=\sum\limits_{i=n}\binom{i}{n}g(i)\Leftrightarrow g(n)=\sum\limits_{i=n}(-1)^{i-n}\binom{i}{n}f(i) \]把右边的东西带到左边里面就能证了。
应用
可以解决关于“钦定”的问题？
斯特林数
有两类，分开说。
第二类斯特林数
虽然被称作「第二类」，第二类斯特林数却在斯特林的相关著作和具体数学中被首先描述，同时也比第一类斯特林数常用得多。
第二类斯特林数（斯特林子集数） \(\begin{Bmatrix}n\\ k\end{Bmatrix}\)，表示将 \(N\) 个两两不同的元素，划分为 \(k\) 个相同的非空子集的方案数。
递推式
\[\begin{Bmatrix}n\\m\end{Bmatrix} = \begin{Bmatrix}n-1\\m-1\end{Bmatrix} + m\begin{Bmatrix}n-1\\m\end{Bmatrix} \]边界为：\(\begin{Bmatrix}n\\0\end{Bmatrix}=[n=0]\)。
利用组合意义证明。考虑第 \(n\) 个球的放置：
-
在原有 \(m-1\) 个盒子的情况下开一个新盒子，把第 \(n\) 个球放进去，方案数为 \(\begin{Bmatrix}n-1\\m-1\end{Bmatrix}\)。
-
在原有 \(m\) 个盒子的情况下，把第 \(n\) 个球放进其中一个盒子，方案数为 \(m\begin{Bmatrix}n-1\\m\end{Bmatrix}\)。
根据加法原理，加一下就有了递推式。
通项公式
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!} \]设有 \(n\) 个不同的球，放进 \(i\) 个不同的盒，
- 允许空盒的方案数为 \(G_i\)。
- 不允许空盒的方案数为 \(F_i\)。
显然有：
\[G_i=i^n\\G_i=\sum\limits_{j=0}^{i}\binom{i}{j}F_j \]根据二项式反演，有：
\[\begin{aligned}F_i&=\sum\limits_{j=0}^{i}(-1)^{i-j}\binom{i}{j}G_j\\&=\sum\limits_{j=0}^{i}(-1)^{i-j}j^n\frac{i!}{j!(i-j)!}\end{aligned} \]考虑 \(F_m\) 和 \(\begin{Bmatrix}n\\m\end{Bmatrix}\) 的关系，第二类斯特林数要求盒子相同，所以显然有 \(F_m=m!\cdot \begin{Bmatrix}n\\m\end{Bmatrix}\)，除掉 \(m!\) 以去掉标号。
于是：
\[\begin{Bmatrix}n\\m\end{Bmatrix}=\sum\limits_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!} \]同一行的计算
即为给定 \(n\)，求：
\[\begin{Bmatrix}n\\0\end{Bmatrix},\begin{Bmatrix}n\\1\end{Bmatrix},\begin{Bmatrix}n\\2\end{Bmatrix},\dots,\begin{Bmatrix}n\\n\end{Bmatrix} \]的值。
算两个数组：
\[f_i=\frac{i^n}{i!},g_i=\frac{(-1)^i}{i!} \]把 \(f\) 和 \(g\) 卷积就行了。
同一列的计算
给定 \(n,k\)，求：
\[\begin{Bmatrix}0\\k\end{Bmatrix},\begin{Bmatrix}1\\k\end{Bmatrix},\begin{Bmatrix}2\\k\end{Bmatrix},\dots,\begin{Bmatrix}n\\k\end{Bmatrix} \]的值。
回想例题 P5748 集合划分计数，这个例题其实就是同一行第二类斯特林数求和。我们考虑通过 EGF 求解本题。
只有一个盒子且必须放，我们构造数列 \(a=\langle0,1,1,1,\dots\rangle\)，它的第 \(n\) 项表达将 \(n\) 个不同的球放进一个盒子里的方案数。
由于我们盒子必须放东西，所以 \(a_0=0\)。
我们能求出 \(a\) 的 EGF：\(\hat F(x)=\sum\limits_{i\ge 1}\dfrac{x^i}{i!}=e^x-1\)。
在那个题的学习中，我们知道了：
- \(\hat F(x)^k\) 表示不同的/有标号的球放进 \(k\) 个不同的/有标号的盒子的生成函数。
- \(\dfrac{\hat F(x)^k}{k!}\) 表示不同的/有标号的球放进 \(k\) 个相同的/无标号的盒子的生成函数。
于是乎，我们就有：
\[\begin{Bmatrix}i\\k\end{Bmatrix}=\left[\frac{x^i}{i!}\right]\frac{\hat F(x)^k}{k!} \]其中 \(\left[\dfrac{x^i}{i!}\right]\) 的含义为 \(x^i\) 项的系数乘以 \(i!\)。
于是我们多项式快速幂算出 \(\hat F(x)^k\) 即可。
注意，这里 \(\hat F(x)^k\) 的常数项为 \(0\)，不能直接 \(\ln \exp\) 做，但一次项是 \(1\)，所以我们可以提一个 \(x^k\) 出来，就能做了。
oiwiki 上还说，\(e^{\hat F(x)}\)，也就是同一行求和，就是贝尔数的生成函数。贝尔数是啥我都不知道。
性质
- \(m^n=\sum\limits_{i=0}^{m}\begin{Bmatrix}n\\i\end{Bmatrix}i!\dbinom{m}{i}\)
第一类斯特林数
第一类斯特林数（斯特林轮换数） \(\begin{bmatrix}n\\ k\end{bmatrix}\)，表示将 \(n\) 个两两不同的元素，划分为 \(k\) 个相同的非空轮换的方案数。
一个轮换就是一个首尾相接的环形排列。我们可以写出一个轮换 \([A,B,C,D]\)，并且我们认为 \([A,B,C,D]=[B,C,D,A]=[C,D,A,B]=[D,A,B,C]\)，即，两个可以通过旋转而互相得到的轮换是等价的。注意，我们不认为两个可以通过翻转而相互得到的轮换等价，即 \([A,B,C,D]\neq[D,C,B,A]\)。
递推式
\[\begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\m\end{bmatrix} \]边界为 \(\begin{bmatrix}n\\0\end{bmatrix}=[n=0]\)。
利用组合意义证明。考虑第 \(n\) 个元素的放置：
-
在原有 \(m-1\) 个轮换的情况下开一个新轮换，把第 \(n\) 个元素放进去，方案数为 \(\begin{bmatrix}n-1\\m-1\end{bmatrix}\)。
-
在原有 \(m\) 个轮换的情况下，把第 \(n\) 个球放进其中一个轮换，方案数为 \((n-1)\begin{bmatrix}n-1\\m\end{bmatrix}\)。
根据加法原理，加一下就有了递推式。
通项公式
没有。
同一行的计算
即为给定 \(n\)，求：
\[\begin{bmatrix}n\\0\end{bmatrix},\begin{bmatrix}n\\1\end{bmatrix},\begin{bmatrix}n\\2\end{bmatrix},\dots,\begin{bmatrix}n\\n\end{bmatrix} \]的值。
我们搞出来 OGF：
\[F_n(x)=\sum\limits_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i \]根据递推公式，有：
\[F_n(x)=(n-1)F_{n-1}(x)+xF_{n-1}(x) \]于是有：
\[F_n(x)=\prod\limits_{i=0}^{n-1}(x+i)=x^{\overline{n}} \]那么上升幂咋求？？？？？
我们考虑分治。因为上升幂满足：
\[x^{\overline{2n}}=x^{\overline{n}}\cdot (x+n)^{\overline{n}} \]假如说当前已经求出 \(f(x)\) 的各项系数，我们考虑如何计算 \(f(x+n)\) 的各项系数。这个搞明白了用上面式子随便写写就行了（注意考虑 \(n\) 为奇数时最后面还有一项 \((x+n-1)\)）。
我们有（\(a\) 为 \(f(x)\) 的各项系数）：
\[f(x+n)=\sum\limits_{i=0}^{n}a_i(x+n)^i \]二项式定理展开：
\[f(x+n)=\sum\limits_{i=0}^{n}a_i\sum\limits_{j=0}^{i}\binom{i}{j}n^{i-j}x^j \]更换枚举顺序：
\[f(x+n)=\sum\limits_{j=0}^{n}x^j\sum\limits_{i=j}^{n}a_i\binom{i}{j}n^{i-j} \]把二项式拆开：
\[f(x+n)=\sum\limits_{j=0}^{n}\frac{x^j}{j!}\sum\limits_{i=j}^{n}\frac{i!a_in^{i-j}}{(i-j)!} \]我们令 \(A(x)=x!a_x\)，\(B(x)=\dfrac{n^x}{x!}\)，于是有：
\[f(x+n)=\sum\limits_{j=0}^{n}\frac{x^j}{j!}\sum\limits_{i=j}^{n}A(i)B(i-j) \]枚举 \(i-j\)：
\[f(x+n)=\sum\limits_{j=0}^{n}\frac{x^j}{j!}\sum\limits_{i=0}^{n-j}A(i+j)B(i) \]此时我们考虑把 \(A\) 翻转，即 \(A'(n-x)=A(x)\)，于是有：
\[f(x+n)=\sum\limits_{j=0}^{n}\frac{x^j}{j!}\sum\limits_{i=0}^{n-j}A'(n-j-i)B(i) \]于是我们把 \(A'\) 和 \(B\) 求个卷积，设 \(C=A'\times B\)，原式就成了：
\[f(x+n)=\sum\limits_{j=0}^{n}\frac{C(n-j)}{j!}x^j \]这样就得出了 \(f(x+n)\) 的各项系数了！
同一列的计算
给定 \(n,k\)，求：
\[\begin{bmatrix}0\\k\end{bmatrix},\begin{bmatrix}1\\k\end{bmatrix},\begin{bmatrix}2\\k\end{bmatrix},\dots,\begin{bmatrix}n\\k\end{bmatrix} \]的值。
我们用 EGF 搞搞。
首先考虑 \(i\) 个球放进 \(1\) 个轮换里的 EGF。
\(m\) 个球放进一个轮换里的方案是多少？可以先考虑 \(m\) 个球的排列数，显然为 \(m!\)，而其中每 \(m\) 个排列在轮换意义下会等价，故方案数为 \(\dfrac{m!}{m}=(m-1)!\)。
于是就可以写出来 EGF 了：
\[\hat F(x)=\sum\limits_{i=1}^{n}\frac{(i-1)!x^i}{i!}=\sum\limits_{i=1}^{n}\frac{x^i}{i} \]思考一下后会有：
- \(\hat F(x)^k\) 表示不同的/有标号的球放进 \(k\) 个不同的/有标号的轮换的生成函数。
- \(\dfrac{\hat F(x)^k}{k!}\) 表示不同的/有标号的球放进 \(k\) 个相同的/无标号的轮换的生成函数。
于是乎，我们就有：
\[\begin{bmatrix}i\\k\end{bmatrix}=\left[\frac{x^i}{i!}\right]\frac{\hat F(x)^k}{k!} \]把第二类斯特林数·列的代码改改就行了。
卡特兰数
记作 \(H_n\)。
常见公式
\[\begin{aligned}&H_n=\frac{\binom{2n}{n}}{n+1}(n\ge 2,n\in \mathbb{N}_+)\\&H_n=\begin{cases}\sum\limits_{i=1}^{n}H_{i-1}H_{n-i} & n\ge 2,n\in \mathbb{N}_+ \\ 1 & n=0,n=1\end{cases}\\&H_n=\frac{H_{n-1}(4n-2)}{n+1}\\&H_n=\dbinom{2n}{n}-\dbinom{2n}{n-1}\end{aligned} \]递推式/封闭形式
\[H_n=\sum\limits_{i=0}^{n-1}H_iH_{n-1-i}(n\ge 2) \]其中 \(H_0=1,H_1=1\)。记起 OGF 为 \(H(x)\)。
构造个方程，去解它的封闭形式：
\[H(x)=1+xH(x)^2 \]解出来：
\[H(x)=\frac{1\pm \sqrt{1 - 4x}}{2x} \]经过讨论，舍掉正号：
\[H(x)=\frac{1- \sqrt{1 - 4x}}{2x} \]然后我们运用牛顿二项式定理啊，双阶乘的化简技巧啊之类的东西展开它，得出：
\[H(x)=\sum\limits_{n\ge 0}\dbinom{2n}{n}\frac{1}{n+1}x^n \]这样就解出了通项公式。
伯努利数
可以用来求自然数幂和。
\[\begin{aligned}&B_0=1\\&B_k=1-\frac{1}{k+1}\sum\limits_{i=0}^{k-1}\binom{k+1}{i}B_i\\&\sum\limits_{j=0}^{m}\binom{m+1}{j}B_j=[m=0]\end{aligned} \]我们有其 EGF：
\[\sum\limits_{n=0}\frac{B_nx^{n}}{n!}=\frac{x}{e^x-1} \]可以用 EGF 预处理伯努利数。
有个神奇的定理：
\[\sum\limits_{i=0}^{n-1}i^k=\frac{1}{k+1}\sum\limits_{i=0}^{k}\binom{k+1}{i}B_in^{k+1-i} \]或者说：
\[\sum\limits_{i=0}^{n}i^k=n^k + \frac{1}{k+1}\sum\limits_{i=0}^{k}\binom{k+1}{i}B_in^{k+1-i} \]所以预处理伯努利数，就能 \(O(k)\) 求自然数幂和。
这就是个例题。
分拆数
经典例题：P4389 付公主的背包
记 \(p(n,k)\) 为把 \(n\) 拆分成 \(k\) 个正整数之和的方案数，有：
\[p(n,k) = p(n-1,k-1) + p(n-k,k) \]或者用生成函数求。假如说可以分成的整数集合为 \(D\)，有生成函数：
\[F(x)=\prod\limits_{k\in D}\sum\limits_{i=0} x^{ik}=\prod\limits_{k\in D}\frac{1}{1-x^k} \]其第 \(n\) 项系数为把 \(n\) 拆分成 \(D\) 中的数的方案数。其求法：
\[\begin{aligned} F(x)&=\prod\limits_{k\in D}\frac{1}{1-x^k}\\ &=\exp \sum\limits_{k\in D}\ln \frac{1}{1-x^k}\\ &=\exp \sum\limits_{k\in D}\sum\limits_{i=1}\frac{x^{ik}}{i} \end{aligned}\]后面可以通过拆贡献计算。推倒与计算过程在多项式习题-付公主的背包中有详细讲。
例题
P5824 十二重计数法
题解真的写的很详细了……我不写了……
\[\begin{aligned}\\\\\\\\\\\\\\\\\end{aligned} \] 标签：bmatrix,begin,end,组合,limits,sum,数学,Bmatrix From： https://www.cnblogs.com/baoyangawa/p/18091109