组合数学第三章答案
3.1题（宗传玉）
某甲参加一种会议，会上有6位朋友，某甲和其中每人在会上各相遇12次，每二人各相遇6次，每三人各相遇3次，每五人各相遇2次，每六人各相遇一次，1人也没有遇见的有5次，问某甲共参加了几次会议
解:
设A i为甲与第i个朋友相遇的会议集，i＝1，…，6．则
故甲参加的会议数为:28+5=33.
3.2题（宗传玉）
求从1到500的整数中被3和5整除但不被7整除的数的个数.
解:
设A3：被3整除的数的集合
A5：被5整除的数的集合
A7：被7整除的数的集合
所以
3.3.题（宗传玉）
n个代表参加会议，试证其中至少有2人各自的朋友数相等。
解:
每个人的朋友数只能取0，1，…，n－1．但若有人的朋友数为0，即此人和其他人都不认识，则其他人的最大取数不超过n－2．故这n个人的朋友数的实际取数只有n－1种
可能．，所以至少有２人的朋友数相等．
3.4题（宗传玉）
试给出下列等式的组合意义.
解:
(a) 从n 个元素中取k 个元素的组合，总含有指定的m 个元素的组合数为)
(
)(
k
n m n m
k m n --=--。
设这m 个元素为a 1,a 2,…,a m ,Ai 为不含a i 的组合（子集），i=1,…,m.
()
∑∑
∑
==∈?==???
? ??-???? ??-=
-+???
? ??==???
?
??--???
?
??-=m
l l
m
l l m i i l
j i
l
k l n k m A k n k n m n k l n l j
1
)
,(),...,(1
m
1
i i
i i i 1)
1(A
A
A
A
11
1
21
3.5题（宗传玉）
设有三个7位的二进制数：a1a2a3a4a5a6a7，b1b2b3b4b5b6b7，c1c2c3c4c5c6c7．试证存在整数i 和j，1≤i≤j≤7，使得下列之一必定成立：a i=a j=b i=b j，a i=a j=c i=c j，b i=b j=c i=c j．
证：
显然，每列中必有两数字相同，共有种模式，有０或１两种选择．故共有·2
种选择．·2=6．现有7列，．即必有２列在相同的两行选择相同的数字，即
有一矩形，四角的数字相等．
3.6题（宗传玉）
在边长为1的正方形内任取5个点试证其中至少有两点，其间距离小于
证：
把１×１正方形分成四个(1/2)×.则这５点中必有两点落在同一个
小正方形内．而小正方形内的任两点的距离都小于．
3.7题（王星）
在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2．
证：
把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在同一个小三角形中．小三角形中任意两点间的距离都小于1/2．
3.8题（王星）
任取11个整数，求证其中至少有两个数它们的差是10的倍数。
证：
整数的个位数的可能取值为０，１，…，９．共１０种可能．11个整数中必有２个数的个位数相同，即这两个数之差能被１０整除．
3.9题（王星）
把从1到326的326个整数任意分为5个部分，试证其中有一部分至少有一个数是某两个数之和，或是另一个数的两倍。
证：
用反证法。设存在划分P1∪P2∪P3∪P4∪P5＝[1，326]，Pi中没有数是两数之差．，则有一Pi中至少有66个数，A＝{ a1 ,…,a66} ，a1＜a2＜??＜a66 ，以下按书上174页的例题证明可得．
3.10题（王星）
A、B、C三种材料用作产品I、II、III的原料，但要求I禁止用B、C作原料，II不能用B
作原料， III 不允许用A 作原料，问有多少种安排方案？（假定每种材料只做一种产品的原料） 解：
按题意可得如下的带禁区的棋盘,其中有阴影的表示禁区． 棋盘多项式为： R( )=R( )R( ) =(1+x)(1+3x+x 2 ) =1+4x+4x 2 + x 3
故方案数＝3!－4?2!+4 ?1!－1 ?0!＝1 3.11题（王星）
n 个球放到m 个盒子中去，n ＜(m/2)(m －1)，试证其中必有两个盒子有相同的球数。 解：
设m 个盒子的球的个数是a1,…,am ， 各不相等，且有0≤a1＜a2＜??＜am ．则有 a2≥1、am ≥m －1，故
≥1+2+…+m －1＝(m/2)(m －1) ， 与n ＜(m/2)(m －1)相矛盾！ 所以必有两个盒子的球数相等．
3.12题（王星）
一年级有100名学生参加中文、英语和数学的考试，其中92人通过中文考试，75人通过英语考试，65人通过数学考试；其中65人通过中、英文考试，54人通过中文和数学考试，45人通过英语和数学考试，求通过3门学科考试的学生数。 解：
设： 通过中文考试的92人为集合A ，通过英语考试的75人为集合B ，通过数学考试的65人为集合C
则∣A ∩B ∣=65，∣A ∩C ∣=54，∣B ∩C ∣=45
由∣A ∪B ∪C ∣=∣A ∣+∣B ∣+∣C ∣-∣A ∩B ∣-∣A ∩C ∣- ∣B ∩C ∣+∣A ∩B ∩C ∣
故∣A ∩B ∩C ∣=∣A ∪B ∪C ∣-∣A ∣-∣B ∣-∣C ∣+∣A ∩B ∣+ ∣A ∩C ∣+∣B ∩C ∣ =100-92-75-65+65+54+45 =32
通过3门学科考试的学生数为32。 3.13题（王丹竹） 试证 (1)||||||B A B B A ?-=?
(2)||||||||
C B A B A C C B A ??+?-=??
证明： (1)
A B =? A B B A B =- =B A B ≠?
A B B A B
=- A=B
A B B A B
=- =?
所以A B B A B
=- 成立
(2)A B C A B C =
A B A B
=
A B A B A B
=+- =C
A C
B
C A B C
--+
又因为 由（a ）得 原式=()()()
C A B C C A C B C -=-
3.14题（王丹竹）
}1000,,2,1{ =N ，求其中不被
5和7除尽，但被3除尽的数的数目。
解：
设 3A 为被3除尽的集合 5
A 为被5除尽的集合
7
A 为被7除尽的集合
所以由题意得：3573
3
5
3
5
7
A A A A
A
A
A
A
A =
-
+
-应该少了一个吧？
=100010001000100033537357????????
--+?
???????
????????????
=333-66-47+9=229 3.15题（王丹竹）
}120,,2,1{ =N ,求其中被
2，3，5，7中m 个数除尽的数的数目，m=0，1，2，3，4。求不
超过120的素数的数目。素数？ 解： (1) m=0时 不被2，3，5，7除尽的数为
2
3
5
7
A
A
A
A
=120-
2
3
5
7
2
3
2
5
2
7
A
A A A A A
A
A
A
A
---
+
+
+
+
5
3
3
7
5
7
A A A A A
A ++ -2
3
5
2
3
7
A A
A
A
A
A -
-
2573
5
7
A
A
A
A
A
A
-
+2357A A A A =120-（60+40+24+17）+
（20+12+8+8+8）-（4+2+1+1）=27 m=0 时 23
12020
23A A ??
=
=?????
2
5
12012
25A
A
??
=
=?????
2
7
1208
27A A ??
=
=?????
3
7
1205
37A A ??
=
=?????
5
7
1203
57A
A
??
=
=?????
M=3 时 2351204
235A A A ??
=
=??????
2
3
7
1202
237A A A ??
=
=??????
2
5
7
1201257A A A ??
=
=??
????
35
7
1201
357A
A
A
??
=
=??????
M=4 时 23571200
2357A A A A ??
=
=???????
(2)
因为 2
12111
= ，故不超过120的合数必然是 2，3，5，7的倍数
而且不超过120的合数的因子不可能超过11 设 i A 为不超过120的数的倍数集合，i=2，3，5，7
排除 2，3，5，7这四个数又包含1这个非素数
2，3，5，7本身是素数，故所求不超过120的素数个数应该为 27+4-1=30
3.16题（王丹竹）
求正整数n 的数目，n 除尽4010，30
20中的至少一个数。这道题是这样做吗？ 解：
N 为正整数
设40
10
A
为被40
10除尽
30
20
A 为被30
20除尽
40
10
A =4010n ??
??????
30
20A =30
20n ??
??????
40
30
4030
10
20
10
20n
A A ?
?
=???????
3.17题和3.18题（未完成）（王丹竹）
3.19 题（孔令琪） {1000，1001，。。。，3000}，求其中是4的倍数但不是100的倍数的数目。 此题下面的解法，我个人认为是不正确的。 解：
设A ，B 分是4，100的倍数。
??45055005
100*410003000500
410003000=-=?-=??
?
????=?
?
?
???-=
?=?
?
?
???-=
-
B A A B A B A A
3．20题（孔令琪）
在由a,a,a,b,b,b,c,c,c,组成的排列中，求满足下列条件的排列数， （1）不存在相邻3元素相同； 解：
A ，
B ，
C 分别表示 aaa,bbb,ccc 则：
()
()
()()()
()
1
!
3!5*
3!3!
7*
3!3!
9!3!
91
!
3!5!3!
72
3
3
2
-+-=
??-
?+?+?
+++-
=??=
=??=?=?=?=
==-
-
-
C
B A C
B C A B A C B A
S C B A S C B A C B C A B A C B A
（2）相邻两元素不相同。这个怎么做？
3．21题（孔令琪）
求从O （0，0）点到（8，4）点的路径数。已知（2，1）到（4，1）的线段，（3，1） 到（3，2）的线段被封锁 解：
设A 点坐标（2，1），B 点坐标（4，1），C 点坐标（3，1），D 点坐标（3，2） 令a 为从O 点到M 点经过AC b 为从O 点到M 点经过CB c 为从O 点到M 点经过CD
271
)()(0
063105
84
)2,7(*)1,4(140)3,7(*)1,4(168)3,8(*)1,3()4,12(=??-?+?+?+++-=??=??=?=?=?=======
=-
-
-
c b a c b c a b a c b a s c b a c b a c b c a b a
c c c c c b c c a c s
3．22题（孔令琪）
求满足下列条件 下面对于此题的解法正确，但是答案算错了。 x1+x2+x3=20, 17
37,820,913≤≤≤≤≤≤
x x x
解： 令y1=x1-3,y2=x2,y3=x3-7
21
)321(41)321(313
172816321,31730,2820,1610=++-=++-=-+-+-=++-=≤-=≤-=≤x x x y y y y y y z z z y z y z y z
则所求整数解的数目：c(23,21)=c(23,2)=253 3．23题（孔令琪）
此题解法与上题一样，所以不在求解，如有凝问请与我联系！
3.24题（周英华）
求满足下列条件的整数解数目：x 1+ x 2+ x 3+ x 4=20 1≤x 1≤5,0 ≤x 2≤7,4 ≤x 3≤8,2≤x 4≤6 解：
设y 1= x 1 -1, y 2= x 2, y 3= x 3 -4, y 4= x 4 -2,
y 1+y 2+y 3+y 4=13
0 ≤y 1≤4, 0 ≤y 2≤7, 0 ≤y 3≤4, 0 ≤y 4≤4,
若不附加上界条件的解根据公式应为
1341
1616
56013
133+-??????=== ? ? ???
????
对于有上界的问题要作变换
ε1=4-y 1, ε2=7-y 2, ε3=4-y 3, ε4=4-y 4, ε1≥0 , ε2≥0 , ε3≥0 , ε4≥0 , 于是问题变为
ε1+ε2+ε3+ε4=6 整数解的数目
64199846
63+-????
??=== ? ? ???????
3.25题（周英华）
证明满足下列条件：x 1+ x 2+……+ x n =r
0≤x i ≤k , i=1,2,……，n 的整数解数目为
(1)1(1)1
n
i i n r k
i n i r =-++-????- ?
?-????
∑
解：
S, |S|=???
?
??-+r r n 1
令S 中具有x 1≥k+1的子集A 1，……，x i ≥k+1的子集A i ,
问题转化为求| A 1∩A 2∩…∩A n | |A 1|= |A 1∩A 2 |=
241r n k r +--?? ?-?? … …
| A 1∩A 2∩…∩A n | =0
(1)1(1)1n
i
i n r k i n i r =-++-????
- ? ?
-????
∑
3.26题（周英华）
证明满足下列条件：x 1+ x 2+……+ x n =r
1≤x i ≤k , i=1,2,……，n 的整数解数目为
1(1)1n
i
i n r k i i r =--????- ? ?-????
∑
证明：
令y i = x i -1
则y 1+ y 2+……+ y n =r-n
21r n k r +--??
?-??
0≤y i ≤k , i=1,2,……，n
由上题知0
(1)1(1)1n
i i n r k i n i r =-++-?
???- ? ?
-????
∑
代入得整数解数目为
1(1)1n
i
i n r k i i r =--????
- ? ?-????
∑
3.27题（周英华）
求n 对夫妻排成一行，夫妻不相邻的排列数。这道题可不可以用递推关系试试？ 解：
(1)n 个人排成一行方案数为n! N 对夫妻排成一行方案数为n!2n
令A i 第i 对夫妻相邻而坐的集合，i=1,2,……，n (2)2n 个人排成一行方案数为(2n)!
|A i |相当于将第i 对夫妻作为一个对象排列一行然后换位，故 |A 1|=2(2n-1)!
|A 1∩A 2 |=22(2n-2)! … …
|A 1∩A 2∩…∩A n |=2n n!
故夫妻不相邻排列数为 N=(2n)!-21n ??
???
(2n-1)!+ 222n ??
???
(2n-2)!- ……+(-1)n 2n n!
=0
2n
h h n h =?? ???
∑
(2n-h)!
3.28题（周英华） 未看。
设p,q ∈N ，p 是奇数，现在有pq 个珠子，着q 种颜色，每种颜色有p 个珠子。假定相同颜色的珠子无区别。试分别求满足以下条件的珠子的排列数。
（1）同颜色的珠子在一起；
（2）同颜色的珠子处于不同的块； （3）同颜色的珠子最多在两个块。 解：
同颜色的珠子在一起的排列数 p!
同颜色的珠子处于不同的块的排列数 p!q p
同颜色的珠子最多在两个块的排列数 A i 相当于第i 个某色球处于不同块 | A 1 |=q(pq)!
|A 1∩A 2 |=q 2(pq-1)!
… …
|A 1∩A 2∩…∩A p |=q p (pq-p)! N= q(pq)!- q 21p ??
???
(pq-1)! +……+(-1)p q p (qp-p)!
=0
()p
p i p q p q i i =??
-
???
∑
3.29题（翟聪）
将r 个相同的球放进n 个有标志的盒子里，无一空盒，求方案数。 解：
先拿出n 个球在每个盒子里放一个球，再将剩下的r-n 个球无限制地放入n 个盒子中。根据定理1.3，r-n 个球无限制地放到n 个盒子中共有C(n+r-n-1,r-n)=C(r-1,r-n)=C(r-1,n-1)种放法。
3.30题（翟聪）未看。
试证∑
---1
)1(n i i ????
??
i n ?
??
? ??--+r i r n 1=?
??
?
??--11n r ，r ，n ∈N ，r>n
解：
设共有r-1个不同的红球和n 个不同的白球，从中取出n-1个球.
等式左边每个累加项（不考虑符号）可化为：C(n,i)C(n+r-1-i,n-1-i)表示从这些球中取i 个白球和n-1-i 个红球，表示至少取i 个白球的组合数，即β(i)。
等式右边表示只从r-1个红球中取出n-1个球的组合数，表示恰好取0个白球的组合数，即α(0)。
根据广义容斥定理α(0)= β(0)-β(1)+β(2)-…+(-1)n-1β(n-1)。原式证毕。 3.31题（翟聪） 设B 是A 的子集，
A
=n ，B =m ，求A 的子集包含B 的子集的数目，设子集的元素数目为
r ，m ≤r ≤n 。（没看懂，不会做） 3.32题（翟聪） m,r,,n ∈N,满足m ≤r ≤n,试证?
???
??--r n m
n =∑=-m
i i 0)1(???? ??i m ???
? ??-r i n
证明：
从n 个元素中取k 个的组合，总含有制定的m 个元素的组合数为????
??--m k m n =?
??
?
??--k n m n ，设这m
个元素为12,,.....,
m a a a k
A 为不含k a 的组合（子集），i=1，…,m.
Ki
K K A A A ...21=?
??
?
??-r i n
???
?
??--r n m
n =
m
i i A 1
==???
?
??r n +∑
=-m
i i
1
)
1(·
i
j Kj
m
i m k k k i
A i 1
)
,(),..,(21)
1(=Φ∈∑
-???
? ??k r
3.33 题（翟聪）此题我个人不知道D 是什么玩意？ 求证 a)()(,,)(,,0)r k D n r k D n k r k =
--
证明： 右边=
()
()0
(1)
()!()!
r r k
k
i
r k i i n k i n r --=----∑(
)
(
)0
000
(1)
(0)!()!
r k r k i
r k i i n i n k r k -----=-----+∑
=()r
k *
(
)0
1
(1)
()!()!
r k
i r k i
i n k
i n r --=----∑=左边
b)
(,,)
D n r k
=(1,1,1)
D n r k ---+(n-1)(1,1,)D n r k --+(r-1)((2,2,)D n r k ---(2,2,1)D n r k ---)
()
()()
()()
(
)()(
)(
)
(
)111
1
10
2221210
(1)()!(1)()!(1)*
(1)
(1)!()!
()!
()!
(1)(1)(2)!(1)
(1)!()!()!
r r r r k
r k
r k k
k k
i
r k i
r k i
r k i
i
i i i i r r r k r k k i
r k i
r k i
i
i i n k i n k i n n k i n r n r n r r n k i n k i n r n r -----------===---------==---=
---+-----+
---------
------∑∑∑
∑1
k --??
??
??
???
?
∑
()(
)(
)(
)(
)(
)(
)(
)(
)(
)1
1111
2
22211
(1)
()!(1)
()!(1)*(1)(1)!(1)(1)
(2)!(1)
(1)!r k
r k
r k r i
r k r i
r k r i
r k k
i k i k
i i i i r k r k
r i
r k r i
r k k
i k i i i n k i n k i n n k i r n k i n k i -----------===----------==---=---+-----+
?
?----------??
?
?
∑
∑
∑
∑
∑
1
!(1)!(1)!
()!()!()!!()!(1)!
(1)!!(1)
()!(1)
()!(1)*
(1)
()!
()!!
()!
()!!()!
(2)!((1)r k
r k
r k i
i
i
i i i r r r r k r k r k k r k k r k k n k i n k i n n r r k i i n r r k i i n r r r r ----===------------=
---+-----------∑
∑
∑
2100(2)!
(2)!(1)!2)!!(1)!(1)!(1)(2)!(1)(1)!()!(2)!!()!(1)!!r k r k i i
i i r r k r k k k r k k n k i n k i n r r k i i n r r k i i ----==-??
??---------??---------?
?--------??
???
?
∑∑1
200()!()!1
(1)
(1)
(1)
(1)
()!!
()!!
(1)!!
(2)!(1)!(1)(1)(2)!!(1)!!r k
r k
r k i
i
i
i i i r k r k
i i
i i n k i n k i r k n r k i i r k i i r k i i n k i n k i k r k i i r k i i ----===---==-----=-+--+
-------??---------??------??
∑∑∑
∑∑
1
2
()!(1)!(2)!()(1)
(1)
(1)
(1)
()!!
(1)!!
(2)!!
r k
r k r k i
i
i
i i i n k i n k i n k i r k n k r k i i r k i i r k i i -----===----------=---+
---------∑∑
∑
1
2
()!(1)!(2)!()(1)
(1)
(1)
(1)
()!!
(1)!!
(2)!!
r k
r k r k i
i
i
i i i n k i n k i n k i r k n k r k i i r k i i r k i i -----===----------=---+
---------∑∑
∑
c)
()(,,)*(1,1,)(1)
n k
n k
D n n k n D n n k -=--+-
1
!()!!(1)!(1)
()!(1)
(1)!()!!()!!
(1)!!
(1)!!
!(1)
()!!
n k
n k i
i
i i n k
n n k n n k n k i n k i n k k n k i i n k k n k i i n n k k ---==-------=
----+
----------∑
∑
1
!
1!1!(1)
(1)
(1)
!!
!
!
()!!
n k
n k i
i
n k
i i n n n k i k i n k k ----==-=
-+--∑∑
1
!1!1!(1)
(1)
(1)
!
!
!
!
()!!
n k
n k i
i
n k
i i n n n k i k i n k k ----==-=
-+--∑
∑
得证。 d)
()()(,,)(,,)k
r
t
t
D n r k D n t r t k t =---
()()
(
)()(
)
(
)0
(1)
()!(1)
()!()!
()!
k
r
r r t r k
r k
t
k
t
k t i
r k i
r k i i i i n k i n k i n r n r ------==---=
-----∑∑
(
)(
)0
!!
!()!
()!!()!!
()!!()!()!
(1)
()!(1)
()!()!()!r k
r k
i
r k i
r k i i i i k r r r t k t t r k k r t t r k k t n k
i n k i n r n r ----==---------=
-----∑
∑
(
)(
)0
!
!
()!!()!
!()!()!
(1)
()!(1)
()!()!
()!
r k
r k
i
r k i
r k i i i i r r k t t r k t r k k t n k i n k i n r n r ----==-------=
-----∑
∑
反过程可证。
e)
(,,)*(1,1,)(1,,)D n r k r D n r k D n r k =--+-
()
(
)(
)
(
)()
(
)011
10
(1)
()!()!
*(1)
(1)!(1)
(1)!
()!
(1)!
r r k
k
i
r k i i r r r k r k
k
k
i
r k i
r k i
i i i n k i n r r n k i n k i n r n r --=-------==---=
-----+
-------∑∑
∑
(
)(
)(
)0
1
10
!()!!(1)
()!()!(1)!!
*
(1)!!()!!
(1)
(1)!(1)
(1)!
()!
(1)!
r k
i
r k i i r k r k
i
r k i
r k i i i i r r k k n k i n r r r r r k k r k k n k i n k i n r n r --=------==----=
---------+
-------∑
∑
∑
1
()!(1)!(1)!(1)
(1)
()(1)
()!!
(1)!!
()!!
r k
r k r k
i
i
i
i i i n k i n k i n k i n r r k i i r k i i r k i i ----===---------=
-+---------∑
∑
∑
当i=0时，各项左右相等，对应当n=r-k-1时候，左右也相等。
剩余左右当i=r-k 时候也相等，得证。 F ）
1!(1)(1)()!!!
()!!
!
!
j j
r
n i
n
i j j r n i n r r i i j j -===--=
--∑
∑
∑
3.34题（王卓） n ,
N ∈
设P n 表示在{1，2，……，n}的全排列中，排除了k ，紧随以k+1，k=1，2……，k+1，
试证P n=D n +D n-1, n N ∈. （不会做）
3.35题（王卓）
令D n (k)=D(n,n,k),试证
(a) D n (k)=???
?
??k n D n-k 证明：
()()()()()!1!)1()!
(,,0
i k n i k n k n
i k n i k n n n k n k n n D k D i
k
n i i
k
n i n --???
? ??--???? ??=--???
?
??---???
? ??=
=∑∑
-=-=i ()()
()!1!)1(00
0i k n i k n i k n i k n k n D i
k
n i i
k
n i k
n --???
? ??--=--???
?
??--???? ??-=∑∑-=-=-
()k n n D k n k D -???
?
??=∴ (b)!2121n D n n D n D n n =???
?
??++???? ??+????
?? 证明：
上面等式可变换为：
!02121n D n D n n D n n n =???
? ??++???? ??-+???? ??-
考虑n 元素的集合S={1,2,…,n}，设T 为S 的排列全体，则|T|=n!。设i A 是S 中恰有i 个在其自然位置的n-排列全体，则
n
i i
j i A T A A 0
==
=?φ
所以，∑
==
n
i i A T
||||
而，i n i D i n A -???
? ??=||
因此，∑
=-???
?
??=n
i i n D i n n 0
!
(c)(k+1) D n+1(k+1)=(n+1) D n (k) 证明：
()()()()!111!1111)1(!
01110
1
10
1i k n i k n k n i k n i k n k n k D i
k
n i i
k n i n --???
? ??--???? ??++=---+?
??
?
??--+-???? ??++=
+∑∑
-=--+=+()()()()()()()()()k D n i k n i k n k
n
n i k n i k n k n k k D k n i
k
n i i
k
n i n 1!11!)1(111110
01+=--???
?
??--????
??+=--???? ??--???? ??+++=++∑∑-=-=+
3.36题（王卓）
令D n (k)=D(n,n,k),试证
(a)!)(0
n k kD
n
k n
=∑
=
(b) D n (0)- D n (1)=(-1)n
(c) !)()1(02
n k D
k n
k n
=-∑
=
(d) !)()1()1(0
n k D
r k k k n
k n
=+--∑
=
3.37题（王卓） 试证
(a)()()()n m n m φφφ=,
(b)对于素数1p ,i 1≥,1
)
(--=i i i p
p p φ
()?
??? ?
?-?
??? ??-???? ??-
==k k p p p n n p p p n k 111111212121 φαα
α则根据
()()1
1111--=???? ?
?-=???? ??-=
==i i i i
i
p p p p p n n p
p
n φφ 3.38题（王卓）
试证 (a)()∑=
n
d n
d /φ
()()
()
∑∑
=
=n
d n
d d n d
d
n n //φμφ根据反演定理可得
(b)()()()()()n m h N n m h n m h n m ,,,,,=∈=其中φφφφ
(c)()通常是偶数
n n N n φ,3,≥∈
3.39题（王振华） 3.40题（王振华） 3.41题（王振华） （未完成）
3.42题（王振华）此题解答没我没怎么看懂。
一组人有1990个人，每个人至少有1327个朋友，试证其中四位，使得彼此都是好朋友 解；
令外边的都与括号里的1327个是朋友，1 {1989}，从里边不是外边人朋友的找出 2 {1988} ….. 663 {1327} 再从里边找人出来 662，1 { {1}，1236} 直至 663 { {663} 664} 按上面的方法继续 663 {{663} {663} 1} 把里边的1拿出外边一个进去为 662，1 { {1} {663} {663}}
这样1与里边的都是朋友，括号里前面括号的人与后边的都是朋友，所以一定有四个人彼此是朋友。
3.43题（王振华）
在边长为1的等边三角形内任取5个点试证其中至少有两点，期间距离小于1/2． 证：
把边长为１的三角形分成四个边长为1/2的三角形，如上图：则这５点中必有两点落在 同一个小三角形中．小三角形中任意两点间的距离都小于1/2． 3.44题（王居柱）
单位圆圆周上任意1n +个不同的点至少存在两点其间距离不超过2
2s in π
。
这还用证明吗？ 证明：
把圆周等分成ｎ段相等的弧，每段弧所对的最大弦长为Ｓ＝2
2s in
π
，把ｎ＋１个点
放到这ｎ个圆弧上，根据鸽巢原理，必有两个点在同一段弧上，这两点的距离必小于等于2
2s in
π
。
3.45题 （王居柱）
边长为1的正方形内任取9点，试证存在3个不同的点，由此构成的三角形面积不
过1
8。下面解法中为什么要放在8条边上，可以放在其他地方吗？有其他解法吗？
证明：
把正方形等分为8个三角形，每个三角形的面积为1
8,产生以正方形中心的8条边，把
9个点放到8条边上，根据鸽巢原理，必有两个点在同一条边上，所以可以得到一个三角形的面积小于1
8。
3.46题（王居柱）
任给5个整数，试证其中必存在3个数的和被3除尽。
证明：
课本145页例题，第（4）题
3.47 题（王居柱）
A 是n+1个数的集合，试证其中必存在两个数，它们的差被n 除尽。 证明:
构造一个序列1s =2a -1a , 2s =3a -1a ,……. n s =1n a +-1a , i
s ≠
j s （i ≠j ）,
有两种可能（1）若有一个m s ( 1≤m ≤n )是n 的倍数，则定理得证。 （2）设在序列中没有任何一个元素是n 的倍数，则1s ，2s ………..n s 除n 的余数为1，2，3，……….n-1，因为有n 个数，由鸽巢原理得，必有两个
数的余数是相同的，不妨设i s ，j s 的余数相同，
则 i s =1i a +-1a =bn+r (1)
j s =1j a +-1a =cn+r (2)
两式相减的
1i a +-1
j a
+=（b-c ）n 原式得证。
3.48 题（王居柱）未看。
A={1a ，2a ，…………21k a +} k ≥1,
i
a 是正整数，k=1,2,3,……2k+1,试证A 的任意排列：
1
i a ，2
i a ，…………, 21k i a + 恒有 21
1
k j +=∏（j
i j a a -）为偶数。
证明：
根据鸽巢原理，1a ，2a ，…………21k a +这2k+1个数中必有k+1个数同为偶数或同为
奇数，不妨设这k+1个数为1a ，2a ，…………1k a +，且同为奇数，则1a ，
2a ，…………21k a +中至多有
k 个偶数，根据鸽巢原理，
1
i a ，2
i a ，…………, 1
k i
a + 中至少有一个是奇数，奇数和奇数之差为偶数，所以
j i j a a - 中必有一个是偶数，同理，有k+1个数同为偶数时也成立， 所以原式21
1k j +=∏（j i j a a -）为偶数 得证。
3.49 题（王健）
A 是{1，2，……………,2n}中任意n+1个数,试证至少存在一对a,b ∈A,使下面结果成立：
a
b
证明：
设所取n+1个数是a 1, a 2,……….. a n, a n+1
对a 1, a 2,……….. a n, a n+1序列中的每一个数去掉一切2的因子，直至剩下一个奇数为止。
结果得到由奇数组成的序列r 1, r 2,……….. r n, r n+11到2n 中只有n 个奇数，故序列中至少有两个是相同的。设r i= r j=r 为，对应地有 a i=2
a i
r, a j=2
a j
r,
若，则至少存在一对a,b ∈A,使下面结果成立：
a b
3.50（王健） 未完成
3.51（王健） 未完成
3.52（王健）
未完成
3.53（王健）
未完成
3.54题（孙明柱）
二维空间的（x,y）点的坐标x和y都是整数的点称为格点，任意5个格点的集合A，试证A中至少存在两点，它们的中点也是格点。
证明：
任意5个格点，对于x，y，5个整数中至少存在3个数为偶数或者为奇数
它们的中点就是两个点的对应数的和的一半，
1，当存在三个偶数时，则其中任意两个数的和的一半能被2整除，余下的两个奇数的和也能被2整除，即存在两个格点。
2，当存在四或五个偶数时，则四个偶数中任意取两个的数和是2的倍数，即存在两个格点
反之存在奇数的情况也一样。
所以存在至少存在两点，它们的中点也是格点。
3.55题（孙明柱）
令A为等差数列
1，4，7，10,…,100
中任选20个不同的数，试证其中至少存在两个数，它们的和为104.
证明：
在这34个数中，除去1和52，余下的4和100，7和97，…..49和55，它们的和为104，共16对，从A中任取20个数，除去1和52，从余下的16对数中取18个，根据鸽巢原理，其中至少存在一对数的和为104
3.56题（孙明柱）未看。
平面上6个点，不存在3点共一条直线，其中必存在3点构成一个三角形，有一内角小于30o
。
证明：
首先任意选三个点构成一个三角形，把平面分成三角形内和三角形外两部分，根据鸽巢原理，剩下的三个至少有两个点在三角形内或三角形外，假设至少两个点在三角形内，由于没有三个点共线，
(1)当有两个点在三角形内时，一个三角形至少存在一个内角是锐角，这两点把三角形的这个锐角内角分成三等分，则至少有一个角是小于30o
，的，即存在
一个内角小于30o
的三角形的
(2)当有三个点在三角形内则，由(1)知，肯定存在一个内角小于30o
的三角形的
同理在三角形外也有同样的结论。 3.57题（孙明柱）这题没意义。
n 是大于等于3的整数，则下列数的集合： {2-1，2
31
2
1,21,,2
1n ---- }
中存在一数被n 除尽。 解：
我认为此题有争议,当n=4时，数的集合是{2-1，2
321,21--
} 即：{1，3，7}
都不能被4除尽。
3.58题（孙明柱）这题待解，应该看。
n 个人的集体，试证存在两个人，在余下的n-2个人中，至少有2
n -1个要么与
二人认识，要么与这两个人均不相识。
(完整word版)组合数学课后答案
习题二证明：在一个至少有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个坐标为整数的点，则其中至少有两个点，由它们所连线段的中点的坐标也是整数。证明：有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个相同种类的水果。
组合数学作业答案
第二章作业答案 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。
组合数学课后答案
作业习题答案 习题二 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. 从9 人中选派2 人参加某一活动，有多少种不同选法？ 2. 从9人中选派2人参加文艺活动，1人下乡演出，1人在本地演出，有多少种不同选派方法？ 3. 现从男、女8名学生干部中选出2名男同学和1 名女同学分别参加全校“资源”、“生态” 和“环保”三个夏令营活动，已知共有90 种不同的方案，那么男、女同学的人数是 A.男同学2人，女同学6人 B.男同学3人，女同学5人 C. 男同学5人，女同学3人 D. 男同学6人，女同学2人 4. 一条铁路原有m个车站，为了适应客运需要新增加n个车站（n>1），则客运车票增加了58 种（从甲站到乙站与乙站到甲站需要两种不同车票），那么原有的车站有 A.12 个 B.13 个 C.14 个 D.15 个 5．用0，1 ，2，3，4，5 这六个数字， （1 ）可以组成多少个数字不重复的三位数？ （2）可以组成多少个数字允许重复的三位数？ （3）可以组成多少个数字不允许重复的三位数的奇数？ （4）可以组成多少个数字不重复的小于1000 的自然数？ （5）可以组成多少个大于3000，小于5421 的数字不重复的四位数？ 二、注意附加条件 1.6 人排成一列（1 ）甲乙必须站两端，有多少种不同排法？ （2）甲乙必须站两端，丙站中间，有多少种不同排法？ 2. 由1 、2、3、4、5、6 六个数字可组成多少个无重复数字且是6 的倍数的五位数？ 3. 由数字1 ，2，3，4，5，6，7 所组成的没有重复数字的四位数，按从小到大的顺序排列起来，第379 个数是 A.3761 B.4175 C.5132 D.6157 4. 设有编号为1、2、3、4、5 的五个茶杯和编号为1、2、3、4、5的五个杯盖，将五个杯盖盖在
组合数学课后标准答案
组合数学课后标准答案
————————————————————————————————作者：————————————————————————————————日期：
习题二证明：在一个至少有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个相同种类的水果。
组合数学题目及标准答案
组合数学 例1: 将8个“车”放在8×8的国际象棋棋盘上，如果它们两两均不能互吃，那么称8个“车”处于一个安全状态。问共有多少种不同的安全状态? 解：8个“车”处于安全状态当且仅当它们处于不同的8行和8列上。 用一个排列a1,a2,…,a8 ，对应于一个安全状态，使ai 表示第i 行的ai 列上放置一个“车”。这种对应显然是一对一的。因此，安全状态的总数等于这8个数的全排列总数8!＝40320。 例4：n 位客人在晚会上每人与他人握手d 次，d 是奇数。证明n 偶数。 证：由于每一次握手均使握手的两人各增加 一次与他人握手的次数，因此n 位客人与他人握手 次数的总和 nd 是偶数 — 握手次数的2倍。根据奇偶 性质，已知d 是奇数，那么n 必定是偶数。 例４ 从1到2n 的正整数中任取n +1个，则这n +1个数中，至少有一对数，其中一个是另一个的倍数。 证 设n +1个数是a 1, a 2, ···, an +1。每个数去掉一切2的因子，直至剩下一个奇数为止。组成序列r 1, r 2,, ···, rn +1。这n +1个数仍在[1 , 2n ]中，且都是奇数。而[1, 2n ]中只有n 个奇数，故必有ri =rj = r , 则ai = 2αi r , aj = 2αj r 。若ai ＞aj ，则ai 是aj 的倍数。 例5 设a 1, a 2, ···, am 是正整数，则至少存在一对k 和l , 0≤k
李凡长版 组合数学课后习题答案 习题1
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)
李凡长版-组合数学课后习题答案-习题3
李凡长版-组合数学课后习题答案-习题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
组合数学与图论复习题及参考答案
组合数学与图论复习题及答案 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
组合数学 课后答案
习题二 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个相同种类的水果。
组合数学作业答案1-2章2016
组合数学作业 第一章引言 Page 13, ex3,4,7,30 ex3. 想象一座有64个囚室组成的监狱，这些囚室被排列成8 8棋盘。所有相邻的囚室间都有门。某角落处意见囚室例的囚犯被告知，如果他能够经过其它每一个囚室正好一次之后，达到对角线上相对的另一间囚室，那么他就可以获释。他能获得自由吗？ 解：不能获得自由。 方法一：对64个囚室用黑白两种颜色染色，使得横和竖方向相邻的囚室颜色不同。则对角线上两个囚室颜色为同黑或同白。总共偶数个囚室，若能遍历且不重复，则必然是黑出发白结束，矛盾。 方法二：64个囚室，若要经过每个囚室正好一次，需要走63步，即奇数步。 不妨假设该囚犯在第1行第1列，那么到第8行第8列，横着的方向需要走奇数步，竖着的方向需要走奇数步，即总共需要偶数步。 所以不能恰好经过每个囚室一次到达对角线上的囚室。 ex4. (a) 设f(n)是用多米诺牌(2-牌)对2×n棋盘作完美覆盖的个数。估计一下f(1),f(2),f(3),f(4)和f(5). 试寻找(或证明)这个计数函数f满足的简单关系。利用这个关系计算f(12)。 (b) 设g(n)是用多米诺牌(2-牌)对3×n棋盘作完美覆盖的个数。估计g(1),g(2),…,g(6). 解：(a) f(1)=1, f(2)=2, f(3)=3, f(n+2)=f(n+1)+f(n) f(4)=f(3)+f(2)=5, f(5)=f(4)+f(3)=8 f(6)=f(5)+f(4)=13 f(7)=f(6)+f(5)=21 f(8)=f(7)+f(6)=34 f(9)=f(8)+f(7)=55 f(10)=f(9)+f(8)=89 f(11)=f(10)+f(9)=144 f(12)=f(11)+f(10)=233 (b) g(1)=0, g(2)=3, g(3)=0, g(4)=9+2=11, g(n+4)=4g(n+2)-g(n), g(5)=0, g(6)=41. ex7. 设a和b是正整数，且a是b的因子。证明m×n棋盘有a×b的完美覆盖当且仅当a 既是m又是n的因子，而b是m或n的因子。(提示: 把a×b牌分割成a个1×b牌。) 解：充分性。当a既是m又是n的因子，而b是m或n的因子，则m×n棋盘有a×b的平凡完美覆盖。 必要性。假设m×n棋盘有a×b牌的完美覆盖。则m×n棋盘必有b牌的完美覆盖。根据书中的定理，b是m的因子或n的因子。 下面证明a既是m的因子又是n的因子。 方法一: 因为a是b的因子，所以a×b牌可以分割成b/a个a×a牌。m×n棋盘有a×a的完美覆盖，则必然有a×a牌的完美覆盖。而a×a牌是正方形的，所以只有唯一的一种平凡覆盖方式。从而m是a的倍数，n也是a的倍数。 方法二: 因为a是b的因子，不妨设b=ka。由m×n棋盘有a×b牌的完美覆盖，可任取一个完美覆盖。设第一行的n个方格由p个a×b牌和q个b×a牌盖住，则有n=pb+qa=(pk+q)a，所以n是a的倍数。同理，m也是a的倍数。
组合数学6章作业答案
第6章 容斥原理及应用 6.7 练习题 3、求出从1到10000既不是完全平方数也不是完全立方数的整数个数。 解：∵100001002=,9261213=,10648223= ∴从1到10000，共有100个平方数，21个立方数 又∵409646=，1562556= ∴从1到10000，共有4个6次方数，也就是共有4个数既是平方数又是立方数 计算：10000-100-21+4=9883 ∴从1到10000既不是完全平方数也不是完全立方数的整数有9883个 □ 4、确定多重集{}d c b a S ????=5,4,34，的12-组合的个数。 解：设T ：{}d c b a S ?∞?∞?∞?∞=,,,*的所有12-组合 1A ：a 的个数大于4的12-组合 2A ：b 的个数大于3的12-组合 3A ：c 的个数大于4的12-组合 4A ：d 的个数大于5的12-组合 要求的是： 4321A A A A ??? = T )(4321A A A A +++- )(434232413121A A A A A A A A A A A A ?+?+?+?+?+?+ )(432431421321A A A A A A A A A A A A ??+??+??+??- )(4321A A A A ???+ T =??? ? ??-+121412=455 1A =???? ??-+7147=120 2A =???? ??-+8148=165 3A =???? ??-+7147=120 4A =??? ? ??-+6146=84
21A A ?=???? ??-+3143=20 31A A ?=???? ??-+2142=10 41A A ?=???? ??-+1141=4 32A A ?=???? ??-+3143=20 42A A ?=???? ??-+2142=10 43A A ?=???? ??-+1141=4 321A A A ??=421A A A ??=431A A A ??=432A A A ??=4321A A A A ???=0 455-（120+165+120+84）+（20+10+4+20+10+4）=34 ∴多重集{}d c b a S ????=5,4,34，的12-组合的个数是34 □ 9、确定方程 204321=+++x x x x 满足 611≤≤x ，702≤≤x ，843≤≤x ，624≤≤x 的整数解的个数。 解：设 116x y -=， 227x y -=， 338x y -=， 446x y -= 则原方程等价于 确定方程 74321=+++y y y y 满足 501≤≤y ， 702≤≤y ， 403≤≤y ， 404≤≤y 的整数解的个数。 设S ：74321=+++y y y y 的所有非负整数解的集合 1A ：74321=+++y y y y 的所有满足61≥y 的非负整数解的集合 2A ：74321=+++y y y y 的所有满足82≥y 的非负整数解的集合 3A ：74321=+++y y y y 的所有满足53≥y 的非负整数解的集合 4A ：74321=+++y y y y 的所有满足54≥y 的非负整数解的集合 若j i ≠，则?=?j i A A ,那么要求的是：
组合数学习题解答
第一章： 1.2. 求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。 解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。 1.4. 10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？ 解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。故两人坐在一起的方式数共有2*9！，于是两人不坐在一 起的方式共有 10！- 2*9！。 1.5. 10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？ 解：这是一组圆排列问题，10个人围圆就坐共有10 ! 10 种方式。 两人坐在一起的方式数为9 ! 92? ,故两人不坐在一起的方式数为：9！-2*8！。 1.14. 求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？ 解：(1)在1到9999中考虑，不是4位数的整数前面补足0， 例如235写成0235,则问题就变为求： x 1+x 2+x 3+x 4=5 的非负整数解的个数，故有 F （4，5）=??? ? ??-+=515456 (2)分为求： x 1+x 2+x 3+x 4=4 的非负整数解，其个数为F （4，4）=35 x 1+x 2+x 3+x 4=3 的非负整数解，其个数为F （4，3）=20 x 1+x 2+x 3+x 4=2 的非负整数解，其个数为F （4，2）=10 x 1+x 2+x 3+x 4=1 的非负整数解，其个数为F （4，1）=4 x 1+x 2+x 3+x 4=0 的非负整数解，其个数为F （4，0）=1 将它们相加即得， F （4，4）+F （4，3）+F （4，2）+F （4，1）+F （4，0）=70。 第二章： 2.3. 在边长为1的正三角形任意放置5个点，则其中至少有两个点的距离≤1/2。 解：将边为1的正三角形分成边是为1/2的四个小正三角形，将5个点放入四个小正三角形中，由鸽笼原理知，至少有一个小正三角形中放有2个点，而这两点的距离≤1/2。 1/2 1/2 1/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.从9人中选派2人参加某一活动，有多少种不同选法？ 2.从9人中选派2人参加文艺活动，1人下乡演出，1人在本地演出，有多少种不同选派方法？ 3. 现从男、女8名学生干部中选出2名男同学和1名女同学分别参加全校“资源”、“生态”和“环保”三个夏令营活动，已知共有90种不同的方案，那么男、女同学的人数是 A.男同学2人，女同学6人 B.男同学3人，女同学5人 C. 男同学5人，女同学3人 D. 男同学6人，女同学2人 4.一条铁路原有m个车站，为了适应客运需要新增加n个车站（n>1），则客运车票增加了58种（从甲站到乙站与乙站到甲站需要两种不同车票），那么原有的车站有 A.12个 B.13个 C.14个 D.15个 5．用0，1，2，3，4，5这六个数字， （1）可以组成多少个数字不重复的三位数？ （2）可以组成多少个数字允许重复的三位数？ （3）可以组成多少个数字不允许重复的三位数的奇数？ （4）可以组成多少个数字不重复的小于1000的自然数？ （5）可以组成多少个大于3000，小于5421的数字不重复的四位数？ 二、注意附加条件 1.6人排成一列（1）甲乙必须站两端，有多少种不同排法？ （2）甲乙必须站两端，丙站中间，有多少种不同排法？ 2.由1、2、3、4、5、6六个数字可组成多少个无重复数字且是6的倍数的五位数？ 3.由数字1，2，3，4，5，6，7所组成的没有重复数字的四位数，按从小到大的顺序排列起来，第379个数是 A.3761 B.4175 C.5132 D.6157 4. 设有编号为1、2、3、4、5的五个茶杯和编号为1、2、3、4、5的五个杯盖，将五个杯盖盖在五个茶杯上，至少有两个杯盖和茶杯的编号相同的盖法有 A.30种 B.31种 C.32种 D.36种 5.从编号为1，2，…，10,11的11个球中取5个，使这5个球中既有编号为偶数的球又有编号为奇数的球，且它们的编号之和为奇数，其取法总数是 A.230种 B.236种 C.455种 D.2640种 6.从6双不同颜色的手套中任取4只，其中恰好有1双同色的取法有 A.240种 B.180种 C.120种 D.60种 7. 用0，1，2，3，4，5这六个数组成没有重复数字的四位偶数，将这些四位数从小到大排列起来，第71个数是。 三、间接与直接 1.有4名女同学，6名男同学，现选3名同学参加某一比赛，至少有1名女同学，由多少种不同选法？ 2. 6名男生4名女生排成一行，女生不全相邻的排法有多少种？ A B含有4个元素，试求同时满足下列两个条件的集合C的个数：（1） 3.已知集合A和B各12个元素， ? () C A B C A≠?,?表示空集。 且C中含有三个元素；（2） 4. 从5门不同的文科学科和4门不同的理科学科中任选4门，组成一个综合高考科目组，若要求这组科目中
Richard A.Brualdi 组合数学习题解答
1 20081215 1Richard A.Brualdi() Email:ge
2
2.9.1060()1 ()10 Y={y1,y2,···,y10}10Y k C k10C110+C210+···+C1010=210?1 S={s1,s2,···,s1023}, 1 s i 600,i=1,2,···,1023(2.1) S s i=s j,s i s j 9(2.1)S Y(2.1)52+53+···+60=504 S29?1=511S S 2.10.n>1( /) n{1,2,···,n}i n i0 n i n?1 0,n?11,2,···,n?2 2.16.100(0)3 3
4
3.16.66×6 24 6 (1,j1),(2,j2),···,(6,j6) j1,j2,···,j6{1,2,···,6}6! 6! 6!62 6!C26 3.17.248×8 6 (i1,j1),(i2,j2),···,(i6,j6) i1, (i686i1) i2<··· 6 7×7 7C47P47 736×6 C36P36572C36P36 C47P47+72C36P36 3.21.9716 i) ii)43() ()? i)9716 16216 ii)3×528 216?28 3.22.S n1,n2,···,n k n1=1.n=n1+n2+···+n k S n! n1!n2!···n k! n+1n1=1S n! 1.2. 求在1000和9999之间各位数字都不相同，而且由奇数构成的整数个数。 解：由奇数构成的4位数只能是由1，3，5，7，9这5个数字构成，又要求各位数字都不相同，因此这是一组从5个不同元素中选4个的排列，所以，所求个数为：P(5,4)=120。 1.4. 10个人坐在一排看戏有多少种就坐方式？如果其中有两人不愿坐在一起，问有多少种就坐方式？ 解：这显然是一组10个人的全排列问题，故共有10！种就坐方式。如果两个人坐在一起，则可把这两个人捆绑在一起，如是问题就变成9个人的全排列，共有9！种就坐方式。而这两个人相捆绑的方式又有2种（甲在乙的左面或右面）。故两人坐在一起的方式数共有2*9！，于是两人不坐在一 起的方式共有 10！- 2*9！。 1.5. 10个人围圆桌而坐，其中两人不愿坐在一起，问有多少种就坐方式？ 解：这是一组圆排列问题，10个人围圆就坐共有 10!10 种方式。 两人坐在一起的方式数为9!92? ,故两人不坐在一起的方式数为：9！-2*8！。 1.14. 求1到10000中，有多少正数，它的数字之和等于5？又有多少数字之和小于5的整数？ 解：(1)在1到9999中考虑，不是4位数的整数前面补足0， 例如235写成0235,则问题就变为求： x 1+x 2+x 3+x 4=5 的非负整数解的个数，故有 F （4，5）=??? ? ??-+=515456 x1+x2+x3+x4=4 的非负整数解，其个数为F（4，4）=35 x1+x2+x3+x4=3 的非负整数解，其个数为F（4，3）=20 x1+x2+x3+x4=2 的非负整数解，其个数为F（4，2）=10 x1+x2+x3+x4=1 的非负整数解，其个数为F（4，1）=4 x1+x2+x3+x4=0 的非负整数解，其个数为F（4，0）=1 将它们相加即得， F（4，4）+F（4，3）+F（4，2）+F（4，1）+F（4，0）=70。 第二章： 2.3. 在边长为1的正三角形内任意放置5个点，则其中至少有两个点的距离≤1/2。解：将边为1的正三角形分成边是为1/2的四个小正三角形，将5个点放入四个小正三角形中，由鸽笼原理知，至少有一个小正三角形中放有2个点，而这两点的距离≤1/2。 1/2 1/2 1/2 2.5. 在图中，每个方格着红色或蓝色，证明至少存在两列有相同的着色。 ?=种，现有5列，由鸽笼原理知，至少有二列着色方式解：每列着色的方式只可能有224组合数学习题解答