排列组合(加乘、排列、组合、捆绑、插空、隔板)

1、计数专题学习目标1 .正确理解“标数”法计算路径数目；2 .正确理解“加法原理”、“乘法原理”的意义和运用场景；3 .正确理解“排列”、“组合”的意义、区别和计算公式；4 .正确掌握“优选法” “捆绑法”、“插空法”、“隔板法”这些排列组合解题技巧, 理解各种排列组合解题技巧的原理，所解决的问题类型及其解题方法；一.标数法例题：在左下图中，从 A点沿实线走最短路径到 B点，共有多少条不同路线?分析与解：题目要求从左下向右上走，所以走到任一点，例如右上图中的D点，不是经过左边的 E点，就是经过下边的 F点。如果到E点有a种走法（此处a = 6）,到F点有b种走法（此处b=4）,根 据加法原理，到

2、 D点就有（a+b）种走法（此处为6 + 4=10）。我们可以从左下角 A点开始，按加法原 理，依次向上、向右填上到各点的走法数（见右上图），最后得到共有35条不同路线。二.加乘原理加法原理：分情况、分类计数；乘法原理：分步骤完成，各步骤单独计数，再连乘；加乘混合：加法、乘法混合使用；（1） 一个步骤内有多种情况时，在计算本步骤时用加法，再总体用乘法计算出所有情况；（2）总体分几种情况，分别计算各种情况时分步骤用乘法，再将各种情况汇总用加法加法原理与乘法原理的区别：乘法原理和加法原理是两个重要而常用的计数法则，在应用时一定要注意 它们的区别。乘法原理是把一件事 分几步完成，这几步缺一不可，所以

3、完成任务的不同方法数等于各步 方法数的乘积；加法原理是把完成一件事的方法分成几类，每一类中的任何一种方法都能完成任务（一步完成任务），所以完成任务的不同方法数等于各类方法数之和。例题：由A村去B村有2条路可走，由B村去C村有4条路可走，问从 A村经B村去C村，共有多少种不同的走法?三.排列组合排列：有顺序要求(交换顺序，就产生新的计数)乘法原理；A52=5%从n个不同的元素中取出 m (mEn)个元素，按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列.(1)两个排列相同，指的是两个排列的元素完全相同，并且元素的排列顺序也相同.(2)如果两个排列中，元素不完全相同，它们是不同的

4、排列；(3)如果两个排列中，虽然元素完全相同，但元素的排列顺序不同，它们也是不同的排列.计算：乘法原理：从n个不同元素中取出 m个元素的排列数是n(n1) (n-2) i|(n-m+1),即Pm =n(n 1)(n2)| Knm+1),这里，mEn,且等号右边从n开始，共有m个因数相乘。组合：无顺序要求(交换顺序，不产生新的计数)除法原理；C52= (5M) + (2X)从n个不同元素中取出mj(mWn)元素组成一组不计较组内各元素的次序，叫做从n个不同元素中取出m个元素的一个组合.(1)从排列和组合的定义可以知道，排列与元素的顺序有关，而组合与顺序无关.(2)如果两个组合中，元素不完全相同，

5、它们是不同的组合；(3)如果两个组合中的元素完全相同，那么不管元素的顺序如何，都是相同的组合.计算：除法原理：从n个不同元素中取出 m个元素(mWn)的所有组合的个数，叫做从 n个不同元素中 取出m个不同元素的组合数.记作onmo一般地，求从n个不同元素中取出的 m个元素的排列数Pmn可分成以下两步：第一步：从n个不同元素中取出m个元素组成一组，共有 Cnm种方法；第二步：将每一个组合中的 m个元素进行全排列，共有 Pm种排法.根据乘法原理，得到pm=cm p二.因此，组合数cnm4=n(n-1 :n：2) "I(n-m+1pmmm，( m 1) .(m-2)川 3 2 1(运用除法

6、，将元素完全相同，元素顺序不同的多种排列合并成一种组合).【例1】 小新、阿呆等七个同学照像，分别求出在下列条件下有多少种站法？(1)七个人排成一排；(2)七个人排成一排，小新必须站在中间.(3)七个人排成一排，小新、阿呆必须有一人站在中间.(4)七个人排成一排，小新、阿呆必须都站在两边.(5)七个人排成一排，小新、阿呆都没有站在边上.(6)七个人战成两排，前排三人，后排四人.(7)七个人战成两排，前排三人，后排四人.小新、阿呆不在同一排。(1) P77 =5040 (种)。(2)只需排其余6个人站剩下的6个位置.P66 =720 (种).(3)先确定中间的位置站谁，冉排剩下的6个位置.2 X

7、P66 =1440(种).(4)先排两边，再排剩下的 5个位置，其中两边的小新和阿呆还可以互换位置.2父傍=240 (种).(5)先排两边，从除小新、阿呆之外的5个人中选2人，再排剩下的5个人，P52Mp5 =2400 (种).(6)七个人排成一排时，7个位置就是各不相同的.现在排成两排，不管前后排各有几个人，7个位置还是各不相同的，所以本题实质就是 7个元素的全排列.P7 =5040 (种).(7)可以分为两类情况：“小新在前，阿呆在后”和“小新在前，阿呆在后”，两种情况是对等的，所以只要 求出其中一种的排法数，再乘以 2即可.4X3xp5 x2=2880(种).排队问题，一般先考虑特殊情况

8、再去全排 列。【巩固】现有男同学3人，女同学4人(女同学中有一人叫王红)，从中选出男女同学各 2人，分别参加数 学、英语、音乐、美术四个兴趣小组：(1)共有多少种选法？ (2)其中参加美术小组的是女同学的选法有多少种(3)参加数学小组的不是女同学王红的选法有多少种？(4)参加数学小组的不是女同学王红，且参加美术小组的是女同学的选法有多少种？3 24 3(1)从3个男同学中选出2人，有3-2 =3种选法。从4个女同学中选出2人，有43 =6种选法。在四个人确定的情况下，参加四个不同的小组有4>><2X1=24种选法。3X6X24=432,共有432种选法。(2)在四个人确定的情

9、况下，参加美术小组的是女同学时有2>X2X=12种选法。3X6X12=216 ,所以其中参加美术小组的是女同学的选法有216种。(3)考虑参加数学小组的是王红时的选法，此时的问题相当于从3个男同学中选出2人，从3个女同学中选出1人，3个人参加3个小组时的选法。3X3 4X2X1=54,所以参加数学小组的是王红时的选法 有54种，432-54=378 ,所以参加数学小组的不是女同学王红的选法有378种。(4)考虑参加数学小组的是王红且参加美术小组的是女同学时的选法，此时的问题相当于从3个男同学中选出2人参加两个不同的小组，从 3个女同学中选出1人参加美术小组时的选法。3X24=18,所以参

10、加数学小组的是王红且参加美术小组的是女同学时的选法有18种，216-18=198，所以参加数学小组的不是女同学王红，且参加美术小组的是女同学的选法有198种。四.优选法优选法：对于问题中的特殊元素、特殊位置要优先安排确定。在操作时，针对实际问题，有时 “元素优先”，有时“位置优先”。注意：看特殊，分步、分类，限制完，自由排，注意“ 0”。难点：不管是位置优先还是元素优先，都要看清是分类还是分步来解决问题；注意“0”，题目中往往对于“0”有暗含的限制条件。例题.由数字1、2、3、4、5组成没有重复数字的五位数，其中小于 50000的偶数共有多少个？解析一：利用位置优先方法。偶数则要求个位为偶数，

11、小于50000则首位要小于5。：第一步，首先看个位，从2个偶数中选择有C12种选法；第二步，看首位，从个数上已选数字和5之外的数字选，则有C13种选法；第三步，对于剩下的三个位置没有限制，则可以随意选择剩下的三 个数字排上去，则有 A33种选法。根据乘法计数原则，共有：C12XC13 W33=36。解析二：利用元素优先方法。第一步，从数字2、4中选一个放在个位上，有 C12种选法；第二步，从个数上已选数字和 5之外的数字选一个放在首位上，则有 C13种选法；第三步，对于剩下的三个数字没有限制，则可以随意安排到剩下的三个数位上去，则有 A33种选法。根据乘法计数原则，共有： C12 >C1

12、3 XA44=36 。五.“捆绑法”捆绑法：用于解决"相邻问题”，即在解决对于某几个元素 要求相邻的问题时，先将其"捆绑"后整体考 虑，也就是将相邻元素视作"一个"大元素进行排序，然后再考虑大元素内部各元素间排列顺序 的解题策略。注意：运用捆绑法解决排列组合问题时，一定要注意“捆绑”起来的大元素内部的顺序问题。解题过程是"先捆绑，再排列”。例题：若有A、B、C、D、E五个人排队，要求 A和B两个人必须站在相邻位置，则有多少排队方法？【解析】：题目要求 A和B两个人必须排在一起，首先将 A和B两个人"捆绑"，视其为&

13、quot;一个人"，也即 对"A, B"、C、D、E"四个人"进行排列，有 种排法。又因为捆绑在一起的 A、B两人也要排序，有 种排法。根据分步乘法原理，总的排法有 种。六.“插空法”插空法：用于解决"不邻问题”，即在解决对于某几个元素 要求不相邻的问题时，先将其它元素排好， 再将指定的不相邻的元素插入已排好元素的间隙或两端位置，从而将问题解决的策略。注意：运用插空法解决排列组合问题时，一定要注意插空位置包括先排好元素"中间空位"和"两端空位”。解题过程是"先排列，再插空"。例题：若有

14、A、B、C、D、E五个人排队，要求 A和B两个人必须不站在一起，则有多少排队方法？【解析】：题目要求 A和B两个人必须隔开。首先将 C、D、E三个人排列，有 种排法；若排成D C E,则D、C、E"中间"和"两端"共有四个空位置，也即是：-D C E ,此时可将A、B两人插到四个空位置中的任意两个位置，有种插法。由乘法原理，共有排队方法：<七.“隔板法”（插板法）隔板法：有n个相同的元素，要求分到 m组中，并且要求每组中至少有一个元素问有多少种分法?基本思路：将n个相同的元素排成一行，n个元素之间出现了( n-1)个空档，现在我们用(m-1 ) 个

15、“档板”插入n-1)个空档中，就把n个元素隔成有序的 m份，每个组依次按组序号分 到对应位置的几个元素(可能是1个、2个、3个、4个、.)，这样不同的插入办法就对应着n个相同的元素分到 m组的一种分法，这种借助于这样的虚拟“档板”分配元素的方 法称之为插板法。【基本题型】【例1】共有10完全相同的球分到7个班里，要求每个班至少要分到一个球，问有几种不同分法？解析一：我们首先用常规方法。若想将 10个球分到7个班里，球的分法共三类：第一类：有3个班每个班分到2个球，其余4个班每班分到1个球。这样，第一步，我们从 7个 班中选出3个班，每个班分2个球；第二步，从剩下的 4个班中选4个班，每班分1球

16、。 其分法种数为：C (7, 3) *C (4, 4) =35注明：由于排版的关系，我用 C (n, m)和A (n, m)代替原来的组合与排列公式。第二类：有1个班分到3个球，1个班分到2个球，其余5个班每班分到1个球。其分法种数： C (7, 1) *C (6, 1) *C (5, 5) =42第三类：有1个班分到4个球，其余的6个班每班分到1个球。其分法种数：C (7, 1) * C (6, 6) =7所以，10个球分给7个班，每班至少一个球的分法种数为：35+42+7=87 (种)。解析二：从上面的解题过程可以看出，用常规方法解这类题，需要分类计算，计算过程繁琐。并且如 果元素个数较多

17、的话处理起来就变得十分的困难了。因此我们需要寻求一种新的方法解决问 题，也就是插板法。我们可以将10个相同的球排成一行，10个球之间出现了 9个空隙，现在我们用6个档板”插 入这9个空隙中，就“把10个球隔成有序的7份，每个班级依次按班级序号分到对应位置的几 个球(可能是1个、2个、3个、4个)，这样，借助于虚拟“档板”就可以把10个球分到了 7 个班中。由上述分析可知，原问题就可以转化成：在 9个空档之中插入6个“档板” 6个档板可把球分为 7组)的问题，这是一个很简单的组合问题，其方法种数为：C (9, 6) =84【总结】：对于这种要求每组元素至少要分到一个的情况，则只需在 n个元素的n

18、-1个间隙中放置m-1块隔板把它隔成 m份即可，共有C (n-1 , m-1 )种不同方法【注意】： 这种插板法解决相同元素分到不同组的问题非常简单，但同时也提醒各位考友，这类问题 模型适用前提相当严格，必须同时满足以下3个条件：（1）所有要分的元素须完全相同；（2）所要分的元素必须分完，决不允许有剩余；（3）参与分元素的每组至少分到 1个，决不允许出现分不到元素的组。这样对于很多的问题，是不能直接利用插板法解题的。但，可以通过一定的转变，将其变成符合上面3个条件的问题，这样就可以利用插板法解决，并且常常会产生意想不到的效果。【基本题型的变形（一）】题型：有n个相同的元素，要求分到 m组中，问

19、有多少种不同的分法？解题思路：这种问题是允许有些组中分到的元素为“0”，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上1个，这样所要元素总数就 m个，问题也就是转变成将（n+m）个元 素分到m组，并且每组至少分到一个的问题，也就可以用插板法来解决。【例2】有8个相同的球放到三个不同的盒子里，共有（）种不同方法.解析：这道题很多同学错选 C,错误的原因是直接套用“插板法”，而忽略了题中并没有说每个盒子至少要分到一个球，也就是可以出现空盒子。原题并不符合“插板法”的条件不过，此题只要我们多一个小变化，就可以将其转化为用“插板法”解题的类型了。我们可以人为地在每个盒子增加一个球，原有8个相同的球放到三个不同的盒子里这样这个问题就变成了， 11个相同的球