1.14 6个引擎分列两排，要求引擎的点火顺序两排交错开来，试求从一个特定引擎开始有多少方案？
解： 设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
1.16 n 个完全一样的球放在r 个有标志的盒子里面()r n ≥ ，无一空盒，问有多少种方案？
解：r 个盒子无一空盒，说明先要从n 个球中取出r 个先放每个盒中一个； 余下n-r 个无标志的球，放入r 个有标志的盒子中，根据定理可以得出 结果是()()r n n C r n r n r C --=-+-+,1,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
）
，
11
n n
n
r r r
p p r
p
+-=
+ =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）12285001031524210=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）343243350C C ++?= （3）312323122240C 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 =+≥=∈<<，试证：
2
111323n
k n n T k =++????
==+ ? ?????
∑
解题：（1）：因为x,y 的最小值为1，所以(2,3,4,........)z n ∈ 当z=2时：x=y=1,
当z=3时：x,y 各有两种选择11
22C C
………
当z=n+1时：x,y 各有两种选择11n 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 ，有3
1
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中的任选两点构成的直线，有45
2
10=C 条；（3）由P 1~P 5中的一个点及P 6~P 15中的一个点构成的直线，有
5011015=C C 条。因此，符合要求的直线共有1+45+50=96条。
（b ）根据题意，符合条件的三角形有三种可能：（1）P 1~P 5中任选两个点
及P 6~P 15中任选一个点构成三角形：有10011025=C C 个；（2）P 1~P 5中任选一个点及P 6~P 15中任选两个点构成三角形：有22521015=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)
32
21
1a a a p p p ，其中
.......,21p p 是质数，....2,1a a 是正整数。
则n 的因子数有(a1+1)(a2+1)(a3+1)............个。 得 2n =.. (3)
232
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)
,()!(!!
)!(!!
!)!(!)!()!(!!!!)!()!()!
()!(!!)
,(),(0
0000n 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 ！，故2
n 个不同的球放入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．54m个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。 证明：
排列组合知识点总结+典型例题及答案解析
排列组合知识点总结+典型例题及答案解析 一．基本原理 1．加法原理：做一件事有n 类办法，则完成这件事的方法数等于各类方法数相加。 2．乘法原理：做一件事分n 步完成，则完成这件事的方法数等于各步方法数相乘。 注：做一件事时，元素或位置允许重复使用，求方法数时常用基本原理求解。 二．排列：从n 个不同元素中，任取m （m ≤n ）个元素，按照一定的顺序排成一 .m n m n A 有排列的个数记为个元素的一个排列，所个不同元素中取出列，叫做从 1.公式：1.()()()()! ! 121m n n m n n n n A m n -=+---=…… 2. 规定：0!1= (1)!(1)!,(1)!(1)!n n n n n n =?-+?=+ (2) ![(1)1]!(1)!!(1)!!n n n n n n n n n ?=+-?=+?-=+-； (3) 111111 (1)!(1)!(1)!(1)!!(1)! n n n n n n n n n +-+==-=- +++++ 三．组合：从n 个不同元素中任取m （m ≤n ）个元素并组成一组，叫做从n 个不同的m 元素中任取 m 个元素的组合数，记作 Cn 。 1. 公式： ()()()C A A n n n m m n m n m n m n m m m ==--+= -11……!! !! 10 =n C 规定： 组合数性质： .2 n n n n n m n m n m n m n n m n C C C C C C C C 21011 =+++=+=+--…… ，， ①；②；③；④ 111 12111212211 r r r r r r r r r r r r r r r r r r n n r r r n n r r n n n C C C C C C C C C C C C C C C +++++-+++-++-++++ +=+++ +=++ +=注： 若1 2 m m 1212m =m m +m n n n C C ==则或 四．处理排列组合应用题 1.①明确要完成的是一件什么事（审题） ②有序还是无序 ③分步还是分类。
组合数学作业答案
第二章作业答案 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、元素：我们把问题中被取的对象叫做元素 2、排列：从n 个不同元素中，任取m （m n ≤）个元素（这里的被取元素各不相同）按照一定的顺．．．． 序．排成一列，叫做从n 个不同元素中取出m 个元素的一个排列．．．． 。 说明：（1）排列的定义包括两个方面：①取出元素，②按一定的顺序排列（与位置有关） （2）两个排列相同的条件：①元素完全相同，②元素的排列顺序也相同 合作探究二 排列数的定义及公式 3、排列数：从n 个不同元素中，任取m （m n ≤）个元素的所有排列的个数叫做从n 个元素中取出 m 元素的排列数，用符号m n A 表示 议一议：“排列”和“排列数”有什么区别和联系？ 4、排列数公式推导 探究：从n 个不同元素中取出2个元素的排列数2n A 是多少？3n A 呢？m A n 呢？ )1()2)(1(+-?--=m n n n n A m n （,,m n N m n *∈≤） 说明：公式特征：（1）第一个因数是n ，后面每一个因数比它前面一个少1，最后一个 因数是1n m -+，共有m 个因数； （2）,,m n N m n *∈≤ 即学即练: 1.计算 (1）410A ； (2）25A ；(3)3355A A ÷ 2.已知101095m A =???，那么m = 3．,k N +∈且40,k ≤则(50)(51)(52)(79)k k k k ----用排列数符号表示为( ) A ．5079k k A -- B ．2979k A - C ．3079k A - D ．3050k A - 例1． 计算从c b a ,,这三个元素中，取出3个元素的排列数，并写出所有的排列。 5 、全排列：n 个不同元素全部取出的一个排列，叫做n 个不同元素的全排列。 此时在排列数公式中， m = n 全排列数：(1)(2)21!n n A n n n n =--?=（叫做n 的阶乘）. 即学即练:口答（用阶乘表示）：（1）334A （2）44A （3）)!1(-?n n 排列数公式的另一种形式： )! (!m n n A m n -= 另外，我们规定 0! =1 .
完整版排列组合练习题及答案
排列组合》 一、排列与组合 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的五个杯盖，将五个杯盖盖在
组合数学习题4(共5章)
第四章 生成函数 1. 求下列数列的生成函数： （1）{0,1,16,81,…,n 4,…} 解：G{k 4 }= 235 (11111) 1x x x x x +++-（） （2）343,,,333n +?????????? ? ? ????? ???? 解：3n G n +?????? ?????=4 1(1)x - （3）{1,0,2,0,3,0,4,0,……} 解：A(x)=1+2x 2+3x 4+4x 6+…=2 1 1x -. （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 -=0 k 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 的系数，便得
组合数学课后标准答案
组合数学课后标准答案
————————————————————————————————作者：————————————————————————————————日期：
习题二证明：在一个至少有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.进一步理解和应用分步计数原理和分类计数原理。 2.掌握解决排列组合问题的常用策略;能运用解题策略解决简单的综合应用题。提高学生解决问题分析问题的能力 3.学会应用数学思想和方法解决排列组合问题. 复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1m 种不同的方法，在第2类办法中有2m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有： 12n N m m m =+++ 种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n 个步骤，做第1步有1m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有： 12n N m m m =??? 种不同的方法． 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。 3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素. 4.解决排列组合综合性问题，往往类与步交叉，因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,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.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排, 先排末位共有1 3C 然后排首位共有1 4C 最后排其它位置共有 34A 由分步计数原理得1 1 3 434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间，也不种在两端的花盆里，问有多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素，同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元 素内部进行自排。由分步计数原理可得共有 522522480A A A =种不同的排法 练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略 例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈节目不能连续出场,则节目的出场顺序有多少种？ 解:分两步进行第一步排2个相声和3个独唱共有55A 种， 第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种 46 A 不同的方法,由分步计数原理,节目的不同顺序共有54 56A A 种 练习题：某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个新节目插入原节目单中，且两个新节目不相邻，那么不同插法的种数为 30 四.定序问题倍缩空位插入策略 例4. 7人排队,其中甲乙丙3人顺序一定共有多少不同的排法 解:(倍缩法)对于某几个元素顺序一定的排列问题,可先把这几个元素与其他元素一起进行排列,然后用总排列数除以这几个元素 之间的全排列数,则共有不同排法种数是： 73 73/A A (空位法)设想有7把椅子让除甲乙丙以外的四人就坐共有 47 A 种方法，其余的三个位置甲乙丙共有 1种坐法，则共有4 7A 种方法。 思考:可以先让甲乙丙就坐吗? （插入法)先排甲乙丙三个人,共有1种排法,再把其余4四人依次插入共有 方法 练习题:10人身高各不相等,排成前后排，每排5人,要求从左至右身高逐渐增加，共有多少排法？ 5 10C 五.重排问题求幂策略 例5.把6名实习生分配到7个车间实习,共有多少种不同的分法 解:完成此事共分六步:把第一名实习生分配到车间有 7 种分法.把第二名实习生分配到车间也有7种分依此类推,由分步计数原 理共有6 7种不同的排法 练习题： 1． 某班新年联欢会原定的5个节目已排成节目单，开演前又增加了两个新节目.如果将这两个节目插入原节目单中，那么不同插 法的种数为 42 4 4 3 允许重复的排列问题的特点是以元素为研究对象，元素不受位置的约束，可以逐一安排各个元素的位置，一般地n 不同的元素没有限制地安排在m 个位置上的排列数为n m 种
第一章 什么是组合数学
第一章什么是组合数学 组合学问题在生活中随处可见。例如，计算下列赛制下总的比赛次数：n个球队参赛，每队只和其他队比赛一次。创建幻方。在纸上画一个网络。用铅笔沿着网络的线路走，在笔不离开纸面且不重复线路的条件下，笔画出网络因。在玩扑克牌游戏中，计算满堂红牌的手数，以确定出现一手满堂红牌的几率。所有这些都是组合学问题。正如人们想到的．组合数学的历史渊源扎根于数学娱乐和游戏之中。过去研究过的许多问题，不论出于消遣还是出于对其美学的考虑，如今在纯科学和应用科学中都具有高度的重要性。今天，组合数学是数学的一门重要分支，而且它的影响还在继续扩大。组合数学自60年代以来急速发展的部分原因就在于计算机在我们的社会中所发挥的重要影响，而且这种影响还在继续发挥。由于运算速度的持续增加，计算机已经能够解决大型问题，这在以前是不可能做到的。然而计算机不能独立运行，它需要编程来控制。这些程序的基础往往是求解问题的组合学算法，对于这些算法，运行时间效率和存储需求分析需要更多的组合学思想。 组合数学近期发展的另一个原因是它对于那些过去很少与数学正式接触的学科的适用性。由此我们发现，组合数学的思想和技巧不仅正在用于数学应用的传统自然科学领城，而且也用于社会科学、生物科学、信息论等领域。此外，组合数学和组合学思想在许多数学分支中已经变得越来越重要。 组合数学涉及到将一个集合的物体排列成满足一些指定规则的格式。如下两类一般性问题反复出现： 排列的存在性如果有人想要排列—个集合的成员使得某些条件得以满 足，那么这样一种排列是否可行根本就不是显而易见的。这是最根本的问题。如果这种排列不总是可能的，那么我们要问，这种排列在什么样的(必要和充分)条件下能够实现？ 排列的计数和分类如果一个指定的排列是可能的，那么就会存在多种 方法去实现它。此时，人们就可以计数并将它们分类。 虽然对任何组合问题都可以考虑其存在性和计数问题，但在实践中常常发生的却是：如果存在性问题需要广泛地研究，那么计数问题则是非常困难的。然而，如果指定的排列问题的存在性容易解决，那么计算实现该排列的方法的数目则是可能的。在例外的情形下(即当它们的数目较小时)，这些排列可以被列出来，理解列出所有的排列与确定它们的数目之间的区别很重要。一旦这些排列被列出，它们就可通过与整数集{1，2，3，…，n}之间建立一一对应而被数出，其中n 是某个整数。我们计数的方法就是：1，2，3…，n。但是，我们主要关心的是事先不列出指定类型的排列而确定它们的数目的方法。当然，这些排列的总数也许很大以至于不可能把它们部列出来，概括地说，许多组合学问题常呈现下列形式：“能否排列…?” “存在一个……吗?” “能用多少方法—…?” “计算……的数目。”
高中数学排列组合题型总结与易错点提示25587汇编
排列组合 复习巩固 1.分类计数原理(加法原理) 完成一件事，有n 类办法，在第1类办法中有1 m 种不同的方法，在第2类办法中有2 m 种不同的方法，…，在第n 类办法中有n m 种不同的方法，那么完成这件事共有：12n N m m m =+++种不同的方法． 2.分步计数原理（乘法原理） 完成一件事，需要分成n 个步骤，做第1步有1 m 种不同的方法，做第2步有2m 种不同的方法，…，做第n 步有n m 种不同的方法，那么完成这件事共有：12n N m m m =???种不同的方法． 3.分类计数原理分步计数原理区别 分类计数原理方法相互独立，任何一种方法都可以独立地完成这件事。 分步计数原理各步相互依存，每步中的方法完成事件的一个阶段，不能完成整个事件． 一.特殊元素和特殊位置优先策略 例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,以免不合 要求的元素占了这两个位置. 先排末位共有13 C C 1 4 A 3 4 C 1 3 然后排首位共有14 C 最后排其它位置共有34 A 由分步计数原理得113434 288C C A = 练习题:7种不同的花种在排成一列的花盆里,若两种葵花
不种在中间，也不种在两端的花盆里，问有多少不同的种法？ 二.相邻元素捆绑策略 例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法. 解：可先将甲乙两元素捆绑成整体并看成一个复合元素， 同时丙丁也看成一个复合元素，再与其它元素进行排列，同时对相邻元素内部进行自排。由分步计数原理可得共有5225 2 2 480A A A 种不同的排法 乙 甲丁 丙 练习题:某人射击8枪，命中4枪，4枪命中恰好有3枪连在一起的情形的不同种数为 20 三.不相邻问题插空策略 例3.一个晚会的节目有4个舞蹈,2个相声,3个独唱,舞蹈 节目不能连续出场,则节目的出场顺序有多少种？ 解:分两步进行第一步排2个相声和3个独唱共有55 A 种，第二步将4舞蹈插入第一步排好的6个元素中间包含首尾两个空位共有种46 A 不同的方法,由分步计数原理,节目的不同顺序共有5456 A A 种 练习题：某班新年联欢会原定的5个节目已排成节目单， 要求某几个元素必须排在一起的问题,可以用捆绑法来解决问题.即将需要相邻的元素合并为一个元素,再与其它元素 一起作排列 ,同时要注意合并元素内部也必须排列. 元素相离问题可先把没有位置要求的元素进行排队再把不相邻元素插入中间和两端
高中数学排列组合中的典型例题与分析(三)
排列与组合的八大典型错误、 24种解题技巧 三大模型 一、知识点归纳 二、基本题型讲解 三、排列组合解题备忘录 1.分类讨论的思想 2.等价转化的思想 3.容斥原理与计数 4.模型构造思想 四、排列组合中的8大典型错误 1．没有理解两个基本原理出错 2.判断不出是排列还是组合出错 3.重复计算出错 4.遗漏计算出错 5.忽视题设条件出错 6.未考虑特殊情况出错 7．题意的理解偏差出错 8.解题策略的选择不当出错 五、排列组合24种解题技巧 1．排序问题 相邻问题捆绑法 相离问题插空排 定序问题缩倍法（插空法） 定位问题优先法 多排问题单排法 圆排问题单排法 可重复的排列求幂法 全错位排列问题公式法 2．分组分配问题 平均分堆问题去除重复法（平均分配问题） 相同物品分配的隔板法 全员分配问题分组法 有序分配问题逐分法 3．排列组合中的解题技巧 至多至少间接法 染色问题合并单元格法 交叉问题容斥原理法 构造递推数列法 六．排列组合中的基本模型 分组模型（分堆模型） 错排模型 染色问题
七．排列组合问题经典题型与通用方法 （一）排序问题 1.相邻问题捆绑法:题目中规定相邻的几个元素捆绑成一个组，当作一个大元素参与排列.例1.,,,,A B C D E 五人并排站成一排，如果,A B 必须相邻且B 在A 的右边，则不同的排法有（）A、60种 B、48种 C、36种 D、24种 解析：把,A B 视为一人，且B 固定在A 的右边，则本题相当于4人的全排列，4 424A =种，答案：D . 2.相离问题插空排:元素相离（即不相邻）问题，可先把无位置要求的几个元素全排列，再把规定的相离的几个元素插入上述几个元素的空位和两端. 例2.七人并排站成一行，如果甲乙两个必须不相邻，那么不同的排法种数是（）A、1440种B、3600种C、4820种D、4800种 解析：除甲乙外，其余5个排列数为5 5A 种，再用甲乙去插6个空位有2 6A 种，不同的排法种数是5 2 563600A A =种，选B . 3.定序问题缩倍法:在排列问题中限制某几个元素必须保持一定的顺序，可用缩小倍数的方法. 例3.A,B,C,D,E 五人并排站成一排，如果B 必须站在A 的右边（,A B 可以不相邻）那么不同的排法有（）A、24种B、60种C、90种D、120种 解析：B 在A 的右边与B 在A 的左边排法数相同，所以题设的排法只是5个元素全排列数的一半，即 5 51602 A =种，选 B .11.定位问题优先法：某个或几个元素要排在指定位置，可先排这个或几个元素；再排其它的元素。 例11.现有1名老师和4名获奖同学排成一排照相留念，若老师不站两端则有不同的排法有多少种？ 解析：老师在中间三个位置上选一个有1 3A 种，4名同学在其余4个位置上有4 4A 种方法；所以共有1 4 3472A A =种。 12.多排问题单排法:把元素排成几排的问题可归结为一排考虑，再分段处理。 例12.（1）6个不同的元素排成前后两排，每排3个元素，那么不同的排法种数是（）A、36种B、120种C、720种D、1440种 （2）8个不同的元素排成前后两排，每排4个元素，其中某2个元素要排在前排，某1个元素排在后排，有多少种不同排法？ 解析：（1）前后两排可看成一排的两段，因此本题可看成6个不同的元素排成一排，共 66720A =种，选C . （2）解析：看成一排，某2个元素在前半段四个位置中选排2个，有2 4A 种，某1个元素排在后半段的四个位置中选一个有1 4A 种，其余5个元素任排5个位置上有5 5A 种，故共有1 2 5 4455760A A A =种排法. 16.圆排问题单排法:把n 个不同元素放在圆周n 个无编号位置上的排列，顺序（例如按顺时钟）不同的排法才算不同的排列，而顺序相同（即旋转一下就可以重合）的排法认为是相同的，它与普通排列的区别在于只计顺序而无首位、末位之分，下列n 个普通排列：
组合数学作业答案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.
排列组合计算公式及经典例题汇总
排列组合公式/排列组合计算公式 排列A------和顺序有关 组合 C -------不牵涉到顺序的问题 排列分顺序,组合不分 例如把5本不同的书分给3个人,有几种分法. "排列" 把5本书分给3个人,有几种分法"组合" 1．排列及计算公式 从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号A(n,m)表示. A(n,m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)!(规定0!=1). 2．组合及计算公式 从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n 个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号
c(n,m) 表示. c(n,m)=A(n,m)/m!=n!/((n-m)!*m!)；c(n,m)=c(n,n-m); 3．其他排列与组合公式 从n个元素中取出r个元素的循环排列数＝A(n,r)/r=n!/r(n-r)!. n个元素被分成k类，每类的个数分别是n1,n2,...nk这n个元素的全排列数为 n!/(n1!*n2!*...*nk!). k类元素,每类的个数无限,从中取出m个元素的组合数为 c(m+k-1,m). 排列（Anm(n为下标，m为上标)） Anm=n×（n-1）....（n-m+1）；Anm=n！/（n-m）！（注：！是阶乘符号）；Ann（两个n分别为上标和下标）=n！；0！=1；An1（n为下标1为上标）=n
组合数学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 ,那么要求的是：
