排列组合问题解法
- 格式:doc
- 大小:202.50 KB
- 文档页数:6
排列组合问题的20种解法排列组合问题联系实际生动有趣,但题型多样,思路灵活,因此解决排列组合问题,首先要认真审题,弄清楚是排列问题、组合问题还是排列与组合综合问题;其次要抓住问题的本质特征,采用合理恰当的方法来处理。
复习巩固分类计数原理(加法原理)完成一件事,有n类办法,在第1类办法中有m种不同的方法,在1第2类办法中有m种不同的方法,…,在第n类办法中有n m种不同2的方法,那么完成这件事共有:种不同的方法.2.分步计数原理(乘法原理)完成一件事,需要分成n个步骤,做第1步有m种不同的方法,做1第2步有m种不同的方法,…,做第n步有n m种不同的方法,那么2完成这件事共有:种不同的方法.3.分类计数原理分步计数原理区别分类计数原理方法相互独立,任何一种方法都可以独立地完成这件事。
分步计数原理各步相互依存,每步中的方法完成事件的一个阶段,不能完成整个事件.解决排列组合综合性问题的一般过程如下:1.认真审题弄清要做什么事2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。
3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素.4.解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数. 解:由于末位和首位有特殊要求,应该优先安排,占了这两个位置.先排末位共有13C 然后排首位共有14C最后排其它位置共有34A由分步计数原理得113434288C C A =练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间,也不种在两端的花盆里,问有多少不同的种法 二.相邻元素捆绑策略例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法.解:可先将甲乙两元素捆绑成整体并看成一个复合元素,同时丙丁也看成一个复合元素,再与其它元素进行排列,同时对相邻元素内部进行自排。
排列组合是组合数学中的一个重要概念,涉及到对一组对象进行排列或组合的方式。
下面列举几个经典的排列组合题型及解法:
1. 排列问题:
-题型:从n个不同元素中选取m个元素,有多少种排列方式?
-解法:使用排列数的公式P(n, m) = n! / (n-m)!,其中n!表示n 的阶乘。
2. 组合问题:
-题型:从n个不同元素中选取m个元素,有多少种组合方式?
-解法:使用组合数的公式C(n, m) = n! / (m!(n-m)!),其中n!表示n的阶乘。
3. 重复排列问题:
-题型:从n个元素中选取m个元素进行排列,允许元素重复,有多少种排列方式?
-解法:使用重复排列数的公式P'(n, m) = n^m,其中^n表示n的m次方。
4. 重复组合问题:
-题型:从n个元素中选取m个元素进行组合,允许元素重复,有多少种组合方式?
-解法:使用重复组合数的公式C'(n, m) = C(n+m-1, m),其中C(n, m)表示组合数。
5. 圆排列问题:
-题型:将n个不同的物体围成一个圆圈,有多少种不同的排列方式?
-解法:使用圆排列数的公式P(n) = (n-1)!。
以上是一些常见的排列组合题型及其解法。
在实际问题中,可能会出现更加复杂和变化的情况,需要根据具体问题进行分析和推导解法。
教学目标1.进一步理解和应用分步计数原理和分类计数原理。
2.掌握解决排列组合问题的常用策略;能运用解题策略解决简单的综合应用题。
提高学生解决问题分析问题的能力3.学会应用数学思想和方法解决排列组合问题. 复习巩固1.分类计数原理(加法原理)完成一件事,有n 类办法,在第1类办法中有1m 种不同的方法,在第2类办法中有2m种不同的方法,…,在第n 类办法中有n m 种不同的方法,那么完成这件事共有:种不同的方法.2.分步计数原理(乘法原理)完成一件事,需要分成n 个步骤,做第1步有1m 种不同的方法,做第2步有2m 种不同的方法,…,做第n 步有n m 种不同的方法,那么完成这件事共有:种不同的方法.3.分类计数原理分步计数原理区别分类计数原理方法相互独立,任何一种方法都可以独立地完成这件事。
分步计数原理各步相互依存,每步中的方法完成事件的一个阶段,不能完成整个事件. 解决排列组合综合性问题的一般过程如下: 1.认真审题弄清要做什么事2.怎样做才能完成所要做的事,即采取分步还是分类,或是分步与分类同时进行,确定分多少步及多少类。
3.确定每一步或每一类是排列问题(有序)还是组合(无序)问题,元素总数是多少及取出多少个元素.4.解决排列组合综合性问题,往往类与步交叉,因此必须掌握一些常用的解题策略 一.特殊元素和特殊位置优先策略例1.由0,1,2,3,4,5可以组成多少个没有重复数字五位奇数.解:由于末位和首位有特殊要求,应该优先安排, 先排末位共有13C 然后排首位共有14C 最后排其它位置共有34A由分步计数原理得113434288C C A =练习题:7种不同的花种在排成一列的花盆里,若两种葵花不种在中间,也不种在两端的花盆里,问有多少不同的种法?二.相邻元素捆绑策略例2. 7人站成一排 ,其中甲乙相邻且丙丁相邻, 共有多少种不同的排法.解:可先将甲乙两元素捆绑成整体并看成一个复合元素,同时丙丁也看成一个复合元素,再与其它元素进行排列,同时对相邻元素内部进行自排。
排列组合问题是数学中的一类问题,它涉及到从一组物品中选择出某种特定排列或组合的问题。
比如,从n个不同的物品中取出m (m≤n)个物品,求出所有可能的组合数。
排列组合问题的解决方法有多种,其中最常用的是排列组合的基本解法,也就是组合数学中的组合数公式。
组合数公式是一种计算从n个不同的物品中取出m(m≤n)个物品的所有可能组合数的方法,它的公式如下:C(n, m)=n!/(m!(n-m)!)其中,C(n, m)表示从n个不同的物品中取出m个物品的所有可能组合数,n!表示n的阶乘,m!表示m的阶乘,(n-m)!表示(n-m)的阶乘。
举例来说,如果从5个不同的物品中取出3个物品,那么求出所有可能的组合数,可以用组合数公式来计算:C(5, 3)=5!/(3!(5-3)!)=5!/6!=5×4×3/6×5×4=10因此,从5个不同的物品中取出3个物品的所有可能组合数为10。
组合数公式是排列组合问题中最常用的解法,它可以用来计算出任意给定n个不同物品中取出m(m≤n)个物品的所有可能组合数。
但是,在某些特殊情况下,组合数公式可能会有一定的局限性,比如当n和m都比较大的时候,计算出的组合数可能会比较大,这时候可能无法用组合数公式来求解。
除了组合数公式,还可以使用枚举法来解决排列组合问题。
枚举法是一种比较简单的解决方法,它的基本思想是通过枚举出所有可能的排列或组合,然后用穷举的方法来求解问题。
举例来说,如果要求从5个不同的物品中取出3个物品的所有可能组合,那么可以枚举出所有可能的组合,如下:ABCABDABEACDACEADEBCDBCEBDECDE从上面的例子可以看出,通过枚举法可以得到10种可能的组合,这正是从5个不同的物品中取出3个物品的所有可能组合数。
枚举法有一定的缺点,即当n和m都比较大的时候,可能会出现计算量太大的情况,导致程序运行时间过长。
除了组合数公式和枚举法,还有一种比较常用的解决排列组合问题的方法,即递归法。
解排列组合问题常用方法(二十种)一、定位问题优先法(特殊元素和特殊位置优先法)例1、由01,2,3,4,5,可以组成多少个没有重复数字五位奇数? 分析:特殊元素和特殊位置有特殊要求,应优先考虑。
末位和首位有特殊要求。
先排末位,从1,3,5三个数中任选一个共有13C 种组合;然后排首位,从2,4和剩余的两个奇数中任选一个共有14C 种组合;最后排中间三个数,从剩余四个数中任选三个共有34A 种排列。
由分步计数原理得113344288C C A =。
变式1、7种不同的花种在排成一列的花盆里,若两种葵花不种在中间,也不种在两端的花盆里,问有多少不同的种法?分析:先种两种不同的葵花在不受限制的四个花盒中共有24A 种排列,再种其它葵花有55A 种排列。
由分步计数原理得25451440A A =。
二、相邻问题捆绑法例2、7人站成一排 ,其中甲乙相邻且丙丁相邻,共有多少种不同的排法?分析:分三步。
先将甲乙两元素捆绑成整体并看成一个复合元素,将丙丁两元素也捆绑成整体看成一个复合元素,再与其它元素进行排列,同时在两对相邻元素内部进行自排。
由分步计数原理得522522480A A A =。
变式2、某人射击8枪,命中4枪,4枪命中恰好有3枪连在一起的情形的不同种数为 。
分析:命中的三枪捆绑成一枪,与命中的另一枪插入未命中四枪形成的五个空位,共有25A 种排列。
三、相离问题插空法例3、一个晚会节目有4个舞蹈,2个相声,3个独唱,舞蹈不能连续出场,则节目出场顺序有多少种?分析:相离问题即不相邻问题。
分两步。
第一步排2个相声和3个独唱共有55A 种排列,第二步将4个舞蹈插入第一步排好后形成的6个空位中(包含首尾两个空位)共有46A 种排列,由分步计数原理得545643200A A =。
变式3、某班新年联欢会原定的5个节目已排成节目单,开演前又增加了两个新节目,如果将这两个新节目插入原节目单中且不相邻,那么不同插法的种数为 。
第一课时 排列组合问题的解题方法(一)教学目标:掌握几类特殊的排列问题的解决技巧.教学重点:掌握“条件排列”、“集团排列”、“间隔排列”、“部分顺序排列”问题的解题技巧.教学难点:如何应用“技巧”解题.教学过程:【例析技巧】一.集团排列问题:部分元素必须安排在一起(相邻)的排列问题,称之为“集团排列”问题.解决这类问题,常用“捆绑法”,其方法是先排“集团”部的元素,再把这个大“元素”与其它元素一起排列即可.例1 若7位同学站成一排(1)甲、乙两同学必须相邻的排法共有多少种?(2)甲、乙和丙三个同学都相邻的排法共有多少种?(3)甲、乙两同学必须相邻,而且丙不能站在排头和排尾的排法有多少种?(4)甲、乙、丙三个同学必须站在一起,另外四个人也必须站在一起的排法有多少种?解:(1)先将甲、乙两位同学“捆绑”在一起看成一个元素与其余的5个元素(同学)一起进行全排列有66A 种方法;再将甲、乙两个同学“松绑”进行排列有22A 种方法.所以这样的排法一共有62621440A A ⋅=种. (2)方法同上,一共有55A 33A =720种.(3)解法一:将甲、乙两同学“捆绑”在一起看成一个元素,此时一共有6个元素,因为丙不能站在排头和排尾,所以可以从其余的5个元素中选取2个元素放在排头和排尾,有25A 种方法;将剩下的4个元素进行全排列有44A 种方法;最后将甲、乙两个同学“松绑”进行排列有22A 种方法.所以这样的排法一共有25A 44A 22A =960种方法.解法二:将甲、乙两同学“捆绑”在一起看成一个元素,此时一共有6个元素,若丙站在排头或排尾有255A 种方法,所以,丙不能站在排头和排尾的排法有960)2(225566=⋅-A A A 种方法.解法三:将甲、乙两同学“捆绑”在一起看成一个元素,此时一共有6个元素,因为丙不能站在排头和排尾,所以可以从其余的四个位置选择共有14A 种方法,再将其余的5个元素进行全排列共有55A 种方法,最后将甲、乙两同学“松绑”,所以,这样的排法一共有14A 55A 22A =960种方法. (4)将甲、乙、丙三个同学“捆绑”在一起看成一个元素,另外四个人“捆绑”在一起看成一个元素,时一共有2个元素,∴一共有排法种数:342342288A A A =(种)说明:对于相邻问题,常用“捆绑法”(先捆后松).二. 间隔排列问题:部分元素不能安排在一起(间隔)的排列问题,称之为“间隔排列”问题.解决这类问题,常用“插空法”,其方法是先排不需要间隔的元素,再将需要间隔的元素通过插空的方式插进来即可.例2 在一条南北方向的步行街同侧有8块广告牌,牌的底色可选用红、蓝两种颜色.若只要求相邻两块牌的底色不都为红色,则不同的配色方案共有( )A.55.B.56.C.46.D.45.解:没有红牌,一种方法;有一块红牌,让其插空,有18C 种方法;有二块红牌,让其插空,有27C 种方法;有三块红牌,让其插空,有36C 种方法;有四块红牌,让其插空,有45C 种方法;共有方法12348765155C C C C ++++=种. 说明:对于不相邻问题,常用“插空法”(特殊元素后考虑).例3 某仪表显示屏上一排有7个小孔,每个小孔可显示出0或1,若每次显示其中三个孔,但相邻的两孔不能同时显示,则这显示屏可以显示的不同信号的种数有 种.解:四个孔不亮,三个孔亮,相当于三个亮着的孔在四个不亮的孔之间插空,故有35222C ⨯⨯⨯=80种方法.三. 部分不同元素定序与部分相同元素排列问题:部分不同元素在排列前后的顺序固定不变(不一定相邻)的排列问题,称之为“定序排列”问题.解决这类问题的基本方法有三种.(1)“消序法”(有些地方叫“整体法”),即若有m n +个元素排成一列,其中有m 个元素之间的排列顺序不变,将这m n +个元素任意排成一列,共有m nm n A ++种不同的排法,其中未定序的n 个元素排在某一特定位置的排列的个数有mm A 种排法,但只有一个排列是我们所需要的排列,因而共有m n m n m m A A ++种不同的排法.类似地还可推广到一般情形,如有有m n k ++个元素排成一列,其中有m 个元素之间的排列顺序不变,且另外k 个元素之间的排列顺序也不变,则共有m n k m n k m k m kA A A ++++中不同的算法. (2)逐一插空法:先将定序的元素进行排列,再将其它元素逐一插入这组元素两端及中间.(3)优序法:先将所有位置中按“特殊元素”个数选出若干位置,并把这些特殊元素按规定顺序排上去,再将普通元素在其余位置上全排列.例4 若5男5女排成一排,按下列要求各有多少种排法(1)男女相间;(2)女生按指定顺序排列.解:(1)先将男生排好,有55A 种排法;再将5名女生插在男生之间的6个“空挡”(包括两端)中,有552A 种排法.故本题的排法有5555228800N A A =⋅=(种); (2)方法1(消序法):10510105530240A N A A ===; 方法2(逐一插空法):5个女生按序排列,有1中方法,5个男生逐个插空,有6,7,8,9,10种方法,共有67891030240⨯⨯⨯⨯=种方法.方法3(优序法):设想有10个位置,先将男生排在其中的任意5个位置上,有510A 种排法;余下的5个位置排女生,因为女生的顺序已经指定,所以她们只有一种排法.故本题的结论为510130240N A =⨯=(种). 例5 今有2本相同的语文书,3本相同的数学书,4本相同的英语书排成一排,有多少种不同的排法?解:(消序法)有992342341260A A A A =种. 例6 一个楼梯共18个台阶,12步登完,可一步登一个台阶,也可一步登两个台阶,一共有多少种不同的走法?解:根据题意,要想12步登完,只能6个一步登一个台阶,6个一步登二个台阶.因此,把问题转化为“相同元素”的排列问题.因此有12126666924A A A =(种). 点评:对于部分不同元素定序排列以及相同元素的排列问题,可用优序法.【随堂练习】1.从5位同学中选派4位同学在星期五、星期六、星期日参加公益活动,每人一天,要求星期五有2人参加,星期六、星期日各有1人参加,则不同的选派方法共有( B )A .40种B .60种C .100种D .120种2.安排3名支教老师去6所学校任教,每校至多2人,则不同的分配方案共有210种.(用数字作答)3.用数字0,1,2,3,4,5组成没有重复数字,且比20000大的五位偶数有( )A.288个B.240个C.144个D.126个4.如图,用6种不同的颜色给图中的4个格子涂色,每个格子涂一种颜色,要求最多使用3种颜色且相邻的两个格子颜色不同,则不同的涂色方法共有 390 种(用数字作答).5.某校开设9门课程供学生选修,其中,,A B C 三门由于上课时间相同,至多选一门,学校规定每位同学选修4门,共有 75 种不同选修方案.(用数值作答)6.从班委会5名成员中选出3名,分别担任班级学习委员、文娱委员与体育委员,其中甲、乙二人不能担任文娱委员,则不同的选法共有 36 种.(用数字作答)【课后作业】1.某校安排5个班到4个工厂进行社会实践,每个班去一个工厂,每个工厂至少安排一个班,不同的安排方法共有240种.(用数字作答)2.将数字1,2,3,4,5,6拼成一列,记第i 个数为i a (i =1,2,…,6),若11a ≠,33a ≠,55a ≠,135a a a <<,则不同的排列方法有 30 种(用数字作答).解:分两步:(1)先排1a ,3a ,5a ,当1a =2时,有2种;当1a =3时,有2种;当1a =4时,有1种,共有5种;(2)再排2a ,4a ,6a ,共有633=A 种,故不同的排列方法种数为5×6=30,填30.3.中两支围棋队各由8人组成,按事先排好的次序出场进行围棋擂台赛,双方先由1号队员比赛,负者被淘汰,胜者再与负方2号队员比赛,……,直到有一方全部被淘汰为止,另一方获胜,形成一个比赛过程.(1)已知中方动用了5名队员,取得了胜利,问这样的比赛过程有多少种?(2)求由中方第8位选手获得最后胜利的概率.解:(1)中方胜利时,双方共有8+5=13名队员参加了比赛,将他们按淘汰的顺序从左向右排列,则最右为中方5号,右第二个为方8号,从右第三个至最左,共11个位置上,有4个位置排中方队员,其余排方队员,每一种排法,对应一种比赛结果,故共有411330C =种.(2)714816415C p C ==. 4. 若7位同学站成一排(1)甲、乙两同学不能相邻的排法共有多少种?(2)甲、乙和丙三个同学都不能相邻的排法共有多少种?解:(1)解法一:(排除法)3600226677=⋅-A A A ;解法二:(插空法)先将其余五个同学排好有55A 种方法,此时他们留下六个位置(就称为“空”吧),再将甲、乙同学分别插入这六个位置(空)有26A 种方法,所以一共有36002655=A A 种方法. (2)先将其余四个同学排好有44A 种方法,此时他们留下五个“空”,再将甲、乙和丙三个同学分别插入这五个“空”有35A 种方法,所以一共有44A 35A =1440种. 【课后记】第二课时 排列组合问题的解题方法(二)教学目标:掌握几类特殊的排列问题的解决技巧.教学重点:掌握“错位排列”、“圆桌排列”、“转化命题”等问题的解题技巧.教学难点:如何应用“技巧”解题.教学过程:【例析技巧】四.错位排列问题n 个不同元素排成一排,有m 个元素(m n ≤)不排在相应位置的排列种数共有: 112233123(1)n n n n m m n m n m n m n m n m n m A C A C A C A C A ---------+-+⋅⋅⋅+-.当n m =时,规定000!1A ==,这个公式亦成立.例7 五封标号为1~5的信放进5个编号为1~5的信笺里面,若信的编号与信笺的编号都不相同,一共有多少种不同放法.解:这是著名的信封问题,很多著名数学家都研究过.瑞士数学家欧拉按一般情况给出了一个递推公式:用A 、B 、C ……表示写着n 位友人名字的信封,a 、b 、c ……表示n 份相应的写好的信.把错装的总数记为()f n .假设把a 错装进B 里了,包含着这个错误的一切错装法分两类:(1)b 错装进A 里,这时每种错装的其余部分都与a 、b 、A 、B 无关,应有(2)f n -种错装法.(2)b 错装进A 、B 之外的信封,这时的装信工作实际是把(除a 之外的)信纸b 、c ……装入(除B 之外的)1n -个信封A 、C ……,显然这种错装方法有(1)f n -种.错装的其余部分都与a 、b 、A 、B 无关,应有(2)f n -种错装法.总之在a 错装入B 的错误之下,共有错装法(1)(2)f n f n -+-种.装入D ……的2n -种错误之下,同样都有(1)(2)f n f n -+-种错装法.因此()(1)[(1)(2)]f n n f n f n =--+-,显然(1)0f =,(2)1f =.由此可得(5)44f =.注意:用容斥原理亦可解决此题.普遍结论为错排公式1:1111()![1(1)]1!2!3!!n f n n n =-+-+⋅⋅⋅+-. 错排递推公式2: ()(1)[(1)(2)]f n n f n f n =--+-错排公式3:112233123(1)n n n n m m n m n m n m n m n m n m A C A C A C A C A ---------+-+⋅⋅⋅+-例8 有5个人站成一排,其中A 不站第一位,B 不站第二位,C 不站第三位,D 不站第四位,E 不站第五位,共有多少种不同的站法.解析:上面两例实际上可以看成n 个不同元素中有m (m ≤n )错位排列的问题. 而这个问题是其特殊情况,即全错位排列问题.共有514233241505545352515044A C A C A C A C A C A -+-+-=种(注意000!1A ==)例9 同室四人各写一贺年卡,先集中起来.然后每人从中拿一别人送出的贺年卡.则四贺年卡不同的分配方式有A.6种B.9种C.11种D.23种解析:由上面公式得:4132231404434241409A C A C A C A C A -+-+=种,∴选择B 答案.因此可得到全错位排列的公式:n 个不同元素排成一排,第一个元素不在第一位,第二个元素不在第二位,……,第n 个元素不在第n 位的排列数为:11223301230(1)n n n n n n n n n n n n n n A C A C A C A C A -------+-+⋅⋅⋅+-这实际上是公式112233123(1)n n n n m m n m n m n m n m n m n m A C A C A C A C A ---------+-+⋅⋅⋅+-的特殊情况.这个公式很有用,只要有特殊元素不站特殊位置的问题,都可以用这个公式很快得到解决,希望这个公式对大家有所帮助.五. 圆桌排列从n 个不同元素中不重复的取出m (1m n ≤≤)个元素排在一个圆周上,叫做这n 个不同元素的圆排列.如果一个m -圆排列旋转可以得到另一个m -圆排列,则认为这两个圆排列是相同的.特别的,当m n =时,n 个不同元素作成的圆排列总数为(1)!n -.证明:在圆周上任选一个位置排1a 有n 种排法,再选一个位置排2a 有1n -种排法,…,最后一个位置排n a 有1种排法.而这n 个人顺时针(或逆时针)挪动n 次位置都是同一种排列.所以共有!(1)!n n n=-种排法. 例10 有5对夫妇参加一场婚宴,他们被安排在一10个座位的圆桌就餐,但是婚礼操办者并不知道他们彼此之间的关系,只是随机安排座位。
排列组合解题方法排列组合题在高考试题中占据较大比例,或单独命题,或与概率内容相结合,由于排列组合题抽象性较强,解题思路灵活,方法多样,切入点多,学生在解题过程中往往容易出现思维遗漏、或重复的错误。
下面就是小编给大家带来的排列组合解题方法,希望大家喜欢!相离问题插空法主要用来解决 2 个或若干个不相邻元素的排列组合问题,是解决排列组合问题的常见方法之一。
它是指先把无位置要求,无条件限制的元素排列好,然后对有位置要求,受条件限制的元素进行整理,再将受条件限制的元素插入到已排列好的无条件限制元素的间隙或两端中。
例 1 在一张节目单中原有 6 个节目,若保持这些节目相对顺序不变,再添加进去 3 个节目,则所有不同的添加方法共有多少种?解析:该题若直接进行解答较为麻烦,此时可以借助相离问题插空法,可以使问题迎刃而解。
先将原来的6 个节目排列好,这时中间和两端有 7 个空位,然后用一个节目去插 7 个空位,有 A 种方法;接着再用另一个节目去插 8 个空位,有 A 种方法;将最后一个节目插入到 9 个空位中,有 A 种方法,由乘法原理得:所有不同的添加方法 AAA=504 种。
例 2 停车场划出一排 12 个停车位置,今有 8 辆车需要停放,要求空位置连在一起,不同的停车方法有多少种?解析:先排好 8 辆车有 A 种方法,要求空位置连在一起,则在每 2 辆之间及其两端的9 个空当中任选一个,将空位置插入其中有 C 种方法。
故共有 AC 种方法。
相邻问题捆绑法作为排列组合题最为常见的解法之一,就是在解决对于某几个元素相邻问题时,将相邻元素作为整体加以考虑,视为一个“大”元素参与排序,然后再单独对大元素内部各元素间的排列顺序进行一一分析排列。
例 3 有 6 名同学排成一排,其中甲、乙两人必须排在一起的不同排法有多少种?解析:由于甲、乙两人必须要排在一起,故可将甲、乙两人捆绑起来作为一个整体进行考虑,即将两人视为一人,再与其他四人进行全排列,则有 A 种排法,甲、乙两人之间有 A 种排法。
排列组合问题的求解策略
杨昌叶
求解排列组合的综合问题,一般是先选元素(组合),后排列,按元素的性质“分类”和按事件发生连续性过程“分步”,在计数时注意不重复,不遗漏。
常见的解题策略有以下几种:
1. 特殊位置(或元素)优先安排
例1. 从6人中选4人分别到巴黎、伦敦、悉尼、莫斯科四个城市游览,要求每个城市有一人游览,每人只游览一个城市,且这6人中,甲、乙两人不去巴黎游览,则不同的选择方案共有( )
A. 300种
B. 240种
C. 144种
D. 96种
(05年福建卷)
解析:因为甲、乙不去巴黎,故从其余4人选1人去巴黎有C 41
种方法,再从剩余5人中选3人去其余3市,有A 53种方法,所以共有方案C A 4153240=(种)
,故选(B )。
2. 合理分类与准确分步
例2. 从集合{O ,P ,Q ,R ,S}与{0,1,2,3,4,5,6,7,8,9}中各任取2个元素排成一排(字母和数字均不能重复),每排中字母P 、Q 和数字0至多只出现一个的不同排法种数是____________(用数字作答)。
(05年浙江卷)
解析:(1)每排中只有数字0的排法有C C A 91
32
44
; (2)每排中只有字母P 或Q 的排法都有C C A 31
92
44
; (3)每排中无数字0,字母P 、Q 的排法有C C A 32
92
44。
所以不同的排法种数共有:
()C C C C C C A 91323192329244
28424++=
3. 排列、组合混合问题先选元(组合)后排列
例3. 四个不同的小球放入编号为1,2,3,4的四个盒子中,则恰有一个空盒的放法共_________________种(用数字作答)。
(全国高考)
解析:先将4个球分成3组,每组至少1个(即必有一组为2个),分法有C 42
种,然后再将这3组球放入4个盒子中每盒最多装一组,则恰有一个空盒的放法种数为C A 4243144
=(种)。
4. 正难则反、等价转化
例4. 在由数字0,1,2,3,4,5所组成的没有重复数字的四位数中,不能被5整除的数共有_____________个。
(05年全国卷) 解析:用排除法解决。
(1)总的四位数有C A 5153
;
(2)个位数字为0的四位数有A 53;
(3)个位数字为5的四位数有C A 4142。
所以符合条件的四位数个数共有:
C A A C A 51535341423006048192--=--=
另解:直接求有4442
⨯⨯A 法(想一想,为什么?)
5. 相邻问题捆绑处理
例5. 四棱锥的8条棱代表8种不同的化工产品,有公共顶点的两条棱代表的化工产品放在同一仓库是危险的,没有公共顶点的两条棱代表的化工产品放在同一仓库是安全的,现打算用编号为①、②、③、④的4个仓库存放这8种化工产品,那么安全存放的不同放法种数为( )
A. 96
B. 48
C. 24
D. 0
(05年江苏卷)
解析:在四棱锥S ABCD -中
(1)先把安全的产品捆绑在一起有2种方法
①()()()()SA CD SB AD SC AB SD BC ,,,,,,,;
②()()()()SA BC SB CD SC AD SD AB ,,,,,,,。
(2)四组产品放在4个编号不同的仓库里有A 44
种,所以安全存放的方法共有:
22244844
A =⨯=(种)。
故选(B )。
6. 不相邻问题插空处理
例6. 用1,2,3,4,5,6,7,8组成没有重复数字的八位数,要求1与2相邻,3与4
相邻,5与6相邻,而7与8不相邻,这样的八位数共有________________个(用数字作答)。
(05年辽宁卷)
解析:此题是捆绑法和插空法的综合应用问题。
把相邻的两个数捆成一捆,分成四个空,
然后再将7与8插进空中有A 42种插法;而相邻的三捆都有A 22种排法,再它们之间又有A 33种
排序方法。
故这样的八位数共有:
A A A A A 2222223342
8612576=⨯⨯=(个)
7. 定序问题排除处理
例7. 在7名运动员中选4名运动员组成接力队,参加4100⨯接力赛,那么甲、乙两人都不跑中间两棒的安排方法共有多少种?
解析:先从7人中任选4人接力有A 74
种方法,排除甲和乙跑中间棒的221
63
A A 种方法,
但甲、乙二人都跑中间的减了两次,故再加上二人都跑中间棒的A A 2252
种方法,即
A A A A A 7421632252
2400-+=(种)
另解:直接求有A A 5252法(想一想,为什么?)
8. 分排问题直接处理
例8. 有两排座位,前排11个座位,后排12个座位,现安排2人就座,规定前排中间的3个座位不能坐,并且这2人不左右相邻,那么不同排法的种数是( )
A. 234
B. 346
C. 350
D. 363
(04年辽宁卷)
解析:在排列问题中,站若干排与站一排一样,故一共可坐的位子有20个,2个人就座
方法数为A 202
,还需排除两人左右相邻的情况,把可坐的20座位排成连续一行(一排末位B 与二排首位C 相接),任两个座位看成一个整体,即相邻的坐法有A A 1912
2,但这其中包括B 、C 相邻与E 、F (前排中间3座的左E 、右F )相邻,而这种相邻在实际中是不相邻的,还应
再加上222A 。
所以不同排法的种数为:
A A A A 2021912222
2346-+=
故选B 。
9. 构造模型
例9. 6本不同的书,按照以下要求处理,各有几种方法? (1)一堆一本,一堆两本,一堆三本; (2)甲得一本,乙得两本,丙得三本; (3)一人得一本,一人得二本,一人得三本; (4)平均分给甲、乙、丙三人;
(5)平均分成三堆。
解析:本问题中的每一小题都提出了一种类型问题,要搞清类型的归属。
(1)属非均匀分组问题,先在6本书中任取一本,作为一堆,有C 61
种取法,再从余下的5本书中任取2本作为一堆,有C 52种取法,最后余下的3本作为一堆有C 33种取法,故共
有分法:
C C C 615233
60=(种)
(2)属非均匀定向分配问题,与(1)同解,因每种分组方法仅对应一种分配方法,故也共有分法60种。
(3)属非均匀不定向分配问题,由(1)知分成三堆有60种,但每一种分组方法又有A 33
种不同的分配方案,故共有分法6036033
A =(种)。
(4)属均匀定向分配问题,3个人一个一个地来取书,甲取有C 62种,乙再去取有C 42
种,最后余下的归丙有C 22种,故共有
C C C 624222
90=(种)
(5)属均匀分组问题,把6本不同的书分成三堆,每堆2本与把6本不同的书分给甲、乙、丙三,每人2本的区别在于后者相当于把6本不同的书,平均分成三堆后再把分得的三堆书分给甲、乙、丙三个人,因此设把6本不同的书平均分成三堆的方法有x 种,由(4)知
把6本不同的书分给甲、乙、丙三人,每人2本的方法有C C C 624222
种。
所以xA C C C 33624222
= 则x =15(种)
10. 用“树型”图处理
例10. 设ABCDEF 为正六边形,一只青蛙开始在顶点A 处,它每次可随意地跳到相邻两个顶点之一,若在5次之内跳到D 点,则停止跳动,若在5次之内不能到达D 点,则跳完5次也停止跳动,那么这只青蛙从开始到停止,可能出现的不同跳法的种数是( )
A. 6
B. 8
C. 16
D. 26
(05年贵州)
解析:青蛙从A点开始,往相邻两个顶点B和F跳到D点的次数是相同的,又青蛙第一次往B方向跳的跳法可用“树型”图表示如下:
由图知有13种跳法,所以共有跳法2×13=26(种),故选(D),此种方法是解决数量较小排列问题的常用方法之一,优点是把抽象变为直观。