普通生成函数 序列 a
a a 0
序列 a=\langle 1,2,3\rangle 1+2x+3x^2 序列 a=\langle 1,1,1,\cdots\rangle \sum_{n\ge 0}x^n 序列 a=\langle 1,2,4,8,16,\cdots\rangle \sum_{n\ge 0}2^nx^n 序列 a=\langle 1,3,5,7,9,\cdots\rangle \sum_{n\ge 0}(2n+1)x^n 换句话说，如果序列 a
基本运算 考虑两个序列 a,b F(x),G(x)
F(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n 因此 F(x)\pm G(x) \langle a_n\pm b_n\rangle
考虑乘法运算，也就是卷积：
F(x)G(x)=\sum_n x^n \sum_{i=0}^na_ib_{n-i} 因此 F(x)G(x) \langle \sum_{i=0}^n a_ib_{n-i} \rangle
封闭形式 在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简。
例如 \langle 1,1,1,\cdots\rangle F(x)=\sum_{n\ge 0}x^n
那么解这个方程得到
这就是 \sum_{n\ge 0}x^n
考虑等比数列 \langle 1,p,p^2,p^3,p^4,\cdots\rangle F(x)=\sum_{n\ge 0}p^nx^n
\begin{aligned}F(x)px+1 &=F(x)\\F(x) &=\frac{1}{1-px}\end{aligned} 等比数列的封闭形式与展开形式是常用的变换手段。
小练习 请求出下列数列的普通生成函数（形式幂级数形式和封闭形式）。难度的循序渐进的。
a=\langle 0,1,1,1,1,\cdots\rangle a=\langle 1,0,1,0,1,\cdots \rangle a=\langle 1,2,3,4,\cdots \rangle a_n=\binom{m}{n} m n\ge 0 a_n=\binom{m+n}{n} m n\ge 0 答案 第一个：
F(x)=\sum_{n\ge 1}x^n=\dfrac{x}{1-x} 第二个：
\begin{aligned} F(x)&=\sum_{n\ge 0}x^{2n}\\ &=\sum_{n\ge 0}(x^2)^{n}\\ &=\frac{1}{1-x^2} \end{aligned} 第三个（求导）：
\begin{aligned}F(x)&=\sum_{n\ge 0}(n+1)x^n\\&=\sum_{n\ge 1}nx^{n-1}\\&=\sum_{n\ge 0}(x^n)'\\&=\left(\frac{1}{1-x}\right)'\\&=\frac{1}{(1-x)^2}\end{aligned} 第四个（二项式定理）：
F(x)=\sum_{n\ge 0}\binom{m}{n}x^n=(1+x)^m 第五个：
F(x)=\sum_{n\ge 0}\binom{m+n}{n}x^n=\frac{1}{(1-x)^{m+1}} 可以使用归纳法证明。
首先当 m=0 F(x)=\dfrac{1}{1-x}
而当 m>0
\begin{aligned} \frac{1}{(1-x)^{m+1}} &=\frac{1}{(1-x)^m}\frac{1}{1-x}\\ &=\left(\sum_{n\ge 0}\binom{m+n-1}{n}x^n \right)\left(\sum_{n\ge 0}x^n \right)\\ &=\sum_{n\ge 0} x^n\sum_{i=0}^n \binom{m+i-1}{i}\\ &=\sum_{n\ge 0}\binom{m+n}{n}x^n \end{aligned} 斐波那契数列的生成函数 接下来我们来推导斐波那契数列的生成函数。
斐波那契数列定义为 a_0=0,a_1=1,a_n=a_{n-1}+a_{n-2}\;(n>1) F(x) F(x)
F(x)=xF(x)+x^2F(x)-a_0x+a_1x+a_0 那么解得
那么接下来的问题是，如何求出它的展开形式？
展开方式一 不妨将 x+x^2
\begin{aligned} F(x)&=\frac{x}{1-(x+x^2)}\\ &=\sum_{n\ge 0}(x+x^2)^n\\ &=\sum_{n\ge 0}\sum_{i=0}^n\binom{n}{i}x^{2i}x^{n-i}\\ &=\sum_{n\ge 0}\sum_{i=0}^n\binom{n}{i}x^{n+i}\\ &=\sum_{n\ge 0}x^n\sum_{i=0}^n\binom{n-i}{i} \end{aligned} 我们得到了 a_n
展开方式二 考虑求解一个待定系数的方程：
\frac{A}{1-ax}+\frac{B}{1-bx}= \frac{x}{1-x-x^2} 通分得到
\frac{A-Abx+B-aBx}{(1-ax)(1-bx)} = \frac{x}{1-x-x^2} 待定项系数相等，我们得到
\begin{cases} A+B=0\\ -Ab-aB=1\\ a+b=1\\ ab=-1 \end{cases} 解得
\begin{cases} A=\frac{1}{\sqrt{5}}\\ B=-\frac{1}{\sqrt{5}}\\ a=\frac{1+\sqrt{5}}{2}\\ b=\frac{1-\sqrt{5}}{2} \end{cases} 那么我们根据等比数列的展开式，就可以得到斐波那契数列的通项公式：
\frac{x}{1-x-x^2}=\sum_{n\ge 0}x^n \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \right) 这也被称为斐波那契数列的另一个封闭形式（ \frac{x}{1-x-x^2}
对于任意多项式 P(x),Q(x) \dfrac{P(x)}{Q(x)} Q(x) \prod (1-p_ix)^{d_i}
牛顿二项式定理 我们重新定义组合数的运算：
\binom{r}{k}=\frac{r^{\underline{k}}}{k!}\quad(r\in\mathbf{C},k\in\mathbf{N}) 注意 r \alpha\in\mathbf{C}
(1+x)^{\alpha}=\sum_{n\ge 0}\binom{\alpha}{n}x^n 二项式定理其实是牛顿二项式定理的一个特殊情况。
卡特兰数的生成函数 卡特兰数的递推式为
H_n=\sum_{i=0}^{n-1}H_{i}H_{n-i-1} \quad (n\ge 2) 其中 H_0=1,H_1=1 H(x)
我们发现卡特兰数的递推式与卷积的形式很相似，因此我们用卷积来构造关于 H(x)
\begin{aligned} H(x)&=\sum_{n\ge 0}H_nx^n\\ &=1+\sum_{n\ge 1}\sum_{i=0}^{n-1}H_ix^iH_{n-i-1}x^{n-i-1}x\\ &=1+x\sum_{i\ge 0}H_{i}x^i\sum_{n\ge 0}H_{n}x^{n}\\ &=1+xH^2(x) \end{aligned} 解得
H(x)=\frac{1\pm \sqrt{1-4x}}{2x} 那么这就产生了一个问题：我们应该取哪一个根呢？我们将其分子有理化：
H(x)=\frac{2}{1\mp \sqrt{1-4x}} 代入 x=0 H(x) H_0 H(x)=\dfrac{2}{1+\sqrt{1-4x}} H(0)=1 0
因此我们得到了卡特兰数生成函数的封闭形式：
H(x)=\frac{1- \sqrt{1-4x}}{2x} 接下来我们要将其展开。但注意到它的分母不是斐波那契数列那样的多项式形式，因此不方便套用等比数列的展开形式。在这里我们需要使用牛顿二项式定理。我们来先展开 \sqrt{1-4x}
\begin{aligned} (1-4x)^{\frac{1}{2}} &=\sum_{n\ge 0}\binom{\frac{1}{2}}{n}(-4x)^n\\ &=1+\sum_{n\ge 1}\frac{\left(\frac{1}{2}\right)^{\underline{n}}}{n!}(-4x)^n \end{aligned} \tag{1} 注意到
\begin{aligned} \left(\frac{1}{2}\right)^{\underline{n}} &=\frac{1}{2}\frac{-1}{2}\frac{-3}{2}\cdots\frac{-(2n-3)}{2}\\ &=\frac{(-1)^{n-1}(2n-3)!!}{2^n}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^n(2n-2)!!}\\ &=\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!} \end{aligned} 这里使用了双阶乘的化简技巧。那么带回 (1)
\begin{aligned} (1-4x)^{\frac{1}{2}} &=1+\sum_{n\ge 1}\frac{(-1)^{n-1}(2n-2)!}{2^{2n-1}(n-1)!n!}(-4x)^n\\ &=1-\sum_{n\ge 1}\frac{(2n-2)!}{(n-1)!n!}2x^n\\ &=1-\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n \end{aligned} 带回原式得到
\begin{aligned} H(x)&=\frac{1- \sqrt{1-4x}}{2x}\\ &=\frac{1}{2x}\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}2x^n\\ &=\sum_{n\ge 1}\binom{2n-1}{n}\frac{1}{(2n-1)}x^{n-1}\\ &=\sum_{n\ge 0}\binom{2n+1}{n+1}\frac{1}{(2n+1)}x^{n}\\ &=\sum_{n\ge 0}\binom{2n}{n}\frac{1}{n+1}x^{n}\\ \end{aligned} 这样我们就得到了卡特兰数的通项公式。
应用 接下来给出一些例题，来介绍生成函数在 OI 中的具体应用。
食物 食物 在许多不同种类的食物中选出 n
承德汉堡：偶数个 可乐：0 个或 1 个 鸡腿：0 个，1 个或 2 个 蜜桃多：奇数个 鸡块：4 的倍数个 包子：0 个，1 个，2 个或 3 个 土豆片炒肉：不超过一个。 面包：3 的倍数个 每种食物都是以“个”为单位，只要总数加起来是 n n 10007
这是一道经典的生成函数题。对于一种食物，我们可以设 a_n n n n
在理解了方案数可以用卷积表示以后，我们就可以构造生成函数（标号对应题目中食物的标号）：
\displaystyle\sum_{n\ge 0}x^{2n}=\dfrac{1}{1-x^2} 1+x 1+x+x^2=\dfrac{1-x^3}{1-x} \dfrac{x}{1-x^2} \displaystyle \sum_{n\ge 0}x^{4n}=\dfrac{1}{1-x^4} 1+x+x^2+x^3=\dfrac{1-x^4}{1-x} 1+x \dfrac{1}{1-x^3} 那么全部乘起来，得到答案的生成函数：
F(x)=\frac{(1+x)(1-x^3)x(1-x^4)(1+x)}{(1-x^2)(1-x)(1-x^2)(1-x^4)(1-x)(1-x^3)} =\frac{x}{(1-x)^4} 然后将它转化为展开形式（使用封闭形式练习中第五个练习）：
F(x)=\sum_{n\ge 1}\binom{n+2}{n-1}x^n 因此答案就是 \dbinom{n+2}{n-1}=\dbinom{n+2}{3}
Sweet 「CEOI2004」Sweet 有 n i m_i a b
两种方案不同当且仅当吃的个数不同，或者吃的糖果中，某一种糖果的个数在两个方案中不同。
n\le 10,0\le a\le b\le 10^7,m_i\le 10^6
在第 i j
F_i(x)=\sum_{j=0}^{m_i}x^j=\frac{1-x^{m_i+1}}{1-x} 因此总共吃 i
G(x)=\prod_{i=1}^n F_i(x)=(1-x)^{-n}\prod_{i=1}^n(1-x^{m_i+1}) 现在我们要求的是 \sum_{i=a}^b[x^i]G(x)
由于 n\le 10 \prod_{i=1}^n(1-x^{m_i+1}) 2^n
然后对 (1-x)^{-n}
\begin{aligned} (1-x)^{-n} &=\sum_{i\ge 0}\binom{-n}{i}(-x)^i\\ &=\sum_{i\ge 0}\binom{n-1+i}{i}x^i \end{aligned} 我们枚举 \prod_{i=1}^n(1-x^{m_i+1}) x^k c_k (1-x)^{-n}
c_k\sum_{i=a-k}^{b-k}\binom{n-1+i}{i}=c_k\left( \binom{n+b-k}{b-k}- \binom{n+a-k-1}{a-k-1} \right) 这样就可以 O(b)
时间复杂度 O(2^n+b)
build Last update and/or translate time of this articleCheck the history edit Found smelly bugs? Translation outdated? Wanna contribute with us? Edit this Page on Github people Contributor of this article sshwy translate Translator of this article Visit the original article! copyright The article is available under CC BY-SA 4.0 & SATA