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

《研究生组合数学复习要点.ppt》由会员分享，可在线阅读，更多相关《研究生组合数学复习要点.ppt（71页珍藏版）》请在课桌文档上搜索。

1、1,组合数学复习要点,一、排列组合,1.排列和组合的基本性质2.排列组合的计数公式，多重集的排列数和组合 数的求法3.应用,2,二、母函数,1.母函数与数列的关系2.母函数与排列数、组合数的关系3.用普通型母函数解决多重集的组合问题4.用指数型母函数解决多重集的排列问题5.用母函数解递推关系式6.不定方程的整数解的个数与多重集的组合数之 关系,3,三、递推关系,1.常系数线性递推关系的解法（特征根法）2.用待定系数法求常系数线性非齐次递推关系的 特解(前两种类型)3.列递推关系解应用题4.一般递推关系的线性化5.Fibonacci数列及其模型6.第二类Stirling数的组合意义7.Catal

2、an数列及其解法,4,四、容斥原理,1.容斥原理的基本形式(容斥原理、逐步淘汰原理)2.容斥原理的应用(比如解决多重集排列组合问题)3.有限制条件的排列(比如错排问题、相邻禁位排 列问题、保位问题),5,五、抽屉原理,1.抽屉原理的几种基本形式2.抽屉原理的简单应用,6,六、波利亚(Plya)定理,1.置换在研究等价类计数中的作用2.将置换表为轮换之积3.Burnside引理计数公式4.Plya定理计数公式5.Plya定理的应用,7,1、一位学者要在一周内安排50个小时的工作时间，而且每天至少工作5小时，问共有多少种安排方案？,练习题,8,2、n个男n个女排成一男女相间的队伍，试问有多少种不同

3、的方案.若围成一圆桌坐下，又有多少种不同的方案？,9,10,11,解 用,表示所求方法数.易知,使得相邻格子异色的涂色方法数有,其中使得首末两格同色的涂色方法有,所以,用m种颜色去涂,棋盘,每格涂一种颜色,种,种,从而,12,另一解法参见教材P87例3.5.7,13,解(1)先任意选定一个女人入座，有,种方法；,(2)再安排其他女人入座，使得任何两个女人之间至少有k个空座位：,14,此不定方程的解的个数为,于是完成此步骤的方法有,种.,15,(3)最后安排m个男人入座，有m!种方法.,由乘法原理，所求的安排座位方法数为,16,6、某学者每周工作6天,共42小时,每天工作的小时数是整数,且每天工

4、作时间不少于6小时也不多于8小时,如果编排一周的工作时间表,问有多少种不同的方案？,17,18,7、将充分多的苹果、香蕉、橘子和梨进行装袋，要求每袋中苹果数是偶数，香蕉数是5的倍数，橘子最多4个，而梨的个数为0或1。如果每袋装n个水果，求装袋的种类数。,19,20,8、由字母a，b，c，d，e组成的总字母数为n的单词中，要求a与b的个数之和为偶数，问这样的单词有多少个？,解 设满足条件的单词个数为an，这样的单词只有两类：一类包括偶数个a与偶数个b；另一类包括奇数个a与奇数个b.,因此an 对应的母函数为,21,故,22,9、把2n件相异物品放到m个不同的盒中，使得每个盒子中的物品件数均为偶数

5、(零也是偶数)，求不同的放法种数.,解 相应的指母函数是,23,故所求放法数为,24,10、由数字1至9组成的每种数字至少出现1次的,位数有多少个？,解 设所求的数为,则,的指母函数为,25,所以,(此题也可用容斥原理做),26,11、求由0、1、2组成的长为n的三进制串的个数,但其中的0和1不相邻(即01和10从不出现),解 设所求三进制串的个数为,则,(1)若首位是2,则此类三进制串有,(2)若首位是1,则第二位必是1或2.,若第二位是2,则此类串有,若前二位是1,则第三位必是1或2.,若第三位是2,则此类串有,27,；若前n-2位是1,则第n-1位必是1或2.,若第n-1位必是2，则此类

6、串有,若前n-1位是1,则第n位必是1或2，则此类串有2个.,所以首位是1的三进制串有,个.,(3)若首位是0,同理可得三进制串有,个.,因此,得,28,两式相减，得定解问题,求得通解,代入初值得,29,12、有多少个长度为n的0与1串,在这些串中,既不包含子串010，也不包含子串101？,解 设这种数串的个数为,将满足条件的数串分为两类：,(1)最后两位数字相同.这种长度为n的数串可由长度为n-1的串最后一位数字重复一次而得，故这类数串的个数,(2)最后两位数字不同.这种长度为n的数串可由长度为n-2的串最后一位(设为a)重复一次，再加上与a不同的数字而得,故这类数串的个数为,30,于是得递

7、推关系,由Fibonacci数列,得通解,代入初值,得,31,13、平面上有两两相交，无3线共点的n条直线,求这n条直线把平面分成多少个区域？,解 设这n条直线把平面分成,个区域，,易知,条直线把平面分成,去掉所给n条直线中的一条直线,则剩下的n-1,个区域.,线放回原处后,于是得定解问题,再把去掉的那条直,则在,的基础上增加了n个区域,32,解得,显然，当n=1时，上式仍成立.,故n条直线把平面分成,个区域.,33,14、有2n个人排成一队购票，票价5元。2n个人中有n个人有5元的钱币，另外n个人有10元的钱币。开始售票时售票处没有准备找零的钱。问有多少种列队方式，使得只要有10元的人买票，

8、售票处就有5元的钱币找零？,解 将有5元钱币的人赋值1，有10元钱币的人赋值-1，则该问题为：包括n个1和n个-1的2n个数,构成序列，使,34,这2n个数的排列是多重集,的排列，,排列总数为,的排列是：“从左向右扫描，出现-1的累计数超过1的累计数”，所以存在最小的k，使,而这些排列中，不符合要求,35,前k个变号后，可得到一个有n+1个1和n-1个-1的序列，,反之，n+1个1和n-1个-1的序列，必存在k，使得该,序列的前k个数,中1的个数恰比-1的,个数多1.,将这k个数变号，就得到一个有n个1和n,个-1的序列，,于是不合要求的排列与多重集,的排列一一对应.,这种排列有,36,个.,

9、故所求列队方式数为,37,另解 把有5角钱的人用1标识,有1元钱的人用0标识,问题就转化为“由n个1和n个0组成的2n位排列中，从左向右扫描，1的累计数不小于0的累计数”.故所求序列数为,38,15、十个数字(0到9)和四个运算符(+,-,*,/)组成14个元素,求由其中的n个元素的排列构成一形式算术表达式的个数.,解 令,表示n个元素排列成算术表达式的数目，,则,特征方程,解得特征根,得通解,39,代入初始条件得,故,40,16、设有地址从1到n的单元，用以记录一组信息，这个信息的每个元素都占用两个单元，而且存放的地址是完全随机的，因而可能出现两个存放信息单元之间留一个空单元无法存放其它信息

10、.求这n个单元留下空单元的平均数.,解 设这个平均数为,并设某一个信息占用了第,两个单元，,第一部分有i个单元，这i个单元留下空单元,把这组单元剩余的单元分成两,个部分，,的平均数为,第二部分有,个单元，这些,单元留下空单元的平均数为,于是某一个信,41,则留下空单元,息若占用了第,两个单元，,的平均数为,由于用相邻两个单元的几,率相等，故,即,又由,42,得,解得,（解法见教材P69例3.3.7）,43,17、一个计算机系统把一个十进制数字串作为一个编码字，如果它包含偶数个0，就是有效的.求有效的n位编码字的个数an.,解 显然,若末位数是1到9中某个数，则前面n-1位组成的有效数有an-1

11、个，因此，末位数不是0的n位有效数字有 9 an-1个.,若末位数是0，则这样的n位十进制数有10n-1个，,而不是有效数的有 an-1个(因n-1位的有效数后面添一个0就不是有效数了),所以末位数是0的有效数有,44,个.,于是得递推关系,即,解得通解,代入初始条件得,故所求有效数字有,个.,45,18、把 件彼此相异的物品分给甲、乙、丙三人，使得甲至少分得两件物品，乙和丙至少分得一件物品，有多少种不同的分法？,解 设有N种不同的分法.因为把n件彼此相异的物品分给3个人，使得每人至少分得一件物品的方法共有,种，其中使得甲恰分得一件物品的分法有,46,种，故,47,48,49,50,20、n个

12、单位各派2名代表出席一个会议，2n名代表围一圆桌坐下.试问：(1)各单位代表入座的方案有多少种?(2)各单位的2位代表不相邻的方案有多少种?,解(1)这是2n个元的圆排列,故各单位代表入座方式有,(2)设这2n个人入座方式的全体为S，则,S中第i个单位的两个人相邻的入座方式,则,51,由容斥原理，所求方案数为,52,解 设所求数为N，以S表示由,的全排列之集，,作成,以A，B分别表示S中,由容斥原理，,53,22、由a，b，c，d四个字符组成所有n位(n4)字符串中，a，b，c，三个字母同时出现在一个串中至少一次的这种n位字符串的个数有多少？,解 设S表示由a，b，c，d构成的所有n位字符串之

13、集。,则,54,于是所求数为,55,56,57,24、随意把一个39棋盘的每个方格涂成红色或蓝色,证明必有两列方格,它们的涂色方法是一样的.,设K是任一个已用红色或蓝色涂了色的39棋盘,表示K的第i列的涂色方法,以,并令,由抽屉原理,必有某,与第l列的涂色方法是一样的.,则K的第k列,59,证(1)将这个等边三角形分成4个边长为 的等边三角形.,而每个小等边三角形内任意两点之间的距离不超过,由抽屉原理，5个点必有2个点在一个小三角形中，,这2个点的距离不超过,60,(2)将这个等边三角形分成9个边长为 的等边三角形.,而每个小等边三角形内任意两点之间的距离不超过,61,(3)将这个等边三角形分

14、成,个边长为 的等边三角形.,由抽屉原理，10个点必有2个点在一个小三角形中，,这2个点的距离不超过,26、某个宴会共有2n个人出席，每个人均至少认识其中的n个人.求证:可安排这2n个人中的某4个人围圆桌而坐,使得每个人的旁边都是他所认识的人.,证 用平面上的点表示个人,并以V表示这个点所成之集.对V中的任意两个点,如果它们表示的两个人互相认识(不认识),则用红边(蓝边)把这两个点连结起来,这样得到一个2着色的,如果 的边全是红色,则结论显然成立;否则它至少有一条蓝边，,设 是一条蓝边,令,如果,则,68,28、有n个人(n为大于等于4的偶数)举行一次聚会，参加的每个人都有偶数个(有可能是0个

15、)熟人.证明：在这次聚会上有3人有相同个数的熟人.,证 用数学归纳法.,n=4时，只有三种情况：,(1)4个人互不认识；,(2)有1个人有0个熟人，其余3人互相认识；,(3)4人中每个人与另两人认识.,此时无论哪种情况结论均成立.,69,假设n=k时(k为偶数)存在3人，他们有相同个数的熟人.则当n=k+2时，有如下情况：,(1)有0个人有0个熟人；(2)有1个人有0个熟人；(3)有2个人有0个熟人；(4)有3个以上的人有0个熟人；,对于(4)结论显然成立.,对于(1),k+2个人的熟人数只取2k之间的偶数，,以此作为“抽屉”，则必有一个抽屉至少,70,即有3个人有相同熟人数.,对于(2),除去哪个有0个熟人的人，用余下的k+1个人做“物品”，用2k之间的偶数作“抽屉”，则,71,对于(3),除去2个有0个熟人的人，余下的k个人由归纳假设知，这k个人中有3人他们有相同的熟人数.,