二章六节非线性递推关系举例.ppt

第2章 递递推关系与母函数 2.1 递递推关系 2.2 母函数(生成函数) 2.3 Fibonacci数列 2.4 优选优选 法与Fibonacci序列的应应用 2.5 母函数的性质质 2.6 线线性常系数齐齐次递递推关系 2.7 关于常系数非齐齐次递递推关系 2.8 整数的拆分 2.9 ferrers图图像 2.10 拆分数估计计 2.11 指数型母函数 2.12 广义义二项项式定理 2.13 应应用举举例 2.14 非线线性递递推关系举举例 2.15 递递推关系解法的补补充1 2.14 非线线性递递推关系举举例(一)多项项式展开式的讨论讨论(二)第一类类司特林(Stirling)数的讨论讨论(三)第二类类司特林(Stirling)数的讨论讨论2 2.14 非线线性递递推关系举举例 (1)多项项式系数 (x+y)n展开式的通项项xkyn-k项项的系数是:C(n,k) 相当于2个不同的球取n个作有重复的排列，其中x取k个，y取n-k个 也相当于n个不同的球放入2个不同盒子，x盒子放k个，y盒子放n-k个 指数型母函数是？(一)多项项式展开式的讨论讨论3 2.14 非线线性递递推关系举举例 (一)多项项式展开式的讨论讨论 (2)多项项式系数和 (x+y)n展开式的系数和是:2n 这这种情况对应对应 着指数型母函数是？ 展开式的过过程相当于两个不同的元素取n个的有重复的排列。

也相当于把n个不同的球放进进两个不同的盒子中 4 2.14 非线线性递递推关系举举例 (一)多项项式展开式的讨论讨论 (3)多项项式的项项数 (x+y)n展开式的项项数是n+1 相当于从两个不同元素中取n个的组组合数，允许许重复 也相当于把n个一样样的球放进进两个不同的盒子中的方案数 母函数是？ 5 定理2.14 (x1+x2+xm)n 展开式通项项项项数等于C(m+n-1,n)* 系数之和等于mn 的系数是:6称s(n,0),s(n,1),s(n,n)为为第一类类司特林数7其中xk项项的系数为为s(n-1,k-1)-(n-1)s(n-1,k)递递推关系式s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)8递递推关系式s(n,k)=s(n-1,k-1)-(n-1)s(n-1,k)初始条件：s(n,0)=0当kn时时，s(n,k)=0s(n,n)=1*9 例如：红红、黄、蓝蓝3种颜颜色的球3个，放到两个无区别别的盒子里，不允许许空盒其方案如下：123盒ryb盒ybrbry讨论讨论 的是生活中的分堆现现象:与拆分有什么区别别？10 定理2.14 第二类类司特林数S(n,k)有以下性质质：11 性质质1的意思是把n个不同的球放进进0个盒子中或把0个不同的球放进进n个盒子的方案数都是0。

性质质2的意思是把n个不同的球放进进k个盒子中,当球等于或多于盒子时时，至少有一种方案 12 性质质3的意思是把n个球放进进k个盒子中,当盒子多于球数时时，要想使盒子不空是不可能的 性质质4的意思是把n个球放进进1个盒子中,放法只有一种 性质质5的意思是把n个不同的球放进进n个一样样的盒子中,不允许许空盒，放法也只有一种13意思是把n个不同的球放进进2个一样样的盒子中, 当第一个球放进进其中一个盒子后，其余n-1个有标标志的球都有两种选择选择 ，一种是选择选择 与第一个球同盒，第二种选择选择 是与第一个球不同盒共有2n-1种可能， 要排除都放在同一个盒子的情况因此共有2n-1-1种方案14 把n个有标标志的球放进进n-1个一样样的盒子中，因为为必须须保证证每个盒子中都有球，因此只有1个盒子中有2个球，问题问题 就是求两个球的组组合数，因此有C(n,2)种方案15 (1)、剩余的两个球放进进一个盒子中，这样这样 的方案对应对应 着从n中取3个的组组合数，是C(n,3) (2)、剩余的两个球放进进二个盒子中，这样这样 的方案对应对应 着从n中取4个，然后再把4个球两两分成2组组，将4个球分成两组组的方案数是C(4,2)/2。

因此在这这种情况下方案数是：C(n,4)C(4,2)/2=3C(n,4) 例如：1,2,3,4分成两两2组组的方案 (1,2),(3,4),(1,3),(2,4),(1,4),(2,3)16定理2.15 第二类类司特林数满满足下面的递递推关系： 证证明：设设有n个有区别别的球b1,b2,bn,对对于其中的某一个球bi, 根据bi的情况分为为两类类：1、 bi独占一盒，其方案为为S(n-1,m-1) 2、 bi不独占一盒，这这相当于先将剩下的n-1个球放到m个盒子，不允许许空盒，共有S(n-1,m)种不同方案， 然后将bi球放进进其中一盒，共有m种选择选择 方式bi球不独占一盒的方案数为为mS(n-1,m)1718 2、n个有标标志的球放进进m个有区别别的盒子，不允许许空盒问题问题 1、n个有标标志的球放进进m个一样样的盒子，不允许许空盒问题问题 n个有标标志的球b1,b2,bn ，放进进有区别别的m个盒子c1,c2,cm中，无一空盒，其方案数为为m!S(n,m),其中1mn1920 n个球放到m个盒子里，那么球和盒子是否有区别别？是否允许许空盒？共有23=8种状态态，其方案情况如下： 1、n个不同的球放到m个不同的盒子里，允许许空盒？ 2、n个不同的球放到m个不同的盒子里，不允许许空盒。

有mn个方案有m!S(n,m)21 4、n个不同的球放到m个一样样的盒子里，允许许空盒，方案数情况？S(n,1)+S(n,2)+S(n,m),nmS(n,1)+S(n,2)+S(n,n),nm 可分为为空m-1盒，m-2盒，空1盒，都不空 3、n个不同的球放到m个一样样的盒子里，不允许许空盒，方案数情况？有S(n,m)22 5、n个一样样的球放到m个不一样样的盒子里，允许许空盒，方案数情况？有C(m+n-1,n) 6、n个一样样的球放到m个不一样样的盒子里，不允许许空盒，方案数情况？ 先取m个球每盒一个，余下的n-m无区别别的球放进进m个不一样样的盒子中那么有C(m+(n-m)-1,n-m)=C(n-1,n-m)=C(n-1,m-1),23 7、n个一样样的球放到m个一样样的盒子里，允许许空盒，方案数为为： xn项项系数，相当于n用1,2,m进进展拆分的拆分数 8、n个一样样的球放到m个一样样的盒子里，不允许许空盒，方案数为为：的xn项项系数242.13 应应用举举例 错错排问题问题 ：假设设一个排列使得所有的元素都不在原来的位置上，那么称这这个排列为错为错 排，也叫重排1,2的错错排是唯一的,即211,2,3的错错排有312,231。

252.13 应应用举举例对对于1,2,n，设设n个数的错错排数为为Dn综综合以上分析得到递递推关系： 取n分别别与其它的n-1个数之一互换换，其余n-2个数进进展错错排，共得(n-1)Dn-2个错错排 1、与Dn-1的关系： n-1个数进进展错错排，然后n与其中每一个数互换换得到(n-1)Dn-1个错错排 2、与Dn-2的关系：262.13 应应用举举例272.13 应应用举举例282.13 应应用举举例292.13 应应用举举例 实际实际 上这这是一个13579的错错排问题问题302.13 应应用举举例从8个字母中任取4个的组组合数为为C(8,4) 4个字母的错错排数为为：31解：2.13 应应用举举例特解:322.13 应应用举举例332.13 应应用举举例1、与an-1的关系 解：设设n个元素的算术术表达式个数为为an10an-1 2、与an-2的关系40an-2 342.13 应应用举举例 设设n条直线线将平面分成Dn个域，那么第n条直线线被其余的n-1条直线线分割成n段这这n段正好是新增加的n个域的边边界 所以：Dn=Dn-1+n,D1=2, D0=1352.13 应应用举举例 一个椭圆椭圆 将平面分隔成内、外两部分。

an= an-1+2(n-1), a1=2362.13 应应用举举例 设设an表示n个域的涂色方案数，分两种情况来讨论讨论 (1)与an-1的关系，(k-2)an-1 (2)与an-2的关系，(k-1)an-237解：第一位老师师的面试顺试顺 序有6!种第一位老师师：a1a2a3a4a5a6第二位老师师：a2a1a4a3a6a5 3.3 容斥原理举举例 共有6!265 对对第一位老师师的任何一种面试顺试顺 序， 第二门课门课 的顺顺序有：*38第3章 容斥原理与鸽鸽巢原理 3.1 De Morgan定理 1 3.2 容斥原理 1 3.3 容斥原理举举例 1 3.4 棋盘盘多项项式与有限制的排列 2 3.5 有禁区的排列 2 3.6 广义义的容斥原理 3 3.7 广义义容斥原理的应应用 3 2.8 第二类类Stirling数的展开式 1 2.9 欧拉函数(n) 1 2.10 n对对夫妻问题问题 3 *2.11 Mobius反演定理 2.12 鸽鸽巢原理 4 2.13 鸽鸽巢原理举举例 4 2.14 鸽鸽巢原理的推广 4 *2.15 Ramsey数 39。