排列组合问题的常见解题策略
堵车-学组词
盐城师范学院毕业论文(设计)
排列组合问题的常见解题策略
张秀亮
(数学科学学院,2007(2)班,07211249号)
[摘 要]
排列组合是高中数学一大难点,也是高考考查的重点内容,很多人解决
排列组合问题,都感觉无从着手.排列
组合包括排列和组合两部分,其中题型,散,杂.排列组合内容独
特,思维新颖,方法灵活,逻辑性强,规律性强,易于
混淆,容易出错.所以针对这种现状,对排列组合
进行系统分类讨论分析,总结出其中的规律和方法
,
有助于提升排列
组合问题的能力,
解决问题时也比较得心应手.
[关键词] 排列组合 解决 规律和方法
一、 排列问题
所谓排列,就是指从给定个数的元素中取出指定个数的元素进行排序.
排列的定义:从
n
个不同元素中,任取
m
(
mn
)个元素(这里的被取元素各有
不同)
按照一定的顺序排成一列,叫做从
n
个元素中取出
m
个元素的
一个排列.
下面是排列的一些常用解题方法:
(一)分类与分步法
分类计数原
理:做一件事情,完成它可以有
n
类办法,在第一类办法中有
m
1
种
不同的
方法,在第二类办法中有
m
2
种不同的方法,…,在第
n类办法中有
m
n
种不同的方法.那么完
成这件事共有
Nm1
m
2
m
n
中不同的方法.
分步计数原
理:做一件事情,完成它需要分成
n
个步骤,第一步有
m
1
种不同的
方法,
第二步有
m
2
种不同的方法,…,第
n
步有
m
n
种不同的方法,那么完成这件事有
Nm
1
m
2...m
n
种不同的方法.
例1 某信号兵用红,黄,蓝3面旗从上到下挂
在竖直的旗杆上表示信号,每次可以任
意挂一面,二面或三面,并且不同的排序表示不同的信号,一共可
以表示多少种不同的信
号?
解 信号可以分3类:
1
第一类用一面旗表示的信号有
A
3
种;
第1页
共7页
盐城师范学院毕业论文(设计)
第二类用两面旗表示的信号有
A
3
2
种;
第二类用三面旗表示的信号有
A
3
3
种;
13<
br>A
3
2
A
3
33232115
种
; 由分类计数原理,所求信号种树有
A
3
故一共可以表示
15
种
不同的信号.
例2 用
0
到
9
这
10
个数字,可
以组成多少个没有重复数字的三位数?
解 解决排列应用题,常用的思考方式是直接法和间接法.
直接法:通过对问题进行恰当的分类和分步,直接计算符合条件的排列数,如解法
1
,
2
;
间接法:对于有限制条件的排列应用题,可以不考虑限制条件,把所有情况的种
数求
出来,然后再减去不符合限制条件的情况种数,如解法3;对于有限制条件的排列应用题,
要恰当的确定分类与分步的标准,防止重复与遗漏.
法1.用分步计数原理:
1
A
9
2
998648
.
所求的三位
数的个数是:
A
9
法2.符合条件的三位数可以分成三类:没一位数字不是
0
的三位数有
A
9
3
个,个位数是
3
A
9
2
A
9
2
648
.
0
的三位数有<
br>A
9
2
个,由分类计数原理,符合条件的三位数的个数是:
A
9
3
法3.从
0
到
9
这
10
个数字中任取
3个数字的排列数为
A
10
,其中以
0
为排头的排列数为
3
A
9
2
,因此符合条件的三位数的个数是
A
10
A
9
2
648
.
(二)相邻问题捆绑法
有些排列组合
问题可以将相邻的元素捆绑在一起,作为一个整体,然后再进行排列,
这样可以将复杂的问题简单化.
例3
6
名同学排成一排,其中甲、乙两人必须站在一起的不同排法有多少种?
解 因甲、乙两人要排在一起,故将甲、乙两人捆在一起视作一人,与其余四人进行
52
A
2
全排列有种排法,但甲、乙两人之间有种排法,由乘法原理可知,共有
A5
种排法.
说明:从上述解法可以看出,所谓“捆绑法”,就是在解决对于某几个元素要
求相邻问题
时,可整体考虑将相邻元素视作一个“大”元素.
例4 由数字
1
、
2
、
3
、
4
、
5
、
6
、
7
组成无重复数字的七位数.( 1)
求三个偶数必
相邻的七位数的个数; ( 2)求三个偶数互不相邻的七位数的个数.
(1) 解(一) 因为三个偶数
2
、
4
、
6
必须相邻,所
以要得到一个符合条件的七位数可
以分为如下三步: 第一步将
1
、
3
、
5
、
7
四个数字排好有
A
4
4
种不同
的排法; 第二步将
2
、
4
、
6
三个数字捆绑在一起有A
3
3
种不同的捆绑方法; 第三步将第二步捆绑的这个整体插入
第2页
共7页
盐城师范学院毕业论文(设计)
到第一步所排的四个不同数字的五个间隙 (包括两端的两个位置)中的其中一个位置上,
1
1
720
种同的排法.所以共有
720
个有
A
5
种不同的插入方法.根据乘法原理共有
A
4
4
A
3
3
A
5
符合条件的七位数.
解(二) 先把
2
、4
、
6
捆绑在一起看做一个数与
1
、
3
、5
、
7
进行排列共有
A
5
5
种排法.
第二步将
2
、
4
、
6
三个数字 捆绑在一起有
A<
br>3
3
种不同的捆绑方法.根据乘法原理得到
35
A
3
A
5
720
种不同的排法.所以共有
720
个符合条件的七位数
.
(2)解
因为三个偶数
2
、
4
、
6
互不相邻,
所以要得到符合条件的七位数可以分为如
下两步:
第一步将
1
、
3
、
5
、
7
四个数字排好,
有
A
4
4
种不同的排法; 第二步将
2
、
4
、
6
分
别插入到第一步排的四个数字的五个 间隙 (包括两端的两个位置)中的三
个位置上,有
A
5
3
43
A
5
1440
种不同的排法.所以共有
1440
个符合条件的种插入方法.根据乘法原理共有
A<
br>4
七位数.
(三)相离问题插空法
相离问题插空法主要针对元素不能相邻问
题,将不能相邻的元素隔开,主要做法是将
其它元素想排好,再将不能靠一块的插进已经排好元素的间隙
中.
例5 要拍一张有
6
个歌唱节目和
4
个舞蹈节目的演出节目单
,任何两个舞蹈节目不得
相邻,问有多少不同的排法?
解 先将
6
个歌唱节
目排好,其不同的排法为
A
6
6
种,这
6
个歌唱节目的空隙
及两端共
七个位置中再排
4
个舞蹈节目有
A
7
7
种
排法,由乘法原理可知,任何两个舞蹈节目不得相邻
6
的排法为
A
7
4
A
6
种.
说明:从解题过程可以看出,不相邻问题是指要求某些元素不
能相邻,由其他元素将
它隔开,此类问题可以先将其它元素排好,再将所指定的不相邻的元素插入到它们
的间隙
及两端位置,故称插空法.
二、组合问题
组合则是指从给定个数的元素中仅仅取出指定个数的元素,不考虑排序.
组合的定义:从n
个不同元素中,任取
m
(
mn
)个元素(这里被取元素个不
相同)
并成一组,叫做从
n
个不同元素中取出
m
个元素的一个组合.
下面的组合的一些常用解题方法:
(一)标号排位问题分布法
把元素排在指定号码的位置上成为标号排位问题,求解这类问题可先把某个元素按照
第3页
共7页
盐城师范学院毕业论文(设计)
规定排入,第二步再排另一个元素,如此继续下去,依次即可完成.
例6 同室<
br>4
人各写一张贺年卡,先集中起来,然后每人从中拿一张别人送来的贺年卡,
则四张贺年
卡不同的分配方式有多少种?
解 此题可以看成是将数字
1
、
2
、
3
、
4
添入标号为
1
、
2
、
3<
br>、
4
的四个方格里,每
格填一个数,且每个方格的标号与所填数不同的填法问题
.所以先将
1
填入
2
至
4
号的三个
11
方
格中有种
C
3
填法,第二步把被填入方格的对应数字,填入其它
3
个
方格,又有
C
3
种填法,
第三步将余下的两个数字填入余下的两格中只有一种
填法,故共有
3319
种填法.
(二)多元问题分类法
多元问题分类法主要将问题先分成几种情况,先求出每种情况,然后将每种情况归结
起来,算出总体情况
.
例7
4
名男生和
6
名女生组成至少有
1
名男
生参加的三人社会实践活动小组,问组成
方法共有多少种?
211
3
C
6
C
6
2
,所以解 小组
构成有三种情况:
3
男,
2
男
1
女,
1
男
2
女,分别有
C
4
,
C
4
,
C<
br>4
3211
C
4
C
6
C
4
C
6
2
100
种方法. 一共有
C
4
(三)组合中的抽屉原理
抽屉原理有时也被称为鸽巢原理,它是德国数学家狄利克雷首先明确
提出来并用以证
明一些数论中的问题,因此,也称为狄利克雷原理,它是组合数学中一个重要的原理.
抽屉原理的定义:假如有
n1
或多于
n1
个元素放到
n
个元素中去,其中必定至少有一个集
合里有两个元素.
例8 幼儿园买来了
不少白兔,熊猫,长颈鹿塑料玩具,每个小朋友任意选择两件,那
么不管怎样挑选,在任意七个小朋友中
总有两个彼此选的玩具都相同,试试说明道理.
解:从三种玩具中挑选两件,搭配方式整合后和只能是
下面六种:(兔,兔),(兔,
熊猫),(兔,长颈鹿),(熊猫,熊猫),(熊猫,长颈鹿),(长颈
鹿,长颈鹿).把每种方
式看做一个抽屉,把7个小朋友看做物体,那么根据原理
1
,
至少有两个物体要放进同一
个抽屉里,也就是说,至少两人挑选玩具采用同一种搭配方式,选的玩具相同
.
三、排列组合特殊类问题
有些题目属于排列组合,但这些题目特殊
,而且考试中易于犯错,我们把它们作为特
例分下来讨论,有助于掌握.
第4页 共7页
盐城师范学院毕业论文(设计)
(一)排列组合“投球入盒”问题探究
1、不同小球的投放问题
模型1:
n
个不同的小球全部投入到m个不同的盒中,共有
mn
种不同的投放方法.
分析:完成事件的最终结果是:
n
个球全部进入盒子中.可分
n
个步骤完成,
第1 个球有
m
种不同
的投放方法,第
2
个球,第
3
个球⋯⋯第
n
个球也均有m种
不同的投放方
法,由分步计数原理:共有
m
n
种不同投放方法.模型使用的关
键在于分清“球是什么”,
“盒是什么”.
例9 (1)
5
名学生从
3
项体育项目中选择参赛,若每名学生都要参加,且每
一名学生只能参加一项,则有多少种不同的参赛方法?
(2)若
5
名学生争夺
3
项比赛冠军(每一名学生参赛项目不限),则冠军获
得者有几种不同情况(没有并列冠军)?
解
(1)中完成事件的结果是:最终每名学生都要参赛,而每一项可能有
多人参加.故把学生视为“球”
,项目则视为“盒”.
5
个不同的“球”最后都要投入到
3
个
“盒”
中.每一个“球”都有3 种不同投法.故参赛法共有
3
5
243
种.
(2)中完成事件最后的结果是:冠军都被学生夺得.每一项比赛冠军由一人获得,
而一人可
得多项冠军,故把冠军视为“球”,学生视为“盒”,“球”最后要部入“盒“(即
冠军最后全部由学生
夺取),每个球均有5 种投法(对应每个冠皆有可能被5名生中任一
人获得)故三项冠军依次被取得的
情况共有
5
3
种.
2、相同小球的投放问题
n1
模型2:
n
个相同的小球投入到
m
个不同的盒子中
,且每盒至少有一个小球,共有
C
m1
种不同投放方法.
分析:这类问题
用“隔板法”解决比较简捷.
n
个相同的小球之间共有
n1
个空档(两外)现取(
m1
)块相同的“档板”分别插入到(
n1
)个空档中的
m1
个空档,每一
次插入就将
n
个球分成了
m
个
部分(每一部分至少有一个球),即对应一种投球入盒方法,
n1
故共
C
m
1
种不同投法.
例10
已知方程
xyzw100
,求这个方程的正整数解的组数.
解 此题貌似与
排列或组合无关,实质可转化为组合问题解决.
100
为
100
个
1
的和每一
组解相当于把
100
个
1
分成
4
组,每一种分组对应方程的一组正整数解,若将
100
个“
1
”看
成
100
个“相同的小球”,问题转化为:“
100
个相同的小球投入到四个
不同的盒中(
x
、
y
、
z
、
w
视为‘盒’
)每盒至少投入
1
个球,共有多少种不同投放方法?”即在
100
个小
球之间的
99
个空档处选取
3
个,分别插入
3
块“挡板”
,每次插入,被分成
4
组的球的个
第5页 共7页
盐城师范学院毕业论文(设计)
数即为方程相应的一组解,故方程正整数解数共有
3
C
99
156849
组.
1
模型3:
n
个相同的小球,全部投入到
m
个不同的盒子
中(无任何要求);共有
C
n
m
m1
种不同
投放方法.
分析:同样运用“隔板思想”,只是隔板允许相邻,即允许隔板间没有小球,相当于
从
nm1
(n 个小球和m-1 块隔板)个位置中任取m-1 个位置放置m-1
个隔板的组合数.
例11
从
5
个班中选
10
人组成校篮球队(无任何要求)有多少种不同选法?
解 “
10
个人”视为“
10
个相同的小球”班级视为“盒子”10
个小球投入到
5
个盒子
中,是
10
个小球和
4
块挡板两类元素不分顺序的排列问题.即
4
块“挡板”与
10
个球一
4
1001
种选法.
样也要参与排成一列占位置.故有
C
14
(二)插板法解
“插板法”顾名思义就是将元素做为插板插进空档处.
例12 现有
10<
br>个完全相同的球全部分给
7
个班级
,
每班至少
1
个球
,
问共有多少种不的
分法
?
解
题目中球的分法共三类
.
3
(1)
有
3
个班每
个班分到
2
个球
,
其余
4
个班每班分到
1
个球
.
其分法种数
N
1
C
7
.
(2)
有
1
个班分到
3
个球
;
1
个班分到2
个球
;
其余
5
个班每班分到
1
个球
.
其分法种数
11
N
2
C
7
C
6<
br>.
1
(3)
有
1
个班分到
4<
br>个球
;
其余的
6
个班每班分到
1
个球
.
其分法种数
N
3
C
7
.
3111C
6
C
7
C
7
84
.
所以
,
10
个球的分法种数为
NN
1
N2
N
3
C
7
由上面解题过程可以明显感到对这类问题进行分
类计算
,
比较繁琐
,
若是上题中球
的
数目较多处理起来将更加困难,
因此我们需要寻求一种新的模式解决问题,
我们创
设这样一种虚拟的情境———插板
.
将
10
个相同的球排成一行,
10
个球之间出现了
9
个空档
,
现在我们用“档板”把
10
个
球隔成有序的
7
份,每个班级依次按班级序号分到对应位置的几个球( 可能是
1
个、
2
个、
3
个、
4
个)
.这样每个班级分到球的个数不在于它所排的位置,
借助于这样的虚拟“档
板”分配物品的方法称之为插板法.
由上述情境分析知,
分球的方法实际上为档板的插法:
即是在<
br>9
个空之中插入
6
个
“档板”,其方法种数为
NC
9
6
84
.
4
思考:若上题中的球为
15
个全
分给
7
个班级
,
每班至少一个球的分法种数是几
?(
C16
)
由上述问题的解决看到
,
这种插板法解决起来非常简单
,
但同时也提醒大家
,
这类问题
第6页 共7页
盐城师范学院毕业论文(设计)
模型要求满足条件相当严格
,
必须具备以下
3
个条件
:
(1)
所要分的物品规格必须完全相同
.
(2)
所要分的物品必须分完
,
决不允许有剩余
.
(3)
参与分物品的每个成员至少分到
1
个
,
决
不允许出现分不到物品的成员
.
总结:排列组合问题说难也不难,说简单
也容易出错,关键看以何种思路,何种方法
解决,针对一类问题进行细致,仔细的分析,研究,从而掌握
这类的一般方法,对于解决
这类问题有很大帮助.本文主要通过对排列组合的一个分类分析,讨论,列出
了一些常见的
排列组合问题的题型,从中归纳一般规律.
[参考文献]
[1]席明闰.排列组合的问题及解答策略.内江科技.2010第二期
[2]陈绍敏.排列组合中的“投球入盒”.问题研究.2009.7
[3]张亚军.高中数学教与学.第8期
[4]王金锁.数学教学.考试周刊
[5]李智敏.例谈排列组合的若干解题策略.实战实例
[6]张金华.排列组合问题常见解题策略
[7]张军.教师招聘考试专用教材.2011
The Common Permutation And
Combination Problem Solving Strategy
Zhang XiuLiang
[Abstract]
The permutation and combination is high school
maths, but also a difficult the main content of
college entrance
examination examination, a
lot of people solve permutation and combination,
are feeling never begin. The permutation and
combination including permutation and
combination two parts, including bodily form,
scattered, miscellaneous. The permutation
and
combination content is unique, fashion-minded
flexible method, strong logicality, strong
regularity, easy to confuse and
error-prone.
So based on the present situation of the
permutation and combination, systematic
classification discuss analysis, this
paper
summarizes the rules and methods, helps to raise
the ability of the permutation and combination
problem solving problems,
is also handy.
[Key Words]
Permutation and
combination,solve,Rules and methods
第7页
共7页