化学实验室-元宝的折法

数学竞赛中的排列组合问题
江苏省梁丰高级中学 (215600) 张伟新
排列组合问题主要依据分类计数原理和分步计数原理，其本身应用的知识并不多，但
由于题目灵活多样，在各级各类考试中经常出现，在数学竞赛活动中尤其突出。其解题方法
也多种多样，归纳起来，我们一般可用下面的方法来解决。
一、列举法：
例1、从0、1、2、3、4、5、6、7、8、9这10个数中取出3个数，使其和为不小于10的
偶数，不同的取法有 。 （1998年全国高中数学联赛）
解：从10个数中取出3个数，使其和为偶数，则这三个数都为偶数或一个偶数二个
奇数。当 三个数都为偶数时，有
C
5
种取法；当有一个偶数二个奇数时，有
C
5
C
5
种取法。
题意要使其和为不小于10。我们把和为小于10的偶数列举出来，有如下9种不同取法：
（ 0，1，3），（0，1，5），（0，1，7），（0，3，5），（0，2，4），（0，2，6），（1， 2，3），
（1，2，5），（1，3，4）。因此，符合题设要求的取法有
C
5< br>+
C
5
C
5
－9=51种。
例2、设ABCDEF为正六边形，一只青蛙开始在顶点A处，它每次可随意地跳到相邻两顶
点之一。若在5次之内跳到D点，则停止跳动；若5次之内不能到达D点，则跳完5次也
停止跳动。那么这只青蛙从开始到停止，可能出现的不同跳法共 种。
（1997年全国高中数学联赛）
解：如图：青蛙不能经过跳1次、2次或4次到达D点。
F
E
故青蛙的跳法只有下列两种：
（1）青蛙跳3次到达D点，有ABCD，AFED两
种跳法。
A
（2）青蛙一共跳5次后停止，那么，前3次的跳法一定
不到达D，只能到达B或F，则共有AFEF，AFAF，ABAF，ABCB，
ABAB，AFAB这6种跳法。随后的两次跳法各有四种，比如由F
出发的有：FEF，FED，FAF，FAB共4种。因此这5次跳法共有
BC
6

4=24种不同跳法。

一共有2+24=26种不同跳法。
二、分类讨论：
在排列组合问题中 ，利用分类讨论来解决问题最为常见。如何分类、分几类成为解题的
关键。下面举例说明。
例 3、如图：在一个正六边形的六个区域栽种观赏植物，要求同一块中种同一种植物，相邻
的两块种不同的 植物，现有4种不同植物可供选择，则有 种栽种方案？
（2001年全国高中数学联赛）
解：由题意，要求同一块中种同一种植物，相邻的
A
两块种不同的植物。则可先考虑A、C、E．因此作如下分类：
B
F
（1）若A、C、E种同一种植物，此时共
有4

3

3

3=108种方法。
E
C
（2）若A、C、E种二种植物，此时共
D
有3
< br>4

3

3

2

2=432种方 法。


312
312
D

（3）若A、C 、E种三种植物，此时共有
A
4

2

2

2=192种方法。
3
所以共计有108+432+192=732种方法。
例4、从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一
种颜色，每两个具有公共棱的面染成不同的颜色。则不同的染色方案共有 种。
（注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、
下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相
同。） （1996年全国高中数学联赛）
解：本题情况较为复杂，我们对用了多少种颜色进行分类讨论。 < br>（1）若只用三种颜色，从六种不同颜色中选用3种颜色有
C
6
种选法。由于每 两个具有公共
棱的面染成不同的颜色，则正方体的相对面均为同色，由正方体的对称性知这样的染色
方案只有一种。因此共有
C
6
=20种不同的染色方案。
（2）若 只用四种颜色，从六种不同颜色中选用4种颜色有
C
6
种选法。则仅有一个相对面 < br>不同色，共有
C
4
种不同的涂法。因此共有
C
6
< br>C
4
=90种不同的染色方案。
（3）若只用五种颜色，从六种不同颜色中选 用5种颜色有
C
6
种选法。则仅有一个相对面同
色，不妨定为上、下底面， 其有
C
5
种涂法。再涂侧面，有3种涂法。因此共有
C
6

C
5

3=90
种不同的染色方案。
（4）用六种不同颜色来涂色。则六个面的颜色均不相同，假想颜色已经涂好，我们可以通
过 适当的翻转，使上底面均为同一种颜色（例如红色），再考虑下底面，则一定有5种不同
的颜色。对下底 面是同一种颜色的（例如蓝色），再用余下的四种颜色来涂侧面，有
种涂法。因此共有5
3！=30种不同的染色方案。

一共有20+90+90+30=230种不同的染色方案。
三、构造不定方程：
先介绍一个引理：
引理：求证：不定方程
x
1
x
2x
3
x
m
n
（
m2,n2,mn)
的正整数
解有
C
n1
组。
证明：本题可用“挡板法”求解，由于
x
1
1
，
x2
1
，---，
x
m
1
，把n分成n个1，
这n个1共有n―1个空挡。插入m―1块挡板，把n个1分成m个部分。则每一种情况对
应不定方程的一组解，所以原不定方程共有
C
n1
组解。




m1
m1
151
5
4
3
3
2
4
2
4!
3!
3

推论：不定方程
x
1
x
2
x
3
xm
n
（
m2,nN)
的非负整数解有
C
nm 1
组。
证明：把方程
x
1
x
2
x
3
x
m
n
化为
m1
(x
1
1)(x
2
1)(x
3
1)(x
m
 1)nm
，令
x
1
1y
1
，
x
2
1y
2
，
x
3
1y
3
，--- -，
x
m
1y
m
，即求
y
1
y2
y
m
nm

的正整数解的组数，由引理可得共有
C
nm1
组解。
在一些排列组合问题中，除了用其他的解法外，我们还可以用不定方程的正整数解的组
数来确定排列组合数的多少。
例5、已知两个实数集合
A

a< br>1
,a
2
,,a
100

与
B
b
1
,b
2
,,b
50

。 若从A到B
的映射f使得B中每个元素都有原像，且
f(a
1
)f(a< br>2
)f(a
100
)
，则这
样的映射共有 （ ）
（A）
C
100
（B）
C
99
（C）
C
100
（D）
C
99

（2002年全国高中数学联赛）
解：不妨设
b
1
b
2
b
50
，又因为B中每个元素都有原像，设
b
1
原像的集 合为
A
1
，
其元素个数为
x
1
；
b2
原像的集合为
A
2
，其元素个数为
x
2
；- -------
b
50
原像的集合为
A
50
，
其元素个数为
x
50
。 则
x
1
x
2< br>x
50
100
（

），则问题转化为求不定方程 （

）
的正整数解的组数，共有
C
99
组解，故选（D）。
例6、8个女孩和25个男孩围成一圈，任意两个女孩之间至少站两个男孩，那么，共有多
少种不同的排列方法。（只要把圈旋转一下就重合的排法认为是相同的）
（1990年全国高中数学联赛）
解：先排女孩，这是一个圆排列问题，易知共有
49
50484949
m1
8!
7!
种不同的排列。8个女孩的圆排列 < br>8
共留出8个空挡。再排男孩，设这8个空挡中的男孩数分别为
x
1
，
x
2
，
x
3
，------
x
8
，
x
1
x
2
x
8
25
， 由于任意两个女孩之间至少站两个男孩，即求不定方程
在
x
1
2
，
x
2
2
，
x
3
2
，-----，< br>x
8
2
下的正整数解的组数，所以不定方程可化
为
(x< br>1
1)(x
2
1)(x
8
1)17，令
x
1
1y
1
，

x
2
1y
2
，
x
3
1 y
3
，-----，
x
8
1y
8
， 即得y
1
y
2
y
8
17
，其 正整数解的组数是
C
16
。再对男孩全排列，共有
C
16

25!
种排列。所以共有
7
C
16

7!< br>
25!
种不同的排列方式。
77
例7、如果从数1、2、3、-- -14中，按由小到大的顺序取出a
1
、a
2
、a
3
使同时 满足a
2
―a
1

3
与a
3
―a
2

3，那么所有符合上述要求的不同取法有 种。
（1989年全国高中数学联赛）
解：由
a
1
1
，
a< br>2
a
1
3
，
a
3
a
2
3
，
14a
3
0
，令
a
1
x< br>1
，
a
2
a
1
x
2
，
a
3
a
2
x
3
，
14a
3
x
4
，则
x
1
x
2
x
3
x
4
14
，问题即求
不定方程在
x
1
1
，
x
2
3
，
x
3
3
，
x
4
0
下的整数解的组数，又方程转化为
x
1
(x
2
2)(x
3
2)(x
4
1)11
。 令
x
1
y
1
，
x
2
2y
2
，
x
3
2y
3
，
3
。所以符合条件的a
1
、a
2
、
x
4
1y
4
， 而
y
1
y
2
y
3
y
4
11
的正整数解的组数是
C10
a
3
的不同取法有
C
10
=120种。
四、利用递推关系：
在一些排列组合问题中，我们可以从简单问题入手，寻找规律，继而把问题一般化，
寻找更一般的关系式，即递推关系式，然后解决具体问题。
例8、有排成一行的n个方格，用 红、黄、蓝三色涂每个格子，每格涂一色，要求任何相邻
的格不同色，且首尾两格也不同色，问有多少种 涂法？（1991年江苏夏令营）
解：设共有
a
n
种不同涂法。易得
a
1
=3，
a
2
=6，
a
3
=6。且当
n4
时，将n个格子依
此编号后，则格1与格（
n1
）不相邻。
（1）若格（
n1< br>）涂色与格1不同，此时格n只有一色可涂，且前
n1
格满足首尾两格
不同色，故有
a
n1
种不同涂法。
（2）若格（
n1
）涂色与格1相同，此时格（
n2
）与格1涂色必然不同，否则格
（n1
）与格（
n2
）相同，于是前
n2
格有
a< br>n2
种不同涂法。因为格n与格1不同色，
有两种涂法，故有
2a
n 2
种不同涂法。
综上可得递推关系式：
a
n
=
a
n1
+
2a
n2
（
n4
），并可得
an
22(1)
（
n2
）。
例9、一只猴子爬一个8级的梯子，每次可爬一级或上跃二级，最多上跃三级。从地面
上到最上一级，一共可以有 种不同的爬跃方式。
（中等数学2001.3奥林匹克训练题）


nn
3