【组合数学】生成函数

1.形式幂级数

生成函数是解决计数问题的一种有效方法，它的中心思想是：对于一个有限或无限数列 $a_0,a_1,a_2,...$，用 { x i } ( i = 0 , 1 , . . . ) \{x^i\}(i=0,1,...) {xi}(i=0,1,...)这样的生成基构成形式幂级数 $$A(x)=a_0+a_{1}x+a_2{x}^2+...$$ 使 { a i } \{a_i\} {ai?} 与 { x i } \{x^i\} {xi} 成一一对应关系，由此 { a i } \{a_i\} {ai?} 与 { x i } \{x^i\} {xi} 构成了一个整体，通过研究幂级数 $A(x)$，导出数列 { a 0 , a 1 , a 2 , . . . } \{a_0,a_1,a_2,...\} {a0?,a1?,a2?,...}的构造和性质。
称 $A(x)$ 为序列 { a 0 , a 1 , a 2 , . . . } \{a_0,a_1,a_2,...\} {a0?,a1?,a2?,...} 的生成函数，并记为 $G(a_n)$

对于形式幂级数可以像收敛的幂级数那样进行运算，运算的定义和规则完全相同

定义 1.1：对于任意 $A(x)={\sum }_{k=0}^{\infty }{a}_k{x}^k$，规定 $DA(x)$ 为 $A(x)$ 的导数且 $DA(x)\equiv {\sum }_{k=0}^{\infty }k{a}_k{x}^{k?1}$

2.生成函数性质

一个数列和它的生成函数是一一对应的。 已知数列便得知它的生成函数（系数项确定）。同理求得生成函数，则数列也随之而定。
数列 { a 0 , a 1 , a 2 , . . . } \{a_0,a_1,a_2,...\} {a0?,a1?,a2?,...} 的生成函数为 $A(x)={\sum }_{k=0}^{\infty }{a}_k{x}^k$
数列 { b 0 , b 1 , b 2 , . . . } \{b_0,b_1,b_2,...\} {b0?,b1?,b2?,...} 的生成函数为 $B(x)={\sum }_{k=0}^{\infty }{b}_k{x}^k$
可以得到生成函数的如下一些性质

性质 2.1：若 $b_k=\{\begin{array}{cc}0& (k<l)\\ a_{k?l}& (k\ge l)\end{array}$ 则 $B(x)=x^l?A(x)$

性质 2.2：若 $b_k=a_{k+l}$ ,则 $B(x)=\frac{1}{x^l}(A(X)?{\sum }_{k=0}^{l?1}{a}_k{x}^k)$

性质 2.3：若 $b_k={\sum }_{i=0}^k{a}_i$，则 $B(x)=\frac{A(x)}{1?x}$

性质 2.4：若 $b_k={\sum }_{i=k}^{\infty }{a}_i$，则 $B(x)=\frac{A(1)?xA(x)}{1?x}$

性质 2.5：若 $b_k=k{a}_k$，则 $B(x)=xA(x)$

性质 2.6：若 $b_k=\frac{a_k}{k+1}$，则 $B(x)=\frac{1}{x}{\int }_0^{x}A(t)dt$

性质 2.7：若 $c_k=\alpha a_k+\beta b_k$，则 $C(x)\equiv {\sum }_{k=0}^{\infty }{c}_k{x}^k=\alpha A(x)+\beta B(x)$

数列	生成函数
{1,1,1,…}	G { 1 } = 1 1 ? x G\{1\}=\cfrac{1}{1-x} G{1}=1?x1?
{ a 0 , a 1 , a 2 , . . . } \{a^0,a^1,a^2,...\} {a0,a1,a2,...}	G { a k } = 1 1 ? a x G\{a^k\}=\cfrac{1}{1-ax} G{ak}=1?ax1?
{0,1,2,…}	G { k } = x ( 1 ? x ) 2 G\{k\}=\cfrac{x}{(1-x)^2} G{k}=(1?x)2x?
{ 0 ? 1 , 1 ? 2 , 2 ? 3 , . . . } \{0\cdot1,1\cdot2,2\cdot3,...\} {0?1,1?2,2?3,...}	G { k ( k + 1 ) } = 2 x ( 1 ? x ) 3 G\{k(k+1)\}=\cfrac{2x}{(1-x)^3} G{k(k+1)}=(1?x)32x?
{ 0 ? 1 ? 2 , 1 ? 2 ? 3 , 2 ? 3 ? 4 , . . . } \{0\cdot1\cdot2,1\cdot2\cdot3,2\cdot3\cdot4,...\} {0?1?2,1?2?3,2?3?4,...}	G { k ( k + 1 ) ( k + 2 ) } = 6 x ( 1 ? x ) 4 G\{k(k+1)(k+2)\}=\cfrac{6x}{(1-x)^4} G{k(k+1)(k+2)}=(1?x)46x?
{0,1,4,…}	G { k 2 } = x ( 1 + x ) ( 1 ? x ) 3 G\{k^2\}=\cfrac{x(1+x)}{(1-x)^3} G{k2}=(1?x)3x(1+x)?
{0,1,8,…}	G { k 3 } = x 3 + 4 x 2 + x ( 1 ? x ) 4 G\{k^3\}=\cfrac{x^3+4x^2+x}{(1-x)^4} G{k3}=(1?x)4x3+4x2+x?
{ 1 0 ! , 1 1 ! , 1 2 ! , . . . } \{\cfrac{1}{0!},\cfrac{1}{1!},\cfrac{1}{2!},...\} {0!1?,1!1?,2!1?,...}	G { 1 k ! } = e x G\{\cfrac{1}{k!}\}=e^x G{k!1?}=ex
{ ( α 0 ) , ( α 1 ) , ( α 2 ) , . . . } \{\binom{\alpha}{0},\binom{\alpha}{1},\binom{\alpha}{2},...\} {(0α?),(1α?),(2α?),...}	G { ( α k ) } = ( 1 + x ) α G\{\binom{\alpha}{k}\}=(1+x)^\alpha G{(kα?)}=(1+x)α
{ ( n + 0 0 ) , ( n + 1 1 ) , ( n + 2 2 ) , . . . } \{\binom{n+0}{0},\binom{n+1}{1},\binom{n+2}{2},...\} {(0n+0?),(1n+1?),(2n+2?),...}	G { ( n + k k ) } = 1 ( 1 ? x ) n + 1 G\{\binom{n+k}{k}\}=\cfrac{1}{(1-x)^{n+1}} G{(kn+k?)}=(1?x)n+11?

习题1、 求序列{5, 6, 7, …, n + 5, …}的生成函数

习题2、 利用生成函数计算 $1^3+2^3+...+n^3$

3.生成函数求解递推关系

生成函数求解递推关系基本步骤如下：

1. 令 $A(x)={\sum }_{n=0}^{\infty }f(n)x^n$
2. 将关于 $f(n)$ 的递推关系式转化成关于 $A(x)$ 的方程式
3. 解出 $A(x)$ ，将 $A(x)$ 展开成 x 的幂级数， $x^n$ 的系数即是 $f(n)$

习题3、 用生成函数求解递推关系$\{\begin{array}{c}f(n)=4f(n?2)\\ f(0)=0,f(1)=1\end{array}$

习题4、 用生成函数求解递推关系$\{\begin{array}{c}f(n)=f(n?1)+9f(n?2)?9f(n?3)\\ f(0)=0,f(1)=1,f(2)=2\end{array}$

习题5、 用生成函数求解递推关系$\{\begin{array}{c}f(n)=f(n?1)+n^2\\ f(0)=0\end{array}$

4.生成函数在计数问题中的应用