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

母函数及其应用母函数及其应用母函数及其应用1排列组合问题排列组合问题排列组合问题2例例 有限数列有限数列C(n,r)，r0,1,2,n的普母函数是的普母函数是2.1母函数母函数定定义2.1.1 对于数列于数列an，称无穷级数称无穷级数为该数列的（普通型）母函数，简称为该数列的（普通型）母函数，简称普母函数普母函数或或母函数母函数。同时称。同时称an为为G(x)的的生成数列生成数列。例 有限数列C(n,r)，r0,1,2,n的普3例例 无限数列无限数列1，2，n，的普母函数是的普母函数是2.1母函数母函数例例 无限数列无限数列1，1，1，的普母函数是的普母函数是例 无限数列1，2，n，的普母函数是2.1母函数42.1母函数母函数2.1母函数52.1母函数母函数2.1母函数62.1母函数母函数2.1母函数72.1母函数母函数2.1母函数82.1母函数母函数2.1母函数92.1母函数母函数2.1母函数102.1母函数母函数例例 设有设有2个红球，个红球，1个黑球，个黑球，1个白球，问个白球，问（1）共有多少种不同的选取方法，试加以枚举？）共有多少种不同的选取方法，试加以枚举？（2）若每次从中任取）若每次从中任取3个，有多少种不同的取法？个，有多少种不同的取法？解解：设想用：设想用x，y，z分别代表红、黑、白三种球，两个红球的取分别代表红、黑、白三种球，两个红球的取法与法与x0，x1，x2对应起来，即红球的可能取法与对应起来，即红球的可能取法与1xx2中中x的的各次幂一一对应，亦即各次幂一一对应，亦即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个白球，问解：设112.1母函数母函数例例 设有设有2个红球，个红球，1个黑球，个黑球，1个白球，问个白球，问（1）共有多少种不同的选取方法，试加以枚举？）共有多少种不同的选取方法，试加以枚举？（2）若每次从中任取）若每次从中任取3个，有多少种不同的取法？个，有多少种不同的取法？解解：若只考虑每次取：若只考虑每次取3个的方案数，而不需枚举，则令个的方案数，而不需枚举，则令yx，zx，便有便有G(x)(1xx2)(1x)(1x)13x4 x23 x3 x4由由x3的系数即得所求方案数为的系数即得所求方案数为3。2.1母函数例 设有2个红球，1个黑球，1个白球，问解：若122.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。注意到对注意到对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的解数132.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 只需要多项式只需要多项式(1+x+x2+x3+x4+x5)2展开式中展开式中x5的系数就等于的系数就等于x20的系数，由多项式定理：的系数，由多项式定理：C20=6.2.1母函数例 求不定方程k1+k2+k3+k4=20的解数142.1母函数母函数例例 求不定方程求不定方程3 3k1+4k2+2k3+5k4=n的非负整数解的个数。的非负整数解的个数。2.1母函数例 求不定方程3k1+4k2+2k3+5k4=n15例例 确定苹果、香蕉、橘子和梨的确定苹果、香蕉、橘子和梨的n-组合的个数，其中在每个组合的个数，其中在每个n-组合中要求：苹果的个数必须是偶数，香蕉的个数必须是组合中要求：苹果的个数必须是偶数，香蕉的个数必须是5的倍的倍数，橘子的个数最多数，橘子的个数最多4个，梨的个数为个，梨的个数为0或或1个。个。2.1母函数母函数解解：生成函数为：生成函数为:例 确定苹果、香蕉、橘子和梨的n-组合的个数，其中在每个n-16例例 从从n双互不相同的五指袜子中取出双互不相同的五指袜子中取出r只，要求没有任何两只是只，要求没有任何两只是成对的，共有多少种不同的取法？成对的，共有多少种不同的取法？解解：生成函数为：生成函数为:例例 从从n双互不相同的袜子（每双袜子中的两只相同）中取出双互不相同的袜子（每双袜子中的两只相同）中取出r只，只，要求没有任何两只是成对的，共有多少种不同的取法？要求没有任何两只是成对的，共有多少种不同的取法？2.1母函数母函数解解：生成函数为：生成函数为:例 从n双互不相同的五指袜子中取出r只，要求没有任何两只是成17解解：例例 某班有甲乙丙三个小组，人数分别为某班有甲乙丙三个小组，人数分别为5，6，9。把。把5本相同的本相同的书分给甲、乙、丙书分给甲、乙、丙3个小组，再发到个人手上，每人最多发一本。个小组，再发到个人手上，每人最多发一本。考虑将分给某组的某本书发给该组的同学考虑将分给某组的某本书发给该组的同学A与将其发给同学与将其发给同学B被被认为是不同的分法（每个同学最多一本），而且甲、乙两组最认为是不同的分法（每个同学最多一本），而且甲、乙两组最少少1本，甲组最多本，甲组最多5本，乙组最多本，乙组最多6本，丙组最少本，丙组最少2本，最多本，最多9本，本，问有多少种不同的分配方案？问有多少种不同的分配方案？2.1母函数母函数解：例 某班有甲乙丙三个小组，人数分别为5，6，9。把5本相182.1母函数母函数2.1母函数192.1母函数母函数2.1母函数20解解：例例 甲、乙、丙甲、乙、丙3人把人把n（n3）本相同的书搬到办公室，要求甲）本相同的书搬到办公室，要求甲和乙搬的本数一样多，问共有多少种分配的方法？和乙搬的本数一样多，问共有多少种分配的方法？2.1母函数母函数解：例 甲、乙、丙3人把n（n3）本相同的书搬到办公室，要212.1母函数母函数2.1母函数222.1母函数母函数2.1母函数232.1母函数母函数2.1母函数242.1母函数母函数2.1母函数252.1母函数母函数2.1母函数262.1母函数母函数2.1母函数272.1母函数母函数2.1母函数282.1母函数母函数例、一粒骰子连续投掷例、一粒骰子连续投掷2次，求出现点数之和为次，求出现点数之和为10的概率。的概率。2.1母函数例、一粒骰子连续投掷2次，求出现点数之和为10的292.1母函数母函数例、一粒骰子连续投掷例、一粒骰子连续投掷10次，求出现点数之和为次，求出现点数之和为30的概率。的概率。2.1母函数例、一粒骰子连续投掷10次，求出现点数之和为30302.2母函数的性质母函数的性质2.2母函数的性质312.2母函数的性质母函数的性质2.2母函数的性质322.2母函数的性质母函数的性质2.2母函数的性质332.2母函数的性质母函数的性质2.2母函数的性质342.2母函数的性质母函数的性质2.2母函数的性质352.2母函数的性质母函数的性质2.2母函数的性质362.2母函数的性质母函数的性质2.2母函数的性质372.2母函数的性质母函数的性质2.2母函数的性质382.2母函数的性质母函数的性质2.2母函数的性质392.2母函数的性质母函数的性质2.2母函数的性质402.2母函数的性质母函数的性质2.2母函数的性质412.3指数型母函数指数型母函数回顾回顾：普通型母函数较好地解决了各种组合的计数问题。：普通型母函数较好地解决了各种组合的计数问题。启发启发：对排列问题也采用母函数方式。尤其是：对排列问题也采用母函数方式。尤其是n个不尽相异元个不尽相异元素中取素中取r个的排列问题。个的排列问题。观察观察n集的集的r无重排列数和无重排列数和r无重组合数之间有如下关系：无重组合数之间有如下关系：由此受到启发，排列数数列的母函数应该采用形如由此受到启发，排列数数列的母函数应该采用形如 的幂级数为好。的幂级数为好。由于由于这种种类型的型的幂级数很象指数函数数很象指数函数eax的展开式，故取名的展开式，故取名为指数型母函数。指数型母函数。2.3指数型母函数回顾：普通型母函数较好地解决了各种组合的计422.3指数型母函数指数型母函数2.3指数型母函数432.3指数型母函数指数型母函数2.3指数型母函数442.3指数型母函数指数型母函数例例、盒中有盒中有3个红球，个红球，2个黄球，个黄球，3个篮球，从中取个篮球，从中取4个球，排个球，排成一列，问共有多少种不同排列方案？成一列，问共有多少种不同排列方案？2.3指数型母函数例、盒中有3个红球，2个黄球，3个篮球，452.3指数型母函数指数型母函数例例、盒中有盒中有3个红球，个红球，2个黄球，个黄球，3个篮球，从中取个篮球，从中取4个球，排个球，排成一列，问共有多少种不同排列方案？成一列，问共有多少种不同排列方案？所以，从中取所以，从中取4个球的排列方案有个球的排列方案有70种。种。2.3指数型母函数例、盒中有3个红球，2个黄球，3个篮球，462.3指数型母函数指数型母函数2.3指数型母函数472.3指数型母函数指数型母函数2.3指数型母函数482.3指数型母函数指数型母函数2.3指数型母函数492.3指数型母函数指数型母函数2.3指数型母函数502.3指数型母函数指数型母函数例例、五个数字、五个数字1，1，2，2，3能组成多少个四位数？能组成多少个四位数？2.3指数型母函数例、五个数字1，1，2，2，3能组成多少个512.3指数型母函数指数型母函数例例、求、求1，3，5，7，9五个数字组成的五个数字组成的n位数的个数（每个数位数的个数（每个数字可重复出现），要求其中字可重复出现），要求其中3，7出现的次数为偶数，出现的次数为偶数，1，5，9出现的次数不加限制。出现的次数不加限制。2.3指数型母函数例、求1，3，5，7，9五个数字组成的n位522.3指数型母函数指数型母函数例例、求、求1，3，5，7，9五个数字组成的五个数字组成的n位数的个数（每个数位数的个数（每个数字可重复出现），要求字可重复出现），要求1、3、7出现的次数一样多，出现的次数一样多，5和和9出现的次数不加限制。求这样的出现的次数不加限制。求这样的n位数的个数。位数的个数。2.3指数型母函数例、求1，3，5，7，9五个数字组成的n位532.3指数型母函数指数型母函数2.3指数型母函数542.3指数型母函数指数型母函数例例 从从n双互不相同的五指袜子中取出双互不相同的五指袜子中取出r只并排成一列，要求没有只并排成一列，要求没有任何两只是成对的，共有多少种不同的排法？任何两只是成对的，共有多少种不同的排法？解解：生成函数为：生成函数为:例例 从从n双互不相同的袜子（每双袜子中的两只相同）中取出双互不相同的袜子（每双袜子中的两只相同）中取出r只只并排成一列，要求没有任何两只是成对的，共有多少种不同的并排成一列，要求没有任何两只是成对的，共有多少种不同的排法？排法？解解：生成函数为：生成函数为:2.3指数型母函数例 从n双互不相同的五指袜子中取出r只并排552.3指数型母函数指数型母函数2.3指数型母函数562.3指数型母函数指数型母函数例例、确定每位数字都是奇数的、确定每位数字都是奇数的n位数的个数位数的个数an，其中，其中1和和3出现出现偶数次。偶数次。2.3指数型母函数例、确定每位数字都是奇数的n位数的个数an572.3指数型母函数指数型母函数例例、确定每位数字都是奇数的、确定每位数字都是奇数的n位数的个数位数的个数an，其中，其中1和和3出现出现偶数次。偶数次。2.3指数型母函数例、确定每位数字都是奇数的n位数的个数an58谢谢！谢谢！谢谢！59