组合数学复习总结

第五章 1、任意一个由数字1，2，3组成的30位数，从中任意截取相邻的三位，证明在各种不同位置的截取中，至少有两个三位数是相同的。数的位数30还可以再减少吗，为什么？ （证）设该数字为

3021aaaa，其任意的截法可有28种可能，即 a1a2a3，a2a3a4，a3a4a5，…，a28a29a30 但是，由1，2，3组成的3位

数最多只有27个（即3个相异元素取3个的所有重复排列），故由抽屉原理，至少由两段是相同的。 由上面的证明过程可以看出，位数30不能再少，否则，不能保证有两段相同。 若改为截取相邻的5位，首先可知元素1、2、3的5－可重排列共有24335个。其次，由问题的性质可知至少要能截取出不同的244段才能保证结论成立，从而知该数至少应该有248位。 问题的一般描述是：任意一个由数字1，2，…，m组成的n＝kmk位数，从中任意截取相邻的k位，则在各种不同位置的截取中，至少有两个k位数是相同的。若希望至少有r个k位数是相同的，则应有n＝kmrk1。

第六章

1. 一张卡片分成4×2个方格，每格用红蓝两色涂染，可有多少种方法？ （解）如图6.2.1，给每个方格标上号：1,2,…,8，相应的置换为（设卡片只能旋转，不能翻转）

1 2 3 4 5 6

7 8 图6.2.1 卡片染色

821

1p，

4536271812345678876543212p

由Pólya定理知，不同的染色方法数为

1L＝136222148 若卡片还能翻转，但同一个格子对应的正反面要求同色，则除了上述两个置换外，还有沿着横、竖两个对称轴翻转的置换 46352817p3

，

78563412p4

从而可知不同的染色方法数为

2L＝3224148＝76 若同一个格子对应的正反面不要求同色，且卡片既能旋转，又能翻转，则相应的置换为 HBAp8211

，

DECFBGAHp453627182

， BADCFEHGp876543213

，GHEFCDABp876543214

其中A，B，…，H是卡片的背面分别依序与1，2，…，8对应的格子。那么，此时的染色方法数为

3L＝32241816＝16 576

2. 正五角星的五个顶点各镶

嵌一个宝石，若有m种颜色的宝石可供选择，问可以有多少种方案？ （解）设正五角星的5个顶点分别依次为1,2,…,5，因正五角星是可以翻转的，故相应于正五角星的五个顶点的变换有两类，第一类是绕其几何中心的5个平面旋

转变换ip（即旋转72×i度），第二类是以某个顶点与其几何中心的连线为轴的翻转变换，对应的10个置换是

54321p1，

12345p2，13524p3，

14253p4，54321p5

34251q1，

452131q，32415q1，

43512q1，52314q1

由Pólya定理，不同的镶嵌方案数为

L＝3554101mmm

3. 有一个正方形木筐，用漆刷4边。现有三种不同颜色的漆，可有多少种不同的涂法？ （解）将正方形木筐的4条边依次记为1，2，3，4（见图6.2.3），由题意知木筐既可以旋转，又可以翻转。对应的置换为 绕正方形中心逆时针旋转

90i（3210,,,i）的置换

43211q，12342q，

24133q，43214q

以1-3、2-4两组对边的中心的连线为轴的翻转 32415q，42136q

以A-C、B-D两组对角线为轴的翻转 23147q，34128q A 1 B 4 2 D 3 C 图6.2.3 木筐染色 由Pólya定理知，不同涂法总数为 L＝323332381234＝21 第四章 4.某人参加一种会议，会上有6位朋友，他和其中每一人在会上各相遇12次，每二人各相遇6次，每三人各相遇4次，每四人各相遇3次，每五人各相遇2次，与六人都相遇1次，一人也没遇见的有5次，问该人共参加几次会议？ （解）设S为该人参加的所有会议组成的集合。iA为他遇见第i个朋友的所有会议构成的S的子集，则由题意知公共数 121iAR， 62jiAAR，43kjiAAAR, 34lkjiAAAAR ，25mlkjiAAAAAR， 16543216AAAAAAR， 61mlkji， 654321AAAAAA＝654321AAAAAA＝5。

由容斥原理 654321AAAAAA ＝iiiRiRRR6166126161616521 ＝1662563464366261216 ＝28 所以，该人参加的会议次数为 S＝654321AAAAAA＋654321AAAAAA ＝28＋5 ＝33 5.n位的四进制数中，数字1，2，3各自至少出现一次的数有多少个？ （解）设不含数字i的四进制数组成的的集合为iA 321,,i，则公共数 nR40，niAR31，njiAAR22，13213AAAR 由逐步淘汰原理（4.1.2）知所求的四进制数的个数为 0N＝321AAA＝3210332313RRRR＝123341nnn 6.某照相馆给n个人分别照相后，装入每人的纸袋里，问出现以下情况有多少种可能： （1） 没有任何一个人得到自己的相片； （2） 至少有一人得到自己的相片； （3） 至少有两人得到自己的相片。 （解）以任一装法为元素构成

的集合记为S，则!nS。设iA是第i个人的相片装对了纸袋的所有装法组成的集合。则公共数

kR＝kiiiAAA21＝)!(kn

（1）设所求为 1L，则由问题的性质知这是一个错排问题，故

1L＝0N＝nD，即

1L＝!!!!nnn1121111

（2）方法一 设所求为 2L，由对称公式（4.1.1＇）知所求为

2L＝

nAAA21＝nnRnnRnRn1211

21

＝



!!!!!nnn11

31211

11

方法二 问题（1）和（2）所对应的装法构成的集合是互为对立的，故

2L＝1LS＝





!!!!!nnn11

31211

11

（3）设所求为 3L，由保位问题知恰有一人得到自己相片的不同装法有1nD＝11nnDC种，所以 3L＝12nDL ＝



!!!!!nnn11

31211

11

－)!(!!)!(1112111111nnnn ＝!)!(!!!!nnnnn1112132221112 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 （a） （b） （c） 图4.4.3 有禁区的排列 由公式(4.4.7)可得到 R(A)＝( 1＋3x＋x2)( 1＋2x＋x2)＝1＋5x＋8 x2＋5x3＋x4 由定理4.4.2，所求排列数应为 N[B]＝4!－r1(A) 3!＋r2(A)2!－r3(A)1!＋r4(A)0! ＝4!－5×3!＋8×2!－5×1!＋1×0! ＝6 这6个满足条件的排列是

2314 2341 3214 3241 4231 4312 第三章

1、求递推关系32164nnnnaaaa的

通解。 （解）特征方程为

06423xxx，解之

得特征根

1q＝-1， 2q＝2，3q＝3

∴ 通解为 nnn

nCBAa321

其中，A、B、C为任意常数。

2、求递推关系04421nnnaaa的

通解。 （解）特征方程为0442xx，特征根是

二重根221qq，若按单根情形处理，有通解nnnnAAAa22221

，

即一个待定常数。要满足两个初始条件1100,dada，一般是不可能的。其实质在于按特征根确定的两个解nna21

和

nna22

是线性相关

的，即

22

221100

2111

2010aaaaD

。现在的问题就是要找两个线性无关的解1na和2na，使得

021112010aaaaD.

若令nnna22，可以验证2na是（3.2.1）的解，且与nna21线性无关。同时，仿照单根情形，可以证明通解为 nnnnAAa2221

一般情况下，设q是（3.2.1）的k重根，则（3.2.1）的通解为 k

knnAnAAa21

(3.2.5) 更一般的情形，若式（3.2.1）有t个根，其中iq为ik重根



kktitii1,,,2,1

，那么，通解应为 tikjjijninAa111

kknAnAA112111

n

tktkttqnAnAAtt121



(3.2.6)

3、上楼梯问题：某人欲登上n级楼梯，若每次只能跨一级或两级，问他从地面上到第n级楼梯，共有多少种不同的方法？

（解）设上到第n级楼梯的方法数为an ．那么，第一步无非有两种可能： （1） 跨一级，则余下的n－1级有an－1种上法；