《排列组合》核心知识点,中学数学建模方法

一、两个计数原理

（1）分类计数原理：做一件事情，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法，那么完成这件事共有N =m1 +m2+…+mn 种不同的方法.

（2）分步计数原理：做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法，那么完成这件事有N =m1 ×m2×…×mn 种不同的方法.

（3）两个基本原理的作用：计算做一件事完成它的所有不同的方法种数.

（4）两个基本原理的区别：

一个与分类有关，一个与分步有关：加法原理是“分类完成”，乘法原理是“分步完成”.

（5）原理浅释.

分类计数原理（加法原理）中，“完成一件事，有n类办法”，是说每种办法“互斥”，即每种方法都可以独立地完成这件事，同时它们之间没有重复也没有遗漏.因此，进行分类时，要求各类办法彼此之间是相互排斥的，不论哪一类办法中的哪一种方法，都能独立完成这件事，只有满足这个条件，才能直接用加法原理，否则不可以.

分步计数原理（乘法原理）中，“完成一件事，需要分成n个步骤”，是说每个步骤都不足以完成这件事，这些步骤，彼此间也不能有重复和遗漏.如果完成一件事需要分成n个步骤，各步骤都不可缺少，需要依次完成所有步骤才能完成这件事，而各步要求相互独立，即相对于前一步的每一种方法，下一步都有m种不同的方法，那么完成这件事的方法数就可以直接用乘法原理.

可以看出“分”是它们共同的特征，但是，分法却大不相同．

两个原理的公式是：N =m1 +m2+…+mn ；N =m1 ×m2×…×mn .

例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个数呢？答案：个.

二、排列

（1）排列的概念：从n个不同元素中，任取m(m≤n)个元素（这里的被取元素各不相同）按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列.

（2）排列数的定义：从n个不同元素中，任取m(m≤n)个元素的所有排列的个数叫做从n个元素中取出m个元素的排列数，用符号表示.

（3）排列数公式：

（4）阶乘：n!表示从正整数1到n的连乘积，叫做n的阶乘.规定0!=1．

（5）排列数的另一个计算公式：.

三、组合

（1）组合的概念：一般地，从n个不同元素中取出m(m≤n)个元素并组成一组，叫做从n个不同元素中取出m个元素的一个组合.

（2）组合数的概念：从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数．用符号表示．

（3）组合数公式：

（4）组合数的性质1：．规定：=1；

（5）组合数的性质2：

四、排列、组合的应用

解排列组合问题，首先要弄清一件事是“分类”完成还是“分步”完成，对于元素之间的关系，还要考虑“是有序”的还是“无序的”，也就是学会正确使用分类计数原理和分步计数原理、排列定义和组合定义.其次，对一些复杂的带有附加条件的问题，需掌握以下几种常用的解题方法：

（1）特殊优先法：对于存在特殊元素或者特殊位置的排列组合问题，我们可以从这些特殊的元素或位置入手，即先解决特殊元素或特殊位置的问题，再去解决其他元素或位置的问题，这种解法叫做特殊优先法.例如：用0，1，2，3，4这5个数字，组成没有重复数字的三位数，其中偶数共有________个（答案：30个）.

（2）科学分类法：对于较复杂的排列组合问题，由于情况繁多，因此要对各种不同情况进行科学分类，以便有条不紊地进行解答，避免重复或遗漏现象发生.例如：从6台原装计算机和5台组装计算机中任取5台，其中至少有原装与组装计算机各两台，则不同的选取法有_______种（答案：350）.

分组（堆）问题的六个模型：①有序不等分；②有序等分；③有序局部等分；④无序不等分；⑤无序等分；⑥无序局部等分.

（3）插空法：解决一些不相邻问题时，可以先排一些元素然后插入其余元素，使问题得以解决.例如：7人站成一行，如果甲乙两人不相邻，则不同排法种数是______（答案：3600）.

（4）捆绑法：相邻元素的排列，可以采用“整体到局部”的排法，即将相邻的元素当成“一个”元素进行排列，然后再局部排.例如：6名同学坐成一排，其中甲、乙必须坐在一起的不同坐法是________种（答案：240）.

（5）排除法：从总体中排除不符合条件的方法数，这是一种间接解题的方法.

排列组合应用题往往和代数、三角、立体几何、平面解析几何的某些知识联系，从而增加了问题的综合性，解答这类应用题时，要注意使用相关知识对答案进行取舍.例如：从集合{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个错位的）种.(www.xing528.com)

所以有.

用此法可以逐步计算：6个、7个、8个、……元素的错位排列问题.

例3　分别求出符合下列要求的不同排法的种数.

（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人在3个位置上全排列，故有种排法.

点评：排队问题是一类典型的排列问题，常见的附加条件是定位与限位、相邻与不相邻.

例4　假设在100件产品中有3件是次品，从中任意抽取5件，求下列抽取方法各多少种？（1）没有次品；（2）恰有两件是次品；（3）至少有两件是次品.

解　（1）没有次品的抽法就是从97件正品中抽取5件的抽法，共有种.

（2）恰有两件是次品的抽法就是从97件正品中抽取3件，并从3件次品中抽2件的抽法，共有种.

（3）至少有两件次品的抽法，按次品件数来分有两类：

第一类，从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件正品是同一种抽法，但在算式中算作三种不同抽法.

例5　将6本不同的书按下列分法，各有多少种不同的分法？

（1）分给学生甲3本，学生乙2本，学生丙1本；

（2）分给甲、乙、丙三人，其中一人得3本、一人得2本、一人得1本；

（3）分给甲、乙、丙三人，每人2本；

（4）分成3堆，一堆3本，一堆2本，一堆1本；

（5）分成3堆，每堆2本；

（6）分给甲、乙、丙三人，其中一人4本，另两人每人1本；

（7）分成3堆，其中一堆4本，另两堆每堆1本.

分析：（1）分书过程中要分清：是均匀的还是非均匀的；是有序的还是无序的.

（2）特别是均匀的分法中要注意算法中的重复问题.

解　（1）是指定人应得数量的非均匀问题：方法数为；

（2）是没有指定人应得数量的非均匀问题：方法数为；

（3）是指定人应得数量的均匀问题：方法数为；

（4）是分堆的非均匀问题（与（1）等价）：方法数为；

（5）是分堆的均匀问题：方法数为；

（6）是部分均匀地分给人的问题：方法数为；

（7）是部分均匀地分堆的问题：方法数为.

点评：分清是排列还是组合问题.排列与组合的根本区别是元素之间有否顺序.若元素之间交换次序后是两种不同的情形，则是排列问题；若元素之间交换次序后是相同的情形，则是组合问题；另外，若元素之间已经规定了顺序，则仍是组合问题.