生成函数从入门到进门
QcpyWcpyQ
·
·
个人记录
引入
先看下面这个例子：
(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_1a_2+a_1a_3+\cdots+a_{n-1}a_n=\dbinom{n}{2}
所以：
(1+x)^n=1+\dbinom{n}{1}x+\dbinom{n}{2}x^2+\cdots+\dbinom{n}{n}x^n
2^n=1+\dbinom{n}{1}+\dbinom{n}{2}+\cdots+\dbinom{n}{n}
以上运用为生成函数证二项式定理。
定义 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^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)，则该组合数序列的生成函数为：
\prod\limits_{i=1}^{n}(\sum\limits_{m\in M_i}x^m)
试试看！1
有重量为 1\mathrm g,3\mathrm g, 5\mathrm g 重的砝码各两个，问可以称出多少种不同质量的物品。
- 根据定理 1，可构造生成函数：
G(x)=(1+x+x^2)(1+x^3+x^6)(1+x^5+x^{10})
其展开后一共有 19 项，所以答案为 19。
\dfrac{1}{1-x}=1+x+x^2+x^3+\cdots
\dfrac{1}{(1-x)^2}=1+2x+3x^2+4x^3+\cdots
\dfrac{1}{(1-x)^n}=\sum\limits_{i=0}^{\infty}\dbinom{n+i-1}{i}x^i
\dfrac{1}{1-2x}=1+2x+2x^2+2x^3+\cdots
具体可以 \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)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]$ 可得：
$$\begin{aligned}A(x)&=\dfrac{-71x+8}{(1-8x)(1-10x)}\\&=\dfrac{1}{2}\left(\dfrac{7}{1-8x}+\dfrac{9}{1-10x}\right)\\&=\dfrac{1}{2}\left(\sum\limits_{n=0}^{\infty}7\times(8x)^n+\sum\limits_{n=0}^{\infty}9\times(10x)^n\right)\end{aligned}$$
所以 $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)$，则该组合数序列的生成函数为：
$$\prod\limits_{i=1}^{n}(\sum\limits_{m\in M_i}\dfrac{x^m}{x!})$$
指数型生成函数的标志函数为 $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$，可构造生成函数：
$$\begin{aligned}G(x)&=\left(\dfrac{x^2}{
2!}+\dfrac{x^3}{3!}\right)\times\left(1+\dfrac{x}{1!}\right)\times\left(1+x+\cdots+\dfrac{x^n}{n!}+\cdots\right)\times\left(1+\dfrac{x^2}{2!}+\cdots+\dfrac{x^{2n}}{2n!}+\cdots\right)\\&=\dfrac{1}{2}\times\left(\dfrac{1}{6}\times x^2\times\left(3+4x+x^2\right)\right)\times e^x\times\left(e^x+e^{-x}\right)\\&=\dfrac{1}{12}\times\left(x^2\times\left(3+4x+x^2\right)\times\left(e^{2x}+1\right)\right)\end{aligned}$$
所以满足条件的五位数共有：$\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
[luogu P2000](https://www.luogu.com.cn/problem/P2000)
裸题，最终将十个生成函数乘起来推的式子是 $\binom{n+4}{4}$，用多项式乘法计算即可。
------------
### 试试看！6
[HDU-2065](https://vjudge.net/problem/HDU-2065)
裸题。只能出现偶数次的生成函数为 $\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
[POJ-1322](https://vjudge.net/problem/POJ-1322)
根据题意，只有当 $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
[luogu P4451](https://www.luogu.com.cn/problem/P4451)
我们有斐波那契数列的生成函数：
$$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}$$
直接计算即可。