生成函数总结

普通生成函数

生成函数是什么呢？首先对于一个序列$${a_0,a_1,a_2,\cdots}$$，我们希望把它整体的表示出来。

于是想到了函数，可以把这个序列作为系数，放到函数$$\sum_{k=0}^\infty a_kx^k$$里面。

举个例子：$5+3x^2+7x^3+{x^5 \over 9}+\cdots$表示序列$5,0,3,7,{1 \over 9},\cdots$

可以研究一下全是$1$的序列：

$$S=1+x+x^2+\cdots$$

$$xS=0+x+x^2+x^3+\cdots$$

$$(1-x)S=1$$

所以

$$1+x+x^2+x^3+\cdots={1\over 1-x}$$

上式之所以成立，是因为我们假设$−1<x<1$，而不关注具体$x$的取值，这是没有意义的。

变形

现在我们拓展一下：

1、

$x$替换为$-x$

$$1-x+x^2-x^3+\cdots={1\over 1+x}$$

生成序列$1,-1,1,-1,\cdots$

$x$替换为$3x$

$$1+3x+9x^2+27x^3+\cdots={1\over 1-3x}$$

发现要变成$(tx_i)^i$直接改分母就好了

2、

假如要全序列同时乘一个数呢？比如序列$2,2,2,2\cdots$

$$2+2x+2x^2+2x^3\cdots={2 \over 1-x}$$

发现只要分母上乘就好了

还可以组合一下：

$$3\times1+3\times2x+3\times4x^2+3\times 8x^3\cdots={3\over 1-2x}$$

3、

还有一些其他的：

$$1+x^2+x^3+x^6={1\over 1-x^2}$$

生成序列$1,0,1,0,\cdots$

$$x+x^3+x^5+x^7={x\over 1-x^2}$$

生成序列$0,1,0,1,\cdots$

把$1,0,1,0,\cdots$和$0,1,0,1,\cdots$相加得到$1,1,1,1,\cdots$，求和后也是一样

$${1\over 1-x^2}+{x\over 1-x^2}={1\over 1-x}$$

3、

既然生成函数是个函数，不妨对它求个导：

$$(1+x+x^2+x^3+\cdots)’=1+2x+3x^2+4x^3\cdots$$

$$({1\over1-x})’={1\over(1-x)^2}$$

也就是

$${1\over(1-x)^2}=1+2x+3x^2+4x^3\cdots$$

生成序列$1,2,3,4\cdots$

再求个导：

$${2\over(1-x)^3}=2+6x+12x^2+20x^3\cdots$$

除2

$${1\over(1-x)^3}=1+3x+6x^2+10x^3\cdots$$

生成序列$1,3,6,10,\cdots$

差分

通过上面这几条虽然可以得到许多形式的生成函数，但是许多序列比较复杂不能直接表示。这时我们可以考虑序列的差分

比如这个序列$1,3,5,7,\cdots$

$$S=1+3x+5x^2+7x^3+\cdots$$

$$xS=0+x+3x^2+5x^3+7x^4+\cdots$$

$$(1-x)S=1+2x+2x^2+2x^3+\cdots$$

$$(1-x)S={2\over 1-x}-1$$

$$S=-{1\over 1-x}+{2\over (1-x)^2}={1+x\over (1-x)^2}$$

也就是$1,3,5,7,\cdots$可以由$2,4,6,8,\cdots$和$1,1,1,1,\cdots$相减得到

线性递推

就拿最经典的斐波那契来说把：

$$a_n=a_{n-1}+a_{n-2}$$

$$S=1+1x+2x^2+3x^3+5x^4+\cdots$$

$$xS=0+1x+1x^2+2x^3+3x^4+\cdots$$

$$x^2S=0+0x+1x^2+1x^3+2x^4+\cdots$$

$$(1-x-x^2)S=1$$

$$S={1\over 1-x-x^2}$$

如何让结果更加直观一些呢？

$$1-x-x^2=(1-p_1x)(1-p_2x)$$

$$p_1={1+\sqrt5 \over 2},p_2={1-\sqrt5 \over 2}$$

$${1\over 1-x-x^2}={a\over 1-p_1x}+{b \over 1-p_2x}$$

解方程$a(1-p_2x)+b(1-p_1x)=1$

$$a={1\over \sqrt5}p_1,b=-{1\over \sqrt5}p_2$$

这样的话我们就可以得到任意项的系数，也就是斐波那契数列的通项公式：

$$a_i={1\over\sqrt5}(({1+\sqrt5\over 2})^{i+1}-({1-\sqrt5\over 2})^{i+1})$$

总结

来练习一下：

3是$$2x^3 \over (1-x)^2$$

普通生成函数应用

组合应用

将$i$次项系数$a_i$看作一个组合问题中选取问题大小为$i$的方案数。

那么对于两个普通生成函数的加法，则对应了加法原则。

$$C=A+B=\sum_{i=0}^\infty(a_i+b_i)x^i$$

对于生成函数的乘法：

$$C=A\times B=\sum_{i=0}^\infty(\sum_{j=0}^i(a_j\times b_{n-j}))x^i$$

$$c_i=\sum_{j=0}^i(a_j\times b_{n-j})$$

$C$ 的$i$次项系数，是两个和为$i$的问题在加法原则下运用乘法原则的答案。

例题1

对于非负整数$x_1,x_2,x_3,…x_k$,求$x_1+x_2+x_3+..+x_k=n$有多少组非负整数解。

我们可以为每个变量构造一个生成函数，这里每个的权值都是$1$，所以每个变量得到的生成函数均为

$$1+x+x^2+x^3+\cdots+x^n+\cdots$$

(不选为$1$，选$i$个为$x^i$，这里变量的取值没有限制，所以生成函数有无穷多项)，变量的组合相加对应于生成函数的乘积，这样我们将这些多项式相乘得到$f(x)=(1+x+x^2+x^3+\cdots+x^n+\cdots)^k$，把这个函数展开，其中$x^n$这一项的系数就是方程解的个数。

我们把$f(x)$化简一下：

$$f(x)=(1+x+x^2+x^3+\cdots+x^n+\cdots)^k=(1-x)^{-k}=\sum_{n=0}^\infty{n+k-1 \choose k-1}x^n$$

那么系数就是${n+k-1 \choose k-1}$，这和插板法得出的结论是相同的。

例题2

有$ A,B,C,D $四种水果，每种水果都有无限个，现在要求每种水果拿若干个，要求$ A $恰好拿出偶数个，$B $恰好拿出$5 $个倍数个，$C $最多拿$ 4$个，$D $最多拿一个，如果最后恰好拿出$N $个水果，有多少种方案。

对于$ 4 $种水果进行组合，将他们的生成函数相乘。

$$G=A\times B \times C \times D={1\over 1-x^2}\times {1\over 1-x^5}\times(1+x+x^2+x^3+x^4)\times(1+x)={1\over (1-x)^2}$$

那么$G$对应的序列为$1,2,3,4,5\cdots$

所以恰好选取$ N $个水果的方案数为$N + 1$

卡特兰数应用

一个正$n$边形，顶点标号$1 – n$，现在画$n-3$条不相交的对角线将它画分为一些三角形，有多少种方案。

这个数列被称为$Catalan$数，$1, 2, 5, 14, 42,\cdots$

令$c_i$ 表示$i + 2 $边形的对角线划分方案数，特殊的令$ c_0 = 1$。我们知道它的递推式：

$$c_n=\sum_{i=0}^{n-1}c_ic_{n-i-1}$$

构造一个生成函数

$$G(x)=1+1x+2x^2+5x^3+14x^4+\cdots$$

我们发现这个递推式的系数和多项式相乘的系数形式好像差不多。。那么就试着构造一个出来

将生成函数平方一下

$$G(x)^2=\sum_{i=0}^\infty x^i \sum_{j=0}^ic_jc_{k-j}$$

发现后面的就和递推式好像啊

$$G(x)^2=\sum_{i=0}^\infty c_{i+1}x^i$$

所以将$ G(x)^2 $每项次数提高一次，然后补上常数$ 1$，就变成了$G(x)$。

$$G(x)=1+xG(x)^2$$

解得

$$G(x)={1 \pm \sqrt{1-4x} \over 2x}$$

当$x \rightarrow 0$时，假如$$G(x)={1 + \sqrt{1-4x} \over 2x}$$，那么$G(x) \rightarrow \infty$，但是展开式的常数项不是无穷大，舍去。

所以卡特兰数的生成函数为$$G(x)={1 – \sqrt{1-4x} \over 2x}$$

根据二项式定理：

$$(1+x)^a=1+{a \over 1!}x+{a(a-1) \over 2!}x^2+\cdots+{a(a-1)\cdots(a-n+1)\over n!}x^n$$

化一下生成函数的式子

$${1-(1-4x)^{1\over 2}\over 2x}={1 \over 2x}\sum_{k=1}^\infty{1\times3\times \cdots \times(2k-3)\over 2^k} {(4x)^k \over k!}$$

那么系数就是

$$c_k={1\over 2}\times{1\times3\times \cdots \times(2k-3)\times (2k-1)\over 2^{k+1}}\times {4^{k+1}\over (k+1)!}={(2k)!\over (k+1)(k!)^2}={1\over k+1}{2k \choose k}$$

这就是卡特兰数的通项公式。

泰勒公式

要是接着看下去的话要用到的泰勒公式

泰勒公式是什么呢？其实它的主要作用就是用多项式函数来拟合一个普通函数。假如有一个多项式函数，比如$f(x)=a+bx+cx^2$，假如想知道它在某个点的值，就直接代入就好了。但是比如像$f(x)=ln(x)$或者$f(x)=e^x$这种函数就很难知道它在任意一点的取值。

那么我们就想如何用多项式函数去逼近那些难算函数的值。比如

用多项式去逼近 $f(x)=e^x$ 在 $x$ 靠近 $0$ 的函数值

我们先从简单的开始

第一阶段

用下面的这种多项式

$$g(x)=a_0+a_1x$$

来逼近$f(x)=e^x$

这其实就是一条直线。假如我们要用一条直线去逼近，最好的选择就是$e^x$在$(0,1)$的切线了。

这样根据定义的话，这条切线和$e^x$在$x=0$时它们的函数值和一阶导数应该都一样，也就是这条切线的斜率就等于$e^x$在$x=0$的导数。$e^x$的导数又等于它自己，所以

$$\left. {d(e^x) \over dx}\right |_{x=0}=e^0=1$$

所以斜率为$1$，而且$y$截距又为$1$，那么表达式为：

$$g=x+1$$

这就是逼近的结果。那它有多近似呢？我们代入$x=0.1$，$e^{0.1} \approx 1.105170918$，而逼近的值就是$1+x=1.1$，发现我们准确到了小数点的第一位。

第二阶段

下一步用$g(x)=a_0+a_1x+a_2x^2$的二次多项式来逼近$f(x)=e^x$在$x=0$附近的值。这样我们就要要求这两个函数具有相同的函数值，一阶导数和二阶导数。所以

$$f(x)=e^x,f(0)=e^0=1$$

$$f'(x)=e^x,f'(0)=e^0=1$$

$$f”(x)=e^x,f”(0)=e^0=1$$

那么

$$g(x)=a_0+a_1x+a_2x^2,g(0)=a_0=1,a_0=1$$

$$g'(x)=a_1+2a_2x,g'(0)=a_1=1,a_1=1$$

$$g”(x)=2a_2,g”(0)=2a_2=1,a_2={1\over 2}$$

我们就得到了这个函数的表达式：

$$g(x)=1+x+{x^2\over 2}$$

我们接着用$x=0.1$来测试一下，$e^{0.1} \approx 1.105170918$，$g(0.1)=1.105$，我们已经精确到小数点第三位了。

第三阶段

我们再找一个三节多项式$g(x)=a_0+a_1x+a_2x^2+a_3x^3$来逼近试试。

同样的，$e^x$无论几阶导都等于自己，所以

$$g(x)=a_0+a_1x+a_2x^2+a_3x^3,g(0)=a_0=1,a_0=1$$

$$g'(x)=a_1+2a_2x+3a_3x^2,g'(0)=a_1=1,a_1=1$$

$$g”(x)=2a_2+6a_3x,g”(0)=2a_2=1,a_2={1\over 2}$$

$$g”'(x)=6a_3,g”'(0)=6a_3=1,a_3={1\over 6}$$

我们就得到了这个函数的表达式：

$$g(x)=1+x+{x^2 \over 2}+{x^3\over 6}$$

代入得到$g(x)=1.1051666\cdots$，已经非常接近了。。

这样我们可以发现一个规律，就是假如继续添加的话

$$e^x\approx 1+x+{x^2 \over 2!}+{x^3 \over 3!}+{x^4 \over 4!}+\cdots$$

现在就有些概念了，当我们碰到一个不好求值的函数$f(x)$，要求它在靠近某一个固定点$a$的近似值。结果，我们求出了一个多项式，它在$a$点附近和$f(x)$非常相似。一般来说，它大多是这种形式：

$$g(x)=b_0+b_1(x-a)+b_2(x-a)^2+b_3(x-a)^3+\cdots+b_n(x-a)^n$$

为了让$g(x)$和$f(x)$在靠近$a$的时候行为相似，我们要让两个函数的值和前$n$次的导数值都两两相同，也就是：

$$f(a)=g(a)$$

$$f'(a)=g'(a)$$

$$f”(a)=g”(a)$$

$$f”'(a)=g”'(a)$$

$$\cdots$$

$$f^{(n)}(a)=g^{(n)}(a)$$

那么我们把$g(x)$直接微分：

$$g(x)=b_0+b_1(x-a)+b_2(x-a)^2+b_3(x-a)^3+\cdots+b_n(x-a)^n$$

$$g'(x)=b_1+2b_2(x-a)+3b_3(x-a)^2+\cdots+nb_n(x-a)^{n-1}$$

$$g”(x)=2b_2+3(2)b_3(x-a)+\cdots+n(n-1)b_n(x-a)^{n-2}$$

$$g”'(x)=3(2)b_3+\cdots+n(n-1)(n-2)b_n(x-a)^{n-3}$$

$$\cdots$$

$$g^{(n)}(x)=n(n-1)(n-2)\cdots(3)(2)b_n$$

于是

$$f(a)=g(a)=b_0$$

$$f'(a)=g'(a)=1!b_1$$

$$f”(a)=g”(a)=2!b_2$$

$$f”'(a)=g”'(a)=3!b_3$$

$$\cdots$$

$$f^{(n)}(a)=g^{(n)}(a)=n!b_n$$

所以

$$b_0=f(a)$$

$$b_1={f'(a)\over 1!}$$

$$b_2={f”(a)\over 2!}$$

$$b_3={f”'(a)\over 3!}$$

$$\cdots$$

$$b_n={f^{(n)}(a)\over n!}$$

现在我们把它带回去，就得到了泰勒逼近

$$f(x)\approx f(a)+f'(a)(x-a)+{f'(a)\over 2!}(x-a)^2+{f”'(a)\over 3!}(x-a)^3+\cdots+{f^{(n)}(a)\over n!}(n-a)^n$$

带有余项的泰勒公式

皮亚诺余项：当$x\rightarrow x_0$

$$f(x)=f(x_0)+{f'(x_0)\over1!}(x-x_0)+{f^{(2)}(x_0)\over2!}(x-x_0)^2+\cdots+{f^{(n)}(x_0)\over n!}(x-x_0)^n+o((x-x_0)^n)$$

这个式子的余项是高阶无穷小，证明了泰勒公式的准确性。

拉格朗日余项：无需$x\rightarrow x_0$

$$f(x)=f(x_0)+{f'(x_0)\over1!}(x-x_0)+{f^{(2)}(x_0)\over2!}(x-x_0)^2+\cdots+{f^{(n)}(x_0)\over n!}(x-x_0)^n+{f^{(n+1)}(\xi)\over (n+1)!}(x-x_0)^{n+1}$$

这里的$\xi$是一个介于$x_0$和$x$之间的数。这个式子可以算出误差的范围。(就不展开讲了)

常用的：

$$e^x=1+{x\over1!}+{x^2\over2!}+{x^3\over3!}+\cdots+{x^n\over n!}+\cdots$$

$$sin(x)=x-{x^3\over3!}+{x^5\over5!}+\cdots+(-1)^n{x^{2n+1}\over (2n+1)!}+\cdots$$

$$cos(x)=1-{x^2\over2!}+{x^4\over4!}+\cdots+(-1)^n{x^{2n}\over (2n)!}+\cdots$$

$$ln(1+x)={x\over 1}-{x^2\over 2}+{x^3\over 3}+\cdots +(-1)^{n+1}{x^n\over n}+\cdots$$

$$(1+x)^a=1+{a\over 1}x+{a(a-1)\over 2!}x^2+\cdots +{a(a-1)\cdots(a-n+1)\over n!}x^n+\cdots$$

指数型生成函数

普通的生成函数常用来解决无标号的组合问题。

对于有标号的问题，指数型生成函数是很方便的工具。

$$\hat A=a_0+{a_1\over 1!}x+{a_2\over 2!}x^2+{a_3\over 3!}x^3+{a_4\over 4!}x^4+\cdots$$

比如

$$e^x=1+{x\over 1!}+{x^2\over 2!}+{x^3\over 3!}+\cdots$$

就是$1,1,1,1,\cdots$的生成函数

指数型生成函数在处理有标号问题时十分方便。

例如：有$ n $不同个元素的排列数(记作$p_n$，特殊的令$ p_0 = 1$)

$$\hat P=\sum_{n=0}^\infty {n!\over n!}x^n={1\over 1-x}$$

另一些排列问题，例如环排列 (将元素排列在一个环上)。

将$ n$个元素的环排列个数记为$ c_n$，特殊的令$ c_0 = 0$。

$$\hat C=\sum_{n-1}^\infty{(n-1)!\over n!}x^n=\sum_{n=1}^\infty{x^n\over n}$$

还记得$ln(1+x)$的泰勒公式吗：

$$ln(1+x)={x\over 1}-{x^2\over 2}+{x^3\over 3}+\cdots +(-1)^{n+1}{x^n\over n}+\cdots$$

所以

$$\hat C=-ln(1-x)=ln({1\over 1-x})$$

此时可以注意到$ \hat P = e^{\hat C}$，这之间的关系只是巧合吗？

任何一个排列都是可以拆分成一些轮换(环排列)。

例如$ (3, 6, 4, 1, 2, 5) = (3, 1, 4)(6, 2, 5)$

如何通过轮换的生成函数，求出排列的生成函数呢？

从简单的开始，考虑排列具体是由多少个轮换组成，排列只由$ 1 $个轮换组成是$ \hat Q = \hat C$。

排列恰好由$ 2 $个轮换组成，生成函数$ \hat Q(x)$。$2 $个轮换相当于将 $n $个元素染成黑色与白色，同种颜色排成一个轮换，然后组合起来。

$$q_n={1\over 2!}\sum_{t=0}^n{n\choose t}c_tc_{n-t}$$

代入

$$
\begin{aligned}
\hat Q(x) &= {1\over 2!}\sum_{n=0}^\infty{q_n\over n!}x^n\\
&={1\over 2!}\sum_{n=0}^\infty{1\over n!}(\sum_{t=0}^n{n!\over t!(n-t)!}c_tc_{n-t})x^n \\
&={1\over 2!}\sum_{t=0}^\infty \sum_{n=t}^\infty{c_tx^t\over t!}\times{c_{n-t}x^{n-t} \over (n-t)! } \\
&={1\over 2!}\sum_{t=0}^\infty{c_t\over t!}x^t\times \sum_{s=0}^\infty{c_s\over s!}x^s \;\;\;\;(s=n-t)\\
&={1\over 2!}\hat C\times\hat C
\end{aligned}
$$

也就是恰好由两个轮换组合的排列个数的生成函数就是${1\over 2!}\hat C^2$

推广一下发现恰好由$ k $个轮换组合成的排列的生成函数就是${1\over k!}\hat C^2$

$$\sum{c_{n1}\over n1!} \times {c_{n2}\over n2!} \times \dots \times {c_{nk}\over nk!}={1\over n!}\sum{n\choose n1n2\cdots nk}c_{n1}c_{n2}\cdots c_{nk}$$

最后排列的生成函数就是

$$\hat P=\sum_{k=1}^\infty {1\over k!}\hat C^k$$

$$e^x=1+{x\over 1!}+{x^2\over s!}+{x^3\over 3!}+\cdots$$

所以就是把$e^x$中的$x$替换为了$\hat C$

$$\hat P =e^{\hat C}$$

例1

求错位排列方案数的生成函数$ \hat D(x)$，特殊的令$ d_0 = 1$，错排是指一个排列，且$\forall i, i$不在第$i$个位置上。

错排不允许有大小为$1 $的轮换。

在$ \hat C$中去除大小为$ 1 $的轮换，然后组合。

$$\hat C-x=ln({1\over 1-x})-x$$

$$\hat D(x)=e^{\hat C-x}={e^{-x}\over 1-x}$$

例2

使用生成函数方法求$ n $个点的有标号无向联通图(无重边自环)的数量。

如果令$ \hat A$表示有标号无向连通图的生成函数，$\hat B$表示有标号无向图的生成函数。

有标号$ n $个点的无向图很好求解：

$$\hat B=\sum_{i=0}^\infty 2^{i \choose 2}x^i$$

无向图可以看做无向连通图的组合，与排列/轮换之间关系类似。

$$\hat B=e^{\hat A}$$

$$\hat A=ln(\hat B)$$

例3

求伯努利数的生成函数。

伯努利数定义：$B_0=1$，当$n \geq 1$有

$$\sum_{i=0}^{n+1}{n+1 \choose i}B_i=0$$

拆开

$$(n+1)!\sum_{i=0}^n{1\over (n-i+1)!}\times {B_i \over i!}=0$$

换下枚举方式

$$\sum_{j=0}^n={{1\over j+1} \over j!}\times {B_{n-j} \over (n-j)!}$$

这样我们可以把右半边看成另外一个指数生成函数$\hat P$，系数是$1,{1\over 2},{1\over 3},\cdots$

那么

$$\hat P={e^x-1\over x}$$

$\hat B · \hat P$只有零次项系数不为$0$：

$$\hat B · {e^{x}-1 \over x}=b_0=1$$

$$\hat B = {x\over e^x -1}$$

后记

主要摘自雅礼集训课件。自己补充了一些内容(主要是泰勒公式那块)。I hope you enjoy it