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