计数原理与排列组合

概念解读

1．两个计数原理(分清是应用“加法”原理，还是“乘法”原理或是两者同时用)

完成一件事的策略

完成这件事共有的方法

分类加法计数原理

有两类不同方案，第1类方案中有m种不同的方法，第2类方案中有n种不同的方法

N＝m＋n种不同的方法

分步乘法计数原理

需要两个步骤，第1步有m种不同的方法，第2步有n种不同的方法

N＝mn种不同的方法

2.排列（ A-代表-Arrangement--排列数 ）

3．组合（ C-代表-Combination--组合数 ）

组合的定义

从n个不同元素中，任意取出m(m≤n)个元素并成一组，叫作一个组合

组合数的定义

从n个不同元素中取出m(m≤n)个元素后，所有组合的个数

组合数公式

Cn(m)＝m(m)＝m！(n(n－1)(n－2)…(n－m＋1))＝m！(n－m)！(n！)

组合数的性质

(1)Cn(m)＝Cn(n－m)；(2)Cn(m)＋Cn(m－1)＝Cn＋1(m)

4排列问题技法感悟　求解有限制条件排列问题的主要方法

直接法

分类法

选定一个适当的分类标准，将要完成的事件分成几个类型，分别计算每个类型中的排列数，再由分类加法计数原理得出总数

分步法

选定一个适当的标准，将事件分成几个步骤来完成，分别计算出各步骤的排列数，再由分步乘法计数原理得出总数

捆绑法

相邻问题捆绑处理，即可以把相邻元素看作一个整体与其他元素进行排列，同时注意捆绑元素的内部排列

插空法

不相邻问题插空处理，即先考虑不受限制的元素的排列，再将不相邻的元素插在前面元素排列的空中

除法

对于定序问题，可先不考虑顺序限制，排列后，再除以已定元素的全排列

间接法

对于分类过多的问题，按正难则反，等价转化的方法

5组合技法感悟　两类含有附加条件的组合问题的解法

(1)“含有”或“不含有”某些元素的组合题型：若“含”，则先将这些元素取出，再由另外元素补足；若“不含”，则先将这些元素剔除，再从剩下的元素中去选取．

(2)“至少”或“最多”含有几个元素的组合题型：解这类题目必须十分重视“至少”与“最多”这两个关键词的含义，谨防重复与漏解．用直接法或间接法都可以求解，通常用直接法分类复杂时，用间接法求解．

6排列与组合问题的综合应用　

易错提醒　解排列组合综合应用问题的思路

解排列组合综合应用题要从“分析”“分辨”“分类”“分步”的角度入手．“分析”就是找出题目的条件、结论，哪些是“元素”，哪些是“位置”；“分辨”就是辨别是排列还是组合，对某些元素的位置有无限制等；“分类”就是对于较复杂的应用题中的元素往往分成互相排斥的几类，然后逐类解决；“分步”就是把问题化成几个互相联系的步骤，而每一步都是简单的排列组合问题，然后逐步解决．

1．区分某一问题是排列问题还是组合问题的关键与方法

(1)关键：看所选的元素与顺序是否有关．

(2)方法：交换某两个元素的位置，判断对结果是否产生影响，产生影响的是排列问题，否则是组合问题．

2．与组合数相关的几个公式

(1)Cn(0)＋Cn(1)＋…＋Cn(n)＝2n.    (2)Cn(m)＋Cn－1(m)＋…＋Cm＋1(m)＋Cm(m)＝Cn＋1(m＋1).    (3)kCn(k)＝nCn－1(k－1).

3．解决有限制条件排列问题的策略

(1)根据特殊元素(位置)优先安排进行分步，即先安排特殊元素或特殊位置．

(2)根据特殊元素当选数量或特殊位置由谁来占进行分类．

4．组合问题的常见题型及解题思路

(1)常见题型：一般有选派问题、抽样问题、图形问题、集合问题、分组问题等．

(2)解题思路：①分清问题是否为组合问题；②对较复杂的组合问题，要搞清是“分类”还是“分步”，一般是先整体分类，然后局部分步，将复杂问题通过两个原理化归为简单问题．

5．分组、分配问题的求解策略

(1)对不同元素的分配问题．

①对于整体均分，解题时要注意分组后，不管它们的顺序如何，都是一种情况，所以分组后一定要除以An(n)(n为均分的组数)，避免重复计数．

②对于部分均分，解题时注意重复的次数是均匀分组的阶乘数，即若有m组元素个数相等，则分组时应除以m！，分组过程中有几个这样的均匀分组，就要除以几个这样的全排列数．

③对于不等分组，只需先分组，后排列，注意分组时任何组中元素的个数都不相等，所以不需要除以全排列数．

(2)对于相同元素的“分配”问题，常用方法是采用“隔板法”．

6．注意易失误点

(1)分类要全，以免遗漏．

(2)插空时要数清插空的个数，捆绑时要注意捆绑后元素的个数及要注意相邻元素的排列数．

(3)用间接法求解时，事件的反面情况要准确．

方法解读   问题讲解

一 插空法（不邻问题）

某些元素不相邻的排列组合题，即不邻问题，可采用插空法，即在解决对于某几个元素要求不相邻的问题时，先将其它元素排好，再将指定的不相邻的元素插入已排好元素的间隙或两端位置，从而将问题解决的策略。用这种方法解题思路清晰、简便易懂。

例1：把1，2，3，4，5组成没有重复数字且数字 1，2不相邻的五位数，则所有不同排法有多少种？

解析：本题直接解答较为麻烦，因为可先将 3，4，5三个元素排定，共有种排法，然后再将 1，2插入四个空位共有种排法，故由乘法原理得，所有不同的五位数有种。

（2）例2：在一张节目单中原有六个节目，若保持这些节目的相对顺序不变，再添加进去三个节目，则所有不同的添加方法共有多少种？

解析： -o - o - o - o - o - o - ，即六个节目算上前后共有七个空位，那么加上的第一个节目则有种方法； 此时有七个节目， 再用第二个节目去插八个空位有种方法； 此时有八个节目， 用最后一个节目去插九个空位有种方法。由乘法原理得，所有不同的添加方法为：种。

基本题型

基本题型为：n个相同元素，不同个m组，每组至少有一个元素；则只需在 n 个元素的n-1 个间隙中放置 m-1 块隔板把它隔成 m 份，求共有多少种不同方法？

其解题思路为：将 n 个相同的元素排成一行， n 个元素之间出现了（ n-1 ）个空档，现在我们用（ m-1 ）个 “档板 ”插入（ n-1 ）个空档中，就把 n 个元素隔成有序的 m 份，每个组依次按组序号分到对应位置的几个元素（可能是 1 个、2 个、 3 个、 4 个、 ….），这样不同的插入办法就对应着 n 个相同的元素分到 m 组的一种分法，这种借助于这样的虚拟 “档板 ”分配元素的方法称之为插板法。

例题：共有 10 完全相同的球分到 7 个班里，每个班至少要分到一个球，问有几种不同分法？

解析：我们可以将 10 个相同的球排成一行， 10 个球之间出现了 9 个空隙，现在我们用 6 个档板 ”插入这 9个空隙中，就 “把 10 个球隔成有序的 7 份，每个班级依次按班级序号分到对应位置的几个球（可能是 1 个、2 个、 3 个、 4 个），这样，借助于虚拟 “档板 ”就可以把 10 个球分到了 7 个班中。

基本题型的变形

（1）变形1：有 n 个相同的元素，要求分到 m 组中，问有多少种不同的分法？

解题思路：这种问题是允许有些组中分到的元素为 “0”，也就是组中可以为空的。对于这样的题，我们就首先将每组都填上 1 个，这样所要元素总数就 m 个，问题也就是转变成将（ n+m ）个元素分到 m 组，并且每组至少分到一个的问题，也就可以用插板法来解决。

例题：有 8 个相同的球放到三个不同的盒子里，共有（ ）种不同方法 。

解答：题目允许盒子有空，则需要每个组添加 1 个，则球的总数为 8+3 ×1=11，此题就有 C（10 ，2） =45（种）分法了。（两块板放一起C(9,2) + 9 =45）

（2）变形2：有 n 个相同的元素，要求分到 m 组，要求各组中分到的元素至少某个确定值 S（ s>1，且每组的 s值可以不同） ，问有多少种不同的分法？

解题思路： 这种问题是要求组中分到的元素不能少某个确定值 s，各组分到的不是至少为一个了。 对于这样的题，我们就首先将各组都填满，即各组就填上对应的确定值 s 那么多个，这样就满足了题目中要求的最起码的条件，之后我们再分剩下的球。这样这个问题就转变为上面提到的变形1的问题了，也就可以用插板法来解决。

例题：15 个相同的球放入编号为 1、2、 3 的盒子内，盒内球数不少于编号数，有几种不同的放法？

解析：编号 1：至少 1 个，符合要求；

编号 2：至少 2 个：需预先添加 1 个球，则总数 -1 ；

编号 3：至少 3 个，需预先添加 2 个，才能满足条件，后面添加一个，则总数 -2 ；

则球总数 15-1-2=12 个放进 3 个盒子里，所以 C（11，2）=55 （种）。

所谓捆绑法，指在解决对于某几个元素要求相邻问题时，先整体考虑，将相邻元素视作一个整体参与排序，然后再单独考虑这个整体内部各元素间顺序。注意：其首要特点是相邻，其次捆绑法一般都应用在不同物体的排序问题中。

例题：6个不同的球放到5个不同的盒子中，要求每个盒子至少放一个球，一共有多少种方法?

解答：根据题目要求，则其中一个盒子必须得放 2 个，其他每个盒子放 1 个球，所以从 6 个球中挑出 2 个球看成一个整体，则有，这个整体和剩下 4 个球放入 5 个盒子里，则有。方法是。

注意主客体，谁是有选择的权利，谁没有选择的权利。（本例中，实习生有选择的权利，并且每个人都有7种选择）

分堆问题，平均分堆问题，局部平均分堆问题

排列组合问题从解法看，大致有以下几种：

(1) 有附加条件的排列组合问题，大多需要分类讨论的方法，注意分类时应不重不漏；(2)排列与组合的混合型问题，用分类加法或分步乘法计数原理解决；(3)元素相邻，可以看作是一个整体的方法；(4)元素不相邻，可以利用插空法；(5)间接法，把不符合条件的排列与组合剔除掉；(6)穷举法，把不符合条件的所有排列或组合一一写出来 。

二十二 四色原理（涂色问题）

如图所示的五个区域中，要求在每一个区域只涂一种颜色，相邻区域所涂颜色不同，现有四种颜色可供选择，则不同的涂色方法种数为（　　）

A．64 B．72 C．84 D．96

【分析】每个区域只涂一种颜色，相邻区域颜色不相同，然后分类研究，A、C不同色；A、C同色两大类．

【解答】解：分两种情况：

（1）A、C不同色，先涂A有4种，C有3种，E有2种，B、D有1种，有4×3×2＝24种；

（2）A、C同色，先涂A有4种，E有3种，还有2种，B、D各有1种，有4×3×2×2＝48种．

共有72种，故选：B．

【点评】本题考查排列组合的实际应用，区域涂色、种植花草作物是一类题目．分类要全要细．

四色定理的本质正是二维平面的固有属性，即平面内不可出现交叉而没有公共点的两条直线。很多人证明了二维平面内无法构造五个或五个以上两两相连区域，但却没有将其上升到逻辑关系和二维固有属性的层面，以致出现了很多伪反例。不过这些恰恰是对图论严密性的考证和发展推动。