组合数学答案
3.1 某甲参加一种会议, 会上有6位朋友, 某甲和其中每一个人在会上各相遇12次, 每两人各相遇6次, 每3人各相遇4次, 每4人各相遇3次, 每5人各相遇2次, 每6人各相遇1次,1人也没遇见的有5次, 问某甲共参加几次会议?
解:设A 为甲与第i 个朋友相遇的会议集.i=1,2,3,4,5,6.则 │∪A i │=12*C(6,1)-6*C(6,2)+4*C(6,3)-3*(6,4)+2*(6,5)-C(6,6) =28
甲参加的会议数为 28+5=33
3.2:求从1到500的整数中被3和5整除但是不能被7整除的数的个数。 解:
设 A 3:被3整除的数的集合
A 5:被5整除的数的集合 A 7:被7整除的数的集合 所以 |=|
=
-|-|
=33-4=29 |
|
3.3 n 个代表参加会议,试证其中至少有2个人各自的朋友数相等
解:每个人的朋友数只能取0,1,„,n -1.但若有人的朋友数为0,即此人和其 他人都不认识,则其他人的最大取数不超过n -2.故这n 个人的朋友数的实际取数只 有
n -1种可能.,根据鸽巢原理所以至少有2人的朋友数相等.
×3.4试给出下列等式的组合意义
⎛n -m ⎫m l (1) ⎪=∑(-1) ⎝n -k ⎭l =0⎛ l -1⎫(2) ⎪=
⎝n -m -1⎭
n -m
⎛m ⎫⎛n -l ⎫ ⎪ ⎪, n ≥k ≥m ⎝l ⎭⎝ k ⎭
∑
j =0
n -m ⎫⎛n-m -j+l -1⎫j ⎛
(-1) ⎪ ⎪
⎝ j⎭⎝ l ⎭
⎛m +l ⎫
⎪⎝m +l ⎭
⎛m +l -1⎫⎛m +l ⎫⎛m +l ⎫⎛m +l ⎫l (3) ⎪= ⎪- ⎪+ ⎪-... +(-1) ⎝ m -1⎭⎝ m ⎭⎝m +1⎭⎝m +2⎭
证明:
(1)从n 个不同元素中取k ,使得其中必含有m 个特定元素的方案数为(
设这m 个元素为a 1,a 2, …,a m , Ai为包含a i 的组合(子集),i=1,…,m.
⎛n ⎫
|A 1 A 2 ... A m |= ⎪-(A 1 A 2 ... A m )
⎝k ⎭
⎛n ⎫⎛m ⎫⎛n -1⎫⎛m ⎫⎛n -2⎫m
= ⎪-( ⎪ ⎪- ⎪ ⎪+... +(-1)
⎝k ⎭⎝1⎭⎝ k ⎭⎝2⎭⎝ k ⎭m ⎫⎛n -l ⎫l ⎛
=∑(-1) ⎪ ⎪
l =0⎝l ⎭⎝ k ⎭
m
n -m k -m
) =(
n -m n -k
) 。
⎛m ⎫⎛n -m ⎫
⎪ ⎪) ⎝m ⎭⎝ k ⎭
⎛n ⎫⎛l -1⎫
(2)把l 个无区别的球放到n 个不同的盒子,但有m 个空盒子的方案数为 ⎪ ⎪
m n -m -1⎝⎭⎝⎭
令k=n-m,设A i 为第i 个盒子有球,i=1,2,„k
⎛k +l -1⎫
|A 1 A 2 ... A k |= ⎪-(A 1 A 2 ... A k )
k ⎝⎭⎛k +l -1⎫
= ⎪-
k ⎝⎭
k
⎛k ⎫⎛k -1+l -1⎫⎛k ⎫⎛k -2+l -1⎫k
( ⎪ ⎪- ⎪ ⎪+... +(-1) ⎝1⎭⎝ l ⎭⎝2⎭⎝ l ⎭
⎛k ⎫⎛k -k +l -1⎫
⎪ ⎪) k l ⎝⎭⎝⎭
k ⎫⎛k-j+l -1⎫j ⎛
=∑(-1) ⎪ ⎪
j =0⎝j ⎭⎝ l ⎭
(3)设A i 为m+l个元素中去m+i个,含特定元素a 的方案集;N i 为m+l个元素中取m+i
个的方案数。则:
⎛m +l ⎫⎛m +l -1⎫⎛m +l -1⎫N i = ⎪ |Ai |= ⎪ |Ai |= ⎪
m +i m +i -1⎝⎭⎝⎭⎝ m+i⎭⎛m +l -1⎫
|Ai +1|=|Ai |= ⎪
⎝ m+i⎭|Ai |=N i -|Ai | i=1,,2..., l
|A 0|=N 0-|A0|= N 0-|A1|=N 0-(N 1-|A1|)=N 0-N 1+N 2-... +(-1) N l ⎛m +l -1⎫⎛m +l ⎫⎛m +l ⎫⎛m +l ⎫l ⎪= ⎪- ⎪+ ⎪-... +(-1) ⎝ m -1⎭⎝ m ⎭⎝m +1⎭⎝m +2⎭
⎛m +l ⎫ ⎪⎝m +l ⎭
l
3.5 设有3个7位的二进制数
a 1b 1c 1
a 2b 2c 2
a 3b 3c 3
a 4b 4c 4
a 5b 5c 5
a 6b 6c 6
a 7b 7c 6
试证存在整数i 和j , 1≤i
a i =a j =b i =b j , a i =a j =c i =c j b i =b j =c i =c j
解:应用鸽巢原理,在每一个纵列中,含有三个元素,分别都只由两种选择0 或1,应用鸽巢原理所以必有a i =b i ,
a i =c i
b i =c i 中至少一个必然成立;成
立的时候取值的不同可以有这样几种情况:C 32⨯2=6种,而每一横行共有七个元素, 再次用鸽巢原理,必有两列是相同的 即: a i =a j =b i =b j ,
a i =a j =c i =c j
b i =b j =c i =c j 之一必然成立
3.6 在边长为1的正方形内任取5
。
证明:分别连接对边的中点,这样正方形被均匀的分成四个域,在正方形内任取5点,根据鸽巢原理,至少有两点在同一个域中,而一个域内两点的最远距离小
。
1
3.7 在边长为1的等边三角形内任取5点,试证至少有两点距离小于2。 证明:将边长为1的等边三角行分成4
三角形的边长为,21
离小于
12
。
3.8.任取11个整数,求证其中至少有两个数它们的差是10的倍数。
解:易知任意整数的个位数的可能取值只可能为0,1, 2, , 9,共10种可能,而利用鸽巢原理,任取的11个整数中,其中至少有两个整数的个位数相同,这两个个位数相同的整数的差显然是10的倍数。即证。
×3.9 把从1到326的326个整数任意分为5个部分,试证其中有一部分至少有一个数是某两个数之和,或是另一个数的两倍。
解:用反证法。设存在划分 P 1 P 2 P 3 P 4 P 5=[1, 326], P i 中没有数是两数之和,
即P i 中没有数是两数之差。设1到326中至少有⎢
⎢326-1⎥
⎥+1=66个元素属于P 1,5⎣⎦
并设为A ={a 1, a 2, a 66},不妨设a 1
⎢65-1⎥
个元素。设为
⎢4⎥+1=17⎣⎦
c 1
易知存在整数l , m 使得d k =c k +1-c 1=(a l -a 1) -(a m -a 1) =a l -a m 。所以,D 中的元素不属于P 1,也不属于P 2,只能属于P 3 ,P 4 ,P 5。故根据鸽巢原理,设至少存在⎢
⎢16-1⎥
个元素属于P 3。设为f 1
F ={f 1, f 2, f 3, f 4, f 5, f 6}。根据假定,F 中不存在元素是某两个元素之差,令g 1=f 2-f 1, g 2=f 3-f 1, , g 5=f 6-f 1。显然G 中的元素不属于P 3。且,
对于g i 存在p , q , l , m 使得
g i =f i +1-f 1=(c p -c 1) -(c q -c 1) =c p -c q =(a l -a 1) -(a m -a 1) =a l -a m 。
故G 中的元素也不属于P 1和P 2。则G 中的元素属于P 4 ,P 5。对于G 中的5个元素,根据鸽巢原理,设至少存在⎢
⎢5-1⎥
+1=3个属于P 4 。设为h 1
⎣2⎦
H ={h 1, h 2, h 3}。令t 1=h 2-h 1, t 2=h 3-h 1, T ={t 1, t 2}。显然,T 中的元素不属于
P 1, P 2, P 3 ,P 4 ,故T 的元素属于P 5。但根据假定t 1≠t 2-t 1,令u =t 2-t 1,则
1≤u
为5部分的假定相矛盾。
3.10 A,B,C 三种材料用作产品1,2,3的原料,但要求1禁止用B 和C 作原料,
2不能用B 作原料,3不允许用A 作原料,问有多少种安排方案?(假定每种材料只做一种产品的原料)。
解:此问题为有禁区的排列可转化为棋盘多项式求解 如图所示:
P=R =1+4x+4x 2+x 3
r 1=4,r 2=4,r 3=1
=XR+R
根据定理:
n!- r 1(n-1)!+r 2(n-2)!-r 3(n-3)!„„±r n 故方案为:3!-4(3-1)!+4(3-2)!-1=1 3.11 n个球放到m 个盒子中去,n
数。
题解:设m 个盒子的球的个数是a 1, „,a m , 各不相等,且有0≤a 1<a 2<···<a m .则有 a2≥1、a m ≥m -1,故
m 2
m 2m 2
(m -1) ,试证其中必有两个盒子有相同的球
≥1+2+„+m-1=相等.
(m -1) , 与n
×3.12 一年级有100名学生参加中文,英语和数学考试,其中92通过中文考试,75
人通过英语考试,65人通过数学考试;其中65人通过中,英文考试,54人通过中文和数学考试,45人通过英语和数学考试,求通过3门学科考试的学生数。
题解:设A 为通过中文的人数,B 为通过英语的人数,C 为通过数学的人数。
A ⋃B ⋃C =A +B +C -A ⋂B -A ⋂C -B ⋂C +A ⋂B ⋂C
A ⋂B ⋂C =100-92-75-65+65+54+45=323.13 试证
1 |A B|=|B|-|A B|
2 |A B C|=|C|-|A C|-|B C|+|A B C| 证:设全集为S
|A B| = |(S-A ) B|=|S B|-|A B|=|B|-|A B| 同理可证|A B C|=|C|-|A C|-|B C|+|A B C|
3.14 N ={1, 2, 1000},求其中不被5和7除尽,但被3除尽的数的数目。
解: 设U 表示全集,A 3表示能被3除尽的数的集合,A 5表示能被5除尽的数的集合,A 7
_
_
表示能被7除尽的数的集合。则所求的是A 5
A A
7
3
。
A 5=⎢
⎣5
_
⎢1000⎥⎢1000⎥
,, =200A =7⎥⎢7⎥=142
⎦⎣⎦
⎢1000⎥
A 3=1000-A 3=1000-⎢⎥=1000-333=667, 3⎣⎦
⎢1000⎥A 5 A 7=⎢=28, ⎥
⎣35⎦
_
A 5 A 3=A 5 (U -A 3) =A 5-A 5 A 3=200-66=134,
_
同理,A 7 A 3=A 7 (U -A 3) =A 7-A 7 A 3=142-47=95
_
A 5 A 7 A 3=A 5 A 7 (U -A 3) =A 5 A 7-A 5 A 7 A 3=28-9=19
所以,
_
_
_
7
3
A 5
A A =1000-A 5 A 7 A 3
_
_
_
_
=1000-A 5-A 7-A 3+A 5 A 7+A 5 A 3+A 7 A 3-A 5 A 7 A 3 =1000-200-142-667+28+134+95-19=229
N ={1,2, ,120}
3.15.,求其中被2,3,5,7中m 个数除尽的数的数目,m=0,1,2,3,4.
求不超过120的素数的数目。
解:
令A , B, C ,D 分别表示N 中能被2, 3, 5, 7除尽的数。⎢120⎥⎢120⎥A =⎢=60, B ==40⎥⎢⎥
⎣2⎦⎣3⎦⎢120⎥⎢120⎥C =⎢=24, D ==17⎥⎢⎥
⎣5⎦⎣7⎦
⎢120⎥⎢120⎥A ⋂B =⎢=20, A ⋂C =⎥⎢10⎥=126⎣⎦⎣⎦⎢120⎥⎢120⎥A ⋂D =⎢=8, B ⋂C ==8⎥⎢⎥
⎣14⎦⎣15⎦
⎢120⎥⎢120⎥
B ⋂D =⎢=5, C ⋂D ==3⎥⎢⎥
⎣21⎦⎣35⎦
⎢120⎥⎢120⎥
A ⋂B ⋂C =⎢=4, A ⋂B ⋂D ==2⎥⎢⎥
⎣30⎦⎣42⎦⎢120⎥⎢120⎥
B ⋂C ⋂D =⎢=1, A ⋂C ⋂D =⎥⎢70⎥=1105⎣⎦⎣⎦⎢120⎥A ⋂B ⋂C ⋂D =⎢=0⎥
⎣210⎦
α(1) =6+02+04+0
4+01+22+
1+
2+4+81=
+88
1=7+5
14=3
α(2) =α(3) =α(4) =
56
=α(1- ) β(1)
⎛1+1⎫
⎪α⎝1⎭⎛1+2⎫(+2 ) ⎪α⎝1⎭3*-8
4=* 0
+⎛1
-(3) ⎝13⎫⎪α ⎭
(4)
=141-2*5+6
=α β(2)
⎛2+1⎫
(2-) ⎪α
2⎝⎭
+⎛2
+(3) ⎝22⎫⎪α⎭
(4)
+ =56-3*80= 3
β(3)=α(3)-
⎛3+1⎫
⎪α(4) ⎝3⎭
=8-0=8
β=α=
不超过120的素数数目即为:
A ⋂B ⋂C ⋂N -A ⋃B ⋃C D
=120-α(1)+α(2)-α(3)+α(4)=120-141+56-8+0=27
30
20中的至少一个数的数目3.16 求正整数n 的数目,n 除尽1040,
解:
1020
4030
=2=2
4060
⨯5⨯5
40304030
A ={n 除尽10B ={n 除尽20
的数}的数}
A ⋃B =|A |+|B |-|A ⋂B |
|A |=40⨯40, |B |=60⨯30, |A ⋂B |=40⨯30A ⋃B =1600+1800-1200=2200
3.17 n除尽1060, 2050, 3040中至少一个数的除数,求n 的数目
解:1060=260*560, 2050=2100*550, 3040=240*340*540 A :1060的约数 B :2050的约数 C :3040的约数
|A|=61×61=3721 |B|=101×51=5151 |C|=41×31=1271 |A B |= 61×51=3111
|B C |=41×41=1681 |A C |=41×41=1681 |A B C |=41×41=1681 |A B C |=|A |+|B |+|C |-(|A B |+|B C |+|A C |)+|A B C |=5351
23
×3.18 求下列集合中不是n , n 形式的数的数目,n ∈N 。
(1){1, 2, 3, , 10
4
}
4
A =1, 2, 3, , 10
2
2
2
{}, |A |=10000
23
;
解:B ={1, 2, 3 100},|B |=100; B C内元素为1…100000
C ={1, 2, 3 46},|B |=46
3
3
3
B ⋂C =4 通过程序验证既是2次方又是3次方的 |A |-|B |-|C |+B ⋂C =10000-100-46+4 即为所求
(2){103, 103
+1, 10
4
}
A =10, 10+1, , 10
2
2
{
334
}, |A |=10000
-1000+1=9001;
解: B ={32 100},|B |=100-32+1=69;
C ={10, 11, 12 46},|B |=46-10+1=37B ⋂C =1
3
3
3
3
|A |-|B |-|C |+B ⋂C =9001-69-37+1即为所求
3.19 {1000,1001,„,3000},求其中是4的倍数但不是100的倍数的数的数目。 解:A 为4的倍数的整数
B 为100的倍数的整数 |A
|=|A|-|A
|=
= 480
×3.20 在由a,a,a,b,b,b,c,c,c 组成的排列中,求满足下列条件的排列数 (1)不存在相邻3元素相同
(2)相邻两元素不相同
解:(1)设S 为总共的排列数,A a 为3个a 相邻的排列,A b 为3个b 相邻的排列,A c
为3个c 相邻的排列;
所以不存在相邻3元素相同为
A a A b A c =S -A a A b A c
=
9! 3!3!3!
-A a -A b -A c +A a A b +A b A c +A a A c -A a A b A c
5!+3⨯-3! 3!3!3!7!
=1480-3⨯
=1480-420+60-6=1114
(2)设S 为总的排列数,A a 为2个以上a 相邻的排列,A b 为2个以上b 相邻的排列,A c
为2个以上c 相邻的排列;
所以不存在相邻3元素相同为
A a A b A c =S -A a A b A c
=
9! 3!3!3!
-A a -A b -A c +A a A b +A b A c +A a A c -A a A b A c
7!6!
+3⨯-
3!3!!23!!!222!!!228!
=1480-3⨯
=1480-1680+630-90=340
×3.21:求从O (0,0)点到(8,4)点的路径数。已知(2,1)到(4,1)的线段,(3,1)到(3,2)的线段被封锁。
解:由题意设 A 1:从(0,0)点到(8,4)点经过(2,1)到(3,1)的线段.
A 2:从(0,0)点到(8,4)点经过(3,1)到(3,2)的线段. A 3:从(0,0)点到(8,4)点经过(3,1)到(4,1)的线段.
从(0,0)点到(8,4)点经过(2,1)到(4,1)的线段,根据乘法原理
||||||| |-|
|=C(4,12)-( |
|
=495-(168+84+140)+(105+63+0)-0 =271
3—22 求满足条件 x1+x2+x3=20, 3≤x 1≤9,0≤x 2≤8,7≤x 3≤17 的整数解数目. 解:作变量代换
a=x1-3,b=x2,c=x3-7 0≤a ≤6, 0≤b ≤8, 0≤c ≤10
则 方程变为 a+b+c=10
设s 为这个方程的非负整数解集合 ∣s ∣=C(10+3-1,10)=66
设p 1为性质 a≥7,p 2为性质b ≥9,p 3为性质c ≥11
|=C(1,2+1)*C(4-1,8-3+4-1)=C(1,3)*C(3,8)=3*56=168; |=C(1,3+1)*C(4-2,8-3+4-2)=C(1,4)*C(2,7)=4*21=84; |=C(1,3+1)*C(4-1,8-4+4-1)=C(1,4)*C(3,7)=4*35=140;
|= C(1,2+1)*C(4-1,8-4+4-1)= C(1,3) *C(3,7) =3*35=105; |= C(1,2+1)*C(4-2,8-3+4-2)= C(1,3) *C(2,7) =3*21=63; |=0;
|=0;
|+||+|
|)+(|
|+||+||)
令A i 为s 中满足性质p i (i=1,2,3)的集合,
则问题归结为求∣A 1∩A 2∩A 3∣. 可求得是方程a+b+c=10(a≥7,b ≥0,c ≥0) 的整数解集
合, 通过作代换 z1=a-7,z2=b,z3=c 可得
∣A 1∣=C(3+3-1,3)=10 ,
类似可得 ∣ A2∣=C(1+2,1)=3 , ∣A 3∣=0
∣A 1∩A 2∣=0 ∣A 1∩A 3∣=0 ∣A 2∩A 3∣=0 ∣A 1∩A 2∩A 3∣=0
∣ A1∩A 2∩A 3∣=66-13=53
3.23 求满足下列条件
X1+X2+X3=20
6
解:设y1=x1-6.y2=x2-5,y3=x3-10, 则有y1+y2+y3=x1+x2+x3-21=19 设r1=9-y1, r2=15-y2, r3=25-y3
则有r1+r2+r3=49-(y1+y2+y3)=49-19=20 即r1+r2+r3=20
r1>=0, r2>=0, r3>=0 解的数目为
⎛3+20-1⎫
⎪=231⎪
⎝20⎭
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=x 1-1+x 2+x 3-4+x 4-2=13
0≤y 1≤4,0≤y 2≤7,0≤y 3≤4,0≤y 4≤4
⎛13+4-1⎫⎛16⎫⎛16⎫
⎪= ⎪= ⎪=560,令S 中具有y 1≥5的子
⎝13⎭⎝13⎭⎝3⎭
则该问题的非负整数解S ,S =
集为A 1,y 2≥8的子集为A 2,y 3≥5的子集为A 3,y 4≥5的子集为A 4。问题转化为求
A 1⋂A 2⋂A 3⋂A 4。
对于A 1,相当于
(y 1+5) +y 2+y 3+y 4=13 或 y 1+y 2+y 3+y 4=8
具有性质A 1的非负整数解的数目为
⎛8+4-1⎫⎛11⎫⎛11⎫A 1= ⎪= ⎪= ⎪=165
⎝8⎭⎝8⎭⎝3⎭
同理,A 2=56,A 3=165,A 4=165 A 1⋂A 2=
⎛13-5-5+4-1⎫⎛6⎫⎛3⎫⎛6⎫==20A ⋂A ==1A ⋂A =,,1314⎪ ⎪ ⎪ ⎪=20
⎝13-5-5⎭⎝3⎭⎝0⎭⎝3⎭
⎛6⎫⎛3⎫⎛3⎫
A 2⋂A 3= ⎪=1,A 2⋂A 4= ⎪=20,A 3⋂A 4= ⎪=1,
⎝3⎭⎝0⎭⎝0⎭
A 1⋂A 2⋂A 3=A 1⋂A 3⋂A 4=A 2⋂A 3⋂A 4=A 1⋂A 2⋂A 4=0, A 1⋂A 2⋂A 3⋂A 4=0
A 1⋂A 2⋂A 3⋂A 4=S -A 1⋃A 2⋃A 3⋃A 4
=560-(165+56+165+165-20-1-20-1-20-1) =72
3.25证明满足下列条件:x 1+x 2+x 3+x 4=r (1≤x i ≤k , i =1, 2,......., n )
⎛n ⎫⎛r -(k +1) i +n -1⎫
的整数解数目为∑(-1) ⎪ i ⎪⎪ n -1⎪
i =0⎝⎭⎝⎭
n
i
答案:
设A i 为{x i ≥k +1}
由x 1+x 2+x 3+...... +x n =r
得:x 1+x 2+x 3+... +y i +k +1+...... +x n =r 推出:
x 1+x 2+x 3+... +y i +...... +x n =r -(k +1)
⎛r +n -1⎫
⎪|A 1⋂A 2⋂A 3⋂...... ⋂A n |= r ⎪-
⎝⎭
⎛n
∑|A i |+ ⎝i =1
n n
i
∑∑|A
i =1
j >i
⋂A j |+
∑∑∑|A
i =1
j >i k >j
i
⋂A j ⋂A k |+...... +(-1)
n -1
⎫
|A 1⋂A 2⋂... ⋂A n |⎪
⎪⎭
⎛n ⎫⎛r -(k +1) +n -1⎫⎛n ⎫⎛r -2(k +1) +n -1⎫
⎪⎪= 1⎪⎪ r -(k +1) ⎪+ 2⎪⎪ r -2(k +1) ⎪+.......... ..
⎝⎭⎝⎭⎝⎭⎝⎭n ⎫⎛r -(k +1) i +n -1⎫i ⎛
⎪=∑(-1) i ⎪⎪ n -1⎪
i =0⎝⎭⎝⎭
n
3.26 试证满足下条件: 的整数解为
i
∑(-1) i =0n
x 1+x 2+ +x n =r 1≤x i ≤k , i =1, 2, , n
⎛n ⎫⎛r -ki -1⎫
⎪ ⎪ ⎪ ⎪⎝i ⎭⎝n -1⎭
证明:设y i =x i -1 ∴0≤y i ≤k -1, i =1, 2, , n i ≥k
∴ N =A 1 A 2 A n
n
整数解为∑
i =0
⎛n ⎫⎛r -ki -1⎫
⎪(-1) i ⎪⎪ n -1⎪
⎝⎭⎝⎭
i
×3.27 求n 对夫妻排成一行,夫妻不相邻的排列数。
解:令A i =第i 对夫妻相邻而坐的集合,i =1, 2,..., n ,所问的问题为求
n
n
A 1⋂A 2⋂... ⋂A n =N -
⎛n ⎫
∑
i =1
A i +
∑∑
i =1
j >i
A i ⋂A j -... +(-1) A 1⋂A 2⋂... ⋂A n
n
n
n
h
=∑(-1) 2 h ⎪⎪(2n -h -1)! (圆桌)
h =0⎝⎭
×3.28设p,q ∈N ,p 是奇数, 现有pq 个珠子, 着q 种颜色, 每种颜色有p 个珠子,假定相同颜
色的珠子无区别,试分别求满足以下条件的珠子的排列数。 (1) 同颜色的珠子在一起 (2) 同颜色的珠子处于不同的块 (3) 同颜色的珠子最多在两个块
解:
1)由于是同颜色的珠子放在一起,有q !种方案。 2)
3)
3.29 将r 个相同的球放进n 个不同的盒子,无一空盒,求方案数。
根据可重复组合公式,组合意义即是,将r 个相同的球放进n 个不同的盒子,无一空
盒,
所以总方案数为(n+r-1 r).
×3.30 试证:
n -1
∑
i =0
⎛n ⎫⎛n +r -i -1⎫⎛r -1⎫
⎪(-1) i ⎪⎪ r ⎪= n -1⎪⎪
⎝⎭⎝⎭⎝⎭
i
证明:令A 1表示第一个盒子为空;
A 表示第二个盒子为空;
2
A 表示第n 个盒子为空
n
⎛n +r -i +1⎫⎛n +r -i -1⎫
⎪⎪ r ⎪= n -i -1⎪ ⎝⎭⎝⎭
⎛n ⎫⎛n +r -i -1⎫ ⎪ i ⎪⎪ n -i -1⎪表示从n 个不同的盒子中取出i 个为空盒,则剩下的n-i 盒子不⎝⎭⎝⎭
为空。
|
A
1
'
A 2 ... A N |=∑
' '
n -1
(-1)
i
i =0
⎛n ⎫⎛n +r -i -1⎫
⎪ i ⎪⎪ n -i -1⎪⎝⎭⎝⎭
(A I 表示
'
A
I
的非
)
表示的几何意义是R 个相同的球放入n 个不同的盒子中,不许有空盒。
⎛r -1⎫
n -1⎪⎪表示的几何意义是R ⎝⎭
个相同的球放入n 个不同的盒子中,不许有空盒。
几何意义相同所证成立。
×3.31 设B 是A 的子集,| A | = n,| B | = m,求A 的子集中包含B 的数目,设子集的元素数目为r , m≤r ≤n 。 解:
A 的子集中包含B 的那部分,即为在A-B 中任取值的组合数,可为取1,2,3…….n-m 个
n -m
所以,A 的子集中包含B 的数目为∑C n k -m 。
k =0
×3.32
()=∑(-1) ()()
n-m n-r
i
m i
n -i r
i =0
m
左边=(-1)
m
m m
(n -m )! (n -r )!(r -m )!
n -m r
, 右边=(-1)
()()+(-1)()()+
m 0
n r
1
m 1
n -1r
…+
()(). 左边=右边。
⎛r ⎫
×3.33 试证
(1)D (n , r , k ) = k ⎪⎪D (n -k , r -k , 0)
⎝⎭
(2) D (n , r , k ) =D (n -1, r -1, k -1) +(n -1) D (n -1, r -1, k )
+(r -1){D (n -1, r -2, k ) -D (n -2, r -2, k -1)}
其中,D (n , r , -1) 定义为0.
⎛n ⎫ k ⎪⎪ ⎝⎭
(3) D (n , n , k ) =nD (n -1, n -1, k ) +(-1)
n -k
⎛k ⎫⎛r ⎫ ⎪⎪(4) ⎪D (n , r , k ) = ⎪D (n -t , r -t , k -t ), t ≥0 t t ⎝⎭⎝⎭
(5)D (n , r , k ) =rD (n -1, r -1, k ) +D (n -1, r , k ), 其中r
r
(6) D (n , n -r , 0) =
∑
i =0
⎛r ⎫
i ⎪⎪D (n -i , n -i , 0), 其中D (n , n , 0) =D n ⎝⎭
D (n , r , k ) 是3.6节中推广了的错排。
证明:
(1) 此题可由组合含义证明。 等式左边:相当于从n个不同元素中取r个进行排列,其中只有k个元素在原来的位置
⎛r ⎫这样的方案数,为D (n , r , k ) 。等式右边:相当于首先在r个元素中取k个元素,为 ⎪,
⎝k ⎭
然后在n-r 个元素中取r-k 个,对r-k 个元素进行完全错排,为D (n -k , r -k , 0) ,故总的方
⎛r ⎫⎝k ⎭
案数为 ⎪D (n -k , r -k , 0) 。左右两端显然相等,证毕。
(2) (5)此题可由组合含义证明。
从n个不同元素中取r个进行排列,其中只有k个元素在原来的位置的方案数(D (n , r , k ) )可以分为两种情况:即是否包含元素a(a为任意元素)。第一种情况是包
含元素a,则只需在剩下的n-1个元素中取r-1个即可,然后进行只有k个元素不变的错排,方案数为rD (n -1, r -1, k ) ;第二种情况是不包括元素a,则需要在剩下的n-1个元素中取r个元素,进行只有k个元素不变的错排,方案数为D (n -1, r , k ) 。所以总的方案数为: rD (n -1, r -1, k ) +D (n -1, r , k ) ,即D (n , r , k ) =rD (n -1, r -1, k ) +D (n -1, r , k ) ,证毕。×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 ), 试证(1)D n (k ) =(2)(1)D 1
n
()D
+()D
n k n 2
n -k
2
+……+(n )D n =n !
n
(3)(k +1) D n +1(k +1) =(n +1) D n =n !
×3.36 设D n (k)=D(n,n,k),试证
n
(a )∑kD n (k ) =n !
k =0
(b )D n (0) - Dn (1)=(-1)n
n
(c )∑(k-1) 2D n (k ) =n ! „
k =0
n
(d )∑k(k-1)...(k-r +1)D n (k ) =n ! 其中r ≤n 。
k =r
i
i
i -1
3.37 试证对于素数p ,i ≥1,φ(p ) =证明:根据定理 若n =
φ(n ) =n (1-
1)(1-
1
p
-
p
p p
1
a
1
a
2
2
..... )
p
a
k
k
1
p p
)...(1-
2
1
p
k
p 是素数
∴φ(
p
i
) =
p
i
(1-
1p
) =
p
i
-
p
i -1
所证成立。
×3.38 试证:
(1)n =∑d | nΦ(n)
(2) Φ(m,n) Φ(n)= Φ(m) Φ(n)h,其中m,n ∈N,h=(m,n) (3) n∈N,n>=3, Φ(n)通常是偶数。 解:(1)因为Φ(n)=n∑d | nμ(d)/d 所以Φ(n)= ∑d | nμ(d)n /d 所以我们设n=f(n), Φ(n)=g(n) 根据反演定理,可得n =∑d | nΦ(n).
(2)因为Φ(m,n)=mn∑d1,d2 | m,nμ(d1,d2)/d1,d2 根据第一问,可得必然存在一个中间的数h, 使得
Φ(m,n) Φ(n)= Φ(m) Φ(n)h,其中m,n ∈N,h=(m,n)成立。 ×3.39
n ≥2,证明若n 有k 个不同的奇偶因子,则 (1)φ(n )≥n ⨯2-k (2)2k |φ(n )
(3)φ(2n ) ,n 是奇数 =φ(n ) φ(2n ) ,n 是偶数 =2φ(n )解:此题不会。
×3.40 从集合φ={1, 2, 3, 4, 5, 6, 7, 8, 9, A , B , C , D , J , K , L , U , X , Y , Z }中随机抽取28次,求出现块CUBAJULY 1987的几率。 解:
3.42 一组有1990个人,每个人至少有1327个朋友,试证其中4位,使得彼此都是朋友。 答案:
从1990中取出一个人a ,剩下1989个人,则这个人a 至少认识1989中的1327个人,定义为friend1,还剩下1989-1327=662个人不认识定义为strenge1。如果在a 认识的1327个人中又存在一个人b ,他也认识的人也为1327个,因为friend1中只有662个人所以,b 认识的人中一定有至少两个在a 认识的friend1里,所以至少有4位彼此是朋友!
3.43 边长为1的等边三角形内任意5个点,至少有两点,其间距离最多为1/2。 解:把边长为1的等边三角形分成四个边长为1/2的等边三角形,如图所示
则根据鸽巢原理,这五点中必有两点落在同一个边长为1/2的等边三角形
中。而边长为1/2的等边三角形中任意两点间的距离都小于1/2。
3—45 边长为1的正方形内任取9点, 试证存在3个不同的点, 由此构成的三角形面积不超过1/8.
解: 如下图.
把1 × 1的正方形分成四个(1/2)×
(1/2)的正方形, 根据
鸽巢原理,((10-1)/4)+1=3,则这10点中必有三点落在同一个小正方形中, 而小正方形内的任三点构成三角形面积最大为1/8.所以构成的三角形面积不超过1/8.
3.46:给任何5个整数,试证必存在3个数的和被3除尽。
解:所有整数可分为3类,mod3=0,mod3=1,mod3=2,分别标记为A,B,C.
如果在这五个数中,任何一类的个数大于等于3,那么在这个类中任取三个元素,它们的和一定能被三整除。
如果没有任何一类的个数大于等于3,那么只能是2,2,1的组合.
如果A 类元素只有一个,那么B 类,C 类各有2个元素。A ,B ,C 各类各取一个,它们的和一定能被三整除。
如果B 类元素只有一个,那么A 类,C 类各有2个元素。A ,B ,C 各类各取一个,它们的和一定能被三整除。
如果C 类元素只有一个,那么A 类,B 类各有2个元素。A ,B ,C 各类各取一个,它们的和一定能被三整除。
3.47 A 是n+1个数的集合,试证其中必存在两个数,它们的差被n 除尽。
解:如果n+1个元素有相同的值,那么命题自然得证
如果每两个元素之间都有不同的值,那么如下
假设a 为集合中最小的数,现在有值为0,1,2,…,n-1个盒子,现在对于A 中的每
个数a i 进行如下运算
K=(ai -a ) mod n
把a i 放入K 值对应的盒子当中,所以根据鸽巢原理,必有一个盒子内有两个元素,不妨设为a i 和a j ,因为他们满足(ai -a ) mod n =(aj -a ) m od n ,所以a i 和a j 满足
a i -a j mod n =0,所以一定存在两个元素的差被n 除尽
3.48 A={a 1,a 2,…,a 2k+1},k ≥1,a i 是正整数,k=1,2,„,2k+1,试证A 的任意排列:
a i 1,a i 2,
恒有
2k+1
a i 2k+1
为偶数
∏(a
j =1
i j
-a j )
2k+1
证明:另n=|A|=2k+1,则A 中奇数和偶数个数不相等。如果
∏(a
j =1
i j
-a j )中全为“奇数
2k+1
-偶数”或“偶数-奇数”的形式,则A 中奇数和偶数个数相等,与前面矛盾。顾
∏(a
j =1
i j
-a j )
2k+1
中必有“奇数-奇数”或“偶数-偶数”的形式,即
∏(a
j =1
i j
-a j )为偶数。
3.49 A 是{1, 2, 3, , 2n }中任意n+1个数,试证明至少存在一对 a , b ∈A ,使下面 结果成立: a b
解:假设取出任意n+1个数,将它们每一个都拆成2的几次幂乘以一个奇数
的形式;那么一共能拆出n+1个奇数(每个数对应一个奇数)。然而,在上述A 集合
之中,2n 个元素一共只有n 个奇数。所以根据鸽巢原理,能够得出上述n+1个奇数中至少有两个是相等的。而这两个数必然一个能被另一个整除。—〉得证。
×3.51
A 是由13个互不相等的实数组成0
x -y 1+xy
≤2-
3
的集合,则至少有一对
x . y ∈A 使
×3.52.空间2n 个点,n >1,试证用条线段任意连接这2n 个点,必然出现一个三角形,并证明
用n 2条线连接,则可能不出现三角形。
解:将这2n 个点分成两个集合,A , B , |A |=a ,|B |=b , a +b =2n ,则使得A 中每个点都与B 中每个点都有一条边相连,总的需要的边数为ab, 易知当a=b=n时需要的边数最多且为n 2, 又因为总共有n 2+1条线段,则在集合A,B 中一定存在某两个点之间有边,即证必然出现一个三角形。当a=b=n时,用n 2条线段相连时,上述情况则不出现三角形。 ×3.53 三维空间中9个坐标为整数的点,试证在两两相连的线段内,至少有一个坐标为整数的内点。
解: 三维空间中,任意两坐标为整数的点,若这两点相连的线段内不存在坐标为整数的
内点,则对于x,y,z 这三个坐标轴,这两点至少在一个坐标上的差值正好是1。那么,
在这9个坐标为整数的点中,任取一点,与这个点的三个坐标中,存在差值正好是1的共有7类,即:与x 轴差值正好是1,与y 轴差值正好是1,与z 轴差值正好是1,与x,y 轴差值都是1,与x,z 轴差值都是1,与y,z 轴差值都是1,与x,y,z 轴差值都是1。那么,对于剩下的8个点,若存在一点a 不满足这7种情况,那么a 点与这个点相连的线段内必有一个坐标为整数的内点。若剩下的8个点都属于这7种情况之一,那么,运用鸽巢原理,则至少存在两个点属于这7种情况中的同一个情况,那么,这两点中必存在一个坐标为整数的内点。
3.54 二维空间的(x,y )点的坐标x 和y 都是整数的点称为格点。任意5个格点
的集合A ,试证A 中至少存在两点,它们的中点也是格点。 解:集合A={(x 1, y 1),(x 2, y 2),(x 3, y 3),(x 4, y 4),(x 5, y 5)}
x i , y i 均为整数
(x i , y i )有四种情况,分别是:奇偶,偶奇,奇奇,偶偶。
问题就转化为(
x i +x j
2
,
y i +y j
2
)也为整数。
即(x i +x j , y i +y j )也为整数
5个点,4种情况,根据鸽巢原理必有两个点是相同类型 又因为奇+奇=偶,偶+偶=奇,故得证。
×3.55 令A 为从等差数列1,4,7,10„100中选择20个不同的数,试证其中至少存在两
个数,他们的和为100. 题解:假设20个数中任意两个数的和都不为104
a n +bm ≠104 即 1+(n-1)3 + 1+(m-1)3≠104 即n+m≠34
1≤n ≤20, 1≤m ≤20 2≤n+m≤40 即n+m可以为34 即矛盾,成立。
×3.56 平面上6个点,不存在3点共一条直线,其中必存在3点构成一个三角形,有一内角小于30°。 题解:这道题是Ramsey 数的变形,三点构成一个三角,某个点对应的这个角度>30 或
反证法: 假设题设不成立. 即所有构成的角度都>30度;
假设1分别与23456(不妨设顺时针围绕在1周围) 的夹角都>30度, 则总度数>150; 合理;
继续: 三角形124中1点的度数>60 ;又因为2>30 且 4>30 则三内角和>180 ,矛盾, 得证!
×3.57n 是大于等于3的整数,则下列数的集合{2-1,22-1,23-1,„„,2n -1-1}中存在一数被n 除进。 答:此题出错,A 集合中不满足被2的倍数的n 除尽,例如n=6>3,但不满足题设。
×3.58 n 个人的集体,试证存在两个人,在余下的n-2个人中,至少有⎢⎥-1个要么与
2
⎣⎦⎢n ⎥
二人互相认识,要么与这两个人均不认识。
×3.59.S ⊆{1,2, 14,15},A 和B 是S 的不相交子集。若A 和B 的元素之和不等,即属于A 的元素之和不等于属于B 的元素之和,试证 S ≤5
×3.60 下列m*n矩阵的元素是实数
a 11a 21a m 1
a 12a 22 a m 2
a
a 1n a 2n
每行的最大元素与最小元素之差不超过d>0.对梅列元素重新排列成递减序列,即最大元素在第一行,最小元素在第m 行,是证明经过重新排列后的矩阵,每行最大元素与最小元素之差仍然不超过d 。
3.61 n个单位各派两名代表出席一个会议,2n 位代表围着一圆桌坐下,试问 (1) 各单位的代表并排坐着的方案有多少? (2) 各单位的两人互不相邻的方案数又等于多少? 解:(1). (n -1)!*2n
(2). 令A i 第i 个单位的代表相邻而坐的集合,i =1, 2, , n
n
n
n
i
∴|A 1 A 2 A n |=N -∑|A i |+
i =1
∑∑|A
i =1
j >i
A j |- +(-1) |A 1 A 2 A n |
n
|A i |=2(2n -2)! |A i A j |=2(2n -3)!
2
n
|A 1 A 2 A n |=2(n -1)!
n
故各单位的两人互不相邻的方案数:∑2h (n )(2n -h -1)! h
h =0
3.62 一层书架有m 层,分别放置m 类不同种类的书,每层n 册,现将书架上的图书全部
取出清理,清理过程中要求不打乱所在的类别。试问: (1)m 类书全不在各自原来层的方案数有多少?
⎛⎝
11!
12!
- +(-1)
m
解:m 个对象的错排问题 :m ! 1-+
1⎫m
⎪⨯(n ! ) m ! ⎭
(2)每层的n 本书都不在原来的位置上的方案数等于多少? 解:如果某类书不在原来的层上,则对该层的n 本书全排列即可; 如果某类书在原来的层上,则对n 本书进行错排即可:
m k =0
∑C m
k
⎛1111⎛⎛k 1⎫k n 1⎫⎫
()⨯k ! ⨯ 1-+- +(-1)n ! ⨯1-+- +-1⎪⨯(n ! )⨯ ⎪⎪ ⎪
1! 2! k ! 1! 2n ! ⎝⎭⎝⎭⎭⎝
m -k
(3)m 层书都不在原来层次,每层n 本书也不在原来位置上的方案数?
⎛m
解:m ! 1-+- +(-1)
1! 2! ⎝
1
1
1⎫⎛⎛11n 1⎫⎫
()n ! 1-+- +-1⎪⨯ ⎪⎪ ⎪
m ! ⎭⎝⎝1! 2! n ! ⎭⎭
m
3.63 (m+1)行
相同颜色的格子。
列的格子同m 种颜色着色,每格着一色,其中必有一个四角
证:每列有(m+1)行,只有m
种颜色,故一列中必有两格同色.同色的2个格子的行号有
种取法.有m 种色,故有
种同色模式,现有
列,必有两列
的同色模式相同.即由这两列的对应行上有4个格子同色,正好是一个矩形的4个角上的格子.
3.64 两名教师分别对6名学生进行面试(每位教师各负责一门课),每名学生面试时间固
定,试问共有多少种面试的顺序。
解:先对第一门课的学生进行排列,然后再排第二门课的顺序,那么第二门课程的排序就将成为一个错排问题,对每一个第一门课的排列,都对应一系列的错排,即如下 第一门课的顺序有6! 种;
第二门课的顺序有(根据例3-10,错排问题): D 6=6! ( (1/2!) -(1/3!) +(1/4!) -(1/5!) +(1/6!) )=265;
故总顺序有6! ×265种.
3.65:X={0,1,2,3„„9,10} 从X 中任意取7个元素,则其中必有两个元素之和等于10. 解:|X|=11,分为6组{0,10},{1,9},{2,8},{3,7},{4,6},{5}.从这11个数中去7个根据鸽巢原理必有一组取两个数且去两个数的组不能是{5}(因为{5}只有一个元素),无论在其他五组中那个组里,取两个数它们的和都是10,所以得证。
3—66 每边长为3的等边三角形内径取10个点, 试证至少有一对点距离小于1.
解: 如图:
解: 把边长为3的三角形分成9个边长为1的三角形, 根据鸽巢原理,((10-1)/9)+1=2.则10个点中必有两点落在同一小三角形内, 而小三角形中任意两点距离小于1. 证毕 3.68 n 项任务分给r 个人,若n
r 2
(r -1) ,则至少有两人任务数相同。
解:利用反证法,假设,没有两个人有相同的任务数。假设第一个人的任务数为m 1,第二个人的任务数为m 2,„„,第r 个人的任务数为m r 。则有
m 1+m 2+ +m r =n ,m 1≠m 2≠ ≠m r 。
则有,0+1+2+ r -1=证毕。
r (r -1) 2
≤m 1+m 2+ +m r =n ,与假设n
r (r -1) 2
矛盾。则
3.69 试证(mn)!被(m ! ) 答案:
n
整除
组合意义证明: (mn)!的意义是把mn 个有区别的球,放到mn 个无区别的盒子里,且盒
子不允许为空,而且每个盒子里有m 个球的方案数。它等价于把mn 个球分成n 份,每份m 个球,然后去掉重复的每个盒子里m 个球的全排列,一个这样的全排列有n 个,所以去掉
n
(m ! ) 个全排列,得
(mn)!
(m ! )
n
,方案数一定为整数。
×3.71 1, 2,..., n 的全排列中不出现相邻两数相邻的排列数等于多少? 解:C (n +r -1, r )=
p (n +r -1, r ) (n -1)!
×3.72 0,1,2,3,4,5,6,n-1的圆排列,求不出现相邻数相邻的排列数,包括n-1和0作为相邻数.
解:根据容斥原理 假设A i 表示i 和i+1相邻,我们要求的为
n
n n
i
n n n
(n-1)!-∑|A i |+
i =1
∑∑|A
i =1
j =i
⋂A j |-∑
i =1
∑∑
j =i k =j
|A i ⋂A j ⋂A k |+„„„„
3.73 4位十进制数a,b,c,d ,试求满足
a+b+c+d=31的数的数目.
解:这个问题可以看做是,r 个误区别的球,放进n 个盒子,无一空盒,且可以重复
的,所以数目为(n+r-1 r) ,n=4,r=31, 所以计算的数目为:598.
3.74 4位十进制数a b c d,满足a+b+c+d=17,1≤a ≤3, 2≤b ≤4, 3≤c ≤5, 4≤d ≤6, 试求这样数的数目。
解: 令A=a-1,B=b-2,C=c-3,D=d-4
则0≤A ≤2, 0≤B ≤2, 0≤C ≤2, 0≤D ≤2,
A+B+C+D=7
这样的数的数目有四个。
3.75 已知n 是正整数,d 1=1,d 2,„,d r =n 的除数,即 d i |n ,i=1,2, „,r , 试证:
∑φ(d
d i
i
) =
μ(d ) d
n
证:利用Mobius 反演定理,有φ(n)=n*=>
f (n d ) =
∑
d /n
=
∑μ(d ) *d
d /n
n d
φ(n)=g(n) ∑
d /n
g (d ) =
∑φ(d ) =n
d /n
即:n=∑φ(d )
d /n
×3.76试证欧拉函数有φ(n ) =n ∑
d |n
μ(d )
d
其中求和是对n 的所有除数,包括1和n 进行的。 证明:
当n =1时,φ(1)=1,等式右端1*∑
d|1
μ(d )
d
=1*1=1, 左右相等。
p ……k
当n>1时,n =p 11p 22 等式右端n*∑
d|n
k
αα
αk
k
…, p n 1=记p 1p 2
μ(d )
d (-1)
j
=n *∑
d|n1
μ(d )
d
k
=n (1+1p i
∑
d|n1
μ(d )
d
k
) =n (1+
∑∑
j =1I ∈c (k , j )
μ(∏P i )
i ∈I
∏P i
i ∈I
=n (1+
∑∑
j =1I ∈c (k , j )
1∏P i
i ∈I
) =n ∏(1-
i =1
) .
3.77 设f 满足f (mn ) =f (m ) f (n ), g (n ) =解:g (m )(n ) = =
∑
d |n
f (d ) ,试证:g (mn ) =g (m ) g (n )
∑
d 1|m
f (d 1) ⋅∑f (d 2) =
d 2|m
∑∑
d 1|m d 2|m
f (d 1) f (d 2) =
∑∑
d 1|m d 2|m
f (d 1d 2)
∑
f (d 1d 2) =g (mn ) , 证毕。
n
d 1d 2|mn
×3.78 n 是正整数,n 的正除数的数目用τ(n ) 来表示,试证:∑μ(d ) τ() =1
d |n
d
解:因为:τ(n ) 表示n的正除数的数目
所以:τ(n ) =
∑1
d |n
令: ⎨
⎩
⎧f (n ) =τ(n )
g (n ) =1
则:f (n ) =
∑1=∑g (n )
d |n
d |n
根据反演定理,有: g (n ) =
∑
d |n
μ(d ) f () =1,证毕。
d
n