研究生组合数学复习要点.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,研究生组合数学复习要点,研究生组合数学复习要点研究生组合数学复习要点二、母函数1.母函数与数列的关系,2.母函数与排列数、组合数的关系,3.用普通型母函数解决多重集的组合问题,4.用指数型母函数解决多重集的排列问题,5.用母函数解递推关系式,6.不定方程的整数解的个数与多重集的组合数之,关系2,二、母函数,1.母函数与数列的关系,2.,母函数与排列数、组合数的关系,3.,用普通型母函数解决多重集的组合问题,4.,用指数型母函数解决多重集的排列问题,5.,用母函数解递推关系式,6.,不定方程的整数解的个数与多重集的组合数之,关系,2,三、递推关系,1.常系数线性递推关系的解法（特征根法）,2.用待定系数法求常系数线性非齐次递推关系的,特解,(,前两种类型,),3.,列递推关系解应用题,4.,一般递推关系的线性化,5.Fibonacci,数列及其模型,6.,第二类,Stirling,数的组合意义,7.Catalan,数列及其解法,3,四、容斥原理,1.容斥原理的基本形式,(,容斥原理、逐步淘汰原理,),2.容斥原理的应用,(,比如解决多重集排列组合问题,),3.有限制条件的排列,(,比如错排问题、相邻禁位排,列问题、保位问题,),4,五、抽屉原理,1.抽屉原理的几种基本形式,2.抽屉原理的简单应用,5,六、波利亚,(Plya),定理,1.置换在研究等价类计数中的作用,2.将置换表为轮换之积,3.,Burnside,引理计数公式,4.Plya,定理计数公式,5.,Plya,定理的应用,6,1,、一位学者要在一周内安排,50,个小时的工作时间，而且每天至少工作,5,小时，问共有多少种安排方案？,练习题,7,2,、,n,个男,n,个女排成一男女相间的队伍，试问有多少种不同的方案,.,若围成一圆桌坐下，又有多少种不同的方案？,8,9,10,解 用,表示所求方法数,.,易知,使得相邻格子异色的涂色方法数有,其中使得首末两格同色的涂色方法有,所以,用,m,种颜色去涂,棋盘,每格涂一种颜色,种,种,从而,11,另一解法参见教材,P87,例,3.5.7,12,解,(1),先任意选定一个女人入座，有,种方法；,(2),再安排其他女人入座，使得任何两个女人之间至少有,k,个空座位：,13,此不定方程的解的个数为,于是完成此步骤的方法有,种,.,14,(3),最后安排,m,个男人入座，有,m,!,种方法,.,由乘法原理，所求的安排座位方法数为,15,6,、某学者每周工作,6,天,共,42,小时,每天工作的小时数是整数,且每天工作时间不少于,6,小时也不多于,8,小时,如果编排一周的工作时间表,问有多少种不同的方案？,16,17,7,、将充分多的苹果、香蕉、橘子和梨进行装袋，要求每袋中苹果数是偶数，香蕉数是,5,的倍数，橘子最多,4,个，而梨的个数为,0,或,1,。如果每袋装,n,个水果，求装袋的种类数。,18,19,8,、由字母,a,，,b,，,c,，,d,，,e,组成的总字母数为,n,的单词中，要求,a,与,b,的个数之和为偶数，问这样的单词有多少个？,解 设满足条件的单词个数为,a,n,，这样的单词只有两类：一类包括偶数个,a,与偶数个,b,；另一类包括奇数个,a,与奇数个,b.,因此,a,n,对应的母函数为,20,故,21,9,、把,2,n,件相异物品放到,m,个不同的盒中，使得每个盒子中的物品件数均为偶数,(,零也是偶数,),，求不同的放法种数,.,解 相应的指母函数是,22,故所求放法数为,23,10,、由数字,1,至,9,组成的每种数字至少出现,1,次的,位数有多少个？,解 设所求的数为,则,的指母函数为,24,所以,(,此题也可用容斥原理做,),25,11,、求由,0,、,1,、,2,组成的长为,n,的三进制串的个数,但其中的,0,和,1,不相邻,(,即,01,和,10,从不出现,),解,设所求三进制串的个数为,则,(1),若首位是,2,则此类三进制串有,(2),若首位是,1,则第二位必是,1,或,2.,若第二位是,2,则此类串有,若前二位是,1,则第三位必是,1,或,2.,若第三位是,2,则此类串有,26,；若前,n,-,2,位是,1,则第,n,-,1,位必是,1,或,2.,若第,n,-,1,位必是,2,，则,此类串有,若前,n,-1,位是,1,则第,n,位必是,1,或,2,，则此类串有,2,个,.,所以首位是,1,的三进制串有,个,.,(3),若首位是,0,同理可得三进制串有,个,.,因此,得,27,两式相减，得定解问题,求得通解,代入初值得,28,12,、有多少个长度为,n,的,0,与,1,串,在这些串中,既不包含子串,010,，也不包含子串,101,？,解 设这种数串的个数为,将满足条件的数串分为两类：,(1),最后两位数字相同,.,这种长度为,n,的数串可由长度为,n,-,1,的串最后一位数字重复一次而得，故这类数串的个数,(2),最后两位数字不同,.,这种长度为,n,的数串可由长度为,n,-,2,的串最后一位,(,设为,a,),重复一次，再加上与,a,不同的数字而得,故这类数串的个数为,29,于是得递推关系,由,Fibonacci,数列,得通解,代入初值,得,30,13,、平面上有两两相交，无,3,线共点的,n,条直线,求这,n,条直线把平面分成多少个区域？,解 设这,n,条直线把平面分成,个区域，,易知,条直线把平面分成,去掉所给,n,条直线中的一条直线,则剩下的,n,-1,个区域,.,线放回原处后,于是得定解问题,再把去掉的那条直,则在,的基础上增加了,n,个区域,31,解得,显然，当,n,=1,时，上式仍成立,.,故,n,条直线把平面分成,个区域,.,32,14,、有,2,n,个人排成一队购票，票价,5,元。,2,n,个人中有,n,个人有,5,元的钱币，另外,n,个人有,10,元的钱币。开始售票时售票处没有准备找零的钱。问有多少种列队方式，使得只要有,10,元的人买票，售票处就有,5,元的钱币找零？,解 将有,5,元钱币的人赋值,1,，有,10,元钱币的人赋值,-1,，则该问题为：包括,n,个,1,和,n,个,-1,的,2,n,个数,构成序列，使,33,这,2,n,个数的排列是多重集,的排列，,排列总数为,的排列是：“从左向右扫描，出现,-,1,的累计数超过,1,的累计数”，所以存在最小的,k,，使,而这些排列中，不符合要求,34,前,k,个变号后，可得到一个有,n+1,个,1,和,n-1,个,-1,的序列，,反之，,n+1,个,1,和,n-1,个,-1,的序列，必存在,k,，使得该,序列的前,k,个数,中,1,的个数恰比,-1,的,个数多,1.,将这,k,个数变号，就得到一个有,n,个,1,和,n,个,-1,的序列，,于是不合要求的排列与多重集,的排列一一对应,.,这种排列有,35,个,.,故所求列队方式数为,36,另解 把有,5,角钱的人用,1,标识,有,1,元钱的人用,0,标识,问题就转化为“由,n,个,1,和,n,个,0,组成的,2n,位排列中，从左向右扫描，,1,的累计数不小于,0,的累计数”,.,故所求序列数为,37,15,、十个数字,(0,到,9),和四个运算符,(,+,-,*,/),组成,14,个元素,求由其中的,n,个元素的排列构成一形式算术表达式的个数,.,解 令,表示,n,个元素排列成算术表达式的数目，,则,特征方程,解得特征根,得通解,38,代入初始条件得,故,39,16,、设有地址从,1,到,n,的单元，用以记录一组信息，这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留一个空单元无法存放其它信息,.,求这,n,个单元留下空单元的平均数,.,解 设这个平均数为,并设某一个信息占用了第,两个单元，,第一部分有,i,个单元，这,i,个单元留下空单元,把这组单元剩余的单元分成两,个部分，,的平均数为,第二部分有,个单元，这些,单元留下空单元的平均数为,于是某一个信,40,则留下空单元,息若占用了第,两个单元，,的平均数为,由于用相邻两个单元的几,率相等，故,即,又由,41,得,解得,（解法见教材,P69,例,3.3.7,）,42,17,、一个计算机系统把一个十进制数字串作为一个编码字，如果它包含偶数个,0,，就是有效的,.,求有效的,n,位编码字的个数,a,n,.,解 显然,若末位数是,1,到,9,中某个数，则前面,n,-1,位组成的有效数有,a,n,-1,个，因此，末位数不是,0,的,n,位有效数字有,9,a,n,-1,个,.,若末位数是,0,，则这样的,n,位十进制数有,10,n,-1,个，,而不是有效数的有,a,n,-1,个,(,因,n,-1,位的有效数后面添一个,0,就不是有效数了,),所以末位数是,0,的有效数有,43,个,.,于是得递推关系,即,解得通解,代入初始条件得,故所求有效数字有,个,.,44,18,、把 件彼此相异的物品分给甲、乙、丙三人，使得甲至少分得两件物品，乙和丙至少分得一件物品，有多少种不同的分法？,解 设有,N,种不同的分法,.,因为把,n,件彼此相异的物品分给,3,个人，使得每人至少分得一件物品的方法共有,种，其中使得甲恰分得一件物品的分法有,45,种，故,46,47,48,49,20,、,n,个单位各派,2,名代表出席一个会议，,2,n,名代表围一圆桌坐下,.,试问：,(1),各单位代表入座的方案有多少种,?,(2),各单位的,2,位代表不相邻的方案有多少种,?,解,(1),这是,2,n,个元的圆排列,故各单位代表入座方式有,(2),设这,2,n,个人入座方式的全体为,S,，则,S,中第,i,个单位的两个人相邻的入座方式,则,50,由容斥原理，所求方案数为,51,解 设所求数为,N,，以,S,表示由,的全排列之集，,作成,以,A,，,B,分别表示,S,中,由容斥原理，,52,22,、由,a,，,b,，,c,，,d,四个字符组成所有,n,位,(,n,4,),字符串中，,a,，,b,，,c,，三个字母同时出现在一个串中至少一次的这种,n,位字符串的个数有多少？,解,设,S,表示由,a,，,b,，,c,，,d,构成的所有,n,位字符串之集。,则,53,于是所求数为,54,55,56,24,、随意把一个,39,棋盘的每个方格涂成红色或蓝色,证明必有两列方格,它们的涂色方法是一样的,.,证 用红、蓝两色去涂,31,棋盘共有 种涂色方法,.,表示第,i,种涂色方法,.,以,设,K,是任一个已用红色或蓝色涂了色的,39,棋盘,表示,K,的第,i,列的涂色方法,以,并令,由抽屉原理,必有某,与第,l,列的涂色方法是一样的,.,则,K,的第,k,列,57,证,(1),将这个等边三角形分成,4,个边长为 的等边三角形,.,而每个小等边三角形内任意两点之间的距离不超过,由抽屉原理，,5,个点必有,2,个点在一个小三角形中，,这,2,个点的距离不超过,59,(2),将这个等边三角形分成,9,个边长为 的等边三角形,.,而每个小等边三角形内任意两点之间的距离不超过,60,(3),将这个等边三角形分成,个边长为 的等边三角形,.,由抽屉原理，,10,个点必有,2,个点在一个小三角形中，,这,2,个点的距离不超过,61,26,、某个宴会共有,2,n,个人出席，每个人均至少认识其中的,n,个人,.,求证,:,可安排这,2,n,个人中的某,4,个人围圆桌而坐,使得每个人的旁边都是他所认识的人,.,证,用平面上的点表示个人,并以,V,表示这个点所成之集,.,对,V,中的任意两个点,如果它们表示的两个人互相认识,(,不认识,),则用红边,(,蓝边,),把这两个点连结起来,这样得到一个,2,着色的,如果 的边全是红色,则结论显然成立,;,否则它至少有一条蓝边，,设 是一条蓝边,令,如果,则,28,、有,n,个人,(n,为大于等于,4,的偶数,),举行一次聚会，参加的每个人都有偶数个,(,有可能是,0,个,),熟人,.,证明：在这次聚会上有,3,人有相同个数的熟人,.,证 用数学归纳法,.,n=4,时，只有三种情况：,(1)4,个人互不认识；,(2),有,1,个人有,0,个熟人，其余,3,人互相认识；,(3)4,人中每个人与另两人认识,.,此时无论哪种情况结论均成立,.,68,假设,n=k,时,(k,为偶数,),存在,3,人，他们有相同个数的熟人,.,则当,n=k+2,时，有如下情况：,(1),有,0,个人有,0,个熟人；,(2),有,1,个人有,0,个熟人；,(3),有,2,个人有,0,个熟人；,(4),有,3,个以上的人有,0,个熟人；,对于,(4),结论显然成立,.,对于,(1),k+2,个人的熟人数只取,2k,之间的偶数，,以此作为“抽屉”，则必有一个抽屉至少,69,即有,3,个人有相同熟人数,.,对于,(2),除去哪个有,0,个熟人的人，用余下的,k+1,个人做“物品”，用,2k,之间的偶数作“抽屉”，则,70,谢谢观赏！,2020/11/5,71,