《生成函数与排列组合资料教程》由会员分享，可在线阅读，更多相关《生成函数与排列组合资料教程（23页珍藏版）》请在金锄头文库上搜索。
1、例1,解,是什么数列的生成函数？,这是过去没有解决的组合问题！,5 生成函数求解组合问题,例2,解,S 的1组合数=3：a, b, c,S 的2组合数=5：2a, 2c, ab, ac, bc,S 的3组合数=5：2ab, 2ac, b2c, a2c, abc,S 的4组合数=3：2a2c, 2abc, ab2c,S 的5组合数=1：2ab2c,S =2a, b,2c , 求S 的所有n 组合数。,例4,解,用n个水果组成一只个果篮。果篮中可以装4种水果：苹果为偶数，香蕉为奇数，至多有4个桔子，至少有一个西瓜。可以有多少种装法？,例5,解,某单位有8男5女，从中选出一个小组。要求男士为偶数，女
2、士至少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个兰球的各种排列。,（1）求出所有组合：,（2）求出具体的组合成分 三元展开式
3、：,所有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 棋盘着色，要求红格必须为偶数。共有多少种着色方法？,可以把重复数取为无穷。,例5,解,用红、白、蓝给 1xn 棋盘着色，要求红格必须为偶数，至少有一个蓝格。 共有多少种着色方法？,习题（第4版）P182,29，30（3，6），31，36，37， 42，43，45,
