1、1第第2章章 递推关系与母函数递推关系与母函数 2.1 2.1 递推关系递推关系 2.2 2.2 母函数母函数(生成函数生成函数)2.3 Fibonacci 2.3 Fibonacci数列数列 2.4 2.4 优选法与优选法与FibonacciFibonacci序列的应用序列的应用 2.5 2.5 母函数的性质母函数的性质 2.6 2.6 线性常系数齐次递推关系线性常系数齐次递推关系 2.7 2.7 关于常系数非齐次递推关系关于常系数非齐次递推关系 2.8 2.8 整数的拆分整数的拆分 2.9 ferrers2.9 ferrers图像图像 2.10 2.10 拆分数估计拆分数估计 2.11 2
2、.11 指数型母函数指数型母函数 2.12 2.12 广义二项式定理广义二项式定理 2.13 2.13 应用举例应用举例 2.14 2.14 非线性递推关系举例非线性递推关系举例 2.15 2.15 递推关系解法的补充递推关系解法的补充22.11：指数型母函数：指数型母函数 2.11.1 2.11.1 问题的来源问题的来源 对对n n个互不相同的元素进行全排列，个互不相同的元素进行全排列，可得可得n!n!个不同的排列。个不同的排列。k k个不同的元素个不同的元素a a1 1,a,a2 2,a,ak k作允许重复作允许重复的排列的排列:如果如果a a1 1有有n n1 1个，个，a a2 2有有
3、n n2 2个，个，a ak k有有n nk k个，个，n n1 1+n+n2 2+n+nk k=n,=n,这样的这样的n n个元素进行全排列，不同的排个元素进行全排列，不同的排列数为：列数为：n!/(nn!/(n1 1!n!n2 2!n!nk k!)!)3 设有设有k种不同元素，若元素种不同元素，若元素a1最多最多取取n1个，元素个，元素a2 最多取最多取n2个，个，元，元素素ak最多取最多取nk 个，任取个，任取r个元素的排列个元素的排列数记为数记为pr,讨论序列讨论序列pr的情况的情况:2.11：指数型母函数：指数型母函数4 例例1 5个元素中个元素中a1重复了重复了3次，次，a2重复了
4、重复了2次，次，从中取从中取r个组合，其组合数为个组合，其组合数为cr，求取，求取1到到5的组合的组合序列的母函数。序列的母函数。G(x)=(1+x+x2+x3)(1+x+x2)=1+2x+3 x2+3 x3+2 x4+x5(1+x1+x12+x13)(1+x2+x22)展开式中展开式中3 3次方项如下：次方项如下：x1x22+x12x2+x13 x1x22对应的是取一个对应的是取一个x1,两个两个x2,若是作排若是作排列列,其不同排列数为：其不同排列数为：3!2!1!33!1!2!31!3!32.11：指数型母函数：指数型母函数5 为了便于计算，利用上述特点，形式地引进函数。为了便于计算，利
5、用上述特点，形式地引进函数。)!2!11)(!3!2!11()(G22231211exxxxxx!3!1!2!2!131221221xxxxx 展开后三次方项展开后三次方项3)!31!1!21!2!11(x)!3!3!1!2!3!2!1!3()!2!11)(!3!2!11()(G232exxxxxx!3)!3!3!1!2!3!2!1!3(3x2.11：指数型母函数：指数型母函数6 定义：对于序列定义：对于序列a0,a1,a2,a3,定义如下函数定义如下函数为序列为序列ai的指数型母函数。的指数型母函数。.!3!2!1)(G332210exaxaxaax2.11：指数型母函数：指数型母函数 例例
6、 5个元素中个元素中a1重复了重复了3次，次，a2重复了重复了2次，次，从中取从中取r个排列，其排列数为个排列，其排列数为cr，求取，求取1到到5的排列的排列序列的母函数。序列的母函数。)!2!11)(!3!2!11()(G232exxxxxx!3)!3!3!1!2!3!2!1!3(3x7 定理定理2.11.1：设有：设有k种不同元素，若元素种不同元素，若元素a1最多最多取取n1个，元素个，元素a2 最多取最多取n2个，个，元素，元素ak最多取最多取nk 个，任取个，任取r个元素的排列数记为个元素的排列数记为pr,则序列则序列pr的的指数型母函数为：指数型母函数为：)!.!21!1(.)!.!
7、21!1.()!.!21!1()(2221221knnnenxxxnxxxnxxxxGkpr的值为展开式中的值为展开式中xr/r!的系数。的系数。2.11：指数型母函数：指数型母函数8 证明：做完乘法，证明：做完乘法，xr项由如下形式的项组成：项由如下形式的项组成：kmmmmxmxmxk.2121m1+m2+mk=r2.11：指数型母函数：指数型母函数krmmmx.21!.!21rxmmmrrk项的系数为!rxrkmmmr.!21略略9 例例2 由由a,b,c,d这这4个符号取个符号取5个进行排列，要求个进行排列，要求a出现的次数不超过两次，但不能不出现，出现的次数不超过两次，但不能不出现，b
8、不超过不超过一次，一次，c出现的次数不超过出现的次数不超过3次，次，d出现的次数为偶出现的次数为偶数。求满足上上述条件的排列数。数。求满足上上述条件的排列数。解：构造母函数解：构造母函数Ge(x)。a )!2!1()(G2exxx b )!11(x c )!3!2!11(32xxxd )!4!21(42xx!1012600!97650!8140!71785!6645!5215!464!318!25!11098765432xxxxxxxxxx2.11：指数型母函数：指数型母函数10.!3!2!1132xxxex.!3!2!113322xkxkxkekx2.11：指数型母函数：指数型母函数1、2、
9、.!3!2!1132xxxex.!4!21242xxeexx.!3!123xxeexx11 例例3 由由A,G,C,T这这4个符号取个符号取n个进行排列，每个进行排列，每个字符都可以重复选取，求排列数。个字符都可以重复选取，求排列数。解：构造母函数解：构造母函数Ge(x)。)(xeG42)!.!2!11(nxxxnxe4.!34!24!1413322xxx排列数是排列数是4n。2.11：指数型母函数：指数型母函数12 例例4 求求1,3,5,7,9这这5个数字组成的个数字组成的n位数个数，位数个数，要求其中要求其中3出现的次数为偶数，其它数字出现的出现的次数为偶数，其它数字出现的次数无限制。（
10、用指数型母函数求解）次数无限制。（用指数型母函数求解）解：设满足条件的解：设满足条件的r r位数的数目为位数的数目为ar,则序则序列列a0,a1,a2,的母函数为：的母函数为：4242.)!21.)(!4!21()(xxxxxGe2.11：指数型母函数：指数型母函数134242.)!21.)(!4!21()(xxxxxGexxxeeeexG4)(21)()(35xxee 212.11：指数型母函数：指数型母函数)35(21nnna 因此14 例例4 求求1,3,5,7,9这这5个数字组成的个数字组成的n位数个数，位数个数，要求其中要求其中3出现的次数为偶数，其它数字出现的出现的次数为偶数，其它
11、数字出现的次数无限制。（用递推关系求解）次数无限制。（用递推关系求解）解：解：a an n=4a=4an-1n-1+(5+(5n-1n-1-a-an-1n-1)2.11：指数型母函数：指数型母函数a1=4a1=4a an n-3a-3an-1n-1=5=5n n/5/5特解：特解：a an n=k=k5 5n nk=1/2k=1/2nnnha5213 152.11：指数型母函数：指数型母函数a1=4a1=4a an n-3a-3an-1n-1=5=5n n/5 5nnnha5213 h=1/2h=1/2nnna52132116 例例5 用红绿蓝三种颜色去涂用红绿蓝三种颜色去涂1 n的棋盘，的棋
12、盘，每格涂一种颜色，要每格涂一种颜色，要求红蓝二色出现的次数求红蓝二色出现的次数均为偶数，求涂色方案数。均为偶数，求涂色方案数。.)!21(.)!4!21()(2242xxxxxGexxxeeeexG2)(41)(xxxeee)2(4122)2(413xxxeee2.11：指数型母函数：指数型母函数)1(23(41 nnna因此17 n n个不同的元素个不同的元素,取取m m个作有重复的排列个作有重复的排列,与与m m个不同的球放进个不同的球放进n n个有区别的盒子个有区别的盒子,允许空盒允许空盒的放法一一对应的放法一一对应.1,1 2,2 3,3 1,2 2,1 1,3 3,1 2,3 3,
13、2 1,1 2,2 3,3 1,2 2,1 1,3 3,1 2,3 3,2a a号球位置号球位置,b,b号球位置号球位置.3 3个不同的元素取两个作有重复的排列个不同的元素取两个作有重复的排列 2 2个不同的球个不同的球,放进放进3 3个有区别的盒子个有区别的盒子a babb aa bb abaa,ba,ba,b2.11：指数型母函数：指数型母函数18 例例5 5 a1,a2,a3,a4 为为4 4个不同的元素个不同的元素,取取7 7个作有重复的排列个作有重复的排列,要求要求 a1,a2必须出现偶数必须出现偶数次次,3,3出现奇数次。出现奇数次。.)!2!11.)(!3!1(.)!4!21()
14、(23242xxxxxxxGe2.11：指数型母函数：指数型母函数 例例6 6 a1,a2,a7 为为7 7个有区别的球放进个有区别的球放进4 4个有标志的盒子，要求个有标志的盒子，要求1 1，2 2两盒必须含偶数两盒必须含偶数个球，第个球，第3 3盒含奇数个球。盒含奇数个球。.)!2!11.)(!3!1(.)!4!21()(23242xxxxxxxGe19 例例7 n7 n个有标志的球，放进个有标志的球，放进m m个不同的盒子，允个不同的盒子，允许空盒，问有多少种不同的分配方案？许空盒，问有多少种不同的分配方案？mexxxxG.)!3!21()(32mxe m m种不同元素取种不同元素取n
15、n个作允许重复的排列是一个作允许重复的排列是一样的。样的。.!3!2!11)(3322xmxmxmxeG m mn n2.11：指数型母函数：指数型母函数20 例例2.302.30，2.332.33 n n个有标志的球，放进个有标志的球，放进m m个不同个不同的盒子，要求无一空盒，问有多少种不同的分配方的盒子，要求无一空盒，问有多少种不同的分配方案？案？mexxxxG.)!3!2()(32mxe)1(kkmxmkekmC)1()(),(0kmkhhhxhkmkmC)1(!)(),(00 m m种元素取种元素取n n个作允许重复的排列个作允许重复的排列,每一个数每一个数都必须至少取一次。都必须至
16、少取一次。2.11：指数型母函数：指数型母函数21 00!)(,()1(hmkhhkhxkmkmCmknknkmkmCa0)(,()1(2.11：指数型母函数：指数型母函数22n个球放进个球放进m个盒子放法总结个盒子放法总结:n n个球放进个球放进m m个盒子里，球是否有区别，盒个盒子里，球是否有区别，盒子是否有区别，是否允许空盒，共有八种情况：子是否有区别，是否允许空盒，共有八种情况：1 1、有区别、有区别,有区别，有空盒有区别，有空盒mexxxxG.)!3!21()(32 2 2、有区别、有区别,有区别，无空盒有区别，无空盒mexxxxG.)!3!2()(3223 n n个球放进个球放进m
17、 m个盒子里，球是否有区别，盒个盒子里，球是否有区别，盒子是否有区别，是否允许空盒，共有八种情况：子是否有区别，是否允许空盒，共有八种情况：3 3、无区别、无区别,有区别，有空盒有区别，有空盒mxxxxG.)1()(32 4 4、无区别、无区别,有区别，无空盒有区别，无空盒mxxxxG.)()(32n个球放进个球放进m个盒子放法总结个盒子放法总结:24 n n个球放进个球放进m m个盒子里，球是否有区别，盒个盒子里，球是否有区别，盒子是否有区别，是否允许空盒，共有八种情况：子是否有区别，是否允许空盒，共有八种情况：5 5、无区别、无区别,无区别，有空盒无区别，有空盒)1).(1)(1)(1(1
18、)(32mxxxxxG 6 6、无区别、无区别,无区别，无空盒无区别，无空盒)1).(1)(1)(1()(32mmxxxxxxGn个球放进个球放进m个盒子放法总结个盒子放法总结:*252.12：广义二项式定理：广义二项式定理二项式定理二项式定理 nnxnnCxnCxnCnCx),(.)2,()1,()0,()1(2.),1(.!2)1(1)1(2knxkknCxnnnxx .!)1).(1()1(.!2)1(11(2kkxkkaaxaaaxx )262.15 递推关系解法的补充递推关系解法的补充1、母函数法、母函数法2、迭代法、迭代法3、归纳法、归纳法4、置换法、置换法5、相加消去法、相加消去
19、法27例例9 9：求下列递推关系的解：求下列递推关系的解2,1,103221aaaaannn解：用置换法：解：用置换法：21ln3ln2lnnnnaaa2132,lnnnnnnbbbab则有令解特征方程可得：解特征方程可得：1,321rr2.14 递推关系解法的补充递推关系解法的补充nnnkkb)1(3212ln,010bb282.14 递推关系解法的补充递推关系解法的补充nnnkkb)1(3212ln,010bb2132,lnnnnnnbbbab则有令210kk 2132lnkk 42ln,42ln21kknnnb)1(42ln342ln2ln)1(41341nnnn)1(413412ln2
20、92.14 递推关系解法的补充递推关系解法的补充nnabln令nnnb)1(413412lnnnna)1(41341230例例1010：求下列递推关系的解：求下列递推关系的解7,2101aaannn解：解：1 1、猜解法：、猜解法：nnnkk222)1(n21特解一般解：一般解：nnka212.14 递推关系解法的补充递推关系解法的补充nna21831例例1010：求下列递推关系的解：求下列递推关系的解7,2101aaannn解：解：2 2、置换法：、置换法：1221nnnnaa令令nabnn22.14 递推关系解法的补充递推关系解法的补充122211nnnnaa121nnbb12 nnkb128nnbnnnnba2182*322.48 2.48 有红、黄、蓝、白球各两个，绿、紫、有红、黄、蓝、白球各两个，绿、紫、黑球各三个，从中取黑球各三个，从中取1010个球，试为有多少种个球，试为有多少种不同的取法。不同的取法。2.14 递推关系解法的补充递推关系解法的补充2.492.49，2.50,2.51,2.782.50,2.51,2.78
