生成函数
1.OGF
1.1.递归式和OGF
Example 1.
考虑一个问题，一开始池塘里有 \(50\) 只青蛙，视作第 \(0\) 年。
每年青蛙会翻四倍，然后跳出池塘 \(100\) 只，问第 \(n\) 年池塘有多少青蛙。
这个问题很容易找到一个递推式：\(a_{n+1}=4a_n-100,n\ge 0\)。
如果说暴力求得所有 \(a_i\)，复杂度是 \(O(n)\) 的，但是得到了很多不必要的信息。
为了阻止这样时间的浪费，我们想要找到 \(a_n\) 的通项公式。
先写成递归式的样子
\[a_{n+1}=4a_n-100\tag{1} \]初值是 \(a_0=50\)。
这样可以得到无穷多个等式，我们用生成函数的技巧优化成一个等式。
Definition 1. 令 \(\{f_n\}_{n\ge 0}\) 为一个实数序列，形式幂级数 \(F(x)=\sum_{n\ge 0}f_nx^n\) 被称作序列 \(\{f_n\}_{n\ge 0}\) 的普通生成函数 \(\text{Ordinary Generating Funcion}\)，简称 \(\text{OGF}\)。
\(\text{OGF}\) 是最平凡的，所以有时也直接省略 \(\text{ordinary}\)，直接称作生成函数。
为了将生成函数代入上面的式子，只需要在等式两边同时乘上 \(x^{n+1}\)，并对所有 \(n\ge 0\) 求和。
然后就可以得到
\[\sum_{n\ge 0}a_{n+1}x^{n+1}=\sum_{n\ge 0}4a_nx^{n+1}-\sum_{n\ge 0}100x^{n+1}.\tag 2 \]左边可以写成 \(G(x)-a_0\)，右边可以写成 \(4xG(x)-\frac{100x}{1-x}\)，所以可以得到
\[G(x)-50=4xG(x)-\frac{100x}{1-x}.\tag 3 \]重新排列 \((3)\) 可以得到
\[G(x)=\frac{50}{1-4x}-\frac{100x}{(1-x)(1-4x)}.\tag 4 \]\(x^n\) 的系数就是 \(a_n\)，所以要求这个式子 \(x^n\) 的系数。
分开拆右式两项
\[\frac{50}{1-4x}=50\sum_{n\ge 0}(4x)^n=50\sum_{n\ge 0}4^nx^n,\notag\\ \frac{100x}{(1-x)(1-4x)}=100x\cdot\bigg(\sum_{n\ge 0}x^n\bigg)\cdot\bigg(\sum_{n\ge 0}4^nx^n\bigg).\notag \]上面那个式子的系数是容易的，下面的是一个卷积形式。
这个有两种处理办法。
第一种是直接展开卷积式，发现是一个等比数列求和的形式
第二种，考虑找到常数 \(A,B\) 满足
\[\frac{A}{1-x}+\frac{B}{1-4x}=\frac{100x}{(1-x)(1-4x)}. \]肯定能找到，因为通分过去就是右边那样。
然后通分解方程即可得到 \(A=\frac{100}3,B=\frac{-100}3\)，所以
\[\begin{align} \frac{100x}{(1-x)(1-4x)}&=\frac{100}3\cdot \frac 1{1-4x}-\frac{100} 3\cdot \frac 1 {1-x}\notag\\ &=\frac{100}3\bigg(\sum_{n\ge 0}4^nx^n-\sum_{n\ge 0}x^n\bigg)\notag\\ &=\sum_{n\ge 0}(4^n-1)x^n \frac{100} 3. \end{align} \]所以综合起来得到
\[a_n=50 \cdot4^n-100\cdot\frac{4^n-1}{3}.\tag 5 \]代入发现是对的，接下来总结一下解递归式的流程。
- 定义序列 \(\{a_n\}_{n\ge 0}\) 的生成函数 \(G(x)\)。
- 把递归式变成生成函数的一个等式，常用技巧是乘上 \(x^n,x^{n+1},x^{n+k}\) 之类的，然后对所有 \(n\ge 0\) 求和。
- 解出 \(G(x)\)。
- 找到 \(G(x)\) 中 \(x^n\) 的系数 \(a_n\)。
Example 2.
一开始往银行里存 \(1000\) 块钱，每年利润 \(5\%\)，然后新的一年再存 \(500\)，问 \(n\) 年之后账户有多少钱。
先写出递归式，然后按照上面的流程来。
\(a_0=1000,a_{n+1}=1.05\cdot a_n+500\)。
\[\sum_{n\ge 0}a_{n+1}x^{n+1}=\sum_{n\ge 0}1.05a_nx^{n+1}+\sum_{n\ge 0}500x^{n+1}.\tag 6 \]然后就有
\[G(x)-1000=1.05xG(x)-\frac{500x}{(1-x)}. \]移项之后
\[G(x)=\frac{1000}{1-1.05x}-\frac{500x}{(1-x)(1-1.05x)}.\tag 7 \]注意有
\[\frac{500x}{(1-x)(1-1.05x)}=500x\cdot\bigg(\sum_{n\ge 0}x^n\bigg)\cdot\bigg(\sum_{n\ge 0}1.05^nx^n\bigg).\tag 8 \]然后就和上一题一样解这个 \(G(x)\) 即可，过程是非常类似的。
最后得到 \(a_n=1.05^n\cdot 11000-10000\)。
下个例子说明生成函数也能解有更多项的递归式。
Example 3.
令 \(a_0=0,a_1=1,a_{n+2}=3a_{n+1}-2a_n,n\ge 0\)，求通项公式。
令 \(G(x)=\sum_{n\ge 0}a_nx^n\)，等式两边乘上 \(x^{n+2}\) 并对 \(n\ge 0\) 求和得到
\[\sum_{n\ge 0}a_{n+2}x^{n+2}=3\sum_{n\ge 0}a_{n+1}x^{n+2}-2\sum_{n\ge 0}a_nx^{n+2}, \]写成 \(G(x)\) 的形式并解出来
\[G(x)=\frac{x}{1-3x+2x^2}=\frac{A}{x-1}+\frac{B}{2x-1}.\tag 9 \]解到 \(A=1,B=-1\) 之后代入得到
\[G(x)=\frac {-1}{1-x}+\frac 1 {1-2x}.\tag {10} \]把两项分别展开即可得到
\[G(x)=-\sum_{n\ge 0}x^n+\sum_{n\ge 0}2^nx^n=\sum_{n\ge 0}(2^n-1)x^n \]因此就有 \(a_n=2^n-1\)。
1.2.OGF的卷积
Lemma 4. \(\{a_n\}_{n\ge 0}\) 和 \(\{b_n\}_{n\ge 0}\) 为两个序列，让 \(A(x)\) 和 \(B(x)\) 分别为这两个序列的 \(\text{OGF}\)，定义 \(c_n=\sum_{i=0}^n a_ib_{n-i}\)，\(C(x)=\sum_{n\ge 0}c_nx^n\)，那么有
\[A(x)B(x)=C(x). \]换句话说，就是 \(A(x)B(x)\) 中 \(x^n\) 的系数 \(c_n\) 是 \(\sum_{i=0}^n a_ib_{n-i}\)。
Proof. 把 \(A(x),B(x)\) 分别展开成 \(a_0+a_1x+a_2x^2+...\) 和 \(b_0+b_1x+b_2x^2+...\)，考虑其中任意两项的乘积 \(a_ix^i\cdot b_jx^j\)，系数为 \(a_ib_j\)，能加在 \(x^n\) 的系数当且仅当 \(j=n-i\)，因此得证。
上面的引理的组合解释如下
Theorem 5. 令 \(a_n\) 为在大小为 \(n\) 的集合上组合成一个结构的方案数，\(b_n\) 为在大小为 \(n\) 的集合上组合成另一个结构的方案数，\(c_n\) 为把 \(1\) 到 \(n\) 组成的集合划分成 \(S=\{1,2,...,i\}\)，\(T=\{i+1,i+2,...,n\}\)，允许为空，在 \(S\) 上组合成第一种结构，在 \(T\) 上组成第二种结构的方案数。那么令 \(A(x),B(x),C(x)\) 为序列 \(a,b,c\) 的生成函数，那么有
\[A(x)B(x)=C(x). \]Proof. 有 \(a_i\) 种方案在 \(S\) 上组合成第一种结构，\(b_{n-i}\) 在 \(T\) 上组合成第二种结构，对任意 \(i\in[0,n]\) 都成立，所以 \(c_n=\sum_{i=0}^na_ib_{n-i}\)，因此得证。
Example 6. 一个学期有 \(n\) 天，有多少方案能把 \(n\) 天划分成两个部分，在第一部分选 \(1\) 天休息，在第二部分选 \(2\) 天休息。
令 \(f_n\) 为答案，容易发现 \(f_n=\sum_{k=1}^{n-2}k\binom {n-k} 2\)，这个又显然是一个卷积式。
构造 \(A(x)=\sum_{k\ge 0}kx^k,B(x)=\sum_{k\ge 0}\binom k 2 x^k\)。
那么有封闭形式
\[A(x)=\frac x{(1-x)^2},\notag\\ B(x)=\frac {x^2}{(1-x)^3}.\notag \]令 \(F(x)\) 为序列 \(f\) 的生成函数，所以
\[F(x)=A(x)B(x)=\frac{x^3}{(1-x)^5}=x^3\sum_{n\ge 0}\binom {n+4}4x^n=\sum_{n\ge 3}\binom {n+1} 4 x^n. \]所以 \(f_n=\binom {n+1} 4\)。
Example 7. 考虑把 \(n\) 天分成两个部分，每个部分任意选多少天休息，求方案数。
令 \(g_n\) 为答案，\(C(x)\) 为每一部分的生成函数，那么 \(C(x)=\sum_{k\ge 0}2^kx^k=\frac 1 {1-2x}\)。
因此有
\[F(x)=C(x)C(x)=\frac 1{(1-2x)^2}. \]暴力展开得到
\[F(x)=\frac 1 2\cdot \sum_{n\ge 1}n\cdot 2^nx^{n-1}=\sum_{n\ge 0}(n+1)2^nx^n. \]所以 \(g_n=(n+1)\cdot 2^n\)。
Example 8. 找到把 \(n\) 天分成三个部分，第一部分任选多少天休息，第二部分选奇数天休息，第三部分总天数为偶数的方案数。
令 \(g_n\) 为答案，\(A(x),B(x),C(x)\) 为三部分的生成函数。
那么有
\[A(x)=\sum_{n\ge 0}2^nx^n=\frac 1{1-2x}\notag\\ B(x)=\sum_{n\ge 1}2^{n-1}x^n=\frac x{1-2x}\notag\\ C(x)=1+\frac x{1-2x}=\frac {1-x}{1-2x}\notag \]令 \(G(x)\) 是 \(g\) 的生成函数，那么 \(G(x)=A(x)B(x)C(x)=\frac {x(1-3x)}{(1-2x)^3}\)。
把分子拆成两部分暴力算就可以了。
\((1-2x)^{-3}\) 可以尝试暴力展开算，也可以直接用二项式定理展开
\[(1-2x)^{-3}=\sum_{n\ge 0}\binom {-3} n(-2x)^n=\sum_{n\ge 0}\binom {n+2} 2 2^nx^n. \]第二个等号是因为 \(\binom r k=(-1)^k\binom {k-r-1} k\)。
所以
\[G(x)=\sum_{n\ge 0}\binom {n+2} 2 2^nx^{n+1}-3\sum_{n\ge 0}\binom {n+2} 2 2^nx^{n+2}. \]最后得出 \(g_n=2^{n-3}n(5-n)\)，对于 \(n\ge 0\)。
原书上的推理好像是错的（
Example 9. 令 \(p_{\le k}(n)\) 表示 \(n\) 分拆成最大为 \(k\) 的若干个数的方案数，那么有
\[\sum_{n\ge 0}p_{\le k}(n)x^n=\prod_{i=1}^k\frac 1 {1-x^i}\tag {11}\\ =(1+x+x^2+x^3+...)(1+x^3+x^4+x^6+...)...(1+x^k+x^{2k}+x^{3k}+...). \]拆开之后发现方案数正确是显然的。
然而这个式子同时还可以表示 \(n\) 分拆成最多 \(k\) 个数的方案数。
考虑归纳，枚举这 \(k\) 部分的最小值为 \(a\)，那么就在最后一个括号取 \(x^{ak}\)，然后 \(k\) 个数中等于最小值的没了，变成规模至少减一的子问题。
Example 10. 令 \(p(n)\) 表示 \(n\) 的所有分拆方案数，那么有
\[\sum_{n\ge 0}p(n)x^n=\prod_{k=1}^{\infin}\frac 1 {1-x^k}\tag {12} \]这个东西有时候很有用。
Example 11. 令 \(p_{\text{odd}}(n)\) 为把 \(n\) 拆分为奇数的方案数，\(p_{\text{d}}(n)\) 为把 \(n\) 拆分为互不相同的数，那么这两个数相等。
证明两个数相等只要证明生成函数相等即可。
拆分为奇数的方案数是
\[F(x)=\sum_{n\ge 0}p_{\text{odd}}(n)x^n=\prod_{i\ge 1,i \ odd}\frac 1 {1-x^i} \]拆分互不相同的方案数是
\[G(x)=\sum_{n\ge 0}p_{\text d}(n)x^n=\prod_{i\ge 1}(1+x^i)=\prod_{i\ge 1}\frac {1-x^{2i}}{1-x^i}. \]暴力展开，发现 \(G(x)\) 中所有 \(\frac 1 {1-x^i}\) 在 \(i\) 为奇数的时候系数为 \(1\)，\(i\) 为偶数的时候系数为 \(0\)，得证。
1.3.OGF的复合
复合生成函数 \(F(G(x))=\sum_{n\ge 0} f_nG(x)^n\)，由于形式幂级数求和只有在任意 \(x^n\) 的系数都只为有限个数求和时才有定义，所以需要满足 \(G(x)\) 的常数项为 \(0\)。
Definition 12. 令 \(F(x)=\sum_{n\ge 0}f_nx^n\) 为一个形式幂级数，\(G(x)\) 为一个常数项为 \(0\) 的形式幂级数，那么我们定义
\[F(G(x))=\sum_{n\ge 0}f_n(G(x))^n=f_0+f_1G(x)+f_2G(x)^2+... \]下一个定理是生成函数复合的主要应用
Theorem 13. 令 \(a_n\) 为在 \(n\) 元集合上构建一个结构的方案数，\(a_0=0\)，\(h_n\) 表示把 \(1\) 到 \(n\) 的集合分成若干不相交的线段，每个建造一个 \(a\) 结构的方案，令 \(A(x)=\sum_{n\ge 0}a_nx^n,H(x)=\sum_{n\ge 0}h_nx^n\)，有
\[H(x)=\frac 1 {1-A(x)}. \]不同于 Theorem 5，这里不允许有空的，同时钦定了 \(h_0=1\)。
Proof. 由于 \(A(x)^k\) 为把 \(n\) 个分成恰好 \(k\) 个算方案的生成函数，所以对 \(k\ge 1\) 的这个求和即可。
所以有
\[H(x)=1+\sum_{k\ge 1}A(x)^k=\sum_{k\ge 0}A(x)^k=\frac 1{1-A(x)}. \]Example 14. \(n\) 个士兵占成一列，划分成若干段，每一段选一个领导者，方案数为 \(h_n\)，求 \(h_n\)。
就是上面那个定理直接带就行了，\(A(x)=\sum_{k\ge 1}kx^k=\frac x{(1-x)^2}\)。
\[H(x)=\frac {1}{1-A(x)}=\frac {1}{1-\frac {x}{(1-x)^2}}=1+\frac x{1-3x+x^2} \]\(1-3x+x^2\) 因式分解不出来，但是是有两个不同的实数根的，解方程得到 \(\alpha =\frac {3+\sqrt 5} 2,\beta=\frac {3-\sqrt 5} 2\)。
所以设 \(A,B\)，有
\[\frac 1{1-3x+x^2}=\frac {1}{(x-\alpha)(x-\beta)}=\frac A{x-\alpha}-\frac {B}{x-\beta}. \]解方程得到 \(A=B=\frac 1 {\sqrt 5}\)。
代入，然后经过一些简单的化简，得到
\[\frac 1{1-3x+x^2}=\frac 1 {\sqrt 5}\bigg(\frac {\alpha}{1-\alpha x}-\frac {\beta}{1-\beta x}\bigg). \]因此 \(x^n\) 的系数即是 \(\frac 1{\sqrt 5}(\alpha^{n+1}-\beta^{b+1})\)。
所以 \(h_n=\frac 1{\sqrt 5}(\alpha ^{n+1}-\beta^{n+1}),n>0\)，\(n=0\) 时 \(h_0=1\)。
下一个定理系数和分出来的个数有关。
Theorem 15. 令 \(a_n\) 为在 \(n\) 元集合上构建一个结构的方案数，\(a_0=0\)，\(b_n\) 为在 \(n\) 元集合上构建第二种结构的方案数，\(b_0=1\)，\(g_n\) 表示把 \(1\) 到 \(n\) 的集合分成若干不相交的线段，每个建造一个 \(a\) 结构，然后再在所有线段上构造一个 \(b\) 结构的方案，\(g_0=1\)，令 \(A(x),B(x),G(x)\) 分别为 \(a,b,g\) 的生成函数，那么
\[G(x)=B(A(x)). \]Proof. 假设划分成了 \(k\) 条线段，那么有 \(b_k\) 的方案数构造 \(b\) 结构，\(a\) 的方案数是 \([x^n]A(x)^k\)，对 \(G(x)\) 的贡献就是 \(b_kA(x)^k\)，对所有 \(k\) 求和，就有 \(G(x)=\sum_{k\ge 0}b_kA(x)^k\)，因此得证。
Example 16. \(n\) 个士兵站成一列，分成若干段，然后从中选若干段晚上值班，问方案数。
每一段的方案数都是 \(1\)，所以 \(A(x)\) 就是 \(\frac 1{1-x}\)，\(b_k=2^k\)，所以 \(B(x)=\frac 1{1-2x}\)。
代入上一个定理，就可以得到
\[G(x)=B(A(x))=\frac 1{1-\frac {2x}{1-x}}=\frac {1-x}{1-3x}=\frac 1{1-3x}-\frac x{1-3x},\notag\\ G(x)=\sum_{n\ge 0}3^nx^n-\sum_{n\ge 1}3^{n-1}x^n=1+\sum_{n\ge 1}2\cdot3^{n-1}x^n. \]因此对于 \(n\ge 1\)，\(g_n=2\cdot 3^{n-1}\)。
2.EGF
2.1.递归式和EGF
有的时候 \(\text{OGF}\) 推不出封闭形式，可能需要 \(\text{EGF}\)。
Example 17. 令 \(a_0=1\)，\(a_{n+1}=(n+1)(a_n-n+1)\)，对于 \(a_n\) 求通项公式。
\(\text{OGF}\) 发现做不出来，在这里引出 \(\text{EGF}\)。
Definition 18. 令 \(\{f_n\}_{n\ge 0}\) 为一个实数序列，形式幂级数 \(F(x)=\sum_{n\ge 0}f_n\frac {x^n}{n!}\) 被称作序列 \(f\) 的指数生成函数。
叫这个名字的原因是 \(f_n=1\) 的序列的 \(\text{EGF}\) 是 \(e^x\)。
考虑上面那个问题，令 \(A(x)=\sum_{n\ge 0}a_n\frac {x^n}{n!}\) 为序列 \(a\) 的指数生成函数，然后对于式子两边乘上 \(\frac {x^{n+1}}{(n+1)!}\)，并对 \(n\ge 0\) 求和得到
\[\sum_{n\ge 0}a_{n+1}\frac {x^{n+1}}{(n+1)!}=\sum_{n\ge 0}a_n\frac {x^{n+1}}{n!}-\sum_{n\ge 0}(n-1)\frac{x^{n+1}}{n!}.\tag {13} \]写成生成函数
\[A(x)-1=xA(x)-x^2e^x+xe^x,\notag\\ A(x)=\frac {1}{1-x}+xe^x=\sum_{n\ge 0}x^n+\sum_{n\ge 0}\frac {x^{n+1}}{n!}. \]然后要先把这个还原成 \(\sum_{n\ge 0}a_n\frac {x^n}{n!}\) 的形式，把 \(a_n\) 作为系数。
最后可以得到 \(a_n=n!+n\)。
Example 19. 令 \(f_0=0\)，\(f_{n+1}=2(n+1)f_n+(n+1)!\)，对 \(n\ge 0\)。求 \(f_n\) 的通项公式。
令 \(F(x)=\sum_{n\ge 0}f_n\frac {x^n}{n!}\)，两边乘上 \(\frac {x^{n+1}}{(n+1)!}\)，然后对于 \(n\ge 0\) 求和得到
\[\sum_{n\ge 0}f_{n+1}\frac{x^{n+1}}{(n+1)!}=2x\sum_{n\ge 0}f_n\frac{x^n}{n!}+\sum_{n\ge 0}x^{n+1}.\tag {14} \]写成生成函数
\[F(x)=2xF(x)+\frac {x}{1-x},\notag\\ F(x)=\frac x{(1-x)(1-2x)},\notag\\ F(x)=\sum_{n\ge 0}(2^n-1)x^n. \]因此 \(f_n=(2^n-1)n!\)。
2.2.EGF的卷积
Lemma 20. 令 \(a,b\) 为两个序列，\(A(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!},B(x)=\sum_{n\ge 0}b_n\frac{x^n}{n!}\)，定义序列 \(c\) 满足 \(c_n=\sum_{i=0}^n\binom n ia_ib_{n-i}\)，令 \(C(x)\) 是序列 \(c\) 的指数生成函数，那么
\[A(x)B(x)=C(x) \]也就是 \(C(x)\) 中 \(\frac{x^n}{n!}\) 的系数 \(c_n\) 为 \(\sum_{i=0}^n\binom n i a_ib_{n-i}\)。
Proof. 只要考虑 \(A(x)\) 的每一项和 \(B(x)\) 的每一项对 \(C(x)\) 的贡献就行了。
\[a_i\frac {x^i}{i!}\cdot b_j\frac {x^j}{j!}=a_ib_j\frac{x^{i+j}}{i!j!}\cdot \frac{(i+j)!}{(i+j)!}=\frac{x^{i+j}}{(i+j)!}\cdot\binom{i+j}i. \]所以得证。
Theorem 21. 令 \(a_n\) 为在大小为 \(n\) 的集合上组合成一个结构的方案数，\(b_n\) 为在大小为 \(n\) 的集合上组合成另一个结构的方案数，\(c_n\) 为把 \(1\) 到 \(n\) 组成的集合划分成 \(S,T,S\cup T=[n],S\cap T=\empty\)，允许为空，在 \(S\) 上组合成第一种结构，在 \(T\) 上组成第二种结构的方案数。那么令 \(A(x),B(x),C(x)\) 为序列 \(a,b,c\) 的指数生成函数，那么有
\[A(x)B(x)=C(x). \]Proof. 如果 \(S\) 有 \(i\) 个元素，那么选择的方案数是 \(\binom n i\)，而卷积的系数相比于 \(\text{OGF}\) 恰好也只多一个 \(\binom n i\)，所以把 \(\text{OGF}\) 的证明拿过来就好了。
Example 22. 有 \(n\) 个球员，教练要分成一队和二队，随便分，一队的每个人有三种球衣可以选，二队的只有一种，然后每一队还得给每个人的球衣编号从 \(1\) 到 \(sz\)，问方案数。
把两队的 \(\text{EGF}\) 分别求出来卷积即可，因为选 \(k\) 个人的方案数是组合数。
令 \(a,b\) 为两个队伍的方案数序列，那么 \(a_k=k!3^k,b_k=k!\)。
写成生成函数 \(A(x),B(x)\)
\[A(x)=\sum_{k\ge 0}k!3^k\frac{x^k}{k!}=\frac 1{1-3x}.\notag\\ B(x)=\sum_{k\ge 0}k!\frac{x^k}{k!}=\frac 1{1-x}. \]卷积得到
\[C(x)=A(x)B(x)=\frac 1{1-3x}\cdot \frac 1{1-x}. \]可以得到在 \(\frac{x^n}{n!}\) 前的系数 \(c_n=\frac{n!(3^{n+1}-1)}2\)。
\(\text{EGF}\) 还有一个好处就是求导非常方便。
\[\bigg(\frac{x^{n+1}}{(n+1)!}\bigg)'=\frac{x^n}{n!},\notag\\ \bigg(\sum_{n\ge 0}a_n\frac{x^n}{n!}\bigg)'=\sum_{n\ge 0}a_{n+1}\frac {x^n}{n!}. \]实际上是实现了一个系数的左移。
Example 23. 令 \(B(x)\) 为贝尔数 \(B_n\) 的指数生成函数，证明 \(B(x)=e^{e^x-1}\)。
贝尔数的转移式是 \(B_{n+1}=\sum_{i=0}^n \binom n iB_i,n\ge 0\)，\(B_0=1\)，等式两边乘上 \(\frac {x^n}{n!}\)，并对 \(n\ge 0\) 求和
\[\sum_{n\ge 0}B_{n+1}\frac{x^n}{n!}=\sum_{n\ge 0}\sum_{i=0}^n \binom n i B_i\frac{x^n}{n!} \]可以视作 \(B(x)\) 和 \(e^x\) 卷积得到了 \(B'(x)\)。
\[B'(x)=B(x)e^x,\notag\\ \frac{B'(x)}{B(x)}=e^x,\notag \]两边取积分
\[\ln B(x)=e^x+c. \]令 \(x=0\)，所以必须选 \(c=-1\)，因此 \(\ln B(x)=e^x-1,B(x)=e^{e^x-1}\)。
2.3.EGF的复合
\(\text{EGF}\) 的复合其实和 \(\text{OGF}\) 的复合几乎一样，只是从选线段变成了选集合，多了个组合数系数，推导过程也及其类似。
Theorem 24. 令 \(a_n\) 为在 \(n\) 元集合上构建一个结构的方案数，\(a_0=0\)，\(h_n\) 表示把 \(1\) 到 \(n\) 的集合分成若干不相交的集合，每个建造一个 \(a\) 结构的方案，令 \(A(x)=\sum_{n\ge 0}a_nx^n,H(x)=\sum_{n\ge 0}h_nx^n\)，有
\[H(x)=e^{A(x)}. \]Proof. 枚举划分成 \(k\) 个集合，由于任何方案中，都能把选的集合任意交换，会重复 \(k!\) 次，所以
\[H(x)=1+\sum_{k\ge 1}\frac{A(x)^k}{k!}=\sum_{k\ge 0}\frac {A(x)^k}{k!}=e^{A(x)}. \]Example 25. 有多少种不同的方案能把 \(n\) 个人划分成若干组，每个组随便排顺序坐在一个圆桌上。
\(k\) 个人排顺序的方案数是 \((k-1)!\)，所以 \(a_k=(k-1)!\)，求 \(A(x)\) 就是
\[A(x)=\sum_{k\ge 1}(k-1)!\cdot\frac{x^k}{k!}=\sum_{k\ge 1}\frac{x^k}{k}=\ln\bigg(\frac 1{1-x}\bigg). \]后面那个等式是泰勒展开得到的。
代入上面的定理就是
\[H(x)=e^{\big(\ln\frac {1}{1-x}\big)}=\frac 1 {1-x}=\sum_{n\ge 0}x^n=\sum_{n\ge 0}n!\cdot \frac{x^n}{n!}. \]也就是 \(h_n=n!\)，这个式子归纳验证显然是对的。
Example 26. \(f_n\) 表示把 \(1\) 到 \(n\) 的集合分成若干大小为 \(3,4,9\) 的不相交子集的方案数，求 \(f\) 的 \(\text{EGF }F(x)\)。
令 \(a_n,b_n,c_n\) 分别表示只用 \(3,4,9\) 划分 \(1\) 到 \(n\) 的集合的方案数，\(A(x),B(x),C(x)\) 为对应的指数生成函数。
那么显然最后的 \(F(x)=A(x)B(x)C(x)\)。
\(A(x),B(x),C(x)\) 的计算方法是一样的，这里只算 \(A(x)\)。
直接代入 Theorem 24，令 \(T(x)\) 表示一个集合形成一个大小为 \(3\) 的集合的方案数的指数生成函数。
那么有 \(T(x)=\frac {x^3}{3!}\)，因为只有 \(n=3\) 的时候方案数为 \(1\)，其他都是 \(0\)。
\[A(x)=e^{T(x)}=e^{\frac {x^3} {3!}}. \]另外两个也类似，最后
\[F(x)=A(x)B(x)C(x)=e^{\frac{x^3}{3!}+\frac{x^4}{4!}+\frac{x^9}{9!}} \]Theorem 27. 令 \(a_n\) 为在 \(n\) 元集合上构建一个结构的方案数，\(a_0=0\)，\(b_n\) 为在 \(n\) 元集合上构建第二种结构的方案数，\(b_0=1\)，\(g_n\) 表示把 \(1\) 到 \(n\) 的集合分成若干不相交的子集，每个建造一个 \(a\) 结构，然后再在所有线段上构造一个 \(b\) 结构的方案，\(g_0=1\)，令 \(A(x),B(x),G(x)\) 分别为 \(a,b,g\) 的指数生成函数，那么
\[G(x)=B(A(x)). \]Proof. 和上一个版本的区别只在于要乘上一个 \(b_k\) 的系数，所以式子是
\[G(x)=1+\sum_{k\ge 1}b_k\frac {A(x)^k}{k!}=B(A(x)). \]Example 28. 有 \(n\) 张不同的卡片，分成若干个非空集合使得每个集合大小都是偶数，先给每个集合内部定一个顺序，再给这些集合定一个顺序。
\(a_n\) 表示把 \(n\) 个数作为一个大小为偶数的集合的方案数，那么 \(n\) 为偶数时 \(a_n=n!\)，否则 \(a_n=0\)。
\(b_n\) 表示给 \(n\) 个集合定顺序的方案数，显然 \(b_n=n!\) 在任何 \(n\) 上成立。
令 \(A(x),B(x)\) 分别为它们的指数生成函数，就有
\[A(x)=\sum_{n\ge 0}a_n\frac{x^n}{n!}=\sum_{n\ge 2,n \ even}n!\frac{x^n}{n!}=\frac{x^2}{1-x^2},\notag\\ B(x)=\sum_{n\ge 0}b_n\frac{x^n}{n!}=\sum_{n\ge 0}x^n=\frac 1 {1-x}.\notag \]令方案数为 \(g_n\)，对应的指数生成函数为 \(G(x)\)，代入定理就有
\[\begin{align} G(x)&=B(A(x))=\frac{1}{1-\frac{x^2}{1-x^2}}=\frac{1-x^2}{1-2x^2}\notag\\ &=1+\frac{x^2}{1-2x^2}+1+x^2\sum_{n\ge 0}(2x^2)^n=1+\sum_{n\ge 0}2^nx^{2n+2}.\notag \end{align} \]所以当 \(n\) 为奇数的时候 \(g_n=0\)，\(n\) 为偶数时令 \(n=2k\)，\(g_n=2^{k-1}(2k)!\)。
因此对于偶数 \(n\)，\(g_n=2^{\frac n 2}\cdot n!\)。
完结撒花！
标签：方案,frac,函数,sum,2x,生成,nx,ge From： https://www.cnblogs.com/hellojim/p/17032554.html