象Fibonacci数这样获得数学家们的广泛参与和持续关注，其成果可以说是汗牛充栋。在美国，甚至专门有一本杂志刊载这方面的研究。至于Catalan数，也是组合数学里一个重要的研究对象，我们已经看到，许多计算机科学中的问题都与Catalan有关。值得一提的是，我国清代数学家明安图在其《割圜密率捷法》一书中最先应用了Catalan数，取得优秀的研究成果 。
第5章 生成函数
第一节 引论
问题导入： 投掷一次骰子，出现点数1,2,3,4,5,6的概率均为1/6. 问:连续投掷2次，出现点数和为10的概率为多少？ 问:连续投掷10次，出现的点数之和为30的概率为多少？
我们用x?x2?x3?x5?x6表示投掷一次可能出现点数1，2，3，4，5，6，观察
(x?x2?x3?x5?x6)(x?x2?x3?x5?x6)
从两个括号中分别取出xm和xn，使得xm?xn?x10即为两次投掷分别出现点数m,n，且m?n?10。由此得出，展开式中x的10次方的系数就是满足条件的方法数。
第二节 形式幂级数
定义5.2.1 设A(x)=?akx与B(x)??bkxk是Ｒ上的两个形式幂级数，若对任意
kk?0k?0??k?0，有ak?bk，则称A(x)与B(x)相等，记作A(x)?B(x)。
?k?k定义5.2.2 设?为任意实数，A(x)??akx?R[[x]]，则将?A(x)??(?ak)x
k?0k?0称为?与A(x)的数乘积。
定义5.2.3 设A(x)??akx与B(x)??bkxk是Ｒ上的两个形式幂函数，将A(x)与
kk?0k?0??B(x)相加定义为 ,A(x)?B(x)??(ak?bk)xk，并称A(x)?B(x)为A(x)与B(x)的和，
k?0?把运算“＋”叫做加法。 将A(x)与B(x)相乘定义为
A(x)?B(x)??(akb0?ak?1b1???a0bk)xk
k?0?并称A(x)?B(x)为A(x)和B(x)的积，将运算“?”叫作乘法。
定理5.2.1 集合R[[x]]在上述加法和乘法运算下构成一个整环。
定理5.2.2 对于R[[x]]中的任意一个元素
?A(x)??akkx
k?0A(x)有乘法逆元当且仅当a0?0。
?定义5.2.4 对于任意A(x)??ak?k?1kx?R[[x]]，规定DA(x)??kakx, k?0k?0为A(x)的形式导数。
A(x)的ｎ次形式导数可以递归地定义为：
??D0A(x)?A(x)?DｎA(x)?D(Dn?1A(x)) 形式导数满足如下规则：
(1)D(?A(x)??B(x))??DA(x)??DB(x)； (2)D(A(x)?B(x))?A(x)DB(x)?B(x)DA(x)；
(3)D(An(x))?nAn?1(x)DA(x)。
第三节 形式幂函数
性质1 若
b??0(k?l)k??ak?l(k?l)
则B(x)?xl?A(x)。
性质2 若b?a1l?1kk?l，则B(x)?xl(A(x)??akxk)。
k?0
k性质3 若bx)?A(x)k??ai，则B(i?01?x。
k性质4 若bA(1)?xA(x)?k??ai，则B(x)?。这里，i?01?x?ai是收敛的。
i?0
性质5 若bk?kak，则B(x)?xA?(x)。
称DA(x)
性质6 若bk?
性质7 若ck??ak??bk，则C(x)??ckxk??A(x)??B(x)。
k?0?ak1x，则B(x)??A(t)dt。 k?1x0
性质8 若ck?a0bk?a1bk?1???akb0，则C(x)??ckxk?A(x)?B(x)。
k?0?
2?3x?6x2例1 已知?an?的生成函数为A(x)?，求an。
1?2x
例2 计算级数12?22???n2的和。
第四节 用生成函数求解递推关系
例1 求递推关系
?f(n)?7f(n?1)?12f(n?2), ??f(0)?2,f(1)?7.解： 令
A(x)??f(n)xn，
n?0?利用给定的递推关系，算得：f(n)?3n?4n。
5.4.1 用生成函数求解常系数线性齐次递推关系
定理5.4.1 设
P(x)P(x)是有理分式，且多项式P(x)的次数低于Q(x)的次数，则有Q(x)Q(x)分项表示，且表示是唯一的。
5.4.2 用生成函数求解常系数线性非齐次递推关系
例2 求解递推关系
?f(n)?f(n?1)?n4, ??f(0)?0.
例3 求解递推关系
?f(n)?2f(n?1)?4n?1??f(1)?3.
(n?2)
例4 求解卷积形式的递推关系
?f(n)?f(1)f(n?1)?f(2)f(n?2)???f(n?1)f(1)? ?(n?2)?f(1)?1.?
第五节 生成函数在计数问题中的应用
5.5.1 组合数的生成函数
定理5.5.1 设从ｎ元集合S??a1,a2,?,an?中取ｋ个元素的组合数为bk，若限定元素出现的ai次数集合为Mi(1?i?n)，则该组合数序列的生成函数为 ?(?xm)。
i?1m?Min
例１ 求多重集合Mi????a1,??a2,?,??an?的每个ai至少出现一次的ｋ组合数bk。
5.5.2 排列数的指数型生成函数
定理5.5.2 多重集合Mi????a1,??a2,?,??an?的ｋ排列中，若限定元素ai出现的次数集合为Mi(1?i?n)，则排列数的指数型生成函数
?(?i?1nm?Mixm)。 m!
例２ 多重集合Mi????a1,??a2,?,??an?的ｋ排列数序列的指数行生成函数为
k?xx2nkx (1????)?e?e(nx)??n?1!2!k!k?0i?1n，从而bk?nk。