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