牛郎织女缩写-学校logo设计

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

第 1 页 共 7 页
F
A
B
E
D
C

（ 3）若A、C、E种三种植物，此时共有
A
4
3

2
2

2=192种方法。
所以共计有108+432+192=732种方法。
例4、从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一
种颜 色，每两个具有公共棱的面染成不同的颜色。则不同的染色方案共有 种。
（ 注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、
下、左、右、前 、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相
同。） （1996年全国高中数学联赛）
解：本题情况较为复杂，我们对用了多少种颜色进行分类讨论。 < br>（1）若只用三种颜色，从六种不同颜色中选用3种颜色有
C
6
3
种选 法。由于每两个具有公共
棱的面染成不同的颜色，则正方体的相对面均为同色，由正方体的对称性知这样的染色
方案只有一种。因此共有
C
6
3
=20种不同的染色方案。
（2）若只用四种颜色，从六种不同颜色中选用4种颜色有
C
6
4
种选法。 则仅有一个相对面
不同色，共有
C
4
2
种不同的涂法。因此共有< br>C
6
4

C
4
2
=90种不同的染色方案。
（3）若只用五种颜色，从六种不同颜色中选用5种颜色有
C
6
种选法。则仅 有一个相对面同
151
色，不妨定为上、下底面，其有
C
5
种涂法 。再涂侧面，有3种涂法。因此共有
C
6

C
5

3
5
=90种不同的染色方案。
（4）用六种不同颜色来涂色。则六个面的颜色均不相同，假想颜色已经涂好，我们可以通
过适当的翻转，使上底面均为同一种颜色（例如红色），再考虑下底面，则一定有5种不同
的 颜色。对下底面是同一种颜色的（例如蓝色），再用余下的四种颜色来涂侧面，有
种涂法。因此共有5< br>
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
组。
m1
4!
3
3!

证明：本题可用“挡板法”求解，由 于
x
1
1
，
x
2
1
，---，
x
m
1
，把n分成
n个1，这n个1共有n―1个空挡。插入m―1块挡板，把n个1分成m个部分。则每
一种情况对应不定方程的一组解，所以原不定方程共有
C
n1
组解。


第 2 页 共 7 页
m1

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

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

第 3 页 共 7 页

x
2
1y
2
，
x
3
 1y
3
，-----，
x
8
1y
8
， 即得
y
1
y
2
y
8
17
，其
777
正整数解的组数是
C
16
。再对男孩全排列，共有
C
16

25!
种排列。所以共有
C
16

7!

25!
种
不同的排列方式。
例7、如果从数1、2、3、 ---14中，按由小到大的顺序取出a
1
、a
2
、a
3
使 同时满足a
2
―a
1

3
与a
3
―a
2

3，那么所有符合上述要求的不同取法有 种。
（1989年全国高中数学联赛）
解：由
a
1

，
a
2
a
1
3
，
a
3
a2
3
，
14a
3
0
，令
a
1< br>x
1
，
a
2
a
1
x
2，
a
3
a
2
x
3
，
14a3
x
4
，则
x
1
x
2
x3
x
4
14
，问题即求
不定方程在
x
1
1
，
x
2
3
，
x
3
3，
x
4
0
下的整数解的组数，又方程转化为
x
1< br>(x
2
2)(x
3
2)(x
4
1)1 1
。令
x
1
y
1
，
x
2
2 y
2
，
x
3
2y
3
，
x
4
1y
4
， 而
y
1
y
2
y
3
y
4
11
的正整数解的组数是
C10
。所以符合条件的
3
a
1
、a
2
、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
）涂色与格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
种不同涂法。
nn
综上可得 递推关系式：
a
n
=
a
n1
+
2a
n 2
（
n4
），并可得
a
n
22(1)
（< br>n2
）。
3
例9、一只猴子爬一个8级的梯子，每次可爬一级或上跃二级，最多上跃三级。从地面
上到最上一级，一共可以有 种不同的爬跃方式。
（中等数学2001.3奥林匹克训练题）

第 4 页 共 7 页