定义
序列(a)的普通生成函数((OGF))，定义为形式幂级数：
[F(x)=sum_{n}a_nx^n
]
(a)既可以是有穷序列，也可以是无穷序列，常见例子：
(1.)序列(a=<1,2,3>)的(OGF)是(1+2x+3x^2)
(2.)序列(a=<1,1,1,…>)的(OGF)是(sum_{ngeq 0}x^n)
(3.)序列(a=<1,2,4,…>)的(OGF)是(sum_{ngeq 0}2^nx^n)
(4.)序列(a=<1,3,5,…>)的(OGF)是(sum_{ngeq 0}(2n+1)x^n)
如果序列(a)有通项公式，那么它的(OGF)的系数就是通项公式
基本运算
考虑两个序列(a)和(b)的(OGF)，分别是(F(x))和(G(x))，那么有
[F(x)±G(x)=sum_{n}(a_n±b_n)x^n
]
因为(F(x)±G(x))是序列(<a_n±b_n>)的(OGF)
考虑乘法运算，即卷积
[F(x)*G(x)=sum_{n}x^nsum_{i=0}^n a_ib_{n-i}
]
因为(F(x)*G(x))是序列(<sum_{i=0}^n a_ib_{n-i}>)的(OGF)
封闭形式
形式幂级数形式不好表示，考虑转化为封闭形式
(a=<1,1,1,…>)的(OGF F(x)=sum_{ngeq 0}x^n)可以列出
[F(x)=1+x+x^2+…\
xF(x)=x+x^2+x^3+…\
xF(x)+1=F(x)\
F(x)=frac{1}{1-x}
]
这就是(sum_{ngeq 0}x^n)的封闭形式
考虑等比数列(<1,p,p^2,p^3,…>)的普通生成函数(G(x)=sum_{ngeq 0}p^nx^n)，有
[G(x)px+1=G(x)\
G(x)=frac{1}{1-px}
]
例题
(1.a=<0,1,1,1,…>)
[xF(x)+x=F(x)\
F(x)=frac{x}{1-x}\
]
(2.a=<1,0,1,0,1,…>)
[x^2F(x)+1=F(x)\
F(x)=frac{1}{1-x^2}
]
(3.a=<1,2,3,4,…>)
[F(x)=sum_{ngeq 0}(n+1)x^n\
令n=n+1\
F(x)=sum_{ngeq 1}nx^{n-1}\
=sum_{ngeq 0}(x^n)'\
=(frac{1}{1-x})'\
=frac{1}{(1-x)^2}
]
(4.a_n=dbinom{m}{n})
[F(x)=sum_{n}dbinom{m}{n}x^n1^{m-n}\
=(1+x)^m
]
(5.a_n=dbinom{n+m}{n})
归纳法证明：(a_n=frac{1}{(1-x)^{m+1}})
[m=0时,F(x)=frac{1}{1-x}\
m>0时\
frac{1}{(1-x)^{m+1}}=frac{1}{(1-x)^m}frac{1}{1-x}\
=(sum_{ngeq 0}dbinom{m+n-1}{n})(sum_{ngeq 0}x^n)\
=sum_{ngeq 0}(sum_{i=0}^{n}dbinom{m-1+i}{i}x^i*1^{n-i}x^{n-i})\
=sum_{ngeq 0}dbinom{n+m}{n}x^n\
]