排列组合问题的基本解法

第

页共7页

排列组合问题的基本解法

江苏省梁丰高级中学（215600）张伟新排列组合问题主要依据分类计数原理和分步计数原理，其本身应用的知识并不多，但由于题目灵活多样，在各级各类考试中经常出现，在数学竞赛活动中尤其突出。其解题方法也多种多样，归纳起来，我们一般可用下面的方法来解决。

一、列举法：

例1、从0、1、2、3、4、5、6、7、8、9这10个数中取出3个数，使其和为不小于10的偶数，不同的取法有。（1998年全国高中数学联赛）

解：从10个数中取出3个数，使其和为偶数，则这三个数都为偶数或一个偶数二个

奇数。当三个数都为偶数时，有C3种取法；当有一个偶数二个奇数时，有CiC2种取法。

555要使其和为不小于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）。因此，符合题设要求的取法有C3+ciC2—9=51种。

555

例2、设ABCDEF为正六边形，一只青蛙开始在顶点A处，它每次可随意地跳到相邻两顶点之一。若在5次之内跳到D点，则停止跳动；若5次之内不能到达D点，则跳完5次也停止跳动。那么这只青蛙从开始到停止，可能出现的不同跳法共种。

1997年全国高中数学联赛）

解：如图：青蛙不能经过跳1次、2次或4次到达D点。故青蛙的跳法只有下列两种：

（1）青蛙跳3次到达D点，有ABCD,AFED两

种跳法。

（2）青蛙一共跳5次后停止，那么，前3次的跳法一定不到达D，只能到达B或F，则共有AFEF，AFAF，ABAF，ABCB，ABAB，AFAB这6种跳法。随后的两次跳法各有四种，比如由F出发的有：FEF，FED，FAF，FAB共四种。因此这5次跳法共有6x4=24种不同跳法。一共有2+24=26种不同跳法。

、分类讨论：

在排列组合问题中，利用分类讨论来解决问题最为常见。如何分类、分几类成为解题的关键。下面举例说明。

例3、如图：在一个正六边形的六个区域栽种观赏植物，要求同一块中种同一种植物，相邻的两块种不同的植物，现有4种不同植物可供选择，则有种栽种方案？

（2001年全国高中数学联赛）解：由题意，要求同一块中种同一种植物，相邻的两块种不同的植物。则可先考虑A、C、E.因此作如下分类:

（1）若A、C、E种同一种植物，此时共

有4x3x3x3=108种方法。

（2）若A、C、E种二种植物，此时共

有3x4x3x3x2x2=432种方法。

（3）若A、C、E种三种植物，此时共有A3x2x2x2=192种方法。

4

所以共计有108+432+192=732种方法。

例4、从给定的六种不同颜色中选用若干种颜色，将一个正方体的六个面染色，每面恰染一种颜色，每两个具有公共棱的面染成不同的颜色。则不同的染色方案共有种。

（注：如果我们对两个相同的正方体染色后，可以通过适当的翻转，使得两个正方体的上、下、左、右、前、后六个对应面的染色都相同，那么，我们就说这两个正方体的染色方案相同。）（1996年全国高中数学联赛）

解：本题情况较为复杂，我们对用了多少种颜色进行分类讨论。

（1）若只用三种颜色，从六种不同颜色中选用3种颜色有C3种选法。由于每两个具有公共

6

棱的面染成不同的颜色，则正方体的相对面均为同色，由正方体的对称性知这样的染色方案只有一种。因此共有C3=20种不同的染色方案。

6

（2）若只用四种颜色，从六种不同颜色中选用4种颜色有C4种选法。则仅有一个相对面

6

不同色，共有C2种不同的涂法。因此共有C4xC2=90种不同的染色方案。

464

（3）若只用五种颜色，从六种不同颜色中选用5种颜色有C5种选法。则仅有一个相对面同

6

色，不妨定为上、下底面，其有C1种涂法。再涂侧面，有3种涂法。因此共有C5xCix3

565

=90种不同的染色方案。

（4）用六种不同颜色来涂色。则六个面的颜色均不相同，假想颜色已经涂好，我们可以通过适当的翻转，使上底面均为同一种颜色（例如红色），再考虑下底面，则一定有5种不同

4!

的颜色。对下底面是同一种颜色的（例如蓝色），再用余下的四种颜色来涂侧面，有兰=3!

3种涂法。因此共有5x3！=30种不同的染色方案。

一共有20+90+90+30=230种不同的染色方案。

三、构造不定方程：

先介绍一个引理：

引理：求证：不定方程x+x+xFx=n（m>2,n>2,m<n）的正整数解有

123m

Cm-1组。

n-1

证明：本题可用“挡板法”求解，由于x>1，x>1，，x>1，把n分成

12m

n个1,这n个1共有n—1个空挡。插入m—1块"挡板"，把n个1分成m个部分。则每

一种情况对应不定方程的一组解，所以原不定方程共有Cm-1组解。

n-1

推论：不定方程x+x+xbx=n(m>2,neN)的非负整数解有Cm-1组。

123mn+m-1

证明：把方程xbxbxbx=n化为

TOC\o"1-5"\h\z

123m

(xb1)b(xb1)b(xb1)bb(xb1)=nbm，令xb1=y，

123m11

x+1=y,x+1=y,,x+1=y，即求y+ybby=n+m

2233mm12m

的正整数解的组数，由引理可得共有Cm-1组解。

nbm-1

解：不妨设b<b<<b，又因为B中每个元素都有原像，设b原像的集合为A，

在一些排列组合问题中，除了用其他的解法外，我们还可以用不定方程的正整数解的组数来确定排列组合数的多少。

例5、已知两个实数集合A=ia,a,,a｝与B=(b,b,,b｝。若从A到B

12

1001

250

）<f（a）<-

--<f(a)，则这样的映射

的映射f使得B中每个元素都有原像，且f(a

12

100

共有

()

（A）C50

100

（B）C48

99

（C）C49

100

（D）C49

99

2002年全国高中数学联赛)

TOC\o"1-5"\h\z

125011

其元素个数为x；b原像的集合为A，其元素个数为x；b原像的集合为A，

12225050

其元素个数为x。则x+x++x=100(*)，则问题转化为求不定方程(*)

501250

的正整数解的组数，共有C49组解，故选(D)。

99

例6、8个女孩和25个男孩围成一圈，任意两个女孩之间至少站两个男孩，那么，共有多少种不同的排列方法。(只要把圈旋转一下就重合的排法认为是相同的)

(1990年全国高中数学联赛)8!

解：先排女孩，这是一个圆排列问题，易知共有8!=7!种不同的排列。8个女孩的圆排列共

8

留出8个空挡。再排男孩，设这8个空挡中的男孩数分别为x，x，x，x，

1238

xbxbbx=25，由于任意两个女孩之间至少站两个男孩，即求不定方程

128

在x>2，x>2，x>2，，x>2下的正整数解的组数，所以不定方程可化

1238

为（x-1）+（x-1）++（x-1）=17，令x-1=y，

12811

x-1=y,x-1=y,

2233

x-1=y,艮卩得y+yHby=17，其

88128

正整数解的组数是C7。再对男孩全排列，共有C7X25!种排列。所以共有C7X7!x25!种

161616不同的排列方式。

例7、如果从数1、2、3、14中，按由小到大的顺序取出a「a2、a3使同时满足a?—f>3与a3—a2>3,那么所有符合上述要求的不同取法有种。

（1989年全国高中数学联赛）

解：由a>

1

a一a>3，a一a>3，14一a>0，令a=x，

2132311

=x，14-a

23

则x+x+x+x—14，问题即求

不定方程在x>1，x>3，

12

x>3，

3

x>0下的整数解的组数，又方程转化为

4

xH(x-2)H(x-2)H(xH1)—11。

1234

令x—y，

11

x2-2—y2

x-2—y，

33

y4，

而y+y+y+y—11

1234

的正整数解的组数是C3。所以符合条件的

10

1234

af>a2、a3的不同取法有C3=120种。

12310

四、利用递推关系：在一些排列组合问题中，我们可以从简单问题入手，寻找规律，继而把问题一般化，寻找更一般的关系式，即递推关系式，然后解决具体问题。

例8、有排成一行的n个方格，用红、黄、蓝三色涂每个格子，每格涂一色，要求任何相邻

的格不同色，且首尾两格也不同色，问有多少种涂法？（1991年江苏省数学夏令营）

解：设共有a种不同涂法。易得a=3，a=6，a=6。且当n>4时，将n个格子依此编n123

号后，则格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种不同涂法。因为格n与格1不同色,n-2

有两种涂法，故有2a种不同涂法。

n-2

综上可得递推关系式：a=a+2a（n>4），并可得a—2n+2（-1）n（n>2）。

nn-1n-2n

例9、一只猴子爬一个8级的梯子，每次可爬一级或上跃二级，最多上跃三级。从地面

上到最上一级，一共可以有种不同的爬跃方式。

（中等数学2001.3奥林匹克训练题）

解：易得a=1，a=2，a=4，a=7。把问题一般化，设一共有n级梯子，每次可爬一级1234

或上跃二级，最多上跃三级。设共有a种不同的爬跃方式。若第一次爬了一级，则有a种

TOC\o"1-5"\h\z

nn-1

方式；若第一次上跃二级，则有a种方式；若第一次上跃三级，则有a种方式。因此

n-2n-3

a=a+a+a。易得a=81。即共有81种不同的爬跃方式。

nn-1n-2n-38

练习题：

1、用红、黄、蓝三色给正方体表面染色，每面只染一种颜色，每色各染两个面，如果

经过适当翻转可使两个染色的正方体各对应面的颜色相同者视为一种染色方法，那么，不同的染色方法种数为（）

（A）3种（B）5种（C）8种（D）12种

（2003江苏省数学夏令营）（提示：三种颜色都涂相对两面，有1种方法；一种颜色涂相对两面，有3种方法；三种颜色都不涂在相对面，有1种方法。共有5种方法。）

2、如果：（1）a，b，c，d都属于{1,2,3,4};（2）a工b，b工c，c工d，d工a；

（3）a是a，b，c，d中的最小值。那么，可以组成的不同的四位数abcd的个数是。

（2000年全国高中数学联赛）

（提示：（1）abcd由2个不同数字组成，则必有a=c，故有C2=6个。（2）abcd由3

4

个不同数字组成，则a唯一确定，当c=a，b,d有2种取法；当c丰a，c有2种取法，

b=d为余下的数，故有C3x（2+2）=16个。（3）abcd由4个不同数字组成，a=1，故有

4

3！=6个。因此一共有6+16+6=28个不同的四位数。）

3、在正方体的8个顶点、12条棱的中点、六个面的中心及正方体的中心共27个点中，

共线的三点组的个数是（）

（A）57（B）49（C）43（D）37

（1998年全国高中数学联赛）

8x7

（提示：（1）两端点皆为顶点的共线三点组共有8——=28个；（2）两端点皆为面的中心的

2

6x112x3

共线三点组共有叱=3个；两端点皆为各棱中点的共线三点组共有=18个；因此

22共有28+3+18=49个。）

4、将一个四棱锥的每个顶点染上一种颜色，并使同一条棱的两端点异色，如果只有5

种颜色可供使用，那么不同的染色方法的种数是。

（1995年全国高中数学联赛）

（提示：设有1、2、3、4、5五种颜色给四棱锥S-ABCD染色，由于S、A、B所染颜

色不同，则有5x4x3=60种染色方法。设S、A、B已染好，再分类讨论，C、D有7种染法。因此共有60x7=420种染法。）

5、已知直线ax+by+c=0中的a、b、c是取自集合｛—3,—2,—1,0,1,2,3）中的

3个不同的元素，并且该直线的倾斜角为锐角。那么，这样的直线的条数是。

（1999年全国高中数学联赛）

（提示：不妨设a>0，则b<0o（1）当c=0，a有3种取法，b有3种取法，排除2个重复，有9—2=7条0（2）c丰0，a有3种取法，b有3种取法，c有4种取法，有3x3x4=36条.因此有7+36=42条。）

6、在世界杯足球赛前，F国教练为了考察A，A，A这七名队员，准备让他们在

127

三场训练比赛（每场90分钟）中都上场。假设在比赛的任何时刻，这些队员中有且仅有一

人在场上，且A，A，A，A每人上场的总时间（以分钟为单位）均能被7整除，A，

12345

A，A每人上场的总时间（以分钟为单位）均能被13整除。如果每场换人次数不限，那

67么，按每名队员上场的总时间计算，共有多少种不同的情况。

（2002年全国高中数学联赛）

（提示：设第i名队员上场的时间为x分钟（i=1，2,3,，7），问题即求不定方

i

程x+x++x=270在条件7|x（1<i<4）且13lx（5<j<7）下的

1271j

正整数解的组数。由条件，设x+x+x+x=7m，x+x+x=13n，

1234567

m>4,n>3）。于是m、n即是不定方程7m+13n=270的一组正整数解。

270—13n

7

>4

易得3<n<18

（ngN）o进而得到方程的三组正整数解:

m=33

n=3

m=20m=7

n=10

n=17

设x=7y(1<i<4)，

ii

x=31y

jj

5<j<7)。

所以转化求方程组jy1

I

+y+y+y=33

234

y+y+y=3

567

y+y+y+y=201234

j

Iy+y+y=10

567

y+y+y+

j123

Iy+y+y

567

y=7

4的