银川沙坡头-初中生优秀作文选

排 列 组 合（二）
1.隔板原理在组合问题中的应用
问题：把n
个相同的小球放入
m
个不同的盒子中
(nm1)
，要求每 个盒子非空，问有多少种不同的放法？
这是一个常见的组合问题，可先将
n
个小 球排成一列，然后在每两个小球的
n1
个空档中插入
m1
块隔
m 1
板，这样就将
n
个小球分割成
m
组，每组小球依次放入
m
个盒子中，就得到
C
n1
种不同放法。我们不妨把
这种方法称为 “隔板原理”。
例1 某校高一年级共有12个班级，现要从中选出20名同学参加座谈 会，要求每班至少有一名同学参
加，共有多少不同的选法？

例2 把20个相同小球放入编号为1，2，3，4的四个盒子中，要求每个盒子中小球的数目不少于编号
数， 求不同的放法种数。

例3 把10分成3个正整数之和，有
10=1+1+8=1+2+7=3+2+5=„„
如果计入不同的顺序，可用多少种方式写成三个正整数之和。

例4 求不定方程x
1
+x
2
+x
3
+ x
4
=10满足x
1
≥2，x
2
≥4，x
3
≥－5，x
4
≥0的整数解（x
1
,x
2
,x
3
,x
4
）的组数。

例5 10名足球队员进行射门练习，如果总共进球数不超过100个，这些队员进球情况有多少种？

例6 晚会上共有10个演唱节目，4个舞蹈节目，要求每两个舞蹈节目之间至少有2个演 唱节目，有
多少种不同的节目顺序表？
例7. 求方程的正整数解的个数。
例8. 求方程的非负整数解的个数。
例9.将20个相同的小球放入编号分别为1，2，3 ，4的四个盒子中，要求每个盒子中的球数不少于它的编号数，求放
法总数。
2. 递推方法在排列组合中应用
例10、在一个正六边形的六个区域中的每一个区域染上红、黄、蓝、紫四种颜色之一，要求相邻的
两个区域染色不相同，则有多少种不同的染色方法？
F
E
A
D
B
C

例11、用1，2，3，4四种数字可以构造多少个含有偶数个1的
n
位数？

练习：
问题1.同室4人各写一张贺年卡，先集中起来，然后每人从中拿一张别人 送出的贺年卡，则4张贺年卡的不同分配方
式有多少种。
2.设有编号为1、2、3、4的4 个球和编号为1、2、3、4的4个盒，现将这4个球放入这4个盒内要求每个盒子
中各放一球且球的编 号与盒子的编号不同，有多少种投放方法。
3.用1或2这两个数字写10位数，其中任意相邻两个位置不全为1，则共有多少种情形。

4.4个人进行篮球训练，互相传接球，要求每个人接球后马上传给别人，开始由甲发球 ，并作第一次传球，第5次传球
后，球又回到甲手中的方法有多少种。

5.有排成 一行的六个方格，用三种不同的颜色去涂每个格子，每格涂一色，要求任何相邻的格不同色，且首尾两格也
不同色，有多少种涂法。
6.用4种不同颜色涂四边形的4个顶点，要求每点染一种颜色，相邻的顶 点染不同的颜色，则不同的染色方法有( )
（A）84种 （B）72种 （C）48种 （D）24种
7．：如图1，一个地区分为5个行政区域，现给地图着色，要求相邻 区域不得使用同一颜色，现有四种颜色可供选择，
则不同的着色方法共有
2
种。（以数字作答）(2003年全国高考试题)



5
1

3

4

3.染色问题与方法
图1
1 从接姆赛问题谈起
例12（1953，普特南）空间六点，任三点不共线，任四点不共面 ，成对地连接它们得十五条线段，用红色或蓝色染这
些线段（一条线段只染一种颜色）.求证:无论怎样 染,总存在同色三角形。

例13(第6届，IMO)有17位科学家,其中每一个人和其他 所有人的人通信,他们的通信中只讨论三个题目.求证:至少有
三个科学家相互之间讨论同一个题目。

结论：上述二例同属图论中的接姆赛问题.在图论中,将n点中每两点都用线段相连所得的图 形叫做n点完全图,记作k
n
.
这些点叫做“顶点”，这些线段叫做“边”。现在我们 分别用图论的语言来叙述例12、例13.
定理1 若在k
6
中，任染红、蓝两色，则必有一只同色三角形.
定理2 在k
17
中,任染红、蓝、黄三角，则必有一只同色三角形.
定理3一般地,二染色 完全图k
n
,其中的同色三角形的个数
f
n
满足:
1

3
m(m1)(m2),当n2m


2< br>f
n


m(m1)(4m1),当n=4m+1

3
2

m(m1)(4m1),当n=4m+3


3
2 解染色问题的基本方法
(1)代数计算方法（用两种不同的方法起计算图 中同色边、同色角（角的两边颜色相同）、异色角（角的两边颜色不同）、
同色三角形和不全同色的三角 形、„的个数，列出方程或不等式，通过求解便可得出答案）
例14.证明2色完全图
k
6
中必存在2个同色三角形。

（2）组合分析法（通过对染色图的组合结构进行分析讨论，从而达到解决问题之目的）
例1 5．已知n个人的任意3人中必有2个人互相认识，如果其中一定存在4个人互相都认识，求n的最小值。

（3）数学归纳法、构造法和其他方法
例16．（1986，全国）在坐标平面上，纵、横坐标都是整数的点为整点，试设计一种将所有 整点 染色的方法，将每个
整点都染上白色、红色或黑色中的一种颜色，使得：（1）每一种颜色都出现在无穷 多条平行于横轴的直线上；（2）
对任意白色点A，红色点B，黑色点C，总可以找到一个红色点D，使 得ABCD为一平行四边形。证明你设计的染色法符
合上述要求。

3 典型范例解析
例17 能否把1，1，2，2，3，3，„，1986，1986这些数排成一行，使 得两个1之间夹着一个数，两个2之间夹着两
个数，„，两个1986、之间夹着一千九百八十六个数？ 请证明你的结论。

例18． 已知△ABC内部有n个点，连同A、B、C共有n+3个点 ，以这些顶点把△ABC分割成若干个互不重叠的小三角
形，现把A、B、C分别染上红、黄、蓝三色， 其余的点任意染成红、黄、蓝三色之一。证明：三顶点都不同色的小三
角形的总数必是奇数。

例19． 如图,3行7列小方格每一个染上红色或蓝色.试证:存在一个矩形,它的四个角上的小方格颜色相同.

例20． 证明:用15块大小是4×1的矩形瓷砖和1块大小是2×2的矩形瓷砖，不能恰好铺盖8×8矩形的地面.

例21． 如图，是4个1×1的正方形组成的“L”形，用若干个这种“L”形硬纸片无重 迭拼成一个m×n（长为m个
单位，宽为n个单位）的矩形如图29-4（2）.试证明mn必是8的倍 数.

练习：
一、选择题
1、公共汽车上有 4位乘客，其中任何两人都不在同一车站下车，汽车沿途停靠6个站，那么这4位乘客不同的下车
方式共 有（ ）A、15种 B、24种 C、360种 D、480种

2、把10个相同的球放入三个不同的盒子中，使得每个盒子中的球数不 少于2，则不同的放法有
A、81种 B、15种 C、10种 D、4种
3、12辆警卫车护送三位高级领导人，这三位领导人分别坐在其中的三辆车中，要求在开行 后12辆车一字排开，车距
相同，车的颜色相同，每辆车内的警卫的工作能力是一样的，三位领导人所坐 的车不能相邻，且不能在首尾位置。则
共（ ）种安排出行的办法
A、A
9
9
×A
3
10
B、A
9
9
×A
3
8
C、A
3
8
D、C
3
8
4、在正方体的8个 顶点、12条棱的中点、6个面的中心及正方体的中心共27个点中，不共线的三点组的个数是
A、2898 B、2877 C、2876 D、2872
5、有两个同心圆，在外圆上有相异的6个点，内圆上有相异的3个点，由这9个点所确 定的直线最少可有
A、15条 B、21条 C、36条 D、3条
6、已知两个实数集A={a
1
，a
2
，„，a
60
}与B={b
1
，b
2
，„b
25
}，若从A 到B的映射f使得B中每个元素都有原象，且
f（a
1
）≥f（a
2
）≥„≥f（a
60
），则这样的映射共有
A、C
60
B、C
24
59
C、C
25
60
D、C
25
59

二、填空题
7、4410共有 个不同的正约数。
8、有7个人站成一排，其中A、B不能相邻，C、D必须挨在一起，且C要求在A 的右侧，则共有站队方法数是 。
9、两圆相交于A、B两点，在两圆周上另有六点 C、D、E、F、G、H，其中仅E、B、G共线，共他无三点共线，这
八点紧多可以确不同圆的个数是 。
10、一个圆周上有5个红点，7个白点，要求任两个红点不得相邻，那么共有 种排列方法。
11、平面上给定5点，这些点两两间的连线互不平行，又不垂直，也不重合，现从任一 点向其余四点两两之间的连线
作垂线，则所有这些垂线间的交点数最多是 。
12、10人有相应的10个指纹档案，每个指纹档案上都记录有相应人的指纹痕迹，并有检测指示灯和检测时 的手指按钮，
10人某人把手指按在键钮上，若是他的档案，则指示灯出现绿色，否则出现红色，现在这 10人把手指按在10个指纹
档案的键钮上去检测，规定一个人只能在一个档案上去检测，并且两个人不 能在同一档案上去检测，这时指示灯全部
出现红色，这样的情况共有 种。
三、解答题
13、中、日围棋队各出7名队员，按事先安排好的次序出场进行围棋擂台赛，双 方先由1号队员比赛，负者被淘汰，
胜者再与负方的2号队员比赛，„„，直到有一方队员全部被淘汰为 止，另一方获胜，形成一种比赛过程，现在中方
只动用了5名队员，就击败了日方的所有队员，问这样的 比赛过程有多少种？


14、从1到n（n≥3，且n为整数）之间任取3个不同 的整数，使得这3个数的和正好被3整数，如果这样的取法有
53922种，试确定n的取值。

15、集合A中有n个元素，其中有m个是特殊元素（m≤n），已知集合A的五元素子集共 有68个，且每个子集中都
含有至少一个特殊元素，此外，集合A的作地意一个三元素子集都恰好被一个 五元素子集所包含。
（1）求n的取值。
（2）请回答：所有五元素子集中是否有至少含有4个特殊元素的集合？

参考答案
一、选择题
1、可把问转化为：4个不同的元素，放到6个位置中， A
4
6
=360种方法，选C。
2、问题相当于：把4个相同的球放入一个 不同的盒中，有C
2
6
=15种放法，故选B。
3、此题即：3个人坐10 个位置，一人只能坐一个，且两两不得相邻，有A
3
8
种坐法，选C。
4、 用间接法，容易求得共线的三点组共有49个，而所有拓点组共有C
3
27
，所以不共 线的三点且共有C
3
27
-49=2876
（个）故选C。
5、设 P
1
、P
2
、P
3
是内圆上三点，Q
1
、 Q
2
，„，Q
6
分别为三条直线P
1
P
2
、P
2
P
3
、P
3
P
1
与外圆的交点，此 时9个点所
确定的直线最少有C
2
9
- 3（C
2
4
- 1）=21（条），故选B。
6、此题相当于：用25个 从大到小的数从左至右的顺序不变，去插入到a
1
、a
2
、a
3、„、a
60
，这60个数的两数空
隙之间，要求最大数必在a
1
左侧，最小数不得在a
60
右侧，共有C
24
59
个映射，故选B 。
二、填空题
7、由4410=2×3
2
×5×72知：正约数中含2的 指数幂有2种，含3的指数幂有3种情况，含5的指数幂有2种情
况，含7的指数幂有3种情况，而2、 3、5、7均为质数，故根据分步原理共有2×3×2×3=36个不同的正约数。
8、把C、D捆绑起来看作一个元素，元素A只能安放在从左至右的前5个位置中，故对A的位置分类：
若A在左起第1位，则有A
1
4
×A
4
4
×A2
2
=192（种）；
若A在左起第2位，则有A
1
3
×A
1
4
×A
3
3
×A
2
2
= 144（种）；
若A在左起第3位，则有A
1
3
×A
3
3
+A
1
2
×C
1
2
×A
2
2×A
3
3
=66（种）；
若A在左起第4位，则有A
1
2
×C
1
2
×A
2
2
×A
3
3
+A
2
2
×A
3
3
=60（种）；
若A 在左起第5位，则有A
2
2
×A
1
3
×A
3
3
=36（种）；
所以，共有站队方法数498种。
9、过8个点可作C
3
8
个圆，需减去两类：①E、B、G共线，减去1个；②A、B、C、D、E五点共圆及A 、B、F、G、
H五点共圆，减去2（C
3
5
—1），所以最多可以确定不同 圆的个数是37个。
10、用插空法，共有C
5
7
种排列方法。
11、用排除法，设A
1
、A
2
、„、A
5
为平面上给定的 5个点，A
2
、A
3
、A
4
、A
5
之间两 两连线有C
2
4
=6条，从A1出发可
引6条垂线，依此5个点共可引30条 垂线，它们之间最多有C
2
30=435个交点，但应排除以下三种情况：①从A
1< br>、A
2
、
A
3
作A
4
A
5
的三条垂线互相平行，无交点，这样的情形共有C
2
5
C
2
3
=30个；②从Ai（i=1，2，3，4，5）出发的6条垂线
都交于点Ai，这样的点共有5C< br>2
6
=75个，只能留下5个，剩余的应减去；③Ai（i-1，2，3，4，5）中每 三点构成一个
三角形，三角形的高共点，应减去C
3
5
（C
2
3
—1）=20个。
因此，满足题意的交点最多有C
2
30
—30—70—20=315个。 < br>12、此题相当于：10个编号为1，2，3，„，10的球放入十个编号为1，2，3，„，10的盒中 ，要求每个盒中只
盛一球，且号码均不相同，求放法总数。
设这种情况的n个号码时，方法数 为an，第一步是安排第1号球，共有n—1种方法，此时，不妨设1号球安排
在了第i（i≠1）号位 置，再安排第i号球的位置，有两种情况：①第i号球在1号位置，此时剩余的n—2个球要放
在n—2 个盒中的要求依然是号码均不相同，故有a
n
—2种方法；②第i号球不安排在1号位置，此时 如同n—1个球
放入n—1个盒中且号码均不相同，故有方法数为an—1。
所以，a
n
=(n-1)(a
n-2
+a
n-1
)
当n=2时,a
2
=1;当n=3时,a
3
=2.所以a
4
=3(a
2
+a
3
)=9,a
5
=4(a
3
+a
4
)=44,a
6
=5(a
4+a
5
)=265,a
7
=6(a
5
+a
6< br>)=1854,a
8
=7(a
6
+a
7
)=1483 3,a
9
=8(a
7
+a
8
)=133496,a
10
=9(a
8
+a
9
)=1
334961.
所以，这样的情况共有1334961种。
三、解答题
13、设中方的7名队员分 虽为a
1
，a
2
，„，a
7
，日方的7名队员分别是b1
，b
2
，„，b
7
，由于中方只动用了5名队
员，故 可以认为a
6
，a
7
实质上是不参与比赛的，现把中方的5名队员和日方的7 名队员排成一列，显然各自的顺序已定，
只需确定位置即可。

现规定，排在日 方队员b
i
（i=1，2，„，7）右侧的（紧挨着）中方队员是击败b
i
的 队员，据题意，a
5
须在b
7
的右
侧（紧挨着）。其他4名队员a< br>1
，a
2
，a
3
，a
4
可在b
7< br>右侧10个位置中的任4个位置中，故有C
4
10
种情况。
所以，这样的比赛过程有C
4
10
种。
14、用模3对n分类：
（1）当n=3m（m≥1，且m为整数）时，我们可以把从1到n的这n个数分成三部分：①A
1
={1，4，„，3k+1}，
共有m个元素；②A
2
={2，5，„， 3k+2}，共有m个元素；③A
3
={3，6，„，3k+3}，共有m个元素。
易知，A
3
中的任三个数之和能被3整除，有C
3
m
种取法；A1、 A2、A3中各取一个元素，其和亦能被3整除，有
C
1
m
·C
1< br>m
·C
1
m
=m
3
（种）取法；A
1
中任三个数之和也能被3整数，有C
3
m
种取法；A
2
中任三个数 之和也能被3整除，有
C
3
m
种取法，除上面几种情况，再无其他情况使取的 三数之和被3整除。
所以，3C
3
m
+m
3
=53922，即
3m
3
– 3m
2
+ 2m – 107844=0 。
因为3|107844，所以3|m，又2m – 107844 是偶数，所以m必是偶数。
为此，不妨设m=6t（t≥1，且t为整数），则有
54t
3
– 9t
2
+t – 8987=0。
易知当t≥6时，此等式一定不成立，而当t=1 ，2，3，4，5时均不能使该等式成立，故当n=3m（m≥1，且m为
整数时），不存在这样的n。
（2）当n=3m+1（m≥1，且m为整数时），亦可把这n个数分成三部分：①A
1
={1，4，„}，共有m+1个元素；②
A
2
={2，5，„}，共有m个元素； ③A
3
={3，6，„}，共有m个元素，据题意则有。
2C
m
+c
m+1
+（m+1）m=53922。
即5m+m=3×53922。
m（5m+1）=3×53922。
因为（m，5m+1）=（m，1）=1，所以，m与5m+1互质。
而3×53922=2×3×11×19×43。
另一方面，若m≥43，则，故m＜43。
若m≤18，则5m+1必小于11×19×43，故m＞18。
所以，m=19或38，代入等式后均不成立。
综上，当n=3m+2（m≥1，且m为整数）时，也不存在这样的n。
（3）当n=3m+ 2（m≥1，且m为整数）时，则可得C
m
+2Cm+1+（m+1）2m=53922。
据（2）相同的思路，最后可求得m=66。
结合（1）、（2）、（3），n的取值是200。
15、（1）据题意，共有C
n
个三元素子集，因为每一个三元素子集都恰好被一个五元素子集所包含，所以每一个五
元素子集 中包含了C
5
个三元素子集，而这样的五元素子集共有68个，故有
C
n
=68×C
5
，解得n=17。
（2）假设法每个五 元素子集中至多含有3种特殊元素，我们把含有1种特殊元素，2种非特殊元素的三元素子集
设为A3
。
据题意，68个五元素子集中，有C
3
m
个含有3种特殊 元素，且每个子集中可有C
1
3
·C
2
2
（3个A
3
）。
另一方面，含有2种或1种特殊元素的五元素子集，应有68 – C
3
m
（个）
且这样的子集中都有C
2
C
3=C
1
C
4
（6个A
3
）
再者，子集A3
的个数是C
1
m
·C
2
17-m
，即mC< br>2
17-m
。
所以，mC
2
17-m
= 3C
3
m
+6（68 – C
3
m
），即
m
3
– 18m
2
+ 137m – 408=0。
因 为408的正因数1，3，8，17均非上述方程的解，据有理定理方程无正整数解，这说明假设错误，故结论是 肯
定的。
1212
33
3
3
33
2
2< br>22
2
3
332