组合数学复习总结.docVIP

第五章 1、任意一个由数字1，2，3组成的30位数，从中任意截取相邻的三位，证明在各种不同位置的截取中，至少有两个三位数是相同的。数的位数30还可以再减少吗，为什么？ （证）设该数字为，其任意的截法可有28种可能，即 a1a2a3，a2a3a4，a3a4a5，…，a28a29a30 但是，由1，2，3组成的3位数最多只有27个（即3个相异元素取3个的所有重复排列），故由抽屉原理，至少由两段是相同的。 由上面的证明过程可以看出，位数30不能再少，否则，不能保证有两段相同。 若改为截取相邻的5位，首先可知元素1、2、3的5－可重排列共有个。其次，由问题的性质可知至少要能截取出不同的244段才能保证结论成立，从而知该数至少应该有248位。 问题的一般描述是：任意一个由数字1，2，…，m组成的n＝位数，从中任意截取相邻的k位，则在各种不同位置的截取中，至少有两个k位数是相同的。若希望至少有r个k位数是相同的，则应有n＝。 第六章 一张卡片分成4×2个方格，每格用红蓝两色涂染，可有多少种方法？ （解）如图6.2.1，给每个方格标上号：1,2,…,8，相应的置换为（设卡片只能旋转，不能翻转） 1 2 3 4 5 6 7 8 图6.2.1 卡片染色 ， 由Pólya定理知，不同的染色方法数为 ＝ 若卡片还能翻转，但同一个格子对应的正反面要求同色，则除了上述两个置换外，还有沿着横、竖两个对称轴翻转的置换 ， 从而可知不同的染色方法数为 ＝＝76 若同一个格子对应的正反面不要求同色，且卡片既能旋转，又能翻转，则相应的置换为 ，， ， 其中A，B，…，H是卡片的背面分别依序与1，2，…，8对应的格子。那么，此时的染色方法数为 ＝＝16 576 正五角星的五个顶点各镶嵌一个宝石，若有m种颜色的宝石可供选择，问可以有多少种方案？ （解）设正五角星的5个顶点分别依次为1,2,…,5，因正五角星是可以翻转的，故相应于正五角星的五个顶点的变换有两类，第一类是绕其几何中心的5个平面旋转变换（即旋转72×度），第二类是以某个顶点与其几何中心的连线为轴的翻转变换，对应的10个置换是 ，，，， ，，，， 由Pólya定理，不同的镶嵌方案数为 L＝ 有一个正方形木筐，用漆刷4边。现有三种不同颜色的漆，可有多少种不同的涂法？ （解）将正方形木筐的4条边依次记为1，2，3，4（见图6.2.3），由题意知木筐既可以旋转，又可以翻转。对应的置换为 绕正方形中心逆时针旋转（）的置换 ，，， 以1-3、2-4两组对边的中心的连线为轴的翻转 ， 以A-C、B-D两组对角线为轴的翻转 ， A 1 B 4 2 D 3 C 图6.2.3 木筐染色 由Pólya定理知，不同涂法总数为 L＝＝21 第四章 4.某人参加一种会议，会上有6位朋友，他和其中每一人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，与六人都相遇1次，一人也没遇见的有5次，问该人共参加几次会议？ （解）设S为该人参加的所有会议组成的集合。为他遇见第个朋友的所有会议构成的S的子集，则由题意知公共数 ， ，, ，， ， ， ＝＝5。 由容斥原理 ＝ ＝ ＝28 所以，该人参加的会议次数为 ＝＋ ＝28＋5 ＝33 5.n位的四进制数中，数字1，2，3各自至少出现一次的数有多少个？ （解）设不含数字的四进制数组成的的集合为 ，则公共数 ，，， 由逐步淘汰原理（4.1.2）知所求的四进制数的个数为 ＝＝＝ 6.某照相馆给n个人分别照相后，装入每人的纸袋里，问出现以下情况有多少种可能： 没有任何一个人得到自己的相片； 至少有一人得到自己的相片； 至少有两人得到自己的相片。 （解）以任一装法为元素构成的集合记为S，则。设是第个人的相片装对了纸袋的所有装法组成的集合。则公共数 ＝＝ （1）设所求为 ，则由问题的性质知这是一个错排问题，故＝＝，即 ＝ （2）方法一 设所求为 ，由对称公式（4.1.1＇）知所求为 ＝＝ ＝ 方法二 问题（1）和（2）所对应的装法构成的集合是互为对立的，故 ＝＝ （3）设所求为 ，由保位问题知恰有一人得到自己相片的不同装法有＝种，所以 ＝ ＝ － ＝ 7.设有4个元素的排列，其中要求第1个元素不能排在第1个位置，第2个元素不能在1、4号位置，元素3不能在2号、元素4不能在3号位置。问共有多少排列方案数？ 解 所提排列问题对应有禁区的棋盘C（见图4.4.3 (a)），其禁区A（见图4.4.3 (b)）可分离为两个小棋盘A1和A2（见图4.4.3 (c)）。 显见 R(A1)＝1＋3x＋x2， R(A2) ＝1＋2x＋x2