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\cdot 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.生成函数在计数问题中的应用