05-3 第五章 生成函数3.pptx

第1页：封面

第五章生成函数5.1生成函数的定义和性质5.2组合数的生成函数5.3指数型生成函数与多重集的排列数5.4Catalan数列与Stirling数列的生成函数5.5分拆数的生成函数

第2页：有序分拆

§5.5.1有序分拆定理5.5.1对于n的k有序分拆其k有序分拆数数列的生成函数是这个定理等价于如下分配模型：即把n个相同的球放入k个不同的盒子里，第i个盒的容量为，且使每盒非空的方案数为

第3页：推论5.5.1 若对n的k有序分拆的各分

推论5.5.1若对n的k有序分拆的各分量()没有限制，则其k有序分拆数数列的生成函数是，且

第4页：无序分拆

§5.5.2无序分拆在3.6节中可知无序分拆和有序分拆的区别在于是否考虑分拆后的各分量的顺序，将n分拆为k个分部（每一分部的大小不受限制）的分拆数等于将n分拆为最大分部为k（分部个数不限）的分拆数，该分拆数也记为

第5页：定理5.5.2 令B(n)表示正整数的所

定理5.5.2令B(n)表示正整数的所有分拆数，Bk(n)表示n的各分部量都不超过k的分拆数，则它们相应的生成函数分别为(1)(2)(3)

第6页：（1）等于不定方程的非负整数解

（1）等于不定方程的非负整数解的个数。

因此其分拆数列的生成函数为其中展开式中的系数即为n的最大分项不超过k的分拆个数。

第7页：（2）根据定理3.6.3知

（2）根据定理3.6.3知，将n分拆为k个分部（每一分部的大小不受限制）的分拆数等于将n分拆为最大分部为k（分部个数不限）的分拆数，其分拆数相当于求方程的整数解的个数，其生成函数为

第8页：其中展开式中的系数即为n的最

其中展开式中的系数即为n的最大分项等于k的分拆个数容易证明：，因此若，则，因此当，它们对应的生成函数的系数为零，所以

第9页：（3）等于不定方程的非负整数解

（3）等于不定方程的非负整数解的个数。

因此其分拆数列的生成函数为

第10页：推论5.5.2 n的各分部量两两互不

推论5.5.2n的各分部量两两互不相同的分拆数等于n的各分部量是奇数的分拆数。

证明n的各分部量两两互不相同的分拆数的生成函数为而显然是n的各分部量是奇数的分拆数数列的生成函数，因此结论成立.

第11页：例5.5.1 有多少种不同的方案？解这是

例5.5.1用1角、2角、3角的邮票贴出面值6角，求有多少种不同的方案？

解这是可重复的无序分拆，相应的生成函数为显然所求为的系数，为7，说明贴出6角面值的方案有7种。

具体为：6= 1 + 1 + 1 + 1，6 = 2 + 2 + 2，6 = 2 + 2 + 1 + 1，6=2 + 1 + 1 + 1 + 1，6=3 + 3，6=3 + 2 + 1，6=3 + 1 + 1 + 1.例5.5.1中，若考虑不同面值贴的顺序，则有多少种方案。

此问题留作习题