组合数学第二章母函数课件.ppt

1、母函数及其应用母函数及其应用排列组合问题排列组合问题例例 有限数列有限数列C(n,r)，r0,1,2,n的普母函数是的普母函数是2.1母函数母函数定义定义2.1.1 对于数列对于数列an，称无穷级数称无穷级数为该数列的（普通型）母函数，简称为该数列的（普通型）母函数，简称普母函数普母函数或或母函数母函数。同时称。同时称an为为G(x)的的生成数列生成数列。0nnnxaxGnnnnnnxCxCxCC 2210 nx 1例例 无限数列无限数列1，2，n，的普母函数是的普母函数是2.1母函数母函数 nxnxx)1(3212 nxxx21x 11例例 无限数列无限数列1，1，1，的普母函数是的普母函数

2、是2)1(1x 2.1母函数母函数2.1母函数母函数2.1母函数母函数2.1母函数母函数2.1母函数母函数2.1母函数母函数2.1母函数母函数例例 设有设有2个红球，个红球，1个黑球，个黑球，1个白球，问个白球，问（1）共有多少种不同的选取方法，试加以枚举？）共有多少种不同的选取方法，试加以枚举？（2）若每次从中任取）若每次从中任取3个，有多少种不同的取法？个，有多少种不同的取法？解解：设想用：设想用x，y，z分别代表红、黑、白三种球，两个红球的取分别代表红、黑、白三种球，两个红球的取法与法与x0，x1，x2对应起来，即红球的可能取法与对应起来，即红球的可能取法与1xx2中中x的的各次幂一一对

3、应，亦即各次幂一一对应，亦即x01表示不取，表示不取，x表示取表示取1个红球，个红球，x2表表示取两个。对其它球，依此类推。则母函数示取两个。对其它球，依此类推。则母函数 G(x,y,z)(1xx2)(1y)(1z)1(xyz)(x2xyxzyz)(x2yx2zxyz)(x2yz)若令若令xyz1，就得所有不同的选取方案总数为，就得所有不同的选取方案总数为G(1,1,1)13431122.1母函数母函数例例 设有设有2个红球，个红球，1个黑球，个黑球，1个白球，问个白球，问（1）共有多少种不同的选取方法，试加以枚举？）共有多少种不同的选取方法，试加以枚举？（2）若每次从中任取）若每次从中任取3

4、个，有多少种不同的取法？个，有多少种不同的取法？解解：若只考虑每次取：若只考虑每次取3个的方案数，而不需枚举，则令个的方案数，而不需枚举，则令yx，zx，便有便有G(x)(1xx2)(1x)(1x)13x4 x23 x3 x4由由x3的系数即得所求方案数为的系数即得所求方案数为3。2.1母函数母函数例例 求不定方程求不定方程k1+k2+k3+k4=20的解数。其中的解数。其中,限制限制k1可取可取0,2,4;k2可取可取1,3,5;k3可取可取6,7;k4可取可取8,9。解解：设不定方程：设不定方程k1+k2+k3+k4=k的解组数目为的解组数目为ck，本例中，本例中m=4,k=20。注意到对

5、注意到对ki(i=1,2,3,4)的限制，序列的限制，序列 ck 对应的生成函数为对应的生成函数为:G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)2.1母函数母函数例例 求不定方程求不定方程k1+k2+k3+k4=20的解数。其中的解数。其中,限制限制k1可取可取0,2,4;k2可取可取1,3,5;k3可取可取6,7;k4可取可取8,9。G(x)=(1+x2+x4)(x+x3+x5)(x6+x7)(x8+x9)=(1+x2+x4)(1+x2+x4)x(1+x)x6(1+x)x8 =(1+x2+x4)2(1+x)2x15=(1+x+x2+x3+x4+x5)2x15 只

6、需要多项式只需要多项式(1+x+x2+x3+x4+x5)2展开式中展开式中x5的系数就等于的系数就等于x20的系数，由多项式定理：的系数，由多项式定理：C20=6.2.1母函数母函数例例 求不定方程求不定方程3 3k1+4k2+2k3+5k4=n的非负整数解的个数。的非负整数解的个数。542310542846311111111.)1.)(1(.)1.)(1()(xxxxxxxxxxxxxg例例 确定苹果、香蕉、橘子和梨的确定苹果、香蕉、橘子和梨的n-组合的个数，其中在每个组合的个数，其中在每个n-组合中要求：苹果的个数必须是偶数，香蕉的个数必须是组合中要求：苹果的个数必须是偶数，香蕉的个数必须

7、是5的倍的倍数，橘子的个数最多数，橘子的个数最多4个，梨的个数为个，梨的个数为0或或1个。个。2.1母函数母函数)1)(1.)(.)(1()(4325042xxxxxxxxxxG xxxxx 1111111552 211x 解解：生成函数为：生成函数为:01nnxn例例 从从n双互不相同的五指袜子中取出双互不相同的五指袜子中取出r只，要求没有任何两只是只，要求没有任何两只是成对的，共有多少种不同的取法？成对的，共有多少种不同的取法？解解：生成函数为：生成函数为:例例 从从n双互不相同的袜子（每双袜子中的两只相同）中取出双互不相同的袜子（每双袜子中的两只相同）中取出r只，只，要求没有任何两只是成

8、对的，共有多少种不同的取法？要求没有任何两只是成对的，共有多少种不同的取法？2.1母函数母函数 0,nrxrnCnxxG)1()()(12)nG xx解解：生成函数为：生成函数为:0,2rrnC n rx 解解：例例 某班有甲乙丙三个小组，人数分别为某班有甲乙丙三个小组，人数分别为5，6，9。把。把5本相同的本相同的书分给甲、乙、丙书分给甲、乙、丙3个小组，再发到个人手上，每人最多发一本。个小组，再发到个人手上，每人最多发一本。考虑将分给某组的某本书发给该组的同学考虑将分给某组的某本书发给该组的同学A与将其发给同学与将其发给同学B被被认为是不同的分法（每个同学最多一本），而且甲、乙两组最认为是

9、不同的分法（每个同学最多一本），而且甲、乙两组最少少1本，甲组最多本，甲组最多5本，乙组最本，乙组最多多6本，丙组最少本，丙组最少2本，最多本，最多9本，本，问有多少种不同的分配方案？问有多少种不同的分配方案？2.1母函数母函数2.1母函数母函数 926151965)(iiiiiixixixixG2054996655291625292615391615291615xxx 205473801080 xxx 2.1母函数母函数解解：例例 甲、乙、丙甲、乙、丙3人把人把n（n3）本相同的书搬到办公室，要求甲）本相同的书搬到办公室，要求甲和乙搬的本数一样多，问共有多少种分配的方法？和乙搬的本数一样多，

10、问共有多少种分配的方法？2.1母函数母函数 kkxxxxxxxG224211)(xx 1112 2112111411141xxx 0141nnnx 041nnx 0121nnxnn 041121nnnxn 021nnxn2.1母函数母函数2.1母函数母函数2.1母函数母函数2.1母函数母函数2.1母函数母函数2.1母函数母函数542310542846311111111.)1.)(1(.)1.)(1()(xxxxxxxxxxxxxG 2.1母函数母函数2.1母函数母函数例、一粒骰子连续投掷例、一粒骰子连续投掷2次，求出现点数之和为次，求出现点数之和为10的概率。的概率。1010876543212

11、620126222622623)69()987654321)(21(12)21()1()1()()(xxxxxxxxxxxxxxjjxxxxxxxxxxGjj2.1母函数母函数例、一粒骰子连续投掷例、一粒骰子连续投掷10次，求出现点数之和为次，求出现点数之和为30的概率。的概率。30061001010610106231021121081711014232029910)1(11)()(xxjjxjxxxxxxxxGjjjjj2.2母函数的性质母函数的性质2.2母函数的性质母函数的性质2.2母函数的性质母函数的性质2.2母函数的性质母函数的性质2.2母函数的性质母函数的性质2.2母函数的性质母函数

12、的性质2.2母函数的性质母函数的性质2.2母函数的性质母函数的性质2.2母函数的性质母函数的性质2.2母函数的性质母函数的性质2.2母函数的性质母函数的性质2.3指数型母函数指数型母函数回顾回顾：普通型母函数较好地解决了各种组合的计数问题。：普通型母函数较好地解决了各种组合的计数问题。启发启发：对排列问题也采用母函数方式。尤其是：对排列问题也采用母函数方式。尤其是n个不尽相异元个不尽相异元素中取素中取r个的排列问题。个的排列问题。观察观察n集的集的r无重排列数和无重排列数和r无重组合数之间有如下关系：无重组合数之间有如下关系：由此受到启发，排列数数列的母函数应该采用形如由此受到启发，排列数数列

13、的母函数应该采用形如 0!kkkkxa的幂级数为好。的幂级数为好。由于这种类型的幂级数很象指数函数由于这种类型的幂级数很象指数函数eax的展开式，故取名为指数型母函数。的展开式，故取名为指数型母函数。2.3指数型母函数指数型母函数2.3指数型母函数指数型母函数2.3指数型母函数指数型母函数例例、盒中有盒中有3个红球，个红球，2个黄球，个黄球，3个篮球，从中取个篮球，从中取4个球，个球，排成一列，问共有多少种不同排列方案？排成一列，问共有多少种不同排列方案？2.3指数型母函数指数型母函数例例、盒中有盒中有3个红球，个红球，2个黄球，个黄球，3个篮球，从中取个篮球，从中取4个球，个球，排成一列，问

14、共有多少种不同排列方案？排成一列，问共有多少种不同排列方案？所以，从中取所以，从中取4个球的排列方案有个球的排列方案有70种。种。2.3指数型母函数指数型母函数2.3指数型母函数指数型母函数2.3指数型母函数指数型母函数2.3指数型母函数指数型母函数2.3指数型母函数指数型母函数例例、五个数字、五个数字1，1，2，2，3能组成多少个四位数？能组成多少个四位数？2.3指数型母函数指数型母函数例例、求、求1，3，5，7，9五个数字组成的五个数字组成的n位数的个数（每个数位数的个数（每个数字可重复出现），要求其中字可重复出现），要求其中3，7出现的次数为偶数，出现的次数为偶数，1，5，9出现的次数不

15、加限制。出现的次数不加限制。2.3指数型母函数指数型母函数例例、求、求1，3，5，7，9五个数字组成的五个数字组成的n位数的个数（每个数位数的个数（每个数字可重复出现），要求字可重复出现），要求1、3、7出现的次数一样多，出现的次数一样多，5和和9出现的次数不加限制。求这样的出现的次数不加限制。求这样的n位数的个数。位数的个数。2.3指数型母函数指数型母函数2.3指数型母函数指数型母函数例例 从从n双互不相同的五指袜子中取出双互不相同的五指袜子中取出r只并排成一列，要求没有只并排成一列，要求没有任何两只是成对的，共有多少种不同的排法？任何两只是成对的，共有多少种不同的排法？解解：生成函数为：生

16、成函数为:例例 从从n双互不相同的袜子（每双袜子中的两只相同）中取出双互不相同的袜子（每双袜子中的两只相同）中取出r只只并排成一列，要求没有任何两只是成对的，共有多少种不同的并排成一列，要求没有任何两只是成对的，共有多少种不同的排法？排法？00!,)1()(nrnrnerxrnPxrnCxxG解解：生成函数为：生成函数为:012!2,)1()(nrrnerxrnPxPxG2.3指数型母函数指数型母函数2.3指数型母函数指数型母函数例例、确定每位数字都是奇数的、确定每位数字都是奇数的n位数的个数位数的个数an，其中，其中1和和3出现出现偶数次。偶数次。xxxxxxxxxxxxexxxxeeeee

17、eeeeeeeexgeexxxxxexxxexxxxxg)12(41)1(412)()()2()(2.!4!21.!3!21.;!3!21.)!21(.)!4!21()(2422232)(42323232242)(则则由由于于2.3指数型母函数指数型母函数例例、确定每位数字都是奇数的、确定每位数字都是奇数的n位数的个数位数的个数an，其中，其中1和和3出现出现偶数次。偶数次。)0(41325!)41325(!)1325(41)!32!5(41)2(41)12(41)(000003524)(nhnxnxnxnxnxeeeeeexgnnnnnnnnnnnnnnnnnnnxxxxxxe因此序列的通项谢谢！谢谢！