组合数学课件-第二章第五节指数型母函数

第2章递推关系与母函数2.1递推关系2.2母函数(生成函数)2.3Fibonacci数列2.4优选法与Fibonacci序列的应用2.5母函数的性质2.6线性常系数齐次递推关系2.7关于常系数非齐次递推关系2.8整数的拆分2.9ferrers图像2.10拆分数估计

2.11指数型母函数2.12广义二项式定理2.13应用举例2.14非线性递推关系举例

2.15递推关系解法的补充1第2章递推关系与母函数2.1递推关系12.11：指数型母函数

2.11.1问题的来源对n个互不相同的元素进行全排列，可得n!个不同的排列。

k个不同的元素a1,a2,…,ak作允许重复的排列:如果a1有n1个，a2有n2个，…，ak有nk个，n1+n2+…+nk=n,这样的n个元素进行全排列，不同的排列数为：n!/(n1!n2!…nk!)22.11：指数型母函数2.11.1问题的来源设有k种不同元素，若元素a1最多取n1个，元素a2最多取n2个，……，元素ak最多取nk个，任取r个元素的排列数记为pr,讨论序列{pr}的情况:2.11：指数型母函数3设有k种不同元素，若元素a1最多取n1个，

例15个元素中a1重复了3次，a2重复了2次，从中取r个组合，其组合数为cr，求取1到5的组合序列的母函数。

G(x)=(1+x+x2+x3)(1+x

+x2)=1+2x+3x2+3x3+2x4+x5(1+x1+x12+x13)(1+x2+x22)

展开式中3次方项如下：x1x22+x12x2+x13

x1x22对应的是取一个x1,两个x2,若是作排列,其不同排列数为：2.11：指数型母函数4例15个元素中a1重复了3次，a2重

为了便于计算，利用上述特点，形式地引进函数。

展开后三次方项2.11：指数型母函数5为了便于计算，利用上述特点，形式地引进函数。展开后三

定义：对于序列a0,a1,a2,a3,…定义如下函数为序列{ai}的指数型母函数。2.11：指数型母函数

例5个元素中a1重复了3次，a2重复了2次，从中取r个排列，其排列数为cr，求取1到5的排列序列的母函数。6定义：对于序列a0,a1,a2,a3,…定义如下函数

定理2.11.1：设有k种不同元素，若元素a1最多取n1个，元素a2最多取n2个，……，元素ak最多取nk个，任取r个元素的排列数记为pr,则序列{pr}的指数型母函数为：pr的值为展开式中xr/r!的系数。2.11：指数型母函数7定理2.11.1：设有k种不同元素，若元素a1最

证明：做完乘法，xr项由如下形式的项组成：m1+m2+…+mk=r2.11：指数型母函数略8证明：做完乘法，xr项由如下形式的项组成：m1+

例2由a,b,c,d这4个符号取5个进行排列，要求a出现的次数不超过两次，但不能不出现，b不超过一次，c出现的次数不超过3次，d出现的次数为偶数。求满足上上述条件的排列数。

解：构造母函数Ge(x)。2.11：指数型母函数9例2由a,b,c,d这4个符号取5个进行2.11：指数型母函数1、2、102.11：指数型母函数1、2、10

例3由A,G,C,T这4个符号取n个进行排列，每个字符都可以重复选取，求排列数。

解：构造母函数Ge(x)。排列数是4n。2.11：指数型母函数11例3由A,G,C,T这4个符号取n个进行例4求1,3,5,7,9这5个数字组成的n位数个数，要求其中3出现的次数为偶数，其它数字出现的次数无限制。（用指数型母函数求解）解：设满足条件的r位数的数目为ar,则序列a0,a1,a2,…的母函数为：2.11：指数型母函数12例4求1,3,5,7,9这5个数字组成的2.11：指数型母函数132.11：指数型母函数13例4求1,3,5,7,9这5个数字组成的n位数个数，要求其中3出现的次数为偶数，其它数字出现的次数无限制。（用递推关系求解）解：an=4an-1+(5n-1-an-1)2.11：指数型母函数a1=4an-3an-1=5n/5特解：an=k×5nk=1/214例4求1,3,5,7,9这5个数字组成的2.11：指数型母函数a1=4an-3an-1=5n/5h=1/2152.11：指数型母函数a1=4an-3an-1=5n/5h=例5用红绿蓝三种颜色去涂1n的棋盘，每格涂一种颜色，要求红蓝二色出现的次数均为偶数，求涂色方案数。2.11：指数型母函数16例5用红绿蓝三种颜色去涂1n的棋盘，每n个不同的元素,取m个作有重复的排列,与m个不同的球放进n个有区别的盒子,允许空盒的放法一一对应.1,12,23,31,22,11,33,12,33,2a号球位置,b号球位置.3个不同的元素取两个作有重复的排列2个不同的球,放进3个有区别的盒子ababbaabbabaa,ba,ba,b2.11：指数型母函数17n个不同的元素,取m个作有重复的排列,1,1例5a1,a2,a3,a4为4个不同的元素,取7个作有重复的排列,要求

a1,a2必须出现偶数次,3出现奇数次。2.11：指数型母函数例6a1,a2,…,a7为7个有区别的球放进4个有标志的盒子，要求1，2两盒必须含偶数个球，第3盒含奇数个球。18例5a1,a2,a3,a4为4个不同的元素,例7n个有标志的球，放进m个不同的盒子，允许空盒，问有多少种不同的分配方案？m种不同元素取n个作允许重复的排列是一样的。mn2.11：指数型母函数19例7n个有标志的球，放进m个不同的盒子，允许空盒，

例2.30，2.33n个有标志的球，放进m个不同的盒子，要求无一空盒，问有多少种不同的分配方案？m种元素取n个作允许重复的排列,每一个数都必须至少取一次。2.11：指数型母函数20例2.30，2.33n个有标志的球，放进m个不同的2.11：指数型母函数212.11：指数型母函数21n个球放进m个盒子放法总结:n个球放进m个盒子里，球是否有区别，盒子是否有区别，是否允许空盒，共有八种情况：1、有区别,有区别，有空盒2、有区别,有区别，无空盒22n个球放进m个盒子放法总结:n个球放进m个盒子里，球n个球放进m个盒子里，球是否有区别，盒子是否有区别，是否允许空盒，共有八种情况：3、无区别,有区别，有空盒4、无区别,有区别，无空盒n个球放进m个盒子放法总结:23n个球放进m个盒子里，球是否有区别，盒子是否有区别，n个球放进m个盒子里，球是否有区别，盒子是否有区别，是否允许空盒，共有八种情况：5、无区别,无区别，有空盒6、无区别,无区别，无空盒n个球放进m个盒子放法总结:***24n个球放进m个盒子里，球是否有区别，盒子是否有区别，2.12：广义二项式定理二项式定理252.12：广义二项式定理二项式定理252.15递推关系解法的补充1、母函数法2、迭代法3、归纳法4、置换法5、相加消去法262.15递推关系解法的补充1、母函数法2、迭代法3、归纳例9：求下列递推关系的解解：用置换法：解特征方程可得：2.14递推关系解法的补充27例9：求下列递推关系的解解：用置换法：解特征方程可得：2.12.14递推关系解法的补充282.14递推关系解法的补充282.14递推关系解法的补充292.14递推关系解法的补充29例10：求下列递推关系的解解：1、猜解法：一般解：2.14递推关系解法的补充30例10：求下列递推关系的解解：1、猜解法：一般解：2.14例10：求下列递推关系的解解：2、置换法：令2.14递推关系解法的补充***31例10：求下列递推关系的解解：2、置换法：令2.14递2.48有红、黄、蓝、白球各两个，绿、紫、黑球各三个，从中取10个球，试为有多少种不同的取法。2.14递推关系解法的补充2.49，2.50,2.51,2.78322.48有红、黄、蓝、白球各两个，绿、紫、黑球各三个，从中第2章递推关系与母函数2.1递推关系2.2母函数(生成函数)2.3Fibonacci数列2.4优选法与Fibonacci序列的应用2.5母函数的性质2.6线性常系数齐次递推关系2.7关于常系数非齐次递推关系2.8整数的拆分2.9ferrers图像2.10拆分数估计

2.11指数型母函数2.12广义二项式定理2.13应用举例2.14非线性递推关系举例

2.15递推关系解法的补充33第2章递推关系与母函数2.1递推关系12.11：指数型母函数

2.11.1问题的来源对n个互不相同的元素进行全排列，可得n!个不同的排列。

k个不同的元素a1,a2,…,ak作允许重复的排列:如果a1有n1个，a2有n2个，…，ak有nk个，n1+n2+…+nk=n,这样的n个元素进行全排列，不同的排列数为：n!/(n1!n2!…nk!)342.11：指数型母函数2.11.1问题的来源设有k种不同元素，若元素a1最多取n1个，元素a2最多取n2个，……，元素ak最多取nk个，任取r个元素的排列数记为pr,讨论序列{pr}的情况:2.11：指数型母函数35设有k种不同元素，若元素a1最多取n1个，

例15个元素中a1重复了3次，a2重复了2次，从中取r个组合，其组合数为cr，求取1到5的组合序列的母函数。

G(x)=(1+x+x2+x3)(1+x

+x2)=1+2x+3x2+3x3+2x4+x5(1+x1+x12+x13)(1+x2+x22)

展开式中3次方项如下：x1x22+x12x2+x13

x1x22对应的是取一个x1,两个x2,若是作排列,其不同排列数为：2.11：指数型母函数36例15个元素中a1重复了3次，a2重

为了便于计算，利用上述特点，形式地引进函数。

展开后三次方项2.11：指数型母函数37为了便于计算，利用上述特点，形式地引进函数。展开后三

定义：对于序列a0,a1,a2,a3,…定义如下函数为序列{ai}的指数型母函数。2.11：指数型母函数

例5个元素中a1重复了3次，a2重复了2次，从中取r个排列，其排列数为cr，求取1到5的排列序列的母函数。38定义：对于序列a0,a1,a2,a3,…定义如下函数

定理2.11.1：设有k种不同元素，若元素a1最多取n1个，元素a2最多取n2个，……，元素ak最多取nk个，任取r个元素的排列数记为pr,则序列{pr}的指数型母函数为：pr的值为展开式中xr/r!的系数。2.11：指数型母函数39定理2.11.1：设有k种不同元素，若元素a1最

证明：做完乘法，xr项由如下形式的项组成：m1+m2+…+mk=r2.11：指数型母函数略40证明：做完乘法，xr项由如下形式的项组成：m1+

例2由a,b,c,d这4个符号取5个进行排列，要求a出现的次数不超过两次，但不能不出现，b不超过一次，c出现的次数不超过3次，d出现的次数为偶数。求满足上上述条件的排列数。

解：构造母函数Ge(x)。2.11：指数型母函数41例2由a,b,c,d这4个符号取5个进行2.11：指数型母函数1、2、422.11：指数型母函数1、2、10

例3由A,G,C,T这4个符号取n个进行排列，每个字符都可以重复选取，求排列数。

解：构造母函数Ge(x)。排列数是4n。2.11：指数型母函数43例3由A,G,C,T这4个符号取n个进行例4求1,3,5,7,9这5个数字组成的n位数个数，要求其中3出现的次数为偶数，其它数字出现的次数无限制。（用指数型母函数求解）解：设满足条件的r位数的数目为ar,则序列a0,a1,a2,…的母函数为：2.11：指数型母函数44例4求1,3,5,7,9这5个数字组成的2.11：指数型母函数452.11：指数型母函数13例4求1,3,5,7,9这5个数字组成的n位数个数，要求其中3出现的次数为偶数，其它数字出现的次数无限制。（用递推关系求解）解：an=4an-1+(5n-1-an-1)2.11：指数型母函数a1=4an-3an-1=5n/5特解：an=k×5nk=1/246例4求1,3,5,7,9这5个数字组成的2.11：指数型母函数a1=4an-3an-1=5n/5h=1/2472.11：指数型母函数a1=4an-3an-1=5n/5h=例5用红绿蓝三种颜色去涂1n的棋盘，每格涂一种颜色，要求红蓝二色出现的次数均为偶数，求涂色方案数。2.11：指数型母函数48例5用红绿蓝三种颜色去涂1n的棋盘，每n个不同的元素,取m个作有重复的排列,与m个不同的球放进n个有区别的盒子,允许空盒的放法一一对应.1,12,23,31,22,11,33,12,33,2a号球位置,b号球位置.3个不同的元素取两个作有重复的排列2个不同的球,放进3个有区别的盒子ababbaabbabaa,ba,ba,b2.11：指数型母函数49n个不同的元素,取m个作有重复的排列,1,1例5a1,a2,a3,a4为4个不同的元素,取7个作有重复的排列,要求

a1,a2必须出现偶数次,3出现奇数次。2.11：指数型母函数例6a1,a2,…,a7为7个有区别的球放进4个有标志的盒子，要求1，2两盒必须含偶数个球，第3盒含奇数个球。50例5a1,a2,a3,a4为4个不同的元素,例7n个有标志的球，放进m个不同的盒子，允许空盒，问有多少种不同的分配方案？m种不同元素取n个作允许重复的排列是一样的。mn2.11：指数型母函数51例7n个有标志的球，放进m个不同的盒子，允许空盒，

例2.30，2.33n个有标志的球，放进m个不同的盒子，要求无一空盒，问有多少种不同的分配方案？m种元素取n个作允许重复的排列,每一个数都必须至少取一次。2.11：指数型母函数52例2.30，2.33n个有标志的球，放进m个不同的2.11：指数型母函数532.11：指数型母函数21n个球放进m个盒子放法总结:n个球放进m个盒子里，球是否有区别，盒子是否有区别，是否允许空盒，共有八种情况：1、有区别,有区别，有空盒2、有区别,有区别，无空盒54n个球放进m个盒子放法总结:n个