分类、分步计数原理,排列与组合.doc

加（*）号的知识点为了解内容，供学有余力的学生学习使用
一.考纲目标
两个计数原理的理解和应用；排列与组合的定义、计算公式，组合数的两个性质.
二.知识梳理
1分类计数原理：做一件事情，完成它可以有n类办法，在第一类办法中有种不同的方法，在第二类办法中有种不同的方法，……，在第n类办法中有种不同的方法那么完成这件事共有 种不同的方法
2分步计数原理：做一件事情，完成它需要分成n个步骤，做第一步有种不同的方法，做第二步有种不同的方法，……，做第n步有种不同的方法，那么完成这件事有 种不同的方法
3两个基本原理的作用：计算做一件事完成它的所有不同的方法种数
4两个基本原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”
5原理浅释
分类计数原理(加法原理)中，“完成一件事，有n类办法”，是说每种办法“互斥”，即每种方法都可以独立地完成这件事，同时他们之间没有重复也没有遗漏，进行分类时，要求各类办法彼此之间是相互排斥的，不论那一类办法中的哪一种方法，都能独立完成这件事，只有满足这个条件，才能直接用加法原理，否则不可以
分步计数原理(乘法原理)中，“完成一件事，需要分成n个步骤”，是说每个步骤都不足以完成这件事，这些步骤，彼此间也不能有重复和遗漏
如果完成一件事需要分成几个步骤，各步骤都不可缺少，需要依次完成所有步骤才能完成这件事，而各步要求相互独立，即相对于前一步的每一种方法，下一步都有m种不同的方法，那么完成这件事的方法数就可以直接用乘法原理
可以看出“分”是它们共同的特征，但是，分法却大不相同．
两个原理的公式是: ,
6．排列的概念：从个不同元素中，任取（）个元素（这里的被取元素各不相同）按照一定的顺序排成一列，叫做从个不同元素中取出个元素的一个排列
7．排列数的定义：从个不同元素中，任取（）个元素的所有排列的个数叫做从个元素中取出元素的排列数，用符号表示
8．排列数公式：（）
9.阶乘：表示正整数1到的连乘积，叫做的阶乘规定．
10．排列数的另一个计算公式：=
11.组合的概念：一般地，从个不同元素中取出个元素并成一组，叫做从个不同元素中取出个元素的一个组合
12．组合数的概念：从个不同元素中取出个元素的所有组合的个数，叫做从个不同元素中取出个元素的组合数．用符号表示．
13．组合数公式：或
14.组合数的性质1：．规定：；
15．组合数的性质2：＝+
16.解排列组合问题，首先要弄清一件事是“分类”还是“分步”完成，对于元素之间的关系，还要考虑“是有序”的还是“无序的”，也就是会正确使用分类计数原理和分步计数原理、排列定义和组合定义，其次，对一些复杂的带有附加条件的问题，需掌握以下几种常用的解题方法：
（1）特殊优先法：对于存在特殊元素或者特殊位置的排列组合问题，我们可以从这些特殊的东西入手，先解决特殊元素或特殊位置，再去解决其它元素或位置，这种解法叫做特殊优先法.例如：用0、1、2、3、4这5个数字，组成没有重复数字的三位数，其中偶数共有________个（答案：30个）
（2）科学分类法：对于较复杂的排列组合问题，由于情况繁多，因此要对各种不同情况，进行科学分类，以便有条不紊地进行解答，避免重复或遗漏现象发生例如：从6台原装计算机和5台组装计算机中任取5台，其中至少有原装与组装计算机各两台，则不同的选取法有_______种（答案：350）分组（堆）问题的六个模型：①有序不等分；②有序等分；③有序局部等分；④无序不等分；⑤无序等分；⑥无序局部等分；
（3）插空法：解决一些不相邻问题时，可以先排一些元素然后插入其余元素，使问题得以解决例如：7人站成一行，如果甲乙两人不相邻，则不同排法种数是______ (答案:3600)[来源:]
（4）捆绑法：相邻元素的排列，可以采用“整体到局部”的排法，即将相邻的元素当成“一个”元素进行排列，然后再局部排，例如：6名同学坐成一排，其中甲、乙必须坐在一起的不同坐法是________种（答案：240）
（5）排除法：从总体中排除不符合条件的方法数，这是一种间接解题的方法
b、排列组合应用题往往和代数、三角、立体几何、平面解析几何的某些知识联系，从而增加了问题的综合性，解答这类应用题时，要注意使用相关知识对答案进行取舍.例如：从集合{0，1，2，3，5，7，11}中任取3个元素分别作为直线方程Ax+By+C=0中的A、B、C，所得的经过坐标原点的直线有_________条（答案：30）
（6）剪截法（隔板法）：n个 相同小球放入m(m≤n)个盒子里,要求每个盒子里至少有一个小球的放法等价于n个相同小球串成一串从间隙里选m-1个结点剪成m段（插入m－1块隔板），有种方法.
（7）错位法：编号为1至n的n个小球放入编号为1到 n的n个盒子里,每个盒子放一个小球.要求小球与盒子的编号都不同,这种排列称为错位排列.特别当n=2, 3,4,5时的错位数各为1,2,9,44.
2个、3个、4个元素的错位排列容易计算。关于5个元素的错位排列的计算，可以用剔除法转化为2个、3个、4个元素的错位排列的问题：
①5个元素的全排列为：；
②剔除恰好有5对球盒同号1种、恰好有3对球盒同号(2个错位的) 种、恰好有2对球盒同号(3个错位的) 种、恰好有1对球盒同号(4个错位的) 种。
∴ 120-1---＝44.
用此法可以逐步计算：6个、7个、8个、……元素的错位排列问题。
三．考点逐个突破
1.分类、分步计数原理
例1 电视台在“欢乐今宵”节目中拿出两个信箱，其中存放着先后两次竞猜中成绩优秀的观众来信，甲信箱中有30封，乙信箱中有20封现由主持人抽奖确定幸运观众，若先确定一名幸运之星，再从两信箱中各确定一名幸运伙伴，有多少种不同的结果？
解：分两类：
（1）幸运之星在甲箱中抽，再在两箱中各定一名幸运伙伴，有30×29×20=17400种结果；
（2）幸运之星在乙箱中抽，同理有20×19×30=11400种结果因此共有17400+11400=28800种不同结果
例2 从集合{1，2，3，…，10}中，选出由5个数组成的子集，使得这5个数中的任何两个数的和不等于11，这样的子集共有多少个?
解：和为11的数共有5组：1与10，2与9，3与8，4与7，5与6，子集中的元素不能取自同一组中的两数，即子集中的元素取自5个组中的一个数而每个数的取法有2种，
所以子集的个数为2×2×2×2×2=25=32
点评：解本题的关键是找出和为11的5组数，然后再用分步计数原理求解例中选出5个数组成子集改为选出4个数呢? 答案：C·24=80个
2.排列与组合的基本问题
例1 分别求出符合下列要求的不同排法的种数
（1）6名学生排3排，前排1人，中排2人，后排3人；
（2）6名学生排成一排，甲不在排头也不在排尾；[来源:数理化网]
（3）从6名运动员中选出4人参加4×100米接力赛，甲不跑第一棒，
乙不跑第四棒；
（4）6人排成一排，甲、乙必须相邻；
（5）6人排成一排，甲、乙不相邻；
（6）6人排成一排，限定甲要排在乙的左边，乙要排在丙的左边（甲、
乙、丙可以不相邻）
解：（1）分排坐法与直排坐法一一对应，故排法种数为
（2）甲不能排头尾，让受特殊限制的甲先选位置，有种选法，然后其他5人选，有种选法，故排法种数为
（3）有两棒受限制，以第一棒的人选来分类：
①乙跑第一棒，其余棒次则不受限制，排法数为；
②乙不跑第一棒，则跑第一棒的人有种选法，第四棒除了乙和第一棒选定的人外，也有种选法，其余两棒次不受限制，故有种排法，
由分类计数原理，共有种排法
（4）将甲乙“捆绑”成“一个元”与其他4人一起作全排列共有种排法
（5）甲乙不相邻，第一步除甲乙外的其余4人先排好；第二步，甲、乙选择已排好的4人的左、右及之间的空挡插位，共有（或用6人的排列数减去问题（2）后排列数为）
（6）三人的顺序定，实质是从6个位置中选出三个位置，然后排按规定的顺序放置这三人，其余3人在3个位置上全排列，故有排法种
点评：排队问题是一类典型的排列问题，常见的附加条件是定位与限位、相邻与不相邻
例2 假设在100件产品中有3件是次品，从中任意抽取5件，求下列抽取方法各多少种？
（1）没有次品；（2）恰有两件是次品；（3）至少有两件是次品
解：（1）没有次品的抽法就是从97件正品中抽取5件的抽法，共有种
（2）恰有2件是次品的抽法就是从97件正品中抽取3件，并从3件次品中抽2件的抽法，共有种
（3）至少有2件次品的抽法，按次品件数来分有二类：
第一类，从97件正品中抽取3件，并从3件次品中抽取2件，有种
第二类从97件正品中抽取2件，并将3件次品全部抽取，有种
按分类计数原理有种
点评：此题是只选“元”而不排“序”的典型的组合问题，附加的条件是从不同种类的元素中抽取，应当注意：如果第（3）题采用先从3件次品抽取2件（以保证至少有2件是次品），再从余下的98件产品中任意抽取3件的抽法，那么所得结果是种，其结论是错误的，错在“重复”：假设3件次品是A、B、C，第一步先抽A、B第二步再抽C和其余2件正品，与第一步先抽A、C（或B、C），第二步再抽B（或A）和其余2件正品是同一种抽法，但在算式中算作3种不同抽法
例3 求证：①　；②
证明：①利用排列数公式
左右
另一种证法：（利用排列的定义理解）
从n个元素中取m个元素排列可以分成两类：
①第一类不含某特殊元素的排列有
第二类含元素的排列则先从个元素中取出个元素排列有种，然后将插入，共有m个空档，故有种，因此
②利用组合数公式
左
右
另法：利用公式推得
左右
点评：证明排列、组合恒等式通常利用排列数、组合数公式及组合数基本性质
例4 已知是集合到集合的映射
（1）不同的映射有多少个？
（2）若要求则不同的映射有多少个？
分析：（1）确定一个映射，需要确定的像
（2）的象元之和为4，则加数可能出现多种情况，即4有多种分析方案，各方案独立且并列需要分类计算
解：（1）A中每个元都可选0,1,2三者之一为像，由分步计数原理，共有个不同映射
（2）根据对应的像为2的个数来分类，可分为三类：
第一类：没有元素的像为2，其和又为4，必然其像均为1，这样的映射只有一个；
第二类：一个元素的像是2，其余三个元素的像必为0,1,1，这样的映射有个；
第三类：二个元素的像是2，另两个元素的像必为0，这样的映射有个
由分类计数原理共有1+12+6=19（个）
点评：问题（1）可套用投信模型：n封不同的信投入m个不同的信箱，有　种方法；问题（2）的关键结合映射概念恰当确定分类标准，做到不重、不漏
3.排列与组合的综合运用
例1 将6本不同的书按下列分法，各有多少种不同的分法？
⑴分给学生甲3 本，学生乙2本，学生丙1本；
⑵分给甲、乙、丙3人，其中1人得3本、1人得2 本、1 人得1 本；
⑶分给甲、乙、丙3人，每人2本；
⑷分成3堆，一堆3 本，一堆2 本，一堆1 本；
⑸分成3堆，每堆2 本。
⑹分给分给甲、乙、丙3人，其中一人4本，另两人每人1本；
⑺分成3堆，其中一堆4本，另两堆每堆1本。
分析：①分书过程中要分清：是均匀的还是非均匀的；是有序的还是无序的。
②特别是均匀的分法中要注意算法中的重复问题。
解：⑴是指定人应得数量的非均匀问题：方法数为；
⑵是没有指定人应得数量的非均匀问题：方法数为；
⑶是指定人应得数量的均匀问题：方法数为；
⑷是分堆的非均匀问题（与⑴等价）：方法数为；
⑸是分堆的均匀问题：方法数为；
⑹是部分均匀地分给人的问题：方法数为；
⑺是部分均匀地分堆的问题：方法数为。
例2  求不同的排法种数：
（1）6男2女排成一排，2女相邻；
（2）6男2女排成一排，2女不能相邻；
（3）4男4女排成一排，同性者相邻；
（4）4男4女排成一排，同性者不能相邻．
解：（1）是“相邻”问题，用捆绑法解决：.
（2）是 “不相邻”问题，可以用插空法直接求解．6男先排实位，再在7个空位中排2女，即用插孔法解决：.[来源:][来源:]
另法：用捆绑与剔除相结合：.
（3）是“相邻”问题，应先捆绑后排位：.
（4）是 “不相邻”问题，可以用插空法直接求解: .
例3 有13名医生,其中女医生6人.现从中抽调5名医生组成医疗小组前往灾区,若医疗小组至少有2名男医生,同时至多有3名女医生,设不同的选派方法种数为P,则下列等式
(1)
(2);
(3);
(4);
其中能成为P 的算式有_________种.
分析: 交换医疗小组的两成员顺序是同一选派方法,故为组合问题。
用直接法解:选派5名医生分为2男3女,3男2女,4男1女,5男这四类,故(2)正确;
用间接法解: 不考虑限制条件,选派方法有种,需剔除的有1男4女,5女两类,故(3)正确.
因此结论为: (2)(3).
点评：本例要特别防止误选(4).
例4 对某种产品的6件不同正品和4件不同次品,一一进行测试,到区分出所有次品为止.若所有次品恰好在第五次测试被全部发现,则这样的测试方法有 种
解:在各次测试结果中交换其中两者的顺序,成为两种不同的测试方法,因此是排列问题.故所有测试方法是6件不同正品取出1件与4件次品排成一列且最后一件是次品： =576种.
例5 某班新年联欢会原定的5个节目已排成节目单,开演前有增加了2个新节目,如果将这两节目插入节目单中,那么不同的插法种数为______.
解:实质是7个节目的排列,因原定的5个节目顺序不改变,故排这5个节目是一个组合,有种方法,在排新插入的两个节目有种方法,故.
点评：分清是排列还是组合问题
排列与组合的根本区别是元素之间有否顺序.若元素之间交换次序后是两种不同的情形,则是排列问题;若元素之间交换次序后是相同的情形,则是组合问题;另外若元素之间已经规定了顺序,则仍是组合问题。
例6 从10 种不同的作物中选出6 种放入6个不同的瓶子中展出,如果甲、乙两种种子不能放入第1号瓶内,那么不同的放法共有( )种.
A. B. C. D.
解: 先排第1号瓶,从甲、乙以外的8种不同作物种子中选出1种有种方法,再排其余各瓶,有种方法,故不同的放法共有.故选C。
点评：这样解分步合理、过程简捷.但本题更容易想到先从10种不同的作物种子中选出6种,然后排列.由于选出的6种种子中是否含甲、乙不确定,导致后继排列也不确定,这时就要分类了.选出的6种种子中只含甲或只含乙的不同放法都为种,选出的6种种子中,同时含甲与乙的不同放法有种;选出的6种种子中,都不含甲与乙的不同放法有种.故不同的放法共有种.
例7. 有四个不同的小球,全部放入四个不同的盒子内,恰有两个盒子不放球的放法总数为 ___ [来源:]
解:选取两个不放球的盒子,有种选法；把4个球分成两堆,可分为两堆各为1,3个或两堆都有2个球这两类,有种;再把两堆分别放入两个盒子里有种,
所求放法总数为种.
点评：如何实施先组合,后排列
对常见的排列组合综合问题,应先组合,后排列,可分为以下两类.
例8.把9个相同小球放入其编号为1、2、3的三个箱子里,要求每个箱子放球的个数不小于其编号数,则不同的放球方法共有______种.
解:先给编号为2、3的三个箱子里分别放入1个、2个小球,有1种方法；再将剩余的6个小球串成一串，截为三段有种截断法，对应放到编号为1、2、3的三个箱子里。
因此，不同的放球方法有1×10＝10种。
例9 某校准备参加2005年高中数学联赛,把10个选手名额分配到高三年级的8 个教学班,每班至少一个名额,则不同的分配方案共有___种.
解 问题等价于把10个相同小球放入8个盒子里,每个盒子至少有一个小球的放法种数问题。
将9个小球串成一串，截为8段有种截断法，对应放到8个盒子里。
因此，不同的分配方案共有36种。
点评： 剪截法（隔板法）：n个 相同小球放入m(m≤n)个盒子里,要求每个盒子里至少有一个小球的放法等价于n个相同小球串成一串从间隙里选m-1个结点剪成m段（插入m－1块隔板），有种方法.
例10. 编号为1至6的6个小球放入编号为1至6的6个盒子里,每个盒子放一个小球,其中恰有2个小球与盒子的编号相同的放法有____种.
解： 选取编号相同的两组球和盒子的方法有种,其余4组球与盒子需错位排列有9种放法,故所求方法有种.
点评：错位法：编号为1至n的n个小球放入编号为1到 n的n个盒子里,每个盒子放一个小球.要求小球与盒子的编号都不同,这种排列称为错位排列.特别当n=2,3,4,5时的错位数各为1,2,9,44.
例11. 将A、B、C、D、E、F六个不同的电子元件在线路上排成一排组成一个电路,如果元件A不排在始端,元件B不排在末端,那么这六个电子元件组成不同的电路的种数是_ .
解：不考虑限制条件共有种排法,元件A排在始端和B排在末端各有种排法,把它们都剔除,则A排在始端同时B排在末端的总数多减了一次,需补上种.故组成不同的电路种.