当前位置:首页 >> >> 排列组合问题的基本解法

排列组合问题的基本解法


排列组合问题的基本解法
江苏省梁丰高级中学 (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 + 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 共四种。因此这 5 次跳法共有 B C 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 × 4 × 3 × 3 × 2 × 2=432 种方法。
第 1 页 共 7 页
3 1 2 3 1 2

D

(3)若 A、C、E 种三种植物,此时共有 A4 × 2 × 2 × 2=192 种方法。
3

所以共计有 108+432+192=732 种方法。 例 4、从给定的六种不同颜色中选用若干种颜色,将一个正方体的六个面染色,每面恰染一 种颜色,每两个具有公共棱的面染成不同的颜色。则不同的染色方案共有 种。 (注:如果我们对两个相同的正方体染色后,可以通过适当的翻转,使得两个正方体的上、 下、左、右、前、后六个对应面的染色都相同,那么,我们就说这两个正方体的染色方案相 同。 ) (1996 年全国高中数学联赛) 解:本题情况较为复杂,我们对用了多少种颜色进行分类讨论。 (1)若只用三种颜色,从六种不同颜色中选用 3 种颜色有 C 6 种选法。由于每两个具有公共 棱的面染成不同的颜色,则正方体的相对面均为同色,由正方体的对称性知这样的染色 方案只有一种。因此共有 C 6 =20 种不同的染色方案。 (2)若只用四种颜色,从六种不同颜色中选用 4 种颜色有 C 6 种选法。则仅有一个相对面
2 2 不同色,共有 C 4 种不同的涂法。因此共有 C 6 × C 4 =90 种不同的染色方案。 4 5 4 3 3

(3)若只用五种颜色,从六种不同颜色中选用 5 种颜色有 C 6 种选法。则仅有一个相对面同 色,不妨定为上、下底面,其有 C 5 种涂法。再涂侧面,有 3 种涂法。因此共有 C 6 × C 5 × 3
1 5 1

=90 种不同的染色方案。 (4)用六种不同颜色来涂色。则六个面的颜色均不相同,假想颜色已经涂好,我们可以通 过适当的翻转,使上底面均为同一种颜色(例如红色) ,再考虑下底面,则一定有 5 种不同 的颜色。对下底面是同一种颜色的(例如蓝色) ,再用余下的四种颜色来涂侧面,有 种涂法。因此共有 5 × 3!=30 种不同的染色方案。 ∴ 一共有 20+90+90+30=230 种不同的染色方案。 三、构造不定方程: 先介绍一个引理:

4! = 3! 3

引理:求证:不定方程 x1 + x 2 + x 3 + x m = n ( m ≥ 2 , n ≥ 2 , m ≤ n) 的正整数解有
m C n 1 组。 1

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

第 2 页 共 7 页

推论:不定方程 x1 + x 2 + x3 + x m = n ( m ≥ 2 , n ∈ N ) 的非负整数解有 C n + m 1 组。 证明:把方程 x1 + x 2 + x 3 + x m = n 化为

m 1

( x1 + 1) + ( x 2 + 1) + ( x3 + 1) + + ( x m + 1) = n + m ,令 x1 + 1 = y1 ,

x 2 + 1 = y 2 , x3 + 1 = y 3 ,----, x m + 1 = y m ,即求 y1 + y 2 + + y m = n + m
的正整数解的组数,由引理可得共有 C n + m 1 组解。 在一些排列组合问题中, 除了用其他的解法外, 我们还可以用不定方程的正整数解的组 数来确定排列组合数的多少。 例 5、已知两个实数集合 A = {a1 , a 2 , , a100 } 与 B = {b1 , b2 , , b50 }。若从 A 到 B 的映射 f 使得 B 中每个元素都有原像,且 f ( a1 ) ≤ f ( a 2 ) ≤ ≤ f ( a100 ) ,则这样的映射 共有 (A) C100
50
m 1

( (B) C 99
48



(C) C100

49

(D) C 99

49

(2002 年全国高中数学联赛) 解:不妨设 b1 < b2 < < b50 ,又因为 B 中每个元素都有原像,设 b1 原像的集合为 A1 , 其元素个数为 x1 ; b2 原像的集合为 A2 ,其元素个数为 x 2 ;-------- b50 原像的集合为 A50 , 其元素个数为 x50 。 则 x1 + x 2 + + x50 = 100 ( ) ,则问题转化为求不定方程( ) 的正整数解的组数,共有 C 99 组解,故选(D) 。 例 6、8 个女孩和 25 个男孩围成一圈,任意两个女孩之间至少站两个男孩,那么,共有多 少种不同的排列方法。 (只要把圈旋转一下就重合的排法认为是相同的) (1990 年全国高中数学联赛) 解:先排女孩,这是一个圆排列问题,易知共有
49

8! = 7!种不同的排列。8 个女孩的圆排列共 8

留出 8 个空挡。再排男孩,设这 8 个空挡中的男孩数分别为 x1 , x 2 , x3 ,------ x8 ,

x1 + x 2 + + x8 = 25 ,由于任意两个女孩之间至少站两个男孩,即求不定方程
在 x1 ≥ 2 , x 2 ≥ 2 , x3 ≥ 2 ,-----, x8 ≥ 2 下的正整数解的组数,所以不定方程可化 为 ( x1 1) + ( x 2 1) + + ( x8 1) = 17 ,令 x1 1 = y1 ,

第 3 页 共 7 页

x 2 1 = y 2 , x3 1 = y 3 ,-----, x8 1 = y8 , 即得 y1 + y 2 + + y8 = 17 ,其
正整数解的组数是 C16 。再对男孩全排列,共有 C16 × 25! 种排列。所以共有 C16 × 7! × 25! 种
7 7 7

不同的排列方式。 例 7、如果从数 1、2、3、---14 中,按由小到大的顺序取出 a1、a2、a3 使同时满足 a2―a1 ≥ 3 种。 与 a3―a2 ≥ 3,那么所有符合上述要求的不同取法有 (1989 年全国高中数学联赛) 解:由

a1 ≥ 1 , a 2 a1 ≥ 3 , a 3 a 2 ≥ 3 , 14 a3 ≥ 0 ,令 a1 = x1 ,

a 2 a1 = x 2 , a 3 a 2 = x3 , 14 a 3 = x 4 ,则 x1 + x 2 + x3 + x 4 = 14 ,问题即求
不定方程在 x1 ≥ 1 , x 2 ≥ 3 , x3 ≥ 3 , x 4 ≥ 0 下的整数解的组数,又方程转化为

x1 + ( x 2 2) + ( x3 2) + ( x 4 + 1) = 11 。令 x1 = y1 , x 2 2 = y 2 , x3 2 = y 3 ,
3 x 4 + 1 = y 4 , 而 y1 + y 2 + y 3 + y 4 = 11 的正整数解的组数是 C10 。所以符合条件的 3

a1、a2、a3 的不同取法有 C10 =120 种。 四、利用递推关系: 在一些排列组合问题中,我们可以从简单问题入手,寻找规律,继而把问题一般化, 寻找更一般的关系式,即递推关系式,然后解决具体问题。 例 8、有排成一行的 n 个方格,用红、黄、蓝三色涂每个格子,每格涂一色,要求任何相邻 的格不同色,且首尾两格也不同色,问有多少种涂法?(1991 年江苏省数学夏令营) 解:设共有 a n 种不同涂法。易得 a1 =3, a 2 =6, a3 =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 n 2 种不同涂法。因为格 n 与格 1 不同色, 有两种涂法,故有 2a n 2 种不同涂法。 综上可得递推关系式: a n = a n 1 + 2a n 2 ( n ≥ 4 ) ,并可得 a n = 2 + 2( 1) ( n ≥ 2 ) 。
n n

例 9、一只猴子爬一个 8 级的梯子,每次可爬一级或上跃二级,最多上跃三级。从地面 上到最上一级,一共可以有 种不同的爬跃方式。 (中等数学 2001.3 奥林匹克训练题)
第 4 页 共 7 页

解:易得 a1 =1, a 2 =2, a3 =4, a 4 =7。把问题一般化,设一共有 n 级梯子,每次可爬一级 或上跃二级,最多上跃三级。设共有 a n 种不同的爬跃方式。若第一次爬了一级,则有 a n 1 种 方式;若第一次上跃二级,则有 a n 2 种方式;若第一次上跃三级,则有 a n 3 种方式。因此

a n = a n1 + a n 2 + a n 3 。易得 a8 = 81 。即共有 81 种不同的爬跃方式。
练习题: 1、 用红、黄、蓝三色给正方体表面染色,每面只染一种颜色,每色各染两个面,如果 经过适当翻转可使两个染色的正方体各对应面的颜色相同者视为一种染色方法, 那么, 不同 的染色方法种数为 ( ) (A)3 种 (B)5 种 (C)8 种 (D)12 种 (2003 江苏省数学夏令营) (提示:三种颜色都涂相对两面,有 1 种方法;一种颜色涂相对两面,有 3 种方法;三种 颜色都不涂在相对面,有 1 种方法。共有 5 种方法。 ) 2、 如果: (1)a,b,c,d 都属于 { , 2 , 3 , 4}; (2)a ≠ b ,b ≠ c ,c ≠ d ,d ≠ a ; 1 (3)a 是 a,b,c,d 中的最小值。那么,可以组成的不同的四位数 abcd 的个数是 。

(2000 年全国高中数学联赛)
2 (提示: (1) abcd 由 2 个不同数字组成,则必有 a=c,故有 C 4 =6 个。 (2) abcd 由 3

个不同数字组成,则 a 唯一确定,当 c = a , b, d 有 2 种取法;当 c ≠ a ,c 有 2 种取法,
3 (3) abcd 由 4 个不同数字组成, a = 1 ,故有 b=d 为余下的数,故有 C 4 × (2+2)=16 个。

3!=6 个。因此一共有 6+16+6=28 个不同的四位数。 ) 3、 在正方体的 8 个顶点、12 条棱的中点、六个面的中心及正方体的中心共 27 个点中, 共线的三点组的个数是 ( ) (A)57 (B)49 (C)43 (D)37 (1998 年全国高中数学联赛)

8× 7 = 28 个; (2)两端点皆为面的中心的 2 6 ×1 12 × 3 共线三点组共有 = 3 个;两端点皆为各棱中点的共线三点组共有 = 18 个;因此 2 2
(提示: (1)两端点皆为顶点的共线三点组共有 共有 28+3+18=49 个。 ) 4、将一个四棱锥的每个顶点染上一种颜色,并使同一条棱的两端点异色,如果只有 5 种颜色可供使用,那么不同的染色方法的种数是 。 (1995 年全国高中数学联赛) (提示:设有 1、2、3、4、5 五种颜色给四棱锥 S ABCD 染色,由于 S、A、B 所染颜
第 5 页 共 7 页

色不同,则有 5 × 4 × 3=60 种染色方法。设 S、A、B 已染好,再分类讨论,C、D 有 7 种 ) 染法。因此共有 60 × 7=420 种染法。 5、已知直线 ax + by + c = 0 中的 a 、 b 、 c 是取自集合 { 3 , 2 , 1 , 0 ,1 , 2 , 3} 中的 3 个不同的元素,并且该直线的倾斜角为锐角。那么,这样的直线的条数是 。 (1999 年全国高中数学联赛) (1)当 c = 0 , a 有 3 种取法, b 有 3 种取法,排除 2 (提示:不妨设 a > 0 ,则 b < 0 。 个重复, 9-2=7 条。 c ≠ 0 ,a 有 3 种取法, 有 3 种取法,c 有 4 种取法, 3 × 3 × 4= 有 (2) b 有 36 条.因此有 7+36=42 条。 ) 6、在世界杯足球赛前,F 国教练为了考察 A1 , A2 ,---- A7 这七名队员,准备让他们在 三场训练比赛(每场 90 分钟)中都上场。假设在比赛的任何时刻,这些队员中有且仅有一 人在场上,且 A1 , A2 , A3 , A4 每人上场的总时间(以分钟为单位)均能被 7 整除, A5 ,

A6 , A7 每人上场的总时间(以分钟为单位)均能被 13 整除。如果每场换人次数不限,那
么,按每名队员上场的总时间计算,共有多少种不同的情况。 (2002 年全国高中数学联赛) (提示:设第 i 名队员上场的时间为 xi 分钟( i =1,2,3,----,7) ,问题即求不定方 程 x1 + x 2 + + x 7 = 270 在条件 7 xi ( 1 ≤ i ≤ 4 )且 13 x j ( 5 ≤ j ≤ 7 )下的 正整数解的组数。由条件,设 x1 + x 2 + x 3 + x 4 = 7 m , x5 + x 6 + x 7 = 13n ,

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

m=

270 13n ≥ 4 ,易得 3 ≤ n ≤ 18 , n ∈ N ) ( 。进而得到方程的三组正整数解: 7

m = 33 m = 20 m = 7 ,设 xi = 7 y i ( 1 ≤ i ≤ 4 ) x j = 13 y j ( 5 ≤ j ≤ 7 ) , 。 n = 3 n = 10 n = 17
所以转化求方程组

y1 + y 2 + y 3 + y 4 = 33 y5 + y6 + y7 = 3



y1 + y 2 + y3 + y 4 = 20 y5 + y 6 + y 7 = 10

y1 + y 2 + y 3 + y 4 = 7 3 2 3 2 3 2 的正整数解的组数。共有正整数解 C 32 C 2 + C19 C 9 + C 6 C16 =42244 y 5 + y 6 + y 7 = 17
组。)

第 6 页 共 7 页

7、身高两两不等的 10 个人排成一列,每个人都比前面的人高或都比前面的人矮,则符合 种。 (用数字作答) 条件的排法数有 (提示:易知 a1 =1。把问题一般化,设共有 n 个身高两两不等的人,有 a n 种排法。排在 最后一位的必是最高的或是最矮的,则第 n 位上有 2 种排法,前面有 a n 1 种排法,则

a n =2 a n1 ,因此 a10 = 512 种排法。)
8、如图:在一个正六边形的六个区域栽种观赏植物,要求同一块中种同一种植物,相邻 的两块种不同的植物,则有 种栽种方案?(2001 年全国高中数学联赛) 解:本题即例 3,上面用了分类讨论的方法来解决。 F E 事实上我们可以考虑更一般的情形,设 A、B 之后有 n 个区 域 C1 、 C 2 、------ C n ,其中 C1 与 B 相邻, C i +1 与 C i 相邻 ( i = 1,2, n 1) , C n 与 A 相邻。设 C1 、 C 2 、------ C n 共有 a n 种符合条件的栽法,显然 a1 =2,而 C1 、 C 2 、------ C n 各有 3 种栽法,共 3 种栽法,若 C n 与 A 栽种同一种植物,即相
n n

A Cn A C n-1 C2 B C C1 B D

当于 C n 与 A 合并,应当有 a n 1 种栽法,因此 a n + a n 1 = 3 ,因 a1 =2, a 4 =61,又 A、B 共 有 3 × 4=12 种栽法。因此共有 12 × 61=732 种方法。 江苏省梁丰高级中学 邮编:215600 E—mail:Zhangwx@jslfgz.com.cn

第 7 页 共 7 页


赞助商链接
更多相关文档:

超全超全的排列组合的二十种解法

超全超全的排列组合的二十种解法 - 高考难点之排列组合 排列有两种定义,但计算方法只有一种,凡是符合这两种定义的都用这种方法计算。 定义的前 提条件是 m≦n...

排列组合问题的解法

排列组合问题的解法解决排列组合问题要讲究策略,用顺口溜概括为:审明题意,排(组)分清;合理分类,用准加 乘;周密思考,防漏防重;直接间接,思路可循;元素位置,特殊...

排列组合的二十种解法(最全的排列组合方法总结)

排列组合的二十种解法(最全的排列组合方法总结) - 教学目标 1.进一步理解和应用分步计数原理和分类计数原理。 2.掌握解决排列组合问题的常用策略;能运用解题策略...

排列组合问题解法总结

排列组合问题解法总结 - 常见排列组合问题的解法 教学目标 1.进一步理解和应用分步计数原理和分类计数原理. 2.掌握解决排列组合问题的常用策略;能运用解题策略解决...

排列组合的21种解法

排列组合的21种解法 - 搞定排列组合难题二十一种方法 学习目标 1.进一步理解和应用分步计数原理和分类计数原理。 2.掌握解决排列组合问题的常用策略;能运用解题策略...

排列组合解法大全

288 位置分析法和元素分析法是解决排列组合问题最常用也是最基本的方法,若以元素分析为主,需 先安排特殊元素,再处理其它元素.若以位置分析为主,需先满足特殊位置的...

排列组合问题二十种解法(教师版)--成稿

排列组合问题二十种解法(教师版)--成稿 - 课外补充阅读资料 常见“排列-组合”的解题策略 排列组合问题联系实际生动有趣,但题型多样,思路灵活,因此解决排列组合...

经典排列组合应用题的解法技巧

经典排列组合应用题的解法技巧 - 解排列组合应用题的解法 技巧 一. 运用两个基本原理 加法原理和乘法原理是解排列组合应用题的最基本的出发点,可以说对每道应用...

排列组合题解法总结

排列组合解法总结 - 排列组合题型总结 排列组合解法总结 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事 2.怎样做才能完成所要做的事 ,...

排列组合及有效解法

排列组合及有效解法 - 排列组合原理 我们在高中数学中已经学了排列组合的基础知识了,因此大家对“排列组合”这概念应该不会是陌生的。宇宙 中的万事万物严格地说就...

更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com