这两组数据只是总集合的一子集合，可以不包含总集合中的所有数据。
将n个不同的整数组成的集合记作U，从中抽取的两组数据的集合分别记作A和B，假设U中元素的升序排列如下：
a1,a2,a3，……，an;
则所求可按集合A中含元素的个数进行分类：
1.当A含一个元素时，共有C(n,1)种可能子分类。
(1).若A={an}，则B有2^(n-1)-1种选择；
(2).若A={a{n-1}}，则B有2^(n-2)-1种选择；
……
(n).若A={a1}，则B有0种选择；
故此时，符合条件的结果共有2^n-(n+1)
2.当A含两个元素时，
共有C(n,2)种可能子分类。
…………
思路正确，但过于繁琐，不便于实际应用。
1.146个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从一个特定引擎开始有多少方案？
解：设6个引擎分别为1、2、3、4、5、6
不失一般性，我们把1、2、3放在第一排，4、5、6放到第二排。
由题意知从一个特定引擎开始，不妨设从1开始，那么
（1）1开启之后，下一个开始点有4、5、6三种选择
（2）第二排的一个开启之后，下一个开始点有2，3两种选择 （3）然后第一排，第二排剩下俩，那么有两种选择 （4）然后第一排只剩一个，第二排只剩一个，所以就剩一种选择 所以，由乘法法则 方案数=3×2×2×1×1=12
1.15试求从1到1000000的整数中，0出现了多少次？
解：先考虑1到99 9999.
个位为零的整数出现99999×1次 为：10—999990 十位为零的整数出现9999×10次 为：101—999909 百位为零的整数出现999×100次 为：1000—999099 千位为零的整数出现99×1000次 为：10000—990999 万位为零的整数出现9×10000次 为：100000—909999 而100 0000本身有6个零
所以从1到1000000的整数中，0出现的次数为：
99999×1+9999×10+999×100+99×1000+9×10000+6=488895
我认为其解法错误，比如该种分类方法漏掉了100 200 300 400等。
1.16 n 个完全一样的球放在r 个有标志的盒子里面()r n ≥ ，无一空盒，问有多少种方案？
解：r 个盒子无一空盒，说明先要从n 个球中取出r 个先放每个盒中一个； 余下n-r 个无标志的球，放入r 个有标志的盒子中，根据定理可以得出 结果是()()r n n C r n r n r C --=-+-+,1,1 。
我认为答案错误。
00001000100010 (0001000100)
n 个0，r 个1。相到于在n 个球之间的n-1个间隙中选择r-1个插入挡板。
1.17 n 和r 都是正整数，而且r ≤n ，试证下列等式
1) 1
1n n r r p np --=
2) 1(1)n n r r p n r p -=-+ 3) 1,n n r r n
p p r n n r
-=
<- 4) 11n n n r r r p p rp +-=+
5) 1111!(n n n r r r p r r p p +---=+++……1)r
r p -+
1） 证明：左边=n*(n-1)……（n-r+1） 右边= n*(n-1)……（n-r+1） 所以 左边=右边 同理：（2）（3）（4）得证。 5
）
证
明
：
利
用
（
4
）
，
11n n n r r r p p rp +-=+
=11111111()()n n n n n n
r r r r r r p rp rp p r p p --------++=++=……=等式右边
1．18 8个盒子排成一列，5个有标志的球放到盒子中，每个盒子最多放一个球，要
求空盒子不相邻，问有多少种排列方案。
解： P( 5 , 5 )*C( 6 , 3)=2400（种）
答：共有2400种方案。
1.19．n + m 位由m 个0，n 个1组成的符号串，其中n ≤m+1，试问不存在两个1相邻的符号串的数目。
解：该题可以看作是往m 个0里插入n 个1，即从m+1个空中选取n 个空
放1，这样就使得不存在两个1相邻，总的解决方案数为：(1,)C m n +
1.20 甲单位有10个男同志，4个女同志，乙单位有15个男同志，10个女同志，
由他们产生一个7人的代表团，要求其中甲单位占4人，而且7人中男同志5位，试问有多少种方案？
解： 根据题意，符合要求的组合法有3种：（1）甲单位4男0女，乙单位1
男2女；（2）甲单位3男1女，乙单位2男1女；（3）甲单位2男2
女，乙单位3男0女。则对应的组合数为：（1）14175021011504410=C C C C ，（2）50400011021514310
=C C C C ， （3）1228500
1031524210=C C C C 。因此，符合条件的方案数共有：141750+504000+122850=768600种。
1.21 一个盒子里有7个无区别的白球，5个无区别的黑球。每次从中随机取走一球，已知前面取走6个，其中3个是白的。试问第6个球是白球的概率？
解：设6个球的编号分别为1、2……6。6个球中第6个球是白球的所有可能方案为：126、136、146、156、236、246、256、346、356、456，既有10种可能。那么第6个球是白球的概率为10/C （6，3）=1/2。
1.22 求图1-22中从0到P 的路径数。 （1）路径必须经过A 点 （2）路径必须过道路AB （3）路径必须过A 点和C 点
（4）道路AB 封锁（但A,B 两点开放）
解题：（1）35
3253560C C ++?= （2）34
3243350C C ++?= （3）312
323122240C C C +++??= （4）534583243937C C C +++-?=
1.23 令{1,2,.......,1},2,{(,,)|,,,,}s n n T x y z x y z s x z y z =+≥=∈<<，试证：
2111323n
k n n T k =++????
==+ ? ?????
∑
解题：（1）：因为x,y 的最小值为1，所以(2,3,4,........)z n ∈ 当z=2时：x=y=1,
当z=3时：x,y 各有两种选择11
2
2C C ………
当z=n+1时：x,y 各有两种选择11
n
n C C 即：21
n
k T k ==∑
（2）：因为,,x y z s ∈且,x z y z <<。当x=y 时，从(1,2,......1)n +取两
个数，大的给z ，小的给x,y,有21n C +。当x y ≠时，(1,2,......1)n +取三个数，大的给z ，小的给x 或y ，有31
2n C
+，即：2111323n
k n n T k =++????
==+ ? ?????
∑
1.24 A={(a,b)|a,b ≤Z,0≤a ≤9,0≤b ≤5}
(1) 求x-y 平面上以A 作顶点的长方行数目； (2) 求x-y 平面上以A 作顶点的正方形数目；
解：思想是分别以纵坐标0、1、2、3、4为起点，横坐标和纵坐标一起够成的长方形
即：4*C （9，1）+4*C （9，2）+4*C （9，3）+4*C （9，4）+4*C （9，5）+5*C （9，6）+5*C （9，7）+5*C （9，8）+5 + 3*C （9，1）+3*C （9，2）+3*C （9，3）+3*C （9，4）+4*C （9，5）+4*C （9，6）+4*C （9，7）+4*C （9，8）+4 + 2*C （9，1）+2*C （9，2）+2*C （9，3）+3*C （9，4）+3*C （9，5）+3*C （9，6）+3*C （9，7）+3*C （9，8）+3
+ C （9，1）+C （9，2）+C （9，3）+C （9，4）+C （9，5）+C （9，6）+C （9，7）+C （9，8）+1=13374
即以A 作顶点的长方形数目为13374个。 同理以A 作顶点的正方形数目为：
C （9，1）+C （9，2）+C （9，3）+C （9，4）+C （9，5）+ C （9，1）+C （9，2）+C （9，3）+C （9，4）+ C （9，1）+C （9，2）+C （9，3）+ C （9，1）+C （9，2）+ C （9，1）=1071
即以A 作顶点的正方形数目为1071个。
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 ）根据题意，符合条件的直线有三种可能：（1）P 1，P 2，P 3，P 4，P 5构
成的直线，有1条；（2）P 6~P 15中的任选两点构成的直线，有452
10
=C 条；（3）由P 1~P 5中的一个点及P 6~P 15中的一个点构成的直线，有
501
1015=C C 条。因此，符合要求的直线共有1+45+50=96条。
（b ）根据题意，符合条件的三角形有三种可能：（1）P 1~P 5中任选两个点
及P 6~P 15中任选一个点构成三角形：有1001
1025=C C 个；（2）P 1~P 5中任选一个点及P 6~P 15中任选两个点构成三角形：有2252
1015=C C 个；（3）P 6~P 15中任选三个点构成三角形：有1203
10
=C 个。因此，共可组成三角形100+225+120=445个。
1.26．{1,2,...,1000},,,ab 0mod5,{a,b}S a b S =∈≡使求数偶的数目。
解：由题知0mod5ab ≡，说明a*b 能被5整除。则分为两种情况：
① a ,b 同时为5的倍数
1000中5的倍数有200个 方案数为：200*199/2
② a ,b 不同时为5的倍数，即a ,b 中有一个不是5的倍数 方案数为：800*200 总的
总的方案数为：200*199/2+800*200
1．27 6位男宾，5位女宾围一圆桌而坐，
（1） 女宾不相邻有多少种方案。
（2） 所有女宾在一起有多少种方案。
（3） 一女宾A 和两位男宾相邻又有多少种方案。 解：（1）5！*P( 6 , 5 )=120*720 =86400 答：女宾不相邻有86400种方案。 （2）6！*5！=86400
答：所有女宾在一起有86400种方案
（3）8！*2*C （6 ，2）=40320*2*3*5=1209600
答：一女宾A 和两位男宾相邻又有1209600种方案。
1.28 k 和n 都是正整数，kn 位来宾围着k 张圆桌而坐，试求方案数。 解; 方案数为：
[C(nk,n)*(n-1)!]*[ C(n(k-1),n)*(n-1)!] *[ C(n(k-2),n)*(n-1)!]*……*[ C(n,n)*(n-1)!] 整理得：(n-1)!k * C(nk,n)* C(n(k-1),n)*……*C(n,n)= (n-1)!k *(nk)!/ (n!) k =(nk)!/ n k
1.29 从n 个对象中取r 个作圆周排列，求其方案数？
解：()()1,-?r r n C ！
1.30试证下列等式
1(1) , 11 1(2) , 111(3) , 1 n n n r n
r r r n n n r r n r r r n n n r n
r r n r -????=≤≤ ? ?-????
????
-+=≤≤ ? ?-????
-????=≤≤ ? ?-????
证明：（1）
!
!()!(1)!!
(1)!()!!()!1 , 11n r n r n n n r r n r r n r n n n r n
r r r =
--=?=
----????=≤≤ ? ?-????
左边右边所以 （2）
!
!()!1!!
(1)!(1)!!()! 1 , 11n r n r n r n n r r n r r n r n n n r r n
r r r =
--+=?=
--+-????
-+=≤≤ ? ?-????
左边右边所以 （3）
!
!()!(1)!!
!(1)!!()!1 , 1 n r n r n n n n r r n r r n r n n n r n
r r n r =
--=?=
-----????=≤≤ ? ?-????
左边右边所以
1.31 试证明任意r 个相临数的连乘：
(1)(2)...()n n n r +++
被r ！除尽
解： 显而易见，n r r +??
???是一个整数，由
n r r +??
???
=()()!()!(1)(2)...()!!!!!n r n r n n n r r n r r r n r +++++==+-
由于
n r
r
+
??
?
??
是整数，所以
(1)(2)...()
!
n n n r
r
+++
是整数，那么
(1)(2)...()
n n n r
+++可以被r！除尽
1.32：在a,b,c,d,e,f,x,x,x,y,y 的排列中，要求y必须夹在两个X之间，问这样的排列数等于多少？
解：要求y必须在两个x之间，所以符合要求的排列必须有结构“xyxyx”，把“xyxyx”看作一个元素，与a,b,c,d,e,f,排列排列数等于6！。
1—33 已知r,n,k都是正整数,r≥nk,将r个无区别的球放在n个有标志的盒子里,每盒至少k个球,试问有多少种方案?
解: ①先保证每一个盒子至少k个球,因为球无区别,把n个不同盒子每一个盒子放k个球.共kn个.
②问题转化为将(r-nk)个小球放入n个不同盒子,每个盒子可以放任意个球,可以有空盒,根据可从复组合定理可得共(n+r-nk-1,r-nk)=(n+r-nk-1,n-1)
1.34在r，s，t，u，v，w，x，y，z，的排列中求y居于x和z中间的排列数。解：一共9个位置，y只能放到2到8中间，当x放到第一个位置，y放到第二个位置，其他全排列有7！种方法，第一个位置也可以放z，共有2*7！种方法。y放到第三个位置，y前x有两种选择，y后z有6种选择，其他全排列，所以方法有2*6*6！，总方法有2*2*6*6种方法，以此类推算到y在第5个位置因为后边是对称的。
总数=2*（7！+2*6*6！+3*5*6！+4*4*6！）
=72000
1．35 凸十边形的任意三条对角线不共点。试求这凸十边形的对角线交于多少个点？
解：根据题意，每4个点可得到两条对角线，1个对角线交点，从10个顶点任取4个的方案有C(10,4)种，即交于210个点。
1.36 试证明一个整数是另一个整数的平方的必要条件是除尽它的数的数目是奇数。
答案：
由： n= (3)
32211a a a p p p ，其中
.......,21p p 是质数，....2,1a a 是正整数。
则n 的因子数有(a1+1)(a2+1)(a3+1)............个。 得 2n =.. (3)
23
2
22
1
21
a a a p p p ，因为(2a1+1),(2a2+1),(2a3+1)………..
都是奇数，
所以 2n 的因子数为(2a1+1)(2a2+1)(2a3+1)…….个，也是奇数个。
1.37 给出
??
? ??++=??? ??+??? ??-+?+??? ??+??? ??--+??? ??+??? ??--+??? ????? ??m 1r n m m r 0m n 22r 2m 2n 11r 1m 1n 0r m n
m
-r-1 -1 0 m-n
可看作是格路问题:左边第i 项为从点C 到点(-1,i)直接经过(0,i)的路径,
再到点B 的所有路径。左边所有项的和就是从C 点到B 点的所有路径数即为右边的意义.
1.38 给出???
? ??++=???? ??++???? ??++???? ??++???? ??11...21r n r n r r r r r r 的组合意义。 解：设{}1121,,...,,++-=n r n a a a a A ，从A 中取r+1个元素组合成C ，考虑以下n-r+1种情况：
（1）C a ∈1，则A 需从{}1\a A 中取r 个与1a 配合，构成C ，共???
?
??
r n 中可能。 （2）C a C a ∈?21,，则需从{}21,\a a A 中取r 个，加上2a 构成C ，共???
?
??-r n 1种可
能。
（n-r ）,121,...,,--r n a a a C ?,则需从{}r n a a a A -,...,,\21中取r 个组合，再加上1a 构成
C ，共???
? ??+r r 1种可能。
（n-r+1）r n r n a a a a ---,121,...,,C ?,这时只有????
??r r =1种可能。
故???? ??++=???? ??++???? ??++???? ??++???? ??11...21r n r n r r r r r r 1.39
证明:
证：组合意义,右边：m 个球,从中取n 个,放入两个盒子,n 个球中每个球都有两种放法,得到可能的方案数。左边：第i 项的意义是一个盒子中放i 个,另一个盒子放n-i 个,所有的方案数相加应该等于右边。
右式
左式＝==?-=-?
-=--?
=---?
-=--∑
∑∑∑∑=====),(2)
,()!
(!!
)!(!!
!)!(!)!()!(!!!!)!()!()!
()!(!!)
,(),(00000n m C n m C k n k n k n k n n n m m k n n m n n k m k n n m k m k m k m k n k m C k m C n n k n k n
k n
k n
k
证毕。
1.40 从n 个人中选出r 个围成一个圆圈，问有多少种不同方案。
解：首先从n 个人中选出r 个有C(n,r)种方案，r 个人进行一个圆周排列， 根据圆周排列公式，共有r!\r 种方案，既(r-1)!种方案， 所以根据乘法法则，一共有C(n,r)*(r-1)!种方案。
1.41 分别写出按照字典序，由给定排列计算其对应序号的算法及由给定序号计算其对应的算法。
解：生成所有排列的数组A[][]： S1. A[0][]<-p p p n
...2
1
<-12…N ，LEN=1；
S2. j<-0;
j 从0到n ，若p
p
j
j >
-1
,则退出；
S3. i = max{ j | p
p
j
j <
-1
}； S4. h = max{k | p
p
k
i <
-1
}；
S5.将
P 1i -和
p
h 互换的
p
p p n
'12
'1
...；
S6.A[LEN][]<- p
p p n
'12
'
1
...,LEN++；
S7.将
p i
'和p
n
'互换，得
p p p p i
n
......'
'
1
2
'1
；
S8.A[LEN]<-
p p p p i
n
......'
'
1
2
'
1
, LEN++,转到S2;
给定排列计算其对应序号的算法 S1. 输入
p p p n
...2
1
；
S2.j<-0,j 从0到LEN 若A[j][]==
p p p n
...2
1
，则输出j ，退出；
否则j++；
由给定序号计算其对应的算法 S1.输入序号j ；
S2.输出A[j][]，退出；
1.42（a ）按照习题1.41的要求，写出邻位对换法（排列的生成算法之二）的相应算法。 解：
S1.若p1p2…pn 没有数处于活动状态则结束。
S2.将处于活动状态的各数中值最大者设为m ，则m 和它的箭头所指一侧相邻的数互换位置，而且比m 大的所有数的箭头改变方向，即—>改为<—，<—改为—>。转S1。
（b ）写出按照邻位对换法由给定排列生成其下一个排列的算法。 解：
S1.A[i]<—1； S2.i 从2到n 做
始A[i]<—i ，D[i] <—i, E[i] <—-1终； S3.q<—0
i 从1到n 输出A[i]; S4.k<—n;
S5.若k>1则转S6；
S6.D[k] <—D[k]+E[k],p<—D[k]; S7.若p=k 则做E[k] <—-1,转S10； S8.若p=0 则做
始E[k] <—1,q<—q+1转S10终；
S9.p<—p+q ，r<—A[p],A[p] <—A[p+1],A[p+1] <—i ，转S3; S10.k<—k-1转S5.
1.43证明：考虑C(n,k)和C(n,k-1)进行比较。
C(n,k)/C(n,k-1)=(n-k+1)/k 。
当k>n/2时,(n-k+1)/k<1,即C(n,k)当k>n/2时,(n-k+1)/k>1,即C(n,k)>C(n,k-1)得到当k 为最接近n/2的数时，C(n,k)取到最大值。
1.44 （1）用组合方法证明n 2)2(！n 和n n n 3
2!
3?）（都是整数。
（2）证明()
1
2!)!
(+n n n 是整数。 证明：
（1）设有2n 个不同的球放入n 个不同的盒子里，每个盒子两个，这个方案数应该是整数。而把2个球放入同一个盒子里不计顺序，应该把全排列数除掉这些重复计算的次数，n 个盒子内部的排列共重复计算了n )!2(次，得到的2n 个不同球放入n 个不同的盒子里，每盒两个的方案数为
n
n )!2()!
2(，得证。同理，若有3n 个不同的球，放入n 个不同的盒子里，，每个盒子3个球，重复的次数为n )!3(，故方案数为n
n n n n n n 2
3)!
3()23()!3()!3()!3(?=?=，得证。
（2）设有2n 个不同的球，将他们放入n 个相同的盒子，每盒n 个球，这个
方案数应该是整数。由（1）可知，将2n 个不同的球放入n 个不同盒子的方案数为
n
n n )
!()!
2(，若为相同的n 个盒子，则应把n 个盒子的排列数去掉，即n ！，故2n 个
不同的球放入n 个相同的盒子，每盒n 个球的方案数为()1
2!)!
(+n n n ，证毕。
1.45 （1）在2n 个球中，有n 个相同，求从这2n 个球中选取n 个的方案数。
（2） 在3n+1个球中，有n 个相同，求从这3n+1个球中选取n 个的方案数。 解：
（1）相当于从n 个不同的小球中分别取出m 个小球（n m ≤≤0），再从n 个不同小球中取出n-m 个小球。则共有方案数：n n n C n C n C 2),()1,()0,(=+???++
（2）相当于从2n+1个不同的小球中分别取出个小球（n m ≤≤0），再从n
个不同小球中取出n-m 个小球。则共有方案数：∑=+n
m m n C 0
),12(
1.46（1）证明：利用归纳法，当n=1时，0出现偶数次的实例是{1,2}，其中0
出现0次，而当n ＝1时，3n ＋1/2=2，是正确的。
假设当n ＝k 时是正确的，即0出现 3k ＋1/2 次，计算0出现
奇数次的方案，因为总方案数为3k ，
∴0出现奇数次的方案为3k －3k ＋1/2＝3k －1/2.
当n ＝k ＋1时，0出现偶数次的方案数是前k 为出现偶数次，
第k ＋1位是1或2，或是前k 位出现奇数个0，最后一位是0.
总方案数为2×（3k ＋1）/2＋3k －1/2＝13k +＋1/2,正是所要证明的形式，所以0出现偶数次的字符串有3n ＋1/2个。
（2）证明：等式左边第一项表示n 位中有0个0，用()0n
表示，那么这n 位
只能取1或2，有2n 种可能，所以方案为()0n
×2n ，最后一项为
当n 中有最大偶数个0出现时的方案数，所以左边整体表示为n 位字符串中0出现偶数次的方案数，右边也是0出现偶数次的方案数，左边＝右边，即证。
1.47 5台教学机器m 个学生使用，使用第1台和第2台的人数相等，有多少种分配方案？
解：
当使用第1台机器的学生为n 个时，使用第2台机器的学生也为n,从m 个学生中选出2n 个使用这两台机器，剩余的学生可以任意使用剩下的机器的组合数为C(m,2n)C(2n,n)3(m-2n)。
所以总的方案数为∑=-2
/0)2(3),2()2,(m x n m n n C n m C .
1.48 在由n 个0及n 个1构成的字符串中，任意前k 个字符中，0的个数不少于1的个数的字符串有多少？ 解：转化为格路问题,即从(0,0)到(n,n),只能从对角线上方走,可以碰到对角线,故方案数为C(2n,n)-C(2n,n-1).
1.49 在1到n 的自然数中选取不同且互不相邻的k 个数，有多少种方案？ 解：根据不相邻组合的公式，共有C(n-k+1)种方案k 。
1.50
(a)在5个0，4个1组成的字符串中，出现01或10的总次数为4的，有多少个? (b)在m 个0，n 个1组成的字符串中,出现01或10的总次数为k 的，有多少个？ 解：(a)先将5个0排成一列：00000，1若插在两个0中间，“010”，则出现2个“01”或“10”;若插在两端，则出现1个“01”或“10”;要使出现“01”,“10”总次数为4，有两种办法：
(1)把两个1插入0得空当内，剩下的1插入1的前面。
(2)把1个1插入0得空当内，再取两个1分别插入两端，剩下的1插入1的前面。
故总方案数为C(4,2)·3+C(4,1)·3=30 (b)m 个0产生m-1个空当，
若k 为奇数,则必有且只有1个“1”插入头或尾,总方案数为
)2
1
,1()21,1(2+----k n n C k m C
若k 为偶数,总方案数为)2
2
,1()22,1()2,1()2,1(+----+---k n n C k m C k n n C k m C
第一问，出现4个01或10，说明5个0被分成了3段，四个1被分成了两段，然后夹在一起形如001101100；或者5个0被分成了2段，四个1被分成了3段，然后夹在一起形如100100011。于是题目的考虑就变成了5个0如何拆分，4个1如何拆分。 答案是：
C(4,2)*C(3,1)+C(4,1)*C(3,2) 1.51 从()20,...2,1=N 中选出3个数，使得没有两个数相邻，问有多少中方案？
解：???? ??+-r r n 1=???? ?
?+-31320=????
??318种
1.52 从S={1,2,…,n}中选k 个数,使之没有两数相邻,求不同方案数.
解: ??
? ??+-k 1k n
1.53 把n 个无区别的球放进有标志1，2，3，…………n 的盒子里，每个盒子里可以放多余一个球，求有多少中方案。 答案：
相当于在n 个不同的元素中取r 个作允许重复的的组合，其组合数为c(n-k+1,r)
1．54 m 个1，n 个0进行排列，求1不相邻的排列数。设n>m
解： n 个0进行排列，留出n+1个空档，任选m 个空档放1，共有C(n+1,m)种方案。
第
1.55 偶数位的对称，即从左向右的读法与从右向左的读法相同，如3223。试证这样的数可被11整除。 证明：
对称数ABBA 可以写成 A*103+B*102+B*10+A*100，且11MOD10=-1MOD11,用-1代替10
恰好方次是奇偶对应的。使原式相加等于0。
1—56 n 个男人与n 个女人沿一圆桌坐下,问两个女人之间坐一个男人的方案数,又m 个女人n 个男人,且m解: ① n 个女人先沿圆桌坐下,这时正好有n 个空. 即 (P(n,n)/n)n!=(n!n!)/n
② n 个男人沿圆桌坐下,方案数为本P(n,n)/n=n!/n
女人往男人中的n 个空插入为p (n,m).所以方案数为(p (n,,m)n!)/n
1.57：n 个人分别沿着两张圆桌坐下，一张r 个人，另一张n-r 个人，试问有多少种不同的方案？ 解：按照本题的要求，先从n 中选r 个人进行圆排列的方案是C （n ，r ）×(r-1)!。剩下（n-r ）个人再进行圆排列（n-r-1）！。根据乘法原理一共有C （n ，r ）×（r-1）!×（n-r-1）！。
1.58 一圆周上n 个点标以1，2，…，n.每个点与其他n-1个点连以直线，试问这些直线交于圆内多少点？ 解：
图a
图b
如题意可知，每个点i 和其他n-1个点相连，可以引出n-1条直线，那么我们首先求圆内的交点在与点1相连的直线上的个数。 如图a ，对于任意一条直线（1，i ），这条直线上与其他直线的交点数，必然等于（1，i ）的左边点与（1，i ）的右边点相连的边的总条数，总共有
211i n i --????? ? ????? 条边，也就有这么多个交点
所以对于点1引出的所有边，边上的交点数总和为
1
3211n i i n i -=--????? ? ?????
∑ 与点1相连的直线上的交点个数都求出来了，就可以先把点1去掉，如图b ，
计算剩下的n-1个点的直线的交点个数。 所以n 个点一共是：
1
43211n m m i i m i -==--????? ? ?????
∑∑
那么这些直线交于圆内1
43211n m m i i m i -==--????
? ? ?????
∑∑个交点
1.59 n 和k 都是正整数，设平面有n 个点，其中每一点都存在k 个点与之距离
相等。试证k 满足
证明：当k=1时成立，101001000100001…1代表点，0代表单位距离
当k=i 成立，1..101..1001..10001..100001..100000.. ,1..1表示有i 个1
当k=i+1时，1…101…1001…10001…100001…100000…,同样也成立1…1表示有i+1个1
组合数学课后答案
作业习题答案 习题二 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。 证明：
组合数学作业答案
第二章作业答案 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。
完整版排列组合练习题及答案
排列组合》 一、排列与组合 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个相同种类的水果。
李凡长版-组合数学课后习题答案-习题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
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
组合数学 课后答案
习题二 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的倍数。
李凡长版组合数学课后习题标准答案习题
第二章 容斥原理与鸽巢原理 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.
组合数学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
李凡长版 组合数学课后习题答案习题4
第四章 生成函数 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 的系数，便得
排列组合练习题及.答案
《排列组合》 一、排列与组合 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门，组成一个综合高考科目组，若要求这组科目中
李凡长版 组合数学课后习题答案 习题5
第五章 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个数存在一定的置换关系
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.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 除尽。
