一、排列组合问题基本原理
加法原理:
完成一件事情,有m类不同的方式,而每种方式又有多种方法可以实现。那么,计算完成这件事的方法数,就需要把每一类方式对应的方法数加起来。
例:从A地到B地,坐火车有3种方法,坐汽车有5种方法,坐飞机有2种方法,那么从A地到B地一共应该有3+5+2=10种方法。这里从A地到B地有火车、汽车和飞机三类方式,所以使用加法原理。
乘法原理:
完成一件事情,需要n个步骤,每一个步骤又有多种方法可以实现。那么计算完成这件事的方法数,就是把每一个步骤所对应的方法数乘起来。
例:从A地到B地坐飞机需要在C地转机,已知从A地到C地有4种方法,从C地到B地有3种方法。这里从A地到B地,需要分两个步骤完成,第一步从A地到C地,第二步从C地到B地,因此从A地到B地有4×3=12种方法。
分类用加法原理,分步用乘法原理。
二、排列组合问题基本概念
排列:从n个不同元素中任取M个按照一定的顺序排成一列,叫做从n个元素中取出m个元素的一个排列。所有不同排列的个数,称为从n个不同元素中取出m个元素的排列数,一般我们记作Amn。
例:从编号为a、b、c、d的4个孩子中选出2个孩子排成一行,有多少种排法?显然,列举出来有
ab、ac、ad、ba、bc、bd、ca、cb、cd、da、db、dc,共12种;这里,即便是选出来的孩子一样,但排列顺序不一样,排法也就不一样,因此要考虑孩子的顺序,所以是排列问题。排法应该是种。
全排列:n个不同的元素全部取出的一个排列,叫做n个不同元素的一个全排列,即当m=n,时,全排列数。
组合:从n个不同元素中取出m个元素拼成一组,称为从n个元素中取出m个元素的一个组合。不同组合的个数称为从n个不同元素中取出m个元的组合数,一般我们记作Cmn。
例:从编号为a、b、c、d的4个孩子中选出3个孩子去参加运动会,有多少种选法?列举出来,有abc、abd、bcd、acd这4种情况。abc与acb、bca表明选出的都是a、b、c,是一种选法,不需要考虑孩子的顺序,所以是组合问题,选法为C34=4种。
考虑顺序用排列,不考虑顺序用组合。
【例题】林辉在自助餐店就餐,他准备挑选三种肉类中的一种肉类,四种蔬菜中的两种不同蔬菜,以及四种点心中的一种点心。若不考虑食物的挑选次序,则他可以有多少不同选择方法?
A.4种 B.24种
C.72种 D.144种
解析:
一点通:排列组合问题的解题原则是:(1)合理分类;(2)准确分步;(3)先组后排。
三、排列组合问题解题方法
一些排列组合问题条件比较多,直接使用分类或分步来考虑较为复杂,在这种情况下,掌握一些特定的解题方法和公式有助于大家快速解题,下面介绍七种解题方法。
【例题】某单位安排五位工作人员在星期一至星期五值班,每人一天且不重复。若甲、乙两人都不能安排星期五值班,则不同的排班方法共有( )种。
A.6 B.36
C.72 D.120
解析:此题答案为C。星期五有特殊要求,因此先考虑星期五,有3种选择方法,再安排剩余的4天,有A44=24种情况。这里用到的是分步思想,所以应用乘法原理,共有3x24=72种排班方法。
【例题】从15名学生中选出5名参加比赛,其中甲和乙至少有一人要被选上,请问有多少种选法?
A.3003 B.1716 C.1287 D.154440
解析:此题答案为B。甲和乙的情况无非四种:甲乙都选上,甲上乙不上,甲不上乙上,甲乙都不上。
直接考虑甲、乙至少有一人被选上,需要分三种情况讨论。①甲乙都选上,就是从其他13名中再选3名,有C313种情况;②甲上乙不上,就是从其他13名中再选出4名,有C413种情况;③甲不上乙上,同上一种情况,有C413种情况。因此,一共有种选法。
点拨:从对立面考虑,它的对立面只有一种:甲乙都不被选上,较为简便。
从15名学生选出5名参加,有C515种情况,甲、乙都不被选上,也就是从其他13名中选出5名,有C513种情况,因此甲和乙至少一人被选上种选法。
【例题】在航天员进行的一项太空实验中,要先后实施5个程序,程序B和C实施时必须相邻,请问实验顺序的编排方法共有( )。
A.24种 B.48种 C.96种 D.144种
解析:此题答案为B。程序B和程序C实施时必须相邻,则将这两个程序捆绑在一起,作为整体参与排列,相当于4个程序进行排列,有A44=24种情况,B和c本身又有2种情况,因此最终的编排方法有24×2=48种。
【例题】将三盆同样的红花和四盆同样的黄花摆放成一排,要求三盆红花互不相邻,共有多少种不同的方法?
A.8 B.10 C.15 D.20
解析:此题答案为B。由于花是相同的,也就是说不需要考虑顺序问题,所以为组合问题。要求三盆红花互不相邻,则将3盆红花插入四盆黄花形成的5个空位(包括两端)里,有C35=10种不同的方法。
【例题】将10本没有区别的图书分到编号为1、2、3的图书馆,要求每个图书馆分得的图书不小于其编号数,共有多少种不同的分法?
A.12 B.15 C.30 D.45
解析:此题答案为B。因为书相同,不用考虑顺序,所以这是一个组合问题。
方法一,分得的书不小于其编号,可以先分1、2.3本书到3个图书馆中,还剩下10-1-2-3=4本书。若4本书分给1、2、3图书馆中的任一个,有C13=3种情况;若4本书分成(1+3)两份,分给1、2、3中的两个图书馆,有C23×2=6种情况;若4本书分成(2+2)两份,分给1、2、3中的两个图书馆,有C23=3种情况;4本书分成(1+1+2)三份,再从中选出1个分2本书的图书馆,有C13=3种情况,所以一共有3+6+3+3=15种分法。
方法二,将问题转化为“n件相同的物品分成m堆,每堆至少一件”这种标准问题,再用插板法将非常简便。先给编号为2的图书馆1本书、编号为3的图书馆2本书,还剩下10-1-2=7本书,这样问题就变为“7本书分给3个图书馆,每个图书馆至少一本”,采用插板法公式可知,有C26=15种分法。
【例题】一张节目表上原有3个节目,如果保持这3个节目的相对顺序不变,再添进去2个新节目,有多少种安排方法?
A.20 B.12 C.6 D.4
解析:此题答案为A。此题意思为“安排5个节目,其中三个节目相对顺序确定,有多少种方法?”
方法一:归一法。安排5种节目有种方法,三个节目的全排列数为种。根据归一法可知,一共有120÷6=20种安排方法。
方法二:插空法。节目表上原有的3个节目形成4个空(包含两端),将一个新节目插入这4个空中,有种方法,现在这4个节目形成5个空(包含两端),将剩余的一个节目插入这5个空中,有种方法,所以一共有4×5=20种方法。
【例题】有5对夫妇参加一场婚宴,他们被安排在一张10个座位的圆桌就餐,但是婚礼操办者并不知道他们彼此之间的关系,只是随机安排座位。问5对夫妇恰好都被安排在一起相邻而坐的概率是多少?
A.不超过1‰
B.超过1%
C.在5‰到1%之间
D.在1‰到5‰之间
解析:此题答案为D。从中公的命题的分析来看,要求概率的取值范围,首先要确定概率的表达式。“圆桌就餐”与环线排列如出一辙,直接套用公式计算。
不附加任何条件,10人环线排列的情况总数是;
5对夫妇都相邻而坐,则可以看成由两步来完成,首先把每对夫妇看成一个人,5个人环线排列,然后考虑每对夫妇内部的顺序。第一步有种情况;第二步有2×2×2×2×2=32种情况。所以情况总数就是4×32。
所求概率=,这个数的值应该略大于2‰,结合选项来看,可确定本题答案为D。
一点通:排列组合问题一般可一题多解,解题的基本思想都是把复杂的问题简单化。除了基本的“分类”和“分步”方法外,需要牢记:特殊条件优先考虑,复杂问题反面考虑,元素相邻用捆绑法,元素间隔用插空法,元素分组用隔板法,元素定序用归一法,环形问题用线排法。
四、错位重排问题
错位重排问题通常形式为:
编号为1、2、…、n的n封信,装入编号为1、2、…、n的n个信封,要求每封信和信封的编号不同,问有多少种装法?
对于这种问题,有一个固定的递推公式,记n封信的错位重排数为
在公务员考试中,一般只考查n=3、4、5的情况,所以记住就可以快速求解出正确答案了。
【例题】四位厨师聚餐时各做了一道拿手菜。现在要求每人去品尝一道菜,但不能尝自己做的那道菜。问共有几种不同的尝法?
A.6种 B.9种 C.12种 D.15种
解析:此题答案为B。设四位厨师为甲、乙、丙、丁,他们的菜对应为①②③④。甲可以选②③④三盘菜,假定选②,甲、乙、丙、丁对应的情况数有②①④③、②③④①、②④①③三种情况。甲任选一盘有3种情况,那么总共有3×3=9种情况。此题是错位重排问题,即D4=9。
五、公式
(1)排列公式:Pmn=n(n-1)(n-2)…(n-m+1),(m≤n)。 A37=7×6×5
(2)组合公式:
(3)错位排列(装错信封)问题:D1=0,D2=1,D3=2,D4=9,D5=44,D6=265,
(4)N人排成一圈有/N种; N枚珍珠串成一串有/2种。