引入
先看下面这个例子：
\[(1+a_1x)\times(1+a_2x)\times\cdots\times(1+a_nx) \]拆括号得：
\[1+(a_1+a_2+\cdots+a_n)x+(a_1a_2+a_1a_3+\cdots+a_{n-1}a_n)x^2+\cdots+(a_1a_2\cdots a_n)x^n \]其中 \(x^2\) 的系数包含了从 \(n\) 个元素 \(\{a_1,a_2,\cdots,a_n\}\) 中选取两个的组合的全体。
- 令 \(a_i=1\) 我们有：
所以：
\[(1+x)^n=1+\dbinom{n}{1}x+\dbinom{n}{2}x^2+\cdots+\dbinom{n}{n}x^n \]- 令 \(x=1\)，则：
以上运用为生成函数证二项式定理。
定义 1
- 对于序列 \(a_0,a_1,a_2,\cdots\)，定义 \(G(x)=a_0+a_1x+a_2x^2+\cdots\) 为其生成函数。
如 \((1+x)^n\) 就是序列 \(\dbinom{n}{0},\dbinom{n}{1},\dbinom{n}{2},\cdots,\dbinom{n}{n}\) 的生成函数。
普通型生成函数
- 将 \((1+x)\) 的意义和选择物品联系起来。
分析生成函数时，一般将 \(1\) 看作 \(x^0\)，因为它可以表示什么都没选。
那么 \(x^1\) 表示选择了一件物品。\((x^0+x^1)^n\) 可对应于从 \(n\) 件物品中选取若干见物品的情况。其中，若选择了第 \(i\) 件，相当于从第 \(i\) 个括号中提出了 \(x^1\)，反之则提出 \(x^0\)。
对于每件物品而言，选与不选两个事件是相互独立的，所以根据加法原理得到 \((x^0+x^1)=(1+x)\)。而 \(n\) 个物品的选择是独立的，根据乘法原理有 \((1+x)^n\)。
- 由此，在 \((1+x)^n\) 的展开式中，\(x^i\) 的系数就是从 \(n\) 件物品中选取 \(n\) 件物品的所有情况的总数。
定义 2
- 给定序列 \(a_0,a_1,\cdots,a_n,\cdots\)，构造一个函数 \(F(x)=a_0f_0(x)+a_1f_1(x)+\cdots+a_nf_n(x)+\cdots\)，称 \(F(x)\) 为其生成函数，其中序列 \(f_0(x),f_1(x),\cdots,f_n(x),\cdots\) 只作为标志用，成为标志函数。
标志函数最重要的形式就是 \(x^n\)。这种情况下的生成函数一般形式为：
\[F(x)=a_0+a_1x+\cdots+a_nx^n+\cdots \]定理 1
- 设 \(n\) 元集合 \(S=\{a_1,a_2,\cdots,a_n\}\) 中取 \(k\) 个元素的组合是 \(b_k\)，若限定元素 \(a_i\) 出现的次数及何为 \(M_i\ (1\leq i\leq n)\)，则该组合数序列的生成函数为：
试试看！1
有重量为 \(1\mathrm g,3\mathrm g, 5\mathrm g\) 重的砝码各两个，问可以称出多少种不同质量的物品。
- 根据定理 \(1\)，可构造生成函数：
其展开后一共有 \(19\) 项，所以答案为 \(19\)。
- 以下为几个常见的生成函数：
具体可以 \(\mathrm{Taylor}\) 展开或等比方法证明，懒得写。
试试看！2
求 \(n\) 位十进制中出现偶数个 \(5\) 的数的个数。
- 令 \(d=\overline{d_1d_2d_3\cdots d_{n-1}}\)。若 \(d\) 包含偶数个 \(5\)，则 \(d_n\not=5\)，否则 \(d_n=5\)。
令 \(a_n\) 为 \(n\) 位十进制数中出现偶数个 \(5\) 的个数，\(b_n\) 为 \(n\) 位十进制数中出现奇数个 \(5\) 的个数。那么有：
\[\begin{cases}a_n=9a_{n-1}+b_{n-1}\\b_n=9b_{n-1}+a_{n-1}\end{cases} \]其中 \(a_1=8,b_1=1\)。
设 \(\{a\},\{b\}\) 的生成函数分别为：
\[\begin{aligned}A(x)&=a_1+a_2x+\cdots+a_nx^{n-1}+\cdots&[1]\\B(x)&=b_1+b_2x+\cdots+b_nx^{n-1}+\cdots&[2]\end{aligned} \]\((1-9x)\times[1]+(-x)\times[2]\) 得：
\[(1-9x)A(x)-xB(x)=a_1=8\quad[3] \]\((1-9x)\times[2]+(-x)\times[1]\) 得：
\[(1-9x)B(x)-xA(x)=b_1=1\quad[4] \]- 由 \([3][4]\) 可得：
所以 \(a_n=\dfrac{1}{2}(7\times8^{n-1}+9\times10^{n-1})\)。
指数型生成函数（EGF）
指数型生成函数由如下定理描述：
定理 2
- 从多重集合 \(M=\{\infty\times a_1,\infty\times a_2,\infty\times a_3,\cdots,\infty\times a_n\}\) 中选取 \(k\) 个元素的排列中，若限定元素 \(a_i\) 出现的次数集合为 \(M_i\ (1\leq i\leq n)\)，则该组合数序列的生成函数为：
指数型生成函数的标志函数为 \(1,\dfrac{x}{1!},\dfrac{x^2}{2!}\cdots\)。
另外在指数型生成函数的使用过程中，一般都会用到 \(e^x\) 的 \(\mathrm{Taylor}\) 展开式：
\[e^x=\sum\limits_{n=0}^{\infty}\dfrac{x^n}{n!}=1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots+\dfrac{x^n}{n!}+\cdots \]\[\dfrac{e^x+e^{-x}}{2}=\sum\limits_{n=0}^{\infty}\dfrac{x^{2n}}{2n!}=1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots+\dfrac{x^{2n}}{2n!}+\cdots \]\[\dfrac{e^x-e^{-x}}{2}=\sum\limits_{n=0}^{\infty}\dfrac{x^{2n+1}}{(2n+1)!}=x+\dfrac{x^3}{3!}+\dfrac{x^5}{5!}+\cdots+\dfrac{x^{2n+1}}{(2n+1)!}+\cdots \]试试看！3
由 \(1,2,3,4\) 四个数字能组成多少个五位数，要求这些五位数中 \(1\) 出现两次或三次，\(2\) 最多出现一次，\(4\) 出现偶数次。
- 根据定理 \(2\)，可构造生成函数：
所以满足条件的五位数共有：\(\frac{1}{12}\times 5!\times\left(3\times\frac{2^3}{3!}+4\times\frac{2^2}{2!}+1\times\frac{2^1}{1!}\right)=140\) 个。
试试看！4
求 \(1,3,5,7,9\) 这五个数字组成的 \(n\) 位数个数，要求其中 \(3\) 和 \(7\) 出现的次数为偶数，其他数字出现的次数无限制。
设满足条件的 \(r\) 位数的数目为 \(a_r\)，则序列 \(a_0,a_1,a_2,\cdots\) 的生成函数为：
\[\begin{aligned}G_r(x)&=\left(1+\dfrac{x^2}{2!}+\dfrac{x^4}{4!}+\cdots\right)^2\times\left(1+x+\dfrac{x^2}{2!}+\dfrac{x^3}{3!}+\cdots\right)^3\\&=\dfrac{1}{4}\left(e^x+e^{-x}\right)^2\times e^{3x}\\&=\dfrac{1}{4}\left(e^{5x}+2e^{3x}+e^x\right)\\&=\dfrac{1}{4}\sum\limits_{n=0}^{\infty}\left(5^n+2\times 3^n+1\right)\times\dfrac{x^n}{n!}\end{aligned} \]所以 \(a_n=\frac{1}{4}\left(5^n+2\times 3^n+1\right)\)。
例题
试试看！5
裸题，最终将十个生成函数乘起来推的式子是 \(\binom{n+4}{4}\)，用多项式乘法计算即可。
试试看！6
裸题。只能出现偶数次的生成函数为 \(\frac{e^x+e^{-x}}{2}\)，任意次的为 \(e^x\)，乘起来：
\[\left(\frac{e^x+e^{-x}}{2}\right)^2\left(e^x\right)^2=\dfrac{e^{4x}+2e^{2x}+1}{4} \]然后计算第 \(n\) 项的系数，为：
\[\frac{4^n+2\times 2^n}{4}=4^{n-1}+2^{n-1} \]快速幂即可。
试试看！7
根据题意，只有当 $m\leq n,c $ 且 \(n-m\) 为偶数时才有解，下面我们只考虑有解的情况。
首先我们可以根据题意将根据奇偶巧克力分成两类，其中奇数个的有 \(m\) 种颜色，那么我们可以选择其中一种分类的方式，将其写成生成函数的形式，即：
\[F_1^m(x)\times F_2^{c-m}(x)=\left(\frac{e^x-e^{-x}}{2}\right)^m\times\left(\frac{e^x+e^{-x}}{2}\right)^{c-m} \]其中 \(F_1\) 为次数是奇数的生成函数，\(F_2\) 为偶数的。
将 \(e^x\) 看成是一个整体，然后两边分别二项式展开之后做卷积，然后再将 \(e^x\) 展开可得到第 \(n\) 项系数：
\[\begin{aligned}G\left(x\right)&=2^{-c}\times \sum_{i=0}^{m}\left(-1\right)^i{m\choose i}\times e^{\left(m-2i\right)x}\times \sum_{j=0}^{c-m}{c-m\choose j}\times e^{\left(2j-c+m\right)x}\\&=2^{-c}\times \sum_{i=0}^{m}\sum_{j=0}^{c-m}\left(-1\right)^i{m\choose i}{c-m\choose j}\times e^{\left(2m-2i+2j-c\right)x}\\&=2^{-c}\times \sum_{i=0}^{m}\sum_{j=0}^{c-m}\left(-1\right)^i{m\choose i}{c-m\choose j}\times \sum_{k=0}^{\infty}\frac{\left(\left(2m-2i+2j-c\right)x\right)^k}{k!} \end{aligned}\]设第 \(n\) 项的系数为 \(a_n\)，最后的答案为：
\[\dfrac{a_n\times\dbinom{c}{m}\times n!}{2^c\times c^n} \]试试看！8
- 斐波那契通项公式（二阶线性递推）。
我们把斐波那契数列拓展到下标为全体整数，定义：
\[f_n=\begin{cases}0&(n\leq0)\\f_{n-1}+f_{n-2}+\left[n=1\right]&(n>0)\end{cases} \]两边同时乘以 \(x^n\) 得：
\[f_nx^n=f_{n-1}x^n+f_{n-2}x^n+\left[n=1\right]x^n \]这个等式对全体整数 \(n\) 成立，全体累加得：
\[\sum\limits_n f_nx^n=a\sum\limits_nf_{n-1}x^{n-1}+x^2\sum\limits_nf_{n-2}x^{n-2}+x \]将生成函数的定义代入得：
\[F(x)=xF(x)+x^2F(x)+x \]所以解得封闭表达式：
\[F(x)=\dfrac{x}{1-x-x^2} \]裂项得：
\[F(x)=\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\frac{1+\sqrt{5}}{2}x}-\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\frac{1-\sqrt{5}}{2}x} \]即 \(F\) 是两个生成函数的和，这两个生成函数都是等比级数。因此可以写出：
\[[x^n]F(x)=[x^n]\left(\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\frac{1+\sqrt{5}}{2}x}\right)-[x^n]\left(\dfrac{1}{\sqrt{5}}\cdot\dfrac{1}{1-\frac{1-\sqrt{5}}{2}x}\right) \]因此：
\[f_n=\dfrac{1}{\sqrt{5}}\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\dfrac{1}{\sqrt{5}}\left(\dfrac{1-\sqrt{5}}{2}\right)^n \]试试看！9
- 扇形图的生成树（\(n\) 阶线性递推）。
容易写出递推式：
\[f_n=f_{n-1}+\sum\limits_{k=1}^{n-1}f_k+1\left[n\geq1\right] \]用生成函数，得到：
\[\sum\limits_{n}f_nx^n=x\sum\limits_{n}f_{n-1}x^{n-1}+\sum\limits_{n}\left(\sum\limits_{k=1}^{n-1} f_k\right)x^n+\sum\limits_{n \geq 1}x^n \]其中有：
\[\sum\limits_{n}\left(\sum\limits_{k=1}^{n-1} f_k\right)x^n=\sum\limits_{k \geq 1}f_k\left(\sum\limits_{n \geq k+1}x^n\right)=\sum\limits_{k \geq 1}f_kx^k\left(\sum\limits_{n \geq k+1}x^{n-k}\right)=\sum\limits_{k \geq 1}f_kx^k \cdot \dfrac{x}{1-x} \]将生成函数带入：
\[F(x)=xF(x)+F(x)\dfrac{x}{1-x}+\dfrac{x}{1-x} \]所以解得封闭表达式：
\[F(x)=\dfrac{x}{1-3x+x^2} \]同样裂项就可以求出 \(f_n\) 的通项是等比加等比的结构。
试试看！10
我们有斐波那契数列的生成函数：
\[F(x)=\dfrac{x}{1-x-x^2} \]我们知道拆分为恰好 \(k\) 个数时，答案的生成函数为 \(F^k(x)\)，那么答案的生成函数显然为：
\[\begin{aligned}G(x)&=\sum\limits_{i=0}^\infty F^i(x)\\&=\frac{1}{1-F(x)}\\&=\frac{1-x-x^2}{1-2x-x^2}\end{aligned} \]分母写成递推式就是：
\[a_n=2a_{n-1}+a_{n-2} \]乘上分子得到答案：
\[\text{ans}=a_n-a_{n-1}-a_{n-2}=a_{n-1} \]解递推式特征方程，得：
\[x_1=-\sqrt 2+1,x_2=\sqrt 2+1 \]设通项公式为：
\[a_n=c_1(-\sqrt 2+1)^n+c_2(\sqrt 2+1)^n \]分别代入 \(n=0,n=1\)，解得
\[\left\{\begin{aligned}c_1=\frac{\sqrt 2-1}{2\sqrt 2} \\ c_2=\frac{\sqrt 2+1}{2\sqrt 2} \end{aligned}\right. \]注意到 \(\sqrt 2\) 在模 \(10^9+7\) 下存在二次剩余（\(59713600\)），最终答案就出来了：
\[a_n\equiv 485071604\times 940286408^n+514928404\times59713601^n\pmod{10^9+7} \]直接计算即可。
标签：right,入门,dfrac,sum,times,cdots,left,进门,函数 From： https://www.cnblogs.com/QcpyWcpyQ/p/18016998