这是本文档旧的修订版！
生成函数理论 5
基本应用
例 1
依照题意可列出 10 个条件的生成函数 $f_i(x)$，将它们相乘再化简即可。
- $f_1(x)=(1+x^6+x^{12}+\cdots)=\frac{1}{1-x^6}$
- $f_2(x)=(1+x+x^2+\cdots+x^9)=\frac{1-x^{10}}{1-x}$
- $f_3(x)=(1+x+x^2+\cdots+x^5)=\frac{1-x^6}{1-x}$
- $f_4(x)=(1+x^4+x^8+\cdots)=\frac{1}{1-x^4}$
- $f_5(x)=(1+x+x^2+\cdots+x^7)=\frac{1-x^8}{1-x}$
- $f_6(x)=(1+x^2+x^4+\cdots)=\frac{1}{1-x^2}$
- $f_7(x)=(1+x)=\frac{1-x^2}{1-x}$
- $f_8(x)=(1+x^8+x^{16}+\cdots)=\frac{1}{1-x^8}$
- $f_9(x)=(1+x^{10}+x^{20}+\cdots)=\frac{1}{1-x^{10}}$
- $f_{10}(x)=(1+x+x^2+x^3)=\frac{1-x^4}{1-x}$
$\displaystyle f(x)=\prod_{i=1}^{10}f_i(x)=\frac{1}{(1-x)^5}=\sum_{n=0}^{\infty}\binom{n+4}{n}x^n$
$\displaystyle ans_n=\binom{n+4}{4}=\frac{(n+4)(n+3)(n+2)(n+1)}{24}$
由于 $10^{100000}\le n<10^{100001}$，需要用高精度，正解是用 NTT，用 Python 会 TLE，但是竟然可以用 Ruby AC。
Ruby 代码：
C++ 代码：
例 2 （Bell 数）
令 $B_n$ 表示 $[n]$ （$n$ 元集合）所有划分的个数，试找到计算 $B_n$ 的公式。
讨论 $[n]$ 的划分中包含元素 $n$ 的那个子集，设其含有 $k$ （$1\le k\le n$）个元素，则剩余的 $k-1$ 个元素是从 $[n-1]$ 中选取的。而剩余的那些子集为 $n-k$ 个元素的一个划分，所以 $$ B_n=\sum_{k=1}^{n}\binom{n-1}{k-1}B_{n-k},~~~~n\ge 1. $$ 初始值为 $B_0=1,B_1=1$。令 $\displaystyle B(x)=\sum_{n\ge 0}\frac{B_n}{n!}x^n$，两边求导数，得到 $$ \begin{align} \frac{dB(x)}{dx}&=\sum_{n=1}^{\infty}\frac{B_n}{(n-1)!}x^{n-1}\\ &=\sum_{n=1}^{\infty}\frac{1}{(n-1)!}\left(\sum_{k=1}^{n}\binom{n-1}{k-1}B_{n-k}\right)x^{n-1}\\ &=\sum_{n=1}^{\infty}\sum_{k=1}^{n}\frac{x^{k-1}}{(k-1)!}\frac{B_{n-k}x^{n-k}}{(n-k)!}\\ &=\sum_{k=1}^{\infty}\frac{x^{k-1}}{(k-1)!}\sum_{n\ge k}\frac{B_{n-k}x^{n-k}}{(n-k)!}\\ &=\sum_{k=1}^{\infty}\frac{x^{k-1}}{(k-1)!}\sum_{i\ge 0}\frac{B_ix^i}{i!}~~(i=n-k)\\ &=e^xB(x). \end{align} $$ 解微分方程 $\displaystyle \frac{dB(x)}{dx}=e^xB(x)$，可得 $$ B(x)=Ce^{e^x}, $$ 其中 $C$ 为待定常数。由初始条件 $B(0)=1$ 得到 $C=e^{-1}$，即 $$ B(x)=e^{e^x-1}, $$ 从而 $$ \begin{align} B(x)&=\frac{1}{e}\sum_{k=0}^{\infty}\frac{(e^x)^k}{k!}=\frac{1}{e}\sum_{k=0}^{\infty}\frac{1}{k!}\sum_{n=0}^{\infty}\frac{k^nx^n}{n!}\\ &=\frac{1}{e}\sum_{n=0}^{\infty}\left(\sum_{k=0}^{\infty}\frac{k^n}{k!}\right)\frac{x^n}{n!}. \end{align} $$ 因此 $$ B_n=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^n}{k!}. $$
