第1章 排列与组合
1.1 从{1,2,…,50}中找一双数{a,b}，使其满足：()5;() 5.
a a
b b a b -=-≤
[解] (a) 5=-b a
将上式分解，得到55
a b a b -=+??
-=-?
a =
b –5，a=1，2，…，45时，b ＝6，7，…，50。满足a=b-5的点共50-5=45个点. a = b+5，a=5，6，…，50时，b ＝0，1，2，…，45。满足a=b+5的点共45个点. 所以，共计2×45=90个点. (b) 5≤-b a
(610)511(454)1651141531+?+?-=?+?=个点。
1.2 5个女生，7个男生进行排列，
(a) 若女生在一起有多少种不同的排列？ (b) 女生两两不相邻有多少种不同的排列？
(c) 两男生A 和B 之间正好有3个女生的排列是多少？
[解] (a) 女生在一起当作一个人，先排列，然后将女生重新排列。
（7＋1）!×5!=8!×5!＝40320×120=4838400
(b) 先将男生排列有7!种方案，共有8个空隙，将5个女生插入，故需从8个空中选5个空隙，有5
8C 种选择。将女生插入，有5!种方案。故按乘法原理，有：
7!×5
8C ×5!=33868800(种)方案。
(c) 先从5个女生中选3个女生放入A ，B 之间，有3
5C 种方案，在让3个女生排列，有3!种排列，将这5个人看作一个人，再与其余7个人一块排列，有
(7+1)! = 8!
由于A ，B 可交换，如图
**A***B** 或 **B***A**
故按乘法原理，有：
2×3
5C ×3!×8!=4838400（种）
1.3 m 个男生，n 个女生，排成一行，其中m ，n 都是正整数，若
(a) 男生不相邻(m ?n+1)； (b) n 个女生形成一个整体； (c) 男生A 和女生B 排在一起； 分别讨论有多少种方案.
[解] (a) 先将n 个女生排列，有n!种方法，共有n+1个空隙，选出m 个空隙，共有m
n C 1+种
方法，再插入男生，有m!种方法，按乘法原理，有：
n!×m
n C 1+×m!＝n!×
)!1(!)!1(m n m n -++×m!=)!
1()!
1(!m n n n -++种方案。
(b) n 个女生形成一个整体，看作一个人，与m 个男生做重排列，然后，n 个女生内部
再作排列，按乘法原理，有(m+1)!×n!种方案。
(c) 男生A 和女生B 排在一起，看作一人，和其余n-1+m-1=n+m-2个人一起，作排列，共有(n+m-2+1)=(n+m-1)!种方法，A ，B 两人内部交换，故有2×(n+m-1)!种方案。 1.4 26个英文字母进行排列，要求x 和y 之间有5个字母的排列数.
[解] 选入26－2＝24个字母中选取5个字母，有5
24C 种方法，5个字母内部排列，有
5!种方案，再将X*****Y 这7个字母看作一个，与其余19个合起来作排列，共有(19+1)!=20!种方案，又因为X 与Y 可交换，故按乘法原理，有：
2×5
24C ×5!×20!=2×!19!5!24?×5!×20!=40×24! ≈ 40×242?π×24
24?
?
? ??e 又因为：ln40+0.5(lg π+lg48)+24(lg24–lge)
≈1.602059991+0.5(0.497149872+1.681241237)+24(1.380211242-0.434294481) =25.39325777
所以，结果为2510?e ＝2.473191664×2510
1.5 求3000到8000之间的奇整数的数目，而且没有相同的数字. [解] 3000~8000中各位不同的奇数，分类讨论：
首位3，1×8×7×4（末位不能取3） 首位4，1×8×7×5（末位全取） 首位5，1×8×7×4 首位6，1×8×7×5 首位7，1×8×7×4 从而，由加法原理，得：
8×7×（4＋5＋4＋5＋4）=56×22＝1232个。 1.6 计算
11!22!33!!n n ?+?+?++?
[解] 1)!1(!!33!22!1
1-+=?++?+?+?n n n (参见p14) )!1!(1
1
∑-=?=-n k k k n
1.7 试证
(1)(2)(2)n n n ++
被2n 除尽.
[证] !
!)!12(!)!2(!)!2()2()2)(1(n n n n n n n n -=
=++ !)!12(2!!
)!12(!2-=-??=n n n n n n 故能被n
2整除。
1.8 求1040和2030的公因数. [解]因为1040=240·540，2030=(22·5)30=260·530,所以它们的公因数为形如2m ·5n 的数，其中0?m ?40，0?n ?30，故它们的公因数的数目为(40+1)(30+1)=1271。 1.9 试证n 2的正除数的数目是奇数.
[证]当n=1时，因数为10；当n=2时，因数为20，21，22；当n=3时，因数为30，31，32；
设1212n l
l
l
n n p p p = ，(12,,,,n p p p 均为质数)，则122222
12n l
l
l
n n p p p = 的正除数可表示为
12
12n k k k n p p p ，其中12,,,,n k k k 均为整数，且
112202,02,,02,n n k l k l k l ≤≤≤≤≤≤ ，所以2n 的正除数的个数为12(21)(21)(21)n l l l +++ ，结果是奇数的乘积为奇数。
1.10 证明任一正整数n 可惟一地表示成如下形式：
1
!,(0,1)i i i n a i a i i ≥=≤≤≥∑
[证].(1)可表示性：
令M={(a m-1,a m-2,?,a 2,a 1):0≤a i ≤i ，i=1,2,?,m-1}，显然|M |=m!；
N={0,1,2,?,m!-1}，显然|N |=m!，其中m 是大于n 的任意整数。 定义函数f : M →N
f (a m-1,a m-2,?,a 2,a 1)=a m-1(m-1)!+a m-2(m-1)!+?+a 22!+a 11! (*)
显然，0= 0(m-1)!+0(m-1)!+?+0?2!+0?1! ≤ a m-1(m-1)!+a m-2(m-1)!+?+a 22!+a 11!
≤ (m-1)(m-1)!+(m-2)(m-1)!+?+2?2!+1?1!= m!-1 （见P 14） 即0≤ f (a m-1,a m-2,?,a 2,a 1)≤m!-1
由于f 是用普通乘法和普通加法所定义的，故从而f 无歧义。从而有一确定的数K （0≤K ≤m!-1），使K =f (a m-1,a m-2,?,a 2,a 1)
为证N 中的任一数均可表示成上边(*)的形式，只要证明f 是满射函数即可。但由于在两相等且有限的集合上定义的函数，满射性与单射性、双射性是等价的，故只须证明f 是单射函数即可。
否则，设存在某数K 0∈N ,有(a m-1,a m-2,?,a 2,a 1)≠(b m-1,b m-2,?,b 2,b 1)均属于M ，使
K 0=f (a m-1,a m-2,?,a 2,a 1)且K 0=f (b m-1,b m-2,?,b 2,b 1)
由于不相等,故必有某个j(≤m-1)，使a j ≠b j 。不妨设这个j 是第一个不使相等的，即ai=bi )1,1(+-=j m i ，aj ≠bj 且aj a m-1(m-1)!+a m-2(m-1)!+?+a 22!+a 11!= b m-1(m-1)!+b m-2(m-1)!+?+b 22!+b 11! 就可有(b j -a j )j!+(b j-1-a j-1)(j-1)!+?+(b 2-a 2)2!+(b 2-a 1)1!=0 但是 (b j -a j )j!+(b j-1-a j-1)(j-1)!+?+(b 2-a 2)2!+(b 2-a 1)1! ≥(b j -a j )j!-[|b j-1-a j-1|?(j-1)!+?+|b 2-a 2|?2!+|b 2-a 1|?1!] ≥j!-[(j-1)?(j-1)!+?+2?2!+1?1!]=j!-(j!-1)=1 矛盾，这说明f 是单射函数。 由于|M |=|N |=m!有限，故f 是双射函数，当然是满射函数，从而0到m!-1中的任何一个数都可以表示成上边(*)的形式。故，由n ∈N ，都有(a m-1,a m-2,?,a 2,a 1)∈M ，使得 n=a m-1(m-1)!+a m-2(m-1)!+?+a 22!+a 11! 这就证明了任何n 可表示成以上形式。 (2)唯一性：用证明单射的方法，就可以证明表示法的唯一性(表示方法见P 14),留给读者。 1.11 证明(1,)(1)(,1)nC n r r C n r -=++，并给予组合解释. [证].(参见 P 28 (1-8-4)) )1,()1()1()! 1()!1(! )!1(!)!1(),1(++=+--+=---=-r n C r r r n r n r n r n n r n nC 组合意义：（等式右边）由n 个元素中取出r+1个元素组合（有C (n,r+1)种），再从每个组合中取出1个（有r+1种），全部结果为C (n,r+1)(r+1)。（等式左边）由此所得的全部结果相当于从n 个元素中直接取1个元素（有n 种），但有重复，其重复数等于剩下的n-1个元素中取r 个元素的组合C (n-1,r)，故n C (n-1,r)= (r+1)C (n,r+1)。 1.12 试证等式： 1 1 (,)2 n n k kC n k n -==∑ [证].证法一：根据二项式定理，(参见 P 29 (1-8-5)) (1+x )n =1+C (n,1)x +C (n,2)x 2+?+ x n 两边对x 求导，有n(1+x )n-1=C (n,1)+2C (n,2)x +?+ n x n-1 令x =1，即得112),(-==∑n n k n k n kC 。 证法二：组合意义：设有n 个不同的小球，并有A 、B 两个合子，A 合中恰好放入一个球，B 合中可放入任意多个球。有两种放球方法： (1)（等式左边）先从n 个球中选取k 个，再从这k 个球中任选一个放入A 合，剩下的k-1个球全部放入B 合中，方案数共为∑=n k k n kC 1),(； (2)（等式右边）先从n 个球中任选一个放入A 合，剩下的n-1个球每个都有两种可能，要么放入B 合，要么不放，方案数共为n2n-1； 显然，两种放球方法等效，两种放球方案数相等，即112),(-==∑n n k n k n kC 。 1.13 有n 个不同的整数，从中取出两组来，要求第1组的最小数大于另一个组的最大数. [解] 设这n 个不同的数为n m m m m <<<< 321。 若假定第一组取k 1个数，第二组取k 2个数，并且令m=k 1+k 2(m ≥2)，则要求第一组数里的最小数大于第二组的最大数，我们只要先从上边那n 个数中任选m 个数(有C(n,m)种选法)，再从这m 个数中从大到小取k 1个数作为第一组数(有k 1=1,2,?,m-1共m-1种取法)，将其余k 2个数作为第二组数，即可。故总方案数为 12)2(),()1(12 +-=--=∑n n m n m n C m （参见第3题等式） 。 1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从特定一引擎开始有多少 种方案？ [解] 第一次点火仅有一种选择，即点某个特定引擎的火；第二次点另一组某个引擎的火，有三种选择；第三次有2种,……。 即方案数为1?3?2?2?1?1=12。 1.15 试求从1到1 000 000的整数中，0出现的次数. [解] (参见P 8)从1到1 000 000的整数中，0出现的次数相当于10-99，100-999，1000-9999, 10000-99999,100000-999999,以及1 000 000中的0的个数。 10-99中的零的个数为： 9 100-999中的零的个数为： 180818118999992=++=?+?+?个位为零 十位为零 两个零 取法，有的每一种故对百位位为零，十位、个 1000-9999中的零的个数为： 有一位为零 有两位为零 有三位为零 999992931 323???+???+?C C =27+486+2 187 =2 700 10000-99999中的零的个数为： 有一位零 有二位零 有三位零 有四位零 99999992993941 42434????+????+???+?C C C =36+972+8 748+26 244 =36 000 100000-99999中的零的个数为： 有一位零 有二位零 有三位零 有四位零 有五位零 99999999929993994951 5253545?????+?????+????+???+?C C C C =45+1 620+21 870+131 220+295 245=450 000 1，000，000中的0的个数为： 6 故1到1，000，000的整数中0的个数为：9+180+2 700+36 000+450 000+6=488 895。 1.16 n 个完全一样的球放到r 个有标志的盒（n ?r ）中，无一空盒，试问有多少种方案？ [解] 1.17 n 和r 都是正整数，而且r ?n ，试证下列等式： 1 1 111111111()()(1)(),()()!() n n r r n n r r n n r r n n n r r r n n n r r r r r a P nP b P n r P n c P P r n n r d P P rP e P r r P P P ----+-+----==-+= <-=+=++++ [解] (a) 方法一 1 1 ! (1)(1)(1)[1(1)1] ()! (1)![(1)(1)1]! n r n r n P n n n r n n n r n r n n nP n r --==--+=----+--==---+ 方法二（组合意义） 等式左边：从n 个元素种取r 个元素做排列有n r P 种，就是等式左边； 等式右边：先从n 个元素中拿出一个元素排在首位，有n 种方法，然后再从剩下的n-1 个元素中取r-1个元素做后面r-1位的排列,有11--n r P 种方法,按乘法原理,共有n 1 1--n r P 种方法。 (b) 方法一 1 ! (1)(2)(1) ()! (1)(1)[(1)1]! (1) (1)[(1)]! n r n r n P n n n r n r n r n r n n n r n n r n r P n r -= =--+-+-=-+?---+=-+=-+-- 方法二（组合意义法） 等式左边：从n 个元素中取r 个元素做r 位排列，有n r P 种方案。 等式右边：先从n 个元素中取r-1个元素做r-1位排列，有n r P 1-种方法；再从剩下的n-r+1个元素中取1个元素，共有n-r+1种选法，按乘法原理，共有n r P r n 1)1(-+- (c) 方法一 1! (1)(2)(1) ()!(1)(2)(2)(1)()(1)!(1)(1)[(1)1][(1)]!n r n r n P n n n r n r n r n n n r n r n r n r n r n n n n n n r n r P n r n r n r n r -= =--+-+-=--+-+-+---=--+--+==----- 方法二：（组合意义法） 等式左边：从n 个元素中取r 个元素做r 位排列，其方案数为n r P ； 等式右边：从n 个元素中先取出一个元素放在第一位，有n 种方法，再从剩下的n-1个元素种取出r 个元素放在第2位，…，第r 位，第r+1位，有1-n r P 种方法，这样就多了一位，故应除去第r+1位的选取方法，共有n-r 种选法，故总方案为 1--n r P r n n 。 (d) 方法一 11 (1)! (1)(2)[(1)](2) (1)! (2)(1)[(1)1]!! ()!(1)! n r n n r r n P n n n r n r r n n r n r n n r n r r n n r n r n P rP n r n r +-+= =+-+=-++-++-=-+-++?--+?= +=+--+ 方法二：（组合意义） 等式左边：从n+1个不同的元素中取r 个元素进行r 位排列。其方案为1+n r P ； 等式右边：(a) 不取某特定元素b ，则r 个元素需从剩下的n 个元素中取，然后做r 位 排列，共有n r P 种方案。 (b) 取定某特定元素b ，则其余r-1个元素需从剩下的n 个元素中取，先做r-1位排列，共有n r P 1-种方法，再将特定元素b 插入这r-1个元素形成的r 个空隙中，有r 种方法，故按乘法原理，共有r n r P 种方案。 (e) 方法一 （根据(d)可得） 11 1111 221111221111 111111*********!()!(n n n r r r n n n r r r n n n n r r r r n n n n r r r r r r r n n r r r r r r r n n r r r r n n r r P P rP P rP rP P rP rP rP P rP rP rP P rP rP rP rP r r P P P P r r P P P +-----------------+-----+--------=+=++=+++=+++=+++++=+++++=++++ 111 r r r r P +--+ 方法二：组合意义（同样根据d ） 等式左边：从n+1个不同元素取r 个元素做r 位排列，其方案数为：1+n r P 等式右边：设r n b b b b -+1321,,,, 是n-r+1个特定元素。 (a) 不取特定元素r n b b b b -+1321,,,, ，剩下的r 个元素做全排列，有r r P =r!种方案。 (b)(1)：取特定元素1b ，但不取特定元素r n b b b -+132,,, ，于是先在剩下的r 个元素中取r-1个元素做排列，有r r P 1-种方法，然后将1b 插入这r-1个元素的r 个空隙，共有r 种方法，故按乘法原理，有r r r P 1-种方案。 (2)：取特定元素1b ，但不取特定元素r n b b -+13,, ，于是先在剩下的r+1个元素中取r-1 个元素做排列，有1 1+-r r P 种方法，然后，将1b 插入这r-1个元素的r 个空隙，共有r 种方法，故按乘法原理，有r 11+-r r P 种方案。 …… (n-r)：取特定元素1b ，但不取特定元素r n b -+1，于是先在剩下的n-1个元素中取r-1个 元素做排列，有11--n r P 种方法，然后，将1b 插入这r-1个元素的r 个空隙，共有r 种方法，故按乘法原理，有r 11--n r P 种方案。 (n-r+1）：取特定元素1b ，先在剩下的n 个元素中取r-1个元素做排列，有n r P 1-种方法，然后，将1b 插入这r-1个元素的r 个空隙，共有r 种方法，故按乘法原理，有r n r P 1-种方案。 最后，按加法原理，共有： 1111!()n n n r r r r r P P P ----++++ 1.18 8个盒子排成一列，5个有标志的球放到盒子中，每盒最多放一个球，要求空盒不相邻，问有多少种排列方案？ [解] 先将5个球进行全排列，有5!种方法，再将三个空格插入5个球的6个空隙中，有 6 3C 种方法，然后将这些元素的排列一对一的放入8个盒子中，即完成了每盒最多一球，空盒不相邻的放球要求，总方案有：6 35!2400C ?=（种） 1.19 n+m 位由m 个0，n 个1组成符号串，其中n ?m+1，试问不存在两个1相邻的符号串的数目。 [解]：先将m 个0排成一排，再将n 个1插入m 个0的m+1个空隙（因为n ?m+1,这可实现）,就得到了无相邻的n+m 位0-1符号串，其方案数为??? ? ??+n m 1。 1.20 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，由他们产 生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志5位.试问有多少种方案？ [解] 甲单位选4人，则乙单位只能选3人；另外男同志要5人，而乙单位的3人全是男同志，还差2名男同志，故甲单位的男同志人数应至少是2，至多为4。 768600210115044101102151431001031524210=??? ? ?????? ?????? ?????? ??+???? ?????? ?????? ?????? ??+???? ?????? ?????? ?????? ?? 1.21 一个盒子里有7个无区别的白球，5个无区别的黑球. 每次从中随机取走一个球，已知前面取走6个，其中3个是白的. 试问取第6个球是白球的概率. [解] 已知前面取走6个球，有3个白球，则有3个黑球。 故总的取球方案是34556736????????? ? ??； 第六个球是白球的方案是34556725????????? ? ?? 因此取出第6个球是白球的概率5.0213455673634556725==????????? ? ???????????? ??= P 1.22 求下图中从0到P 的路径数： (a) 路径必须过A 点； (b) 路径必须过道路AB ； (c) 路径必须过A 和C ； (d) 道路AB 封锁（但A ，B 两点开放）. [解] O(0,0), A(3,2), B(4,2), P(8,5), C(6,3) (a) 路分为两段：先从O 到A ，再从A 到P ，则有： ???? ??--+-???? ??+2525382235603825=???? ?????? ??= (b)路分为三段：先从O 到A ，再从A 到B ；再从A 到B ；然后从B 到P ； 35037252525481223=???? ?????? ??=???? ??--+-?????? ??+ (c) 路分为三段：先从O 到A ；再从A 到C ；然后从C 到P ； 240241425353568232336223=???? ?????? ?????? ??=???? ??--+-????? ??--+-????? ??+ (d) (采用排除法) 从O 到P 的满足不过AB 的路 ＝ 从O 到P 的路－从O 到P 经过AB 的路，因此： 85328452131350128735093752525++-+-????????-??=-=-= ? ? ? ?-???????? 1.23 另s={1,2,3…,n+1},n ?2 {(,,)|,,,,}T x y z x y z s x z y z =∈<<，试证： 21112223n k n n T k =++???? ==++ ? ????? ∑ [证] ()2 11112111 1 1 11n z z n n z y x z k T z k +--+=======-=∑∑∑∑∑ 而()1331233 +++=+k k k k ，故()[] 1313 1 332 ---+= k k k k ()()()()n n n n 32 33 11113 322 113(1)311133211(1)11111(1)(1)(1)(1)323233 11111(1)(1)(1)(2131) 2233312k k k k k k k k n n n n n n n n n n n n n n n n n n n n n n n n n ====????=+---=+--+-???????? += +-+- =+++-+-+++??????=+++--=++++-- ? ? ???????+?= ?∑∑∑∑2 1111(1)(1)(1)()222233321n n n n n n n n n +++???????+-++-=+?=+? ? ? ?????????? 1.24 A ={(a , b)|a , b ∈Z, 0?a ?9,0?b ?5} (a) 求x-y 平面上以A 作顶点的长方形的数目. (b) 求x-y 平面上以A 作顶点的正方形数目. [解] (a) 先选定横作标，再选定纵坐标，其方案数为： 675256291026210=???=???? ?????? ?? (b) 求x －y 平面上以A 作顶点的正方形数目。 按边长分类： 边长为1的正方形：9×5＝45 边长为2的正方形：(9-1)×(5-1)=32 边长为3的正方形：(9-2)×(5-2)=21 边长为4的正方形：(9-3)×(5-3)=12 边长为5的正方形：(9-4)×(5-1)=5 故总的以x －y 平面上A 点作顶点的正方形的数目，按加法原理可得数目为115. 1.25 平面上有15个点P 1, P 2, … , P 15，其中P 1, P 2, P 3, P 4, P 5共线，此外不存在3点共线的. (a) 求至少过15个点中两点的直线的数目. (b) 求由15个点中3点组成的三角形的数目. [解] (a) (采用排除法) 至少过15个点中两点的直线数目＝在15个点中任选2个点将有一条直线－从1P ～5 P 中选2点构成直线＋1P ～5P 所在的直线l 96125215=+???? ??-???? ??= (b) (采用排除法) 由15个点中3点组成的三角形的数目＝任在15个点中取3点构成三角形的数目－在5个点1P ～5P 中取3点构成的“三角形”的数目 44535315=???? ??-???? ??= 1.26 S={1, 2, … , 1000}，a ，b ∈S ，使ab ≡0 mod 5，求数偶{a, b}的数目. [解] 因为 5m od 0≡ab 所以 ab ＝5k （k 是整数） 1?a ?1000, 1?b ?1000 1?ab ?1000000 1?5k ?1000000 1?k ?200000 所以满足 5m od 0≡ab 且1?a,b ?1000的{a,b}的数目为200000 1.27 6位男宾，5位女宾围一圆桌而坐 (a) 女宾不相邻有多少种方案？ (b) 所有女宾在一起有多少种方案？ (c) 一女宾A 和两位男宾相邻又有多少种方案？ [解] (a) 先将6位男宾作圆排列有120!56 6==Q 再将5位女宾插入6个空格，每格一人，共有6×5×4×3×2×1＝720 按乘法原理：有120×720＝86400 (b) 5位女宾在一起，可看作一人，与6位男宾一起，先做圆排列，有7 7Q =6!=720 然后5位女宾内部作线排列，有5!＝120。 所以，总方案为：720×120＝86400 (c)先将6个男宾做圆排列，共有6 6Q =120种方法。 再将女宾A 随便插入6个空格中的一个，有6种方法。 然后将剩下的4个女宾插入5个空格中，但每个空格不限人数，故相当于将4个有区别 的球放入5个不同的盒子中的放球方案(可重组合)，共有??? ? ??-+4154=5×6×7×8＝1680。 所以，按乘法原理，有120×6×1680＝1209600种方案。 1.28 k 和n 都是正整数，kn 位来宾围着k 张圆桌而坐，试求其方案数. [解] 先将k ×n 个来宾分成k 堆，每堆n 个人，有 k n kn n n n kn k n n n kn )!()!(!!!)!()(,,,=??? ?????=???? ?? 堆 再将每堆n 个人做圆排列，有n n Q ＝(n-1)!,共有k n ])!1[(-种方法。 故按乘法原理，有 []k k k n kn n n kn )!()!1()!()!(=- 1.29 从n 个对象中取r 个作圆排列，求其方案数目. 已知1?r ?n. [解] 每一个r 个人围成的圈（圆排列）r r a a a a ,,,,121- ????? ???---1 211 32121,,,,,,,,,,)(r r r r r r a a a a a a a a a a a a 线排列 即每一个r 圈相当于r 个r 排列。故不同的方案数为)! (! 1),(1r n n r r n P r N -= = 若不计顺逆方向，则为)! (! 21),(21r n n r r n P r N -? ==。 1.30 试证下列等式 1(),111(),111(),0n n n a r n r r r n n n r b r n r r r n n n c r n r r n r -???? =≤≤ ? ?-???? ????-+=≤≤ ? ?-???? -????=≤≤ ? ?-???? [证] (a) 方法一 1!(1)!1!()!(1)![(1)(1)]!n n n n n n r r r n r r r n r r -???? -==?= ? ?---?---???? 方法二：组合意义法： 一方面，从n 个元素中取出r 个元素，然后再做排列，故按乘法原理，其数目为 !r r n ????? ?? 另一方面：先从n 个元素中取出1个元素，排在第一位，再从剩下的n-1个元素中取出r-1个元素，并将这r-1个元素排在第2～r 位，故按乘法原理，其方案数为 )!1(11-???? ? ??--r r n n 这两方面的组合意义相同，故有)!1(11!-???? ? ??--?=????? ??r r n n r r n 因此，有：??? ? ??--=???? ??11r n r n r n (b) 方法一 ()(1)(2)(1)!1(1)(2)11(1)!n n n n r n r r r n n r n n n r n r r r r r ??--+-+= ??? -+??--+-+=?=? ? --?? 方法二：组合意义 一方面：从n 个元素中取出r 个元素来，然后，在做排列，故按乘法原理，其方案数为 !r r n ????? ?? 另一方面：先从n 个元素中先取出r-1个元素，将其排排列再第1～r-1位，再从剩下的n-r+1个元素中取出1个元素排在第r 位。故按乘法原理，其方案数为： ())1(!11+-?-????? ??-r n r r n ； 这两方面的组合意义相同，故有 !r r n ?? ??? ??＝())1(!11+-?-????? ??-r n r r n 所以，有： ???? ??-+-=???? ??11r n r r n r n (c) 方法一 (1)(1)()(1)1 !()(1)1(1)(1)()(1)1 !(1)1 1(1)!!(1)!n n n n r n r n r r r n r n r n n n r n r n r n r r n r n n n n r n r r n r n r ??--+---= ?---?? --+---=? ----?? -= ?= ?----?? 方法二：组合意义 一方面，从n 个元素中取出n-r 个元素，然后再做排列，按乘法原理，其方案数为： )!()!(r n r n r n r n n -???? ??=-???? ??- 另一方面，选从n 个元素中取出1个元素排再第一位，再从剩下的n-1个元素中选取 n-r+1个元素，排在第2～n-r 位。故按乘法原理，其方案数为 ())!1(1!111--????? ??-?=--????? ??---?r n r n n r n r n n n 这两方面的组合意义相同，可得： ()!11)!(--????? ??-?=-???? ??r n r n n r n r n ???? ??--=???? ??r n r n n r n 1 1.31 试证任意r 个相邻数的连乘： (1)(2)()n n n r +++ 被r ！除尽. [证] !!!!)! ()()2)(1(r r r n r n r r n r n n n ???? ? ??+=+= +++ 由于???? ??+r r n 是从n+r 个元素中选取r 个元素的组合数，故当然是整数，因此，(n+1)(n+2)…(n+r)可以整除r!，其商为组合数??? ? ??+r r n 。 1.32 在a, b, c, d, e, f, x, x, x, y, y 的排列中，要求y 必须夹在两个x 之间，问这样的排列数等 于多少？ [解] 由于y 必须乘在两个x 之间，故两个y 只能夹在仅有的三个x 之间，形成图象xyxyx ，形成6个空档。其余的6个元素a,b,c,d,e,y,只能放在这6个空格处，这相当于将6个不同的小球放入6个不同的盒子中，允许空盒，且盒内还要排列的方案数。故： 332640!6!5! 11!616166!6=?=???? ??--+ 1.33 已知r, n, k 都是正整数，r ?nk ，将r 个无区别的球放在n 个有标志的盒子里，每盒至 少k 个球，试问有多少种方案？ [解] 先将nk 个球放入n 个有标志的盒中，每盒k 个球，其方案为1。 再将剩下的r-nk 个球放入这n 个盒中，每盒球数不限，其方案数为 ???? ??----=???? ??---+11)1(1)(n k n r nk r nk r n 故总的方案为 ? ??? ??----=???? ??---?11)1(1)1(1n k n r n k n r 1.34 在r, s, t, u, v, w, x, y, z 的排列中求y 居x 和z 中间的排列数. [解] 由于y 必须居于x 和z 之间，故形成图象xyz ，形成4个空格。其余r,s,t,u,v,w 这6个元素，只能放在这4个空格处，这相当于将6个不同的小球放入4个不同的盒子中，允许空盒，且盒内还要进行排列的方案数。故有： 60480!6!3! 9!614146!6==???? ??--+? 将9个字母进行全排列，有9!中排列，而x,y,z 这3个字母形成的3!个排列只看作一种排列xyz ，故有： 60480! 3! 9= 1.35 凸十边形的任意三条对角线不共点. 试求这凸十边形的对角线交于多少个点？ [解] 从一个顶点可引出7条线和第一条（从右到左）交的有1?7，和第二条交的有2?6条,故和一个顶点引出的7条线相交的点为： 1?7+2?6+3?5+4?4+5?3+6?2+7?1=84 故和从10点引出的对角线交的点有个84?10=840，但每个点重复了四次（因为每个点在两条线上，而每条线有两个端点）。故凸10 边形（这样的）对角线交于 2104 840 =个点, 故也可为2101 2347 89104 10 =??????=C 1.36 试证一整数是另一整数的平方的必要条件是除尽它的数的数目是整数. [证] “必要性”。若整数n 是另一个整数的平方，则n 一定可写成如下形式： e e P P P n ααα222212 1 = （参见P7例4） 其中P1,P2,?,Pe 是e 个不同的素数。由于第9题可得，除尽n 的正整数数目为 (2α1+1)(2α2+1)?(2αe+1)为奇数。 “充分性”。若除尽正整数n 的正整数的数目为奇数。则n 一定是某个正整数的平方，否则，n 不是平方数，则n 一定是可分解成如下形式： e e P P P n βββ 2121= 其中P1,P2,?,Pe 是e 个不同的素数，且β1,β2,?,βe 中至少有一个奇数（否则n 为平 方数）。于是(2β1+1)(2β2+1)?(2βe+1)必为偶数，与充分性假设矛盾。 1.37 给出 11221011220n r n r n r n m r m n r m m m m m -+-+-+++?????????????????? ++++= ??? ??? ??? ??? ?--?????????????????? 的组合意义. [证] 组合意义一： 从(n+r+1)个元素{1,2,?,n+r+1}中取出)1(m r n -++个元素i 1 ? ??++=???? ??-++++m r n m r n r n 111。其中第r+1个位置上的元素i r+1可取 r+1,r+2,?,r+1+m 。 当i r+1取(r+1+k)时(k=0,1,2,?,m)，前边r 个数i 1,i 2,?,i r 可在{1,2,?,r+1+(k-1)}这(r+k) 个数里取，故有??? ? ??+=???? ??+k k r r k r 种取法；后边[(n+r+1-m)-(r+1)]=n-m 个数i r+2,?,i n+r+1-m 可 在{r+1+k+1, ?,n+r+1}这[(n+r+1)-(r+1+k)]=n-k 个数中取，故有???? ??--=???? ??--k m k n m n k n 。根据乘 法原理，当i r+1=r+1+k 时，这样的组合数为??? ? ??+???? ??--=???? ??+?????? ??--k k r k m k n k k r k m k n 1。根据加法 原理，对k=0,1,2,?,m 作和，就有 ???? ??++=???? ??+???? ??-++???? ??+???? ??--+???? ??+???? ??--+???? ?????? ??m r n m m r m n r m n r m n r m n 10222211110 。 注：参见《 Combinatorial Problems and Exercise 》 by L.Lovasz 0143.7 L896c P 18-42 (i) P 96 P 172 (i)The number of those(n+r+1-m)-tuples of{1,2,?,n+r+1}Whose )1(+r st element is r+k+1is ??? ? ??--???? ??+k m k n k k r . Summing for k=0,1,2,?,m,we get the result. 组合意义二：（格路方法） 等式左端：从点A(-r-1,0)到点C(-1,k)(k=0,1,2,?,m)直接经过点D(0,k)再到点B(n-m,m)的路径数(参见本题图1)； 等式右端：从点A(-r-1,0)到点B(n-m,m)的路径数。 1.38 给出1211r r r n n r r r r r +++?????????? ++++= ? ? ? ? ?+?????????? 的组合意义. [证].组合意义一： 等式右端是从n+r+1个元素121,,,+n a a a 中取出r+1个作不允许重复的组合，结果不外乎有以下几种情况(参见P 25等式3的组合意义)： (1) r+1个元素的组合中含有1a 的，相当于从n 个元素1 32,,,+n a a a 中取r 个组合，其组合数为? ?? ? ??r n （即A ）。 (2)r+1个元素的组合中不含有 1a ，但又含有元素2a 的。即一个(r-1)- 组合。依1a 来分，不外乎含1a 和不含1a ；不含1a 的又依2a 分，不外乎含2a 和不含2a 。不含1a 而含2a 的组合，相当于从n-1个元素132,,,+n a a a 中取r 个元素的组合，然后加上2 a 第16题图1 而成，其组合数为??? ? ??-r n 1() 21A A 即。 (3)r+1个元素的组合中不含1a 和2a ，但含有元素3a 的。即不含21,a a 的依3a 来分，不外乎含3a 和不含3a 。不含21,a a 而含3a 的组合，相当于从n-2个元素14,,+n a a 中取出r 个元素的组合，然后再加上3a 而成，其组合数为??? ? ??-r n 2() 321A A A 即。 取出的r+1个组合元素中不含1r n 321a ,,a ,a ,a -- ，但含有元素r n a -的。即不含 1321,,,,--r n a a a a 的，又依r n a -来分，不外乎含有r n a -和不含有r n a -。不含1 21,,,--r n a a a 而含r n a -的组合，相当于从n-(n-r-1)=r+1个元素11,,,+---n r n r n a a a 中取出r 个元素的组合 而加上r n a -而成，其组合数为??? ? ??+r r 1)(121r n r n A A A A --- 即。 (4)由121,,,++-+-n r n r n a a a 组成的(r+1)-组合的组合数为???? ??=???? ??++r r r r 11 )(21r n A A A - 即。而且 ) ()()()()(121121321211即全集X =------r n r n r n r n A A A A A A A A A A A A A A 组合意义二： 等式右端：从n+1个不同元素a 1,a 2,?,a n ,a n+1,中任选r+1个元素的组合方案数； 等式左端：从n+1个不同元素a 1,a 2,?,a n ,a n+1,中选取r+1个元素，一定选元素a r+k+1(k=0,1,2,?,n-r)，但是不选元素a r+k+2,?,a n ,a n+1的组合方案数。 1.39 证明 120110n m m m m m m n m n n n n --??????????????+++= ??? ??? ??? ?-?????????????? [证].借助P 28等式4，可知：??? ? ?????? ??=???? ??--???? ??r n n m r n r m r m (n ≥r) (r=0,1,2,?,n) 从而有???? ??-???? ??++???? ??--???? ??+???? ?????? ??01110n m n m n m m n m m ??? ? ?????? ??++???? ?????? ??+???? ?????? ??=n n n m n n m n n m 10 ?????????? ??++???? ??+???? ?????? ??=n n n n n m 10??? ? ??=n m n 2(用了P 29等式5) 组合意义一： 等式右端可看作从m 个元素中取出n 个元素进行组合。然后对这取出的n 个元素进行 染色（红，白）的所有方案，它为n n m 2??? ? ??； 等式左端可看作先从m 个元素中取出k 个元素（个数为???? ??k m ） ，全部染以红色。再从剩下的(m-k)个元素中取出(n-k)个元素（个数为???? ??--k n k m ） ，全部染以白色。根据乘法原理，从m 个元素中取出n 个元素，k 个染上红色，(n-k)个染上白色的方案数为??? ? ??--???? ??k n k m k m ， k=0,1,2,?,n ； 而从m 个元素中取出n 个元素染以红白两色的方案可分解成有0个，1个，…，n 个染以红色的总和。故根据加法原理，17题成立。 组合意义二： 等式右端：将从m 个不同的小球中任意选出的n 个小球放入两个不同的合子里，注意到每个小球都有两种放法，就得到了可能的放球方案数； 等式左端：先从m 个球中任选k 个球放入第一个合子里(k=0,1,2,?,n)，再从剩下的m-k 个球中任选n-k 个球放入第二个合子里，然后对k 从0到n 求和，就得到了所有可能的放球方案数。 1.40 从n 个人中选r 个围成一个圆圈，问有多少种不同的方案？ [解].每一个r 个人围成的圈（圆排列）r r a a a a ,,,,121- ????? ???---1 211 32121,,,,,,,,,,)(r r r r r r a a a a a a a a a a a a 线排列 即每一个r 圈相当于r 个r 排列。故不同的方案数为)! (! 1),(1r n n r r n P r N -= = 若不计顺逆方向，则为)! (! 21),(21r n n r r n P r N -? == 。 1.41 分别写出按照字典序由给定排列计算其对应序号的算法及由给定序号计算其对应排列 的算法. [解].（略） 1.42 (a) 按照1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法. (b) 写出按照邻位对换法由给定排列生成其下一个排列的算法. [解].（略） 1.43 对于给定的正整数n ，证明，当 11 n 22 n 2 n n k n -+???=????或，若是奇数，若是偶数时，C(n,k)的最大值. [证] 取C (n,k)与C (n,k-1)进行比较。C (n,k)/C (n,k-1)=(n-k+1)/k 。 当k 因此，得到当k=n/2或最接近n/2时，C (n,k)取得最大值。 1.44 (a) 用组合方法证明 (2)!2n n 和(3)! 23 n n n ?都是整数. (b) 证明21 ()! (!)n n n +是整数. [证] (a)考虑2n 个不同的球放入n 个不同的合子里，每合两个的方案数。这个方案数应该是整数。 对2n 个球进行排列的方案数为(2n)!。而把2个球放入同一个合子里不计顺序，重复因子是2。n 个合子内部的排列共重复计算了2n 次，故总的重复因子是2n 。因此，把2n 个不 同的球放入n 个不同的合子里，每合两个的方案数是n n 2)!2(。所以，n n 2 )! 2(是整数。 同理，考虑3n 个不同的球放入n 个不同的合子里，每合3个的方案数。这个方案数应该是整数。 对3n 个球进行排列的方案数为(3n)!。而把3个球放入同一个合子里不计顺序，重复因子是3!=2?3。n 个合子内部的排列共重复计算了2n ?3n 次，故总的重复因子是2n ?3n 。因此， 把3n 个不同的球放入n 个不同的合子里，每合3个的方案数是n n n 32)!3(?。所以，n n n 3 2)! 3(?是整 数。 (b)考虑n 2个不同的球放入n 个相同的合子里，每合n 个的方案数。这个方案数应该是整数。 对n 2个球进行排列的方案数为(n 2)!。而把n 个球放入同一个合子里不计顺序，重复因子是n!。n 个合子内部的排列共重复计算了(n!)n 次，故重复因子是(n!)n 。另外，由于n 个合子相同，放入不同的合子是没有区别的，其重复因子是n!。故此，总的重复因子是(n!)n+1。 因此，把n 2 个不同的球放入n 个相同的合子里，每合n 个的方案数是12)!()!(+n n n 。所以，1 2) !()! (+n n n 是整数。 1.45 (a) 在2n 个球中，有n 个相同. 求从这2n 个球中选取n 个的方案数. (b) 在3n+1个球中，有n 个相同. 求从这3n+1个球中选取n 个的方案数. [解] (a)相当于从n 个不同的小球中取出m 个小球(0≤m ≤n),再从n 个相同的小球中取出n-m 个小球，m=0,1,2,?,n 的方案数。 根据加法原理，这个方案数应该是：C (n,0)+ C (n,1)+?+ C (n,n)=2n 。 同理，考虑3n 个不同的球放入n 个不同的合子里，每合3个的方案数。这个方案数应该是整数。 (b)相当于从2n+1个不同的小球中取出m 个小球(0≤m ≤n),再从n 个相同的小球中取出 n-m 个小球，m=0,1,2,?,n 的方案数。 根据加法原理，这个方案数应该是：C (2n+1,0)+ C (2n+1,1)+?+ C (2n+1,n)。 1.46 证明在由字母表{0, 1, 2}生成的长度为n 的字符串中 (a) 0出现偶数次的字符串有 31 2 n +个； (b) 231222 ,20222n n n n q n n n n q q --??????+?? +++== ? ? ??????????? 其中 [证] (a)方法一：采用（串值）数学归纳法 ［基始］当n=1时，0出现偶数次，长度为1的字符串有2 1 31+=2个（即1和2两个 长度为1的字符串）。所证结论成立； ［归纳假设］当n=m(1≤m ≤k)时，假设所证结论成立。即，0出现偶数次，长度为m 的字符串有2 1 3+m 个； ［归纳］当n=k+1时，0出现偶数次，长度为k+1的字符串包括两部分： (1)给0出现偶数次，长度为k 的字符串后面再增加一位不是0的数（只能是1或2），因此，按乘法原理，由归纳假设，此种字符串有2 13+k ?2=3k +1个； (2)给0出现奇数次，长度为k 的字符串后面再增加一位是0的数，因此，按乘法原理， 由归纳假设，此种字符串有??? ? ??+-2133k k ?1=21 3-k 个； 所以，按加法原理，0出现偶数次，长度为k+1的字符串共有 (3k +1)+2 13-k = 21 31++k 个。所证结论成立；归纳完毕。 方法二：采用指数型母函数方法 设：a n —0出现偶数次，长度为n 的字符串的个数，则{a n }的指数型母函数 24623 2323232233()!(1)(1) 2!4!6!1!2!3!2213(3)(3)[(1)(1)]21!2!3!1!2!3!1(31)(31)(31)[(11)]21!2!3! n n n x x x x x x A x a n x x x x x x e e e e e x x x x x x x x x ∞ =-=? =+++++++++=?+= =++++++++++++=+++++∑ 作业习题答案 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n 个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。 证明： 方法一： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为 奇数+奇数 = 偶数 ； 偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 方法二： 对于平面上的任意整数坐标的点而言，其坐标值对2取模后的可能取值只有4种情况，即：(0,0) ,(0,1) ,(1,0), (1,1)，根据鸽巢原理5个点中必有2个点的坐标对2取模后是相同类型的，那么这两点的连线中点也必为整数。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.9将一个矩形分成(m +1)行112m m +?? + ??? 列的网格每个格子涂1种颜色，有m 种颜色可以选择，证明：无论怎么涂色，其中必有一个由格子构成的矩形的4个角上的格子被涂上同一种颜色。 证明： （1）对每一列而言，有（m+1）行，m 种颜色，有鸽巢原理，则必有两个单元格颜色相同。 （2）每列中两个单元格的不同位置组合有12m +?? ??? 种，这样一列中两个同色单元格的位置组合共有 12m m +?? ??? 种情况 （3）现在有112m m +?? + ??? 列，根据鸽巢原理，必有两列相同。证明结论成立。 2.11证明：从S={1,3,5,…,599}这300个奇数中任意选取101个数，在所选出的数中一定存在2个数，它们之间最多差4。 证明： 第五章 区组设计与编码 1.拉丁方与正交拉丁方 拉丁方：由1，2，…，n 构成n ×n 方阵n n ij a ?)(，如果每行每列中1，2，…，n 各出现一次，则称此方阵为拉丁方。 如： ??? ? ? ?=12212 n ???? ? ? ?????? ? ?=12 3312231 21 3132321 3 n 正交换丁方：设()() n n ij n n ij a A a A ??==) 2(2) 1(1是两个n ×n 的拉丁方，如果矩阵 ()() n n ij ij a a ?) 2()1(,中2n 个数偶()) 2()1(,ij ij a a 互不相同，n j i ,,2, 1, =， 则称1A 和2A 正交，或称1A 和2A 是互相正交的拉丁方。 如：???? ? ? ?=???? ? ??=12 3312 231 ,213132 32121A A 由于??? ? ? ? ?)1,2() 2,1()3,3()3,1()1,3() 2,2()2,3()3,2()1,1(中元素两两不同，故21A A ⊥ 36名军官问题：ij a 表示军官的军衔为i ，军官所在的团为j ，()66),(?j i 要求第一个数字构成拉丁方，第二个数字也构成拉丁方，并且正交。 定理：两两相互正交的n 阶拉丁方的个数不超过n-1个 pf ：设k A A A ,,,21 是两两相互正交的n 阶拉丁方，往证1-≤n k 。设n a a a 21是1， 2，…，n 的一个全排列，() ,,,2,1,) (k l a A n n l ij l ==?对1A 作如下置换 ??? ? ??n a a a n 2 1 21，得一方阵() n n ij a A ?=) 1(1，则1A 与k A A ,2正交。 事实上，如果1A 不与2A 正交，则 ()() n n ij ij a a ?) 2() 1(,中至少有一对数偶出现次数超过1次，设该对数偶为),(m l a a ，则 ),(m a l 在( )) 2() 1(,ij ij a a 中至少出现2次，与2 1 ,A A 正交矛盾，由此不妨设k A A A ,,,21 的 第一行均为),,2,1(n ，任取,1k m l ≤<≤则方阵 ()() n n m ij ij a a ?) ()1(,的第一行均是),,(),2,1(),1,1((r n 从而1不能出现在k A A A ,,,21 的 第2行第1列元素，故这些元素只能取2，3，…, n 中一个，而且取法不能相同，故n k ≤。 2.域与有限域 域：),(,:) 1(,+→?+≠V V V V V φ Abel 群 b a b a +→),( （2） ),(:* * *?→??V V V V Abel 群 ab b a →),( }0/{* V V = （3）分配律成立 ac ab c b a +=+)( ca ba a c b +=+)( 则称),,(?+V 为域 例： Q ，R ，C ， {}Q b a bi a i Q ∈+=,|)( 二元域}1,0{2=F ， p 元域}1,,2,1,0{-=p F p 有限域：元素个数有限的域叫做有限域 比如： },,2,1,0{p F p =模p 的剩余类域， 取)(x f 是][x F p 中n 次不可约多项式，则 组合数学课后标准答案 ————————————————————————————————作者：————————————————————————————————日期： 习题二证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。证明：假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 任取11个整数，求证其中至少有两个数的差是10的整数倍。证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。证明：平面上任取5个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。2.3证明：有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 一次选秀活动，每个人表演后可能得到的结果分别为“通过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？证明：根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？证明：根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 李凡长版-组合数学课后习题答案-习题3 第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2 …a 1 是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1) 表示。 a n 可以有两种情况： 1）不管上述序列中是否有2，因为a n 的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n 1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。 则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 n+4n)/2-2f(n), 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有 17 第一章什么是组合数学 组合学问题在生活中随处可见。例如，计算下列赛制下总的比赛次数：n个球队参赛，每队只和其他队比赛一次。创建幻方。在纸上画一个网络。用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，笔画出网络因。在玩扑克牌游戏中，计算满堂红牌的手数，以确定出现一手满堂红牌的几率。所有这些都是组合学问题。正如人们想到的．组合数学的历史渊源扎根于数学娱乐和游戏之中。过去研究过的许多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。今天，组合数学是数学的一门重要分支，而且它的影响还在继续扩大。组合数学自60年代以来急速发展的部分原因就在于计算机在我们的社会中所发挥的重要影响，而且这种影响还在继续发挥。由于运算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的。然而计算机不能独立运行，它需要编程来控制。这些程序的基础往往是求解问题的组合学算法，对于这些算法，运行时间效率和存储需求分析需要更多的组合学思想。 组合数学近期发展的另一个原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领城，而且也用于社会科学、生物科学、信息论等领域。此外，组合数学和组合学思想在许多数学分支中已经变得越来越重要。 组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。如下两类一般性问题反复出现： 排列的存在性如果有人想要排列—个集合的成员使得某些条件得以满 足，那么这样一种排列是否可行根本就不是显而易见的。这是最根本的问题。如果这种排列不总是可能的，那么我们要问，这种排列在什么样的(必要和充分)条件下能够实现？ 排列的计数和分类如果一个指定的排列是可能的，那么就会存在多种 方法去实现它。此时，人们就可以计数并将它们分类。 虽然对任何组合问题都可以考虑其存在性和计数问题，但在实践中常常发生的却是：如果存在性问题需要广泛地研究，那么计数问题则是非常困难的。然而，如果指定的排列问题的存在性容易解决，那么计算实现该排列的方法的数目则是可能的。在例外的情形下(即当它们的数目较小时)，这些排列可以被列出来，理解列出所有的排列与确定它们的数目之间的区别很重要。一旦这些排列被列出，它们就可通过与整数集{1，2，3，…，n}之间建立一一对应而被数出，其中n 是某个整数。我们计数的方法就是：1，2，3…，n。但是，我们主要关心的是事先不列出指定类型的排列而确定它们的数目的方法。当然，这些排列的总数也许很大以至于不可能把它们部列出来，概括地说，许多组合学问题常呈现下列形式：“能否排列…?” “存在一个……吗?” “能用多少方法—…?” “计算……的数目。” 1 第一章 排列组合 1、 在小于2000的数中，有多少个正整数含有数字2？ 解：千位数为1或0，百位数为2的正整数个数为：2*1*10*10； 千位数为1或0，百位数不为2，十位数为2的正整数个数为：2*9*1*10； 千位数为1或0，百位数和十位数皆不为2，个位数为2的正整数个数为：2*9*9*1； 故满足题意的整数个数为：2*1*10*10+2*9*1*10+2*9*9*1＝542。 2、 在所有7位01串中，同时含有“101”串和“11”串的有多少个？ 解：（1） 串中有6个1：1个0有5个位置可以插入：5种。 （2） 串中有5个1，除去0111110，个数为()6 2 -1＝14。 （或： ()()41 42 *2+＝14） （3）串中有4个1：分两种情况：①3个0单独插入，出去1010101，共()53 -1 种；②其中两个0一组，另外一个单独，则有 ()()2*)2,2(41 52 -P 种。 （4）串中有3个1：串只能为**1101**或**1011**，故共4*2种。 所以满足条件的串共48个。 3、一学生在搜索2004年1月份某领域的论文时，共找到中文的10篇，英文的12篇，德文的5篇，法文的6篇，且所有的都不相同。如果他只需要2篇，但必须是不同语言的，那么他共有多少种选择？ 解：10*12+10*5+10*6+12*5+12*6+5*6 4、设由1，2，3，4，5，6组成的各位数字互异的4位偶数共有n 个，其和为m 。求n 和m 。 解：由1，2，3，4，5，6组成的各位数字互异，且个位数字为2，4，6的偶数均有P(5,3)=60个，于是：n = 60*3 = 180。 以a 1,a 2,a 3,a 4分别表示这180个偶数的个位、十位、百位、千位数字之和，则 m = a 1+10a 2+100a 3+1000a 4。 因为个位数字为2，4，6的偶数各有60个，故 a 1 = (2+4+6)*60=720。 因为千（百，十）位数字为1，3，5的偶数各有3*P(4,2) = 36个，为2，4，6的偶数各有2*P(4,2) = 24个，故 a 2 = a 3 = a 4 = (1+3+5)*36 + (2+4+6)*24 = 612。 因此， m = 720 + 612*(10 + 100 + 1000) = 680040。 5、 从{1，2，…，7}中选出不同的5个数字组成的5位数中，1与2不相邻的数 字有多少个？ 解：1与2相邻：())4,4(253P ??。故有1和 2 但它们不相邻的方案数： ()())4,4(2)5,5(53 5 3 P P ??-? 只有1或2：())5,5(254P ?? 没有1和2：P(5,5) 组合数学与图论复习题及答案 1．Show that if n+1 integers are chosen form the set {1,2, …,2n},then there are always two which differ by at most 2. 从{1,2, …,2n}中选出n+1个数，在这n+1个数中，一定存在两个数，其中一个整数能整除另外一个整数。 任何一个数都可以写成2k*L，其中k是非负数，L是正奇数。现在从1到2n 之间只有n个奇数。由于有n+1个数都能表示成2k*L，而L的取值只有n中，所以有鸽子洞原理知道，至少有两个数的L是一样的，于是对应k小的那个就可以整除k大的另一个数。 2．Show that for any given 52 integers there are exist two of them whose sum, or else difference, is divisible 100. 设52个整数a1，a2，…，a52被100除的余数分别是r1,r2,…,r52，而任意一个数被100除余数为0，1，2，…，99，一共100个。他们可以分为51个类{0},{1,99},{2,98},…,{49,51},{50}。将这51个集合视为鸽笼，则将r1,r2,…,r52放入51个笼子中，至少有两个属于同一个笼子，所以要么有ri＝rj，要么有ri＋rj＝100，也就是说ai－aj|100或者ai＋aj|100。 3．从1，2，3，…，2n中任选n+1个数，证明在这n+1个数中至少有一对数互质。 鸽子洞原理，必有两个数相邻，相邻的两个数互质 4．Prove that Ramsey number R(p,q)≤R(p,q-1)+R(p-1,q). 令N＝R(p,q-1)+R(p-1,q)，从N个人中中随意选取一个a，F表示与a相识的人，S表示与a不相识的人。 在剩下的R(p,q-1)+R(p-1,q)－2＋1个人中，由鸽子洞原理有，或者F中有 R(p,q-1)人，或者S中有R(p-1,q)人。如果F中有R(p,q-1)人，则与a相识的人为p 个；如果S中有R(p-1,q)人，则与a不相识的人有p个。所以有R(p,q)≤ R(p,q-1)+R(p-1,q) 5．There are 10 people, either there are 3 each pair of whom are acquainted, or there are 4 each pair of whom are unacquainted。 从10人中随意选一个人p，F表示与p相识的人，S表示与p不相识的人若F中至少有4人，如果至少有4人不相识，则满足题设；如果有2人相识，则加上p有3人相识，也满足题设。 若F中至多有3人，则S中至少有6人，6人中至少有3人相识，或者不相识。如果相识则满足题设，如果不相识加上p不相识的人就有4个，也满足题设。6．In how many ways can six men and six ladies be seated at round table if the men and ladies to sit in alternate seats 6个男的先进行圆排列，然后6个女的插入空位。 7．In how many ways can 15 people be seated at round table if B refuses to sit next to A What if B only refuses to sit on A right 第二章作业答案 7. 证明，对任意给定的52个整数，存在两个整数，要么两者的和能被100整除，要么两者的差能被100整除。 证明 用100分别除这52个整数，得到的余数必为0, 1,…, 99这100个数之一。将余数是0的数分为一组，余数是1和99的数分为一组，…，余数是49和51的数分为一组，将余数是50的数分为一组。这样，将这52个整数分成了51组。由鸽巢原理知道，存在两个整数分在了同一组，设它们是a 和b 。若a 和b 被100除余数相同，则b a -能被100整除。若a 和b 被100除余数之和是100，则b a +能被100整除。 11. 一个学生有37天用来准备考试。根据过去的经验，她知道她需要不超过60小时的学习时间。她还希望每天至少学习1小时。证明，无论她如何安排她的学习时间（不过，每天都是整数个小时），都存在连续的若干天，在此期间她恰好学习了13小时。 证明 设从第一天到第i 天她共学习了i a 小时。因为她每天至少学习1小时，所以 3721,,,a a a 和13,,13,133721+++a a a 都是严格单调递增序列。因为总的学习时间 不超过 60 小时，所以6037≤a ，731337≤+a 。3721,,,a a a , 13,,13,133721+++a a a 是1和73之间的74个整数，由鸽巢原理知道，它们中存在相 同的整数，有i a 和13+j a 使得13+=j i a a ，13=-j i a a ，从第1+j 天到第i 天她恰好学习了13小时。 14. 一只袋子装了100个苹果、100个香蕉、100个桔子和100个梨。如果我每分钟从袋子里取出一个水果，那么需要多少时间我就能肯定至少已拿出了1打相同种类的水果？ 解 由加强形式的鸽巢原理知道，如果从袋子中取出451)112(4=+-?个水果，则能肯定至少已拿出12个相同种类的水果。因此，需要45分钟。 17. 证明：在一群1>n 个人中，存在两个人，他们在这群人中有相同数目的熟人（假设没有人与他/她自己是熟人）。 证明 因为每个人都不是自己的熟人，所以每个人的熟人的数目是从0到1-n 的整数。若有两个人的熟人的数目分别是0和1-n ，则有人谁都不认识，有人认识所有的人，这是不可能的。因此，这n 个人的熟人的数目是1-n 个整数之一，必有两个人有相同数目的熟人。 第三章作业答案 6. 有多少使下列性质同时成立的大于5400的整数？ (a) 各位数字互异。 (b) 数字2和7不出现。 解 因为只能出现数字0, 1, 3, 4, 5, 6, 8, 9，所以整数的位数至多为8。 ① 考虑8位整数。最高位不能为0，因此8位整数有)7,7(7P ?个。 ② 考虑7位整数。最高位不能为0，因此8位整数有)6,7(7P ?个。 习题二 2.1证明：在一个至少有2人的小组中，总存在两个人，他们在组内所认识的人数相同。 证明： 假设没有人谁都不认识：那么每个人认识的人数都为[1,n-1]，由鸽巢原理知，n个人认识的人数有n-1种，那么至少有2个人认识的人数相同。 假设有1人谁都不认识：那么其他n-1人认识的人数都为[1,n-2]，由鸽巢原理知，n-1个人认识的人数有n-2种，那么至少有2个人认识的人数相同。 假设至少有两人谁都不认识，则认识的人数为0的至少有两人。 2.2任取11个整数，求证其中至少有两个数的差是10的整 数倍。 证明：对于任意的一个整数，它除以10的余数只能有10种情况：0，1，…，9。现在有11个整数，由鸽巢原理知，至少有2个整数的余数相同，则这两个整数的差必是10的整数倍。 2.3证明：平面上任取5个坐标为整数的点，则其中至少有 两个点，由它们所连线段的中点的坐标也是整数。 2.3证明： 有5个坐标，每个坐标只有4种可能的情况：（奇数，偶数）；（奇数，奇数）；（偶数，偶数）；（偶数，奇数）。由鸽巢原理知，至少有2个坐标的情况相同。又要想使中点的坐标也是整数，则其两点连线的坐标之和为偶数。因为奇数+奇数= 偶数；偶数+偶数=偶数。因此只需找以上2个情况相同的点。而已证明：存在至少2个坐标的情况相同。证明成立。 2.4一次选秀活动，每个人表演后可能得到的结果分别为“通 过”、“淘汰”和“待定”，至少有多少人参加才能保证必有100个人得到相同的结果？ 证明： 根据推论2.2.1，若将3*（100-1）+1=298个人得到3种结果，必有100人得到相同结果。 2.5一个袋子里装了100个苹果、100个香蕉、100个橘子和100个梨。那么至少取出多少水果后能够保证已经拿出20个相同种类的水果？ 证明： 根据推论2.2.1，若将4*（20-1）+ 1 = 77个水果取出，必有20个相同种类的水果。 第五章 P ólya 计数理论 1. 计算（123）（234）（5）（14）（23）,并指出它的共轭类. 解：题中出现了5个不同的元素：分别是：1，2，3，4，5。即|S n |＝5。 ??? ? ?????? ?????? ??=512345432152431543215413254321) 23)(14)(5)(234)(123( ??? ? ?????? ??=51234543215214354321 ??? ? ??=5341254321 )5)(34)(12(= （5）（12）（34）的置换的型为1122而S n 中属于1122型的元素个数为15 21!1!2! 52 1=个其共轭类为 （5）（14）（23），（5）（13）（24），（1）（23）（45），（1）（24）（35）， （1）（25）（34），（2）（13）（45），（2）（14）（35），（2）（15）（34）， （3）（12）（45），（3）（14）（25），（3）（15）（24），（4）（12）（35）， （4）（13）（25），（4）（15）（24） 2. 设D 是n 元集合,G 是D 上的置换群.对于D 的子集A 和B ,如果存在G ∈σ, 使得}|)({A a a B ∈=σ,则称A 与B 是等价的.求G 的等价类的个数. 解：根据Burnside 引理∑= =n i i a c G l 1 1)(1，其中c 1(a i )表示在置换a i 作用下保持不变的元素个数，则有 c 1(σI )=n; 设在σ的作用下，A 的元素在B 中的个数为i ，则 c 2(σ)=n －2i ； 若没有其他置换，则G 诱出来的等价类个数为l=i n i n n -=-+)]2([2 1 3. 由0,1,6,8,9组成的n 位数,如果把一个数调转过来读得到另一个数,则称这两 个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n 位数有多少个？ 解：该题可理解为相当于n 位数，0，1，6，8，9这5个数存在一定的置换关系 第二章 容斥原理与鸽巢原理 1、1到10000之间（不含两端）不能被4，5和7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，则 |A|=10000. 记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除的整数集合，则有： |A 1| = L 10000/4」=2500, |A 2| = L 10000/5」=2000, |A 3| = L 10000/7」=1428, 于是A 1∩A 2 表示A 中能被4和5整除的数,即能被20 整除的数，其个数为 | A 1∩A 2|=L 10000/20」=500； 同理， | A 1∩A 3|=L 10000/28」=357, | A 2∩A 3|=L 10000/35」=285, A 1 ∩A 2 ∩ A 3 表示A 中能同时被4,5,7整除的数，即A 中能被4,5,7的最小公倍数lcm(4,5,6)=140整除的数，其个数为 | A 1∩A 2∩A 3|=L 10000/140」= 71. 由容斥原理知，A 中不能被4，5，7整除的整数个数为 ||321A A A ?? = |A| - (|A 1| + |A 2| +|A 3|) + (|A 1∩A 2| + |A 1∩A 3| +|A 3∩A 2|) - |A 1∩A 2∩A 3| = 5143 2、1到10000之间（不含两端）不能被4或5或7整除的整数有多少个？ 解 令A={1,2,3,…,10000}，记A 1、A 2、A 3分别为在1与1000之间能被4,5和7整除 的整数集合，A 中不能被4，5，7整除的整数个数为 ||321A A A ?? = |A| - ||321A A A ?? - 2 = 10000 - L 10000/140」- 2 = 9927 3、1到10000之间（不含两端）能被4和5整除，但不能被7整除的整数有多 少个？ 解 令A 1表示在1与10000之间能被4和5整除的整数集，A 2表示4和5整除， 也能被7整除的整数集。则： |A 1| = L 10000/20」= 500, |A 2| = L 10000/140」= 71, 所以1与10000之间能被4和5整除但不能被7整除的整数的个数为：500-71=429。 4、计算集合{2·a, 3·b, 2·c, 4·d }的5组合数. 解 令S ∞={∞·a, ∞·b,∞·c,∞·d}，则S 的5组合数为()1455 -+ = 56 设集合A 是S ∞的5组合全体，则|A|＝56，现在要求在5组合中的a 的个数小于等 于2，b 的个数小于等于3，c 的个数小于等于2，d 的个数小于等于4的组合数. 定义性质集合P={P 1,P 2,P 3,P 4},其中： P 1：5组合中a 的个数大于等于3； P 2：5组合中b 的个数大于等于4； P 3：5组合中c 的个数大于等于3； P 4：5组合中d 的个数大于等于5. 将满足性质P i 的5组合全体记为A i (1≤i ≤4). 那么，A 1中的元素可以看作是由 S ∞的5－3＝2组合再拼上3个a 构成的，所以|A 1| =()142 2 -+ = 10. Math475Text:Brualdi,Introductory Combinatorics5th Ed. Prof:Paul Terwilliger Selected solutions for Chapter5 1.For an integer k and a real number n,we show n k = n?1 k?1 + n?1 k . First assume k≤?1.Then each side equals0.Next assume k=0.Then each side equals 1.Next assume k≥1.Recall P(n,k)=n(n?1)(n?2)···(n?k+1). We have n k = P(n,k) k! = nP(n?1,k?1) k! . n?1 k?1 = P(n?1,k?1) (k?1)! = kP(n?1,k?1) k! . n?1 k = P(n?1,k) k! = (n?k)P(n?1,k?1) k! . The result follows. 2.Pascal’s triangle begins 1 11 121 1331 14641 15101051 1615201561 172135352171 18285670562881 193684126126843691 1104512021025221012045101 ··· 1 3.Let Z denote the set of integers.For nonnegative n∈Z de?ne F(n)= k∈Z n?k k . The sum is well de?ned since?nitely many summands are nonzero.We have F(0)=1and F(1)=1.We show F(n)=F(n?1)+F(n?2)for n≥2.Let n be https://www.doczj.com/doc/426703376.html,ing Pascal’s formula and a change of variables k=h+1, F(n)= k∈Z n?k k = k∈Z n?k?1 k + k∈Z n?k?1 k?1 = k∈Z n?k?1 k + h∈Z n?h?2 h =F(n?1)+F(n?2). Thus F(n)is the n th Fibonacci number. 4.We have (x+y)5=x5+5x4y+10x3y2+10x2y3+5xy4+y5 and (x+y)6=x6+6x5y+15x4y2+20x3y3+15x2y4+6xy5+y6. 5.We have (2x?y)7= 7 k=0 7 k 27?k(?1)k x7?k y k. 6.The coe?cient of x5y13is35(?2)13 18 5 .The coe?cient of x8y9is0since8+9=18. https://www.doczj.com/doc/426703376.html,ing the binomial theorem, 3n=(1+2)n= n k=0 n k 2k. Similarly,for any real number r, (1+r)n= n k=0 n k r k. https://www.doczj.com/doc/426703376.html,ing the binomial theorem, 2n=(3?1)n= n k=0 (?1)k n k 3n?k. 2 1.1 题 从{1，2，……50}中找两个数{a ，b}，使其满足 （1）|a-b|=5； （2）|a-b|≤5； 解：（1）：由|a-b|=5?a-b=5或者a-b=-5， 由列举法得出，当a-b=5时，两数的序列为（6，1）（7，2）……（50，45），共有45对。 当a-b=-5时，两数的序列为（1，6），（2，7）……（45，50）也有45对。 所以这样的序列有90对。 （2）：由题意知，|a-b|≤5?|a-b|=1或|a-b|=2或|a-b|=3或|a-b|=4或|a-b|=5或|a-b|=0； 由上题知当|a-b|=5时 有90对序列。 当|a-b|=1时两数的序列有（1，2），（3，4），（2，1）（1，2）…（49，50），（50，49）这样的序列有49*2=98对。 当此类推当|a-b|=2，序列有48*2=96对，当|a-b|=3时，序列有47*2=94对，当|a-b|=4时，序列有46*2=92对， 当|a-b|=0时有50对 所以总的序列数=90+98+96+94+92+50=520 1.2题 5个女生，7个男生进行排列，(a) 若女生在一起有多少种不同的排列？(b) 女生两两不相邻有多少种不同的排列？(c) 两男生A 和B 之间正好有3个女生的排列是多少？ 解：（a ）可将5个女生看作一个单位，共八个单位进行全排列得到排列数为：8！×5！， （b ）用x 表示男生，y 表示空缺，先将男生放置好，共有8个空缺， Y X Y X Y X Y X Y X Y X Y X Y 在其中任取5个得到女生两两不相邻的排列数： C （8，5）×7！×5！ （c ）先取两个男生和3个女生做排列，情况如下： 6. 若A ，B 之间存在0个男生， A ，B 之间共有3个人，所有的排列应为 P6=C(5,3)*3!*8!*2 1．若A ，B 之间存在1个男生， A ，B 之间共有4个人，所有的排列应为 P1= C(5,1)*C(5,3)*4!*7!*2 2．若A ，B 之间存在2个男生，A ，B 之间共有5个人，所有的排列应为 P2=C(5,2)*C(5,3)*5!*6!*2 3．若A ，B 之间存在3个男生，A ，B 之间共有6个人，所有的排列应为 P3=C(5,3)*C(5,3)*6!*5!*2 4．若A ，B 之间存在4个男生，A ，B 之间共有7个人，所有的排列应为 P4=C(5,4)*C(5,3)*7!*4!*2 5．若A ，B 之间存在5个男生，A ，B 之间共有8个人，所有的排列应为 P5=C(5,5)*C(5,3)*8!*3!*2 所以总的排列数为上述6种情况之和。 1.3题 m 个男生，n 个女生，排成一行，其中m,n 都是正整数，若 (a)男生不相邻)1(+≤n m ; (b)n 个女生形成一个整体； (c)男生A 和女生B 排在一起； 分别讨论有多少种方案。 解：(a) 可以考虑插空的方法。 n 个女生先排成一排，形成n+1个空。因为1+≤n m 正好m 个男生可以插在n+1个空中，形成不相邻的关系。 则男生不相邻的排列个数为 p p n m n n 1+? (b) n 个女生形成一个整体有n ！种可能，把它看作一个整体和m 个男生排在一起，则排列数有(m+1)!种可能。 因此，共有)!1(!+?m n 种可能。 (c)男生A 和女生B 排在一起，因为男生和女生可以交换位置，因此有2！种可能， A 、B 组合在一起和剩下的学生组成排列有(m+n-1)！ (这里实际上是m+n-2个学生和AB 的组合形成的)种可能。共有组合数为)!1(!2-+?n m 1.4题 26个英文字母进行排列，求x 和y 之间有5个字母的排列数 解：C （24，5）*13！ 1.5题 求3000到8000之间的奇整数的数目，而且没有相同的数字。 解：根据题意，千位可以从3，4，5，7，6中选取，个位可以从1，3，5，7，9中选取；因此 2*5*8*7+3*4*8*7=1232 1.6 题 计算，1·1！+2·2！+3·3！+。。。+n·n ！ 解：由序数法公式可知 1!+1=2! 2·2!+1·1!+1=3! 3·3！+2·2！+1·1！+1=4！ n·n!+(n-1)(n-1)!+。。。+2·2!+1·1!+1= (n+1)! 所以1·1！+2·2！+3·3！+。。。+n·n ！=(n+1)!－１ 1.7题 试证：)2()2)(1(n n n ++被2n 除尽。 证明：因!)!12(!2)!2(-=n n n n !)!12(2 !)! 2(2!)2()2)(1(!2)2()2)(1(-==++=++n n n n n n n n n n n n n n 因为(2n-1)!!是整数所以)2()2)(1(n n n ++能被2n 除尽。 第四章 生成函数 1. 求下列数列的生成函数： （1）{0,1,16,81,…,n 4,…} 解：G{k 4 }= 235 (11111) 1x x x x x +++-（） （2）343,,,333n +?????????? ? ? ????? ???? 解：3n G n +?????? ?? ???=41(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=（2 11x -）2 . （4）{1,k ,k 2,k 3,…} 解：A(x)=1+kx+k 2x 2+k 3x 3+…= 1 1kx -. 2. 求下列和式： （1）14+24+…+n 4 解：由上面第一题可知，{n 4}生成函数为 A(x)=235 (11111)1x x x x x +++-（）=0 k k k a x ∞=∑， 此处a k =k 4 .令b n =14 +24 +…+n 4 ，则b n =0n k k a =∑，由性质3即得数列{b n }的生 成函数为 B(x)= 0n n n b x ∞ =∑=() 1A x x -=34 125(1111)i i i x x x x x i ∞ =++++?? ??? ∑. 比较等式两边x n 的系数，便得 14+24+…+n 4 =b n =1525354511111234n n n n n n n n -+-+-+-++++----???????? ? ? ? ????????? 321 (1)(691)30 n n n n n =+++- （2）1·2+2·3+…+n (n +1) 解：{ n (n +1)}的生成函数为A(x)= 3 2(1) x x -=0k k k a x ∞ =∑，此处a k = n (n +1). 令b n =1·2+2·3+…+n (n +1)，则b n =0 n k k a =∑.由性质3即得数列{b n }的生成 函数为B(x)= n n n b x ∞ =∑= ()1A x x -= 4 2(1)x x -=032n k k k x x k =+?? ?? ?∑. 比较等式两边x n 的系数，便得 第五章 抽屉原理和Ramsey 理论 抽屉原理又称鸽巢原理或重叠原理，是组合数学中两大基本原理之一，是一个极其初等而又应用较广的数学原理。其道理并无深奥之处，且正确性也很明显。但若能灵活运用，便可能得到一些意料不到的结果。 抽屉原理要解决的是存在性问题，即在具体的组合问题中，要计算某些特定问题求解的方案数，其前提就是要知道这些方案的存在性。 1930年英国逻辑学家F. P. Ramsey 将这个简单原理作了深刻推广，即Ramsey 定理，也被称为广义抽屉原理。它是一个重要的组合定理，有许多应用。 5.1 抽屉原理 （一）基本形式 定理5.1.1 （基本形式）将n ＋1个物品放入n 个抽屉，则至少有一个抽屉中的物品数不少于两个。 证 反证之。将抽屉编号为：1,2, …,n ，设第i 个抽屉放有i q 个物品，则 121+=+++n q q q n 但若定理结论不成立，即1≤i q ，即有n q q q +++ 21≤n ， 从而有 n q q q n n ≤+++=+ 211 矛盾。 例 5.1.1 一年365天，今有366人，那么，其中至少有两人在同一天过生日。 注：与概率的区别：抽屉原理讲的是所给出的结论是必然成立的，即100%成立。而概率反映的是不确定性现象发 生的可能性问题，不讨论100%成立的确定性概率问题。 生日悖论：随机选出n 个人，则其中至少有二人同一天出生的概率为 ()A P n =n n P 365 1365- 特例：()A P 23=50.73%，()A P 100=99.99997% 例 5.1.2 箱子中放有10双手套，从中随意取出11只，则至少有两只是完整配对的。 （二）推广形式 定理5.1.2 （推广形式）将121+-+++n q q q n 个物品放入n 个抽屉，则下列事件至少有一个成立：即第i 个抽屉的物品数不少于i q 个。 （证）反证。不然，设第i 个抽屉的物品数小于i q （i ＝1,2, …,n ）(即该抽屉最多有1-i q 个物品)，则有 11 +-∑=n q n i i ＝物品总数≤()n q q n i i n i i -=-∑∑==1 1 1 与假设矛盾。 121+-+++n q q q n = ()()()111121 +-++-+-n q q q （三）特例 推论1 将n(r －1)＋1个物品放入n 个抽屉，则至少有一个抽屉中物品个数不少于r 个。 推论2 将m 个物品放入n 个抽屉，则至少有一个抽屉中物品个数不少于11+?? ?? ??-n m ＝?? ? ???n m 个。其中??x 表示取x 第三章递推关系 1.在平面上画n条无限直线,每对直线都在不同的点相交,它们构成的无限 区域数记为f(n),求f(n)满足的递推关系. 解： f(n)=f(n-1)+2 f(1)=2,f(2)=4 解得f(n)=2n. 2.n位三进制数中,没有1出现在任何2的右边的序列的数目记为f(n),求 f(n)满足的递推关系. 解：设a n-1a n-2,a1是满足条件的n-1位三进制数序列，则它的个数可以用f(n-1)表示。 a n可以有两种情况： 1）不管上述序列中是否有2，因为a n的位置在最左边，因此0 和1均可选； 2）当上述序列中没有1时，2可选； 故满足条件的序列数为 f(n)=2f(n-1)+2n-1 n1, f(1)=3 解得f(n)=2n-1(2+n). 3.n位四进制数中,2和3出现偶数次的序列的数目记为f(n),求f(n)满足 的递推关系. 解：设h(n)表示2出现偶数次的序列的数目，g(n)表示有偶数个2奇数个3的序列的数目，由对称性它同时还可以表示奇数个2偶数个3的序列的数目。则有 h(n)=3h(n-1)+4n-1-h(n-1),h(1)=3 （1） f(n)=h(n)-g(n),f(n)=2f(n-1)+2g(n-1) （2） 将（1）得到的h(n)=(2n+4n)/2代入（2），可得 f(n+1)= (2n+4n)/2-2f(n), f(1)=2. 4.求满足相邻位不同为0的n位二进制序列中0的个数f(n). 解：这种序列有两种情况： 1)最后一位为0，这种情况有f(n-3)个； 2)最后一位为1，这种情况有2f(n-2)个； 所以 f(n)=f(n-3)+2f(n-2) f(1)=2,f(2)=3,f(3)=5. 5.求n位0,1序列中“00”只在最后两位才出现的序列数f(n). 解：最后两位是“00”的序列共有2n-2个。 f(n)包含了在最后两位第一次出现“00”的序列数，同时排除了在n-1位第一次出现“00”的可能； f(n-1)表示在第n-1位第一次出现“00”的序列数，同时同时排除了在n-2位第一次出现“00”的可能； 依此类推，有组合数学课后答案
组合数学 第五章
组合数学课后标准答案
李凡长版-组合数学课后习题答案-习题3
第一章 什么是组合数学
李凡长版 组合数学课后习题答案 习题1
组合数学与图论复习题及参考答案
组合数学作业答案
组合数学 课后答案
李凡长版 组合数学课后习题答案 习题5
李凡长版组合数学课后习题标准答案习题
Richard组合数学第5版-第5章课后习题答案(英文版)
组合数学参考答案(卢开澄第四版) - 修改版
李凡长版 组合数学课后习题答案习题4
组合数学讲义 5章 抽屉原理
李凡长版组合数学课后习题答案习题3
相关主题
文本预览