生成函数详解

这是一篇即将咕咕很久的学习笔记。

定义$f(x)=a_0+a_1x+a_2x^2+a_3x^3...$，$f(x)$就是序列$a_0,a_1,a_2...a_n$的生成函数

01背包问题

给你$w_1,w_2,w_3,...w_n$，每个数只有取和不取的两种状态，求凑成$W$的种类数。

构造$f(x)=\prod_{i=1}^n (x^0+x^{w_i})$，于是答案就是$x^W$的系数。

完全背包问题

给你$w_1,w_2,w_3,...,w_n$，每个数可以取任意多种，求凑成$W$的种类数。

构造$f(x)=\prod_{i=1}^n (\sum _{j=0} x^{w_i\times j})$，答案就是$x^W$的系数。

$\sum _{j=0} x^{w_i \times j}$是无穷的，如何算出？

令$p=x^w_i$，那么有$\sum _{j=0} x^{w_i \times j}=\sum _{j=0} p^j$。

注意到$\sum _{j=0} p^j=\frac{1-p^\infty}{1-p}$，当$x \in (-1,1)$时，$p\in (-1,1)$，所以$p^ \to 0$，于是原式就是$\frac{1}{1-p}$，即$\frac{1}{1-x_i^w}$。

两种生成函数

前面介绍了第一种生成函数：$\sum _{j=0} ^{} x^j =\frac{1}{1-x}(x \in (-1,1))$

现在介绍第二种中的一个特殊情况：$\sum _{j=0}^{} (j+1) \times x^j=?$

我们把两个$\sum _{j=0} ^{} x^j$相乘，凑成$j$的有$(0,j),(1,j-1)...(j,0)$这么多种，共$j+1$种选法。

于是$\sum _{j=0} (j+1) \times x^j=\frac{1}{(x-1)^2}$

推广一下：

$\frac{1}{(x-1)^k}$是什么？

问题转化为凑出$k$个数，使他们的和为$j$的方案数。

插板法即可，答案为$C_{j+k-1}^{k-1}$

于是$\frac{1}{(x-1)^k}=\sum_{j=0} C_{j+k-1}^{k-1} x^j$

注意到$C_{j+k-1}^{k-1}=C_{j+k-1}^j$，这个形式在下面的广义二项式定理里面会用到。

于是我们总结出以下规律：

$\frac{1}{1-x^k}=\sum _{j=0} x^{jk}$

$\frac{1}{(1-x)^k}=\sum_{j=0} C_{j+k-1}^{k-1} x^j$

还有一个有限项数的求和公式：

$\frac{1-x^{k+1}}{1-x}=\sum _{j=0}^k x^k$

广义二项式定理

注意到$\frac{1}{(1-x)^k}=(1-x)^{-k}$。

我们不禁有个大胆的想法，如果$k$可以取任何实数，那么我们就可以表示出$\sqrt{1-x},\sqrt[3]{1-x}$等等的生成函数。

$(1+x)^\alpha = \sum_{j=0} C_{j}^{\alpha} x^j$。

定义：

$C_{\alpha}^{k}=\begin{cases} \frac{\alpha(\alpha-1)(\alpha-2) \dots (\alpha-k+1)}{k!},k>1 \\ 1,k=0 \\ 0,k<0 \end{cases}(k \in \mathbb{Z},\alpha \in \mathbb{R}) \tag{1.1.1}$

来自巨佬ypy的博客。

生成函数的应用

例题1

BZOJ 3028

承德汉堡：$f(x)=1+x^2+x^4+x^6...=\frac{1}{1-x^2}$

可乐：$f(x)=1+x$

鸡腿：$f(x)=1+x+x^2=\frac{1-x^3}{1-x}$

蜜桃多：$f(x)=\sum_{j=0} x^j - (1+x^2+x^4+...)=\frac{1}{1-x}-\frac{1}{1-x^2}=\frac{x}{1-x^2}$

鸡块：$f(x)=\frac{1}{1-x^4}$

包子：$f(x)=1+x+x^2+x^3=\frac{1-x^4}{1-x}$

土豆片炒肉：$f(x)=1+x$

面包：$f(x)=\frac{1}{1-x^3}$

乘起来然后大力化简一波，化成了$\frac{x}{(1-x)^4}$

套进第二个式子：

$\frac{x}{(1-x)^4}=\sum_{j=0} C_{j+3}^{3}x_{j+1}=\sum_{j=1} C_{j+2}^{3}x_{j}$

于是我们所求的就是$C_{j+2}^3$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <bits/stdc++.h>
#define MAXN 200005
#define MOD 10007
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=((x<<3)+(x<<1)+(ch^'0'))%MOD;
        ch=getchar();
    }
    return x*f;
}
inline int ksm(int b,int k){
	int ans=1;
	while (k){
		if (k&1) ans=(ans*b)%MOD;
		b=(b*b)%MOD;
		k>>=1;
	}
	return ans;
}
int main(){
	int n=read();
	printf("%d\n",(n+2)*(n+1)%MOD*(n)%MOD*ksm(6,MOD-2)%MOD);
}

例题2

P2000 拯救世界

本质和上面一题是一样的：

kkksc03：

金：$\frac{1}{1-x^6}$

木：$\frac{1-x^{10}}{1-x}$

水：$\frac{1-x^6}{1-x}$

火：$\frac{1}{1-x^4}$

土：$\frac{1-x^8}{1-x}$

lzn：

金：$\frac{1}{1-x^2}$

木：$1+x$

水：$\frac{1}{1-x^8}$

火：$\frac{1}{1-x^{10}}$

土：$\frac{1-x^4}{1-x}$
大力乘起来，算出$\frac{1}{1-x^5}$

答案即是$C_{n+5-1}^{5-1}=C_{n+4}^4$。

只写了python版本：

1
2

n=(int)(input())
print((n+1)*(n+2)*(n+3)*(n+4)//24)

例题3

试用生成函数推导斐波那契数列通项公式。

斐波那契数列：$fib_1=1,fib_2=1,fib_i=fib_{i-1}+fib_{i-2} (i\ge 3)$

构造$f(x)=\sum _{j=1} fib_j x^j$

所以$f(x) \times x=\sum_{j=2} fib_{j-1}x^j$

$f(x)-f(x)\times x=fib_1x+\sum_{j=3}^{}fib_{j-2}x^j=x+x^2\times f(x)$

所以$f(x)=\frac{x}{1-x-x^2}$

令$\phi =\frac{1+\sqrt{5}}{2},\phi'=\frac{1-\sqrt{5}}{2}$。

分解：$\frac{x}{1-x-x^2}=\frac{x}{(1-\phi'x)(1-\phi x)}=\frac{1}{\sqrt{5}}(\frac{1}{1-\phi x} - \frac{1}{1-\phi' x})$

根据公式$\frac{1}{1-x}=\sum _{j=0} x^{j}$，前面一项化为$(\phi)^n$后面一项化成$(\phi')^n$。

于是我们得到$fib_n=\frac{1}{\sqrt{5}}(\phi ^n-\phi'^n)$。

即$fib_n=-\frac{1}{\sqrt 5}(\frac{1-\sqrt 5}{2})^n+\frac{1}{\sqrt 5}(\frac{1+\sqrt 5}{2})^n$。

补充

已知$f_0=A,f_1=B,f_i=pf_{i-1}+qf_{i-2} (i \ge 2)$

构造$f(x)=\sum _{j=1} f_j x^j$

所以$f(x) \times x= \sum _{j=2} f_{j-1} x^j$

得到$f(x)-pf(x) \times x=Cx + \sum _{j=2} f_{j-2}x^j=Cx+q x^2 f(x)$（其中$C$是一个常数，我们可以不用管它，原理在你使用时自然清楚）

得到$f(x)-px f(x) -qx^2 f(x)=Cx$，于是有$f(x)=\frac{Cx}{1-px-qx^2}$。

设方程$x^2-px-q=0$的解是$x_1,x_2$（$x_1,x_2$又称特征根），注意到把$x=\frac{1}{x_1}$带入$1-px-qx^2$，变成$1-\frac{p}{x_1}-\frac{q}{x_1^2}=\frac{x_1^2-px_1-q}{x_1^2}$

显然为$0$。

于是可以转化为$f_n=C_1 x_1 ^n +C_2x_2^n$

你肯定有疑问，为什么不算出来$C_1,C_2$，直接无脑带进去就好。

事实上$C_1,C_2$公式非常复杂，你肯定也记不住。

考试时，可以解出$C_1,C_2$。

比如一道题：$h_0=1,h_1=3,h_n=2h_{n-1}+2h_{n-2} (n\ge 2)$。

特征根：$x^2-2x-2=0 \to x_{1,2}=\frac{2 \pm \sqrt {4+8}}{2}={1\pm \sqrt{3}}$

带入$h_0=C_1 +C_2,h_1=C_1x_1+C_2x_2$（这里我们特意算出来$h_0$以简化计算）

得到$C_1+C_2=1,C_1(1+\sqrt {3}) +C_2(1-\sqrt{3})=3$

解得$C_1=\frac{2 \sqrt {3}+3}{6},C_2=\frac{-2 \sqrt {3}+3}{6}$

通项公式$h_n=\frac{2 \sqrt {3}+3}{6} (1+\sqrt{3})^n + \frac{-2 \sqrt {3}+3}{6} (1-\sqrt{3})^n$

例题4

试用生成函数推导卡特兰数通项公式。

卡特兰数：

$c'_0=1$

$c'_1=1$

$c'_n=\sum_{i=1}^{n-1}c'_ic'_{n-i-1}$

为了方便，记$c_i=c'_{i-1}$，有$c'_i=c_{i+1}$。

所以有$c_n=c'_{n-1}=\sum_{i=1}^{n-2}c'_ic'_{n-i-2}=\sum_{i=1}^{n-2}c_{i+1}c_{n-i-1}=\sum_{i=2}^{n-1}c_ic_{n-i}$

记$C(x)=\sum _{i=0} c_ix^i$

有$C(x)-C(x)^2=C_1 \times x^1=x$。

于是$C(x)^2-C(x)+x=0$

得到$C(x)=\frac{1\pm\sqrt{1-4x}}{2}$

舍去$\frac{1+\sqrt{1-4x}}{2}$

所以$C(x)=\frac{1}{2x}[1-(1-4x)^{0.5}]$

先化简$(1-4x)^{0.5}$

由$(1+x)^\alpha = \sum_{j=0} C_{j}^{\alpha} x^j$

有$(1-4x)^{0.5}=\sum_{j=0} C_{0.5}^{j}(-4x)^j$。

注意到这里$C_{0.5}^0(-4x)^0=1$，把它放到前面去。

拆一波$C_{0.5}^{j}=\frac{\prod_{k=0}^{j-1} (0.5-k)}{j!}$

放回去：$\sum_{j=1}^ \frac{\prod_{k=0}^{j-1}(0.5-k)}{j!} \times (-4x)^j$

右边除掉一个$(-2)^j$，左边乘$(-2)^j$

变成：$\sum_{j=1}^ \frac{\prod_{k=0}^{j-1}(2k-1)}{j!} \times (2x)^j$

注意到$\sum_{k=0}^{j-1}=-1\times (1 \times 3 \times 5 \times ... \times (2j-3))$，这里我们把那个$-1$放到前面抵消掉减号，下面不再说明。

这时可以发现$(1 \times 3 \times 5 \times ... \times (2j-3))= \frac{(2j-2)!}{2^{j-1}(j-1)!}$

于是我们可以得到$(1-4x)^{0.5}=1-\sum_{j=1} 2^j x^j \times \frac{(2j-2)!}{2^{j-1}(j-1)!} \times \frac{1}{j!}$

等于$1-\sum_{j=1} x^j \times 2\frac{(2j-2)!}{(j-1)!j!}$

带回原式$C(x)=\frac{1}{2x}[1-(1-\sum_{j=0} x^j \times 2\frac{(2j-2)!}{(j-1)!j!})]$

等于$\sum_{j=1} x^{j-1} \times \frac{(2j-2)!}{(j-1)!j!}$。

注意到$x$的次数不能是$j-1$，于是把$k=j-1$带入，变成$\sum _{k=0} x^k \times \frac{(2k)!}{k!(k+1)!}$

于是得到公式$c_n=\frac{(2n)!}{n!(n+1)!}$