生成函数与排列组合.ppt

01020304例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个桔子，至少有一个西瓜。可以有多少种装法？例5解某单位有8男5女，从中选出一个小组。要求男士为偶数，女士至少2人，有多少种组合方式？解请注意：每个人是有区别的！例6解K是偶数，N也是偶数K是奇数，N也是奇数例7解例8解我们有1，5，10，25，50等硬币。50分硬币只有1个，25分硬币有只有3个，其它硬币有很多。用这些硬币恰好组成n分钱，共有多少种方法？1例92解3拆分数问题4把n拆分成m个正整数之和，共有多少种拆分方法？01问题的提出026用指数生成函数求解排列问题指数生成函数例1例2排列数：例3等比数列：01求出所有组合：02先考虑一个特殊问题：即3个红球、2个绿球、3个兰球的各种排列。多重集的排列求出具体的组合成分——三元展开式：所有3组合所有2组合所有4组合求出每个4组合的排列令前式中的4次项化为：考虑指数生成函数