生成函数与排列组合

《生成函数与排列组合》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、例1解是什么数列的生成函数？这是过去没有解决的组合问题！§5生成函数求解组合问题例2解S的1组合数=3：a,b,cS的2组合数=5：2a,2c,ab,ac,bcS的3组合数=5：2ab,2ac,b2c,a2c,abcS的4组合数=3：2a2c,2abc,ab2cS的5组合数=1：2ab2cS={2a,b,2c},求S的所有n组合数。例3解用n个水果组成一只个果篮。果篮中可以装4种水果：苹果为偶数，香蕉为5的倍数，至多有4个桔子，至多有一个西瓜。可以有多少种装法？例4解用n个水果组成一只个果篮。果篮中可以装4种水果：苹果为偶数，香蕉为奇数，至多有4个桔子

2、，至少有一个西瓜。可以有多少种装法？例5解某单位有8男5女，从中选出一个小组。要求男士为偶数，女士至少2人，有多少种组合方式？解请注意：每个人是有区别的！例6解K是偶数，N也是偶数K是奇数，N也是奇数例7解例8解我们有1，5，10，25，50等硬币。50分硬币只有1个，25分硬币有只有3个，其它硬币有很多。用这些硬币恰好组成n分钱，共有多少种方法？例9解拆分数问题把n拆分成m个正整数之和，共有多少种拆分方法？一、问题的提出§6用指数生成函数求解排列问题二、指数生成函数例1例2排列数：例3等比数列：三、多重集的排列先考虑一个特殊问题：即3个红球、2个绿球

3、、3个兰球的各种排列。（1）求出所有组合：（2）求出具体的组合成分——三元展开式：所有2组合所有3组合所有4组合（3）求出每个4组合的排列（4）考虑指数生成函数令前式中的4次项化为：例1解S={2a,b,2c},求S的所有r排列数例2解用1,2,3,4组成一个五位数，1出现至少一次，至多两次；2出现不超过1次；3出现的最多3次；4出现的次数必须是偶数这样的五位数共有多少个？例3解用1,3,5,7,9组成一个n位数，要求3,7出现偶数次。共有多少个这样的n位数？可以把重复数取为无穷。例4解用红、白、蓝给1xn棋盘着色，要求红格必须为偶数。共有多少种着色方

4、法？可以把重复数取为无穷。例5解用红、白、蓝给1xn棋盘着色，要求红格必须为偶数，至少有一个蓝格。共有多少种着色方法？习题（第4版）P18229，30（3，6），31，36，37，42，43，45