排列和组合

一、序言

排列组合是组合学最基本的概念。

所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。

排列组合的中心问题是研究给定要求的排列和组合可能出现的情况总数。 排列组合与古典概率论关系密切。

二、排列的定义

从n个不同元素中，任取m（m≤n,m与n均为自然数,下同）个不同的元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；

从n个不同元素中取出m（m≤n）个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 A(n,m)或表示。

排列公式

三、组合的定义

从n个不同元素中，任取m（m≤n）个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；

从n个不同元素中取出m（m≤n）个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。用符号 C(n,m) 或者表示。

组合公式

四、经典应用

1.枚举法：

例题：设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的盒子，现将这5个球投入5个盒子要求每个盒子放一个球，并且恰好有两个球的号码与盒子号码相同，问有多少种不同的方法？

解：2C₅²=20

从5个球中取出2个与2盒子对上号的有C₅²种，还剩下3个球要与3个盒子符号不能对上，利用枚举法，如果剩下的是3，4，5号球，3号球如果装4号盒时，则4，5号球只有1种装法，同理3号球装5号盒时，4，5号球也只有1种装法，所以总共是有2种装法。因此最终的结果为2C₅²。

点评：

元素比较少的，又比较复杂的排列组合问题，可以用枚举法得到意想不到的结果。

变式：将数字1，2，3，4填入标号为1，2，3，4的四个方格里，每格填一个数，则每个方格的标号与所填数字均不相同的填法有多少种？

2.捆绑法：

例题：7人站成一排，其中甲乙相邻且丙丁相邻，共有多少种不同的排法

解：A⁵₅A²₂A²₂=480

点评：

要求某几个元素必须排在一起的问题，可以用捆绑法来解决，将需要相邻的元素合并为一个元素，再与其他元素一起作排列，同时要注意合并元素内部也必须排列。

变式：七个家庭一起外出旅游，若其中四家是男孩，三家是女孩，现将这七个小孩拍成一排照相留念。若三个女孩要站在一起，四个男孩也要站在一起，共有多少种不同的排法？

3.插空法：

例题：7人站成一排，其中甲乙两人不能相邻，共有多少种不同的排法

解：

A⁵₅C²₆A²₂=3600

点评：

元素不相邻问题，可以先把没有位置要求的元素进行排序，然后再根据题意将不相邻的元素插到已经排序完成的元素之中。

变式：马路上有编号为1，2，3……9的九盏路灯，为节约用电，现要求把其中三盏灯，但不能关掉相邻的2盏或3盏，也不能关掉两端的路灯，满足条件的关灯方法有几种？

4.定序缩倍法：

例题：7人站成一排，其中甲乙丙三人顺序一定，共有多少种不同的排法

解：

A⁷₇/A³₃=840

点评：

对于某几个元素顺序一定的排列问题，可先把这几个元素与其他元素一起进行排列，然后用总排列数除以这几个元素之间的全排列数，即是所得结果。

变式1：10人身高各不相同，排成前后排，每排5人，要求从左至右身高逐渐增加，共有多少种排法？

变式2：将3个完全相同的红球与5个完全相同的白球排成一排，共有多少种排法？

5.特殊定位优先法：

例题：1名老师和4名获奖同学排成一排照相留念，若老师不站两端则有不同的排法有多少种？

解：

C¹₃A⁴₄=72

总共有5个位置，因为老师不站在两端，所以从中间的3个位置选1个，剩下的4位学生全排列。

点评：

某个或几个元素要排在指定位置，可先排这个或几个元素；再排其它的元素。

变式：由0，1，2，3，4，5可以组成多少个没有重复的五位奇数？

6.多排问题单排法：

例题：6个不同的元素排成前后两排，每排3个元素，那么不同的排法种数有几种？

解：

A⁶₆=120

点评：

把元素排成几排的问题可归结为一排考虑，再分段研究

变式1：8个不同的元素排成前后两排，每排4个元素，其中某2个元素要排在前排，某1个元素排在后排，有多少种不同排法？

变式2：10名学生分坐两行，要求面对面坐下，但其中甲乙两位同学不可相邻也不可面对面，有多少种做法？

7.同元素分配隔板法：

（1）每份至少含有1个元素

例题：10个三好学生名额分到7个班级，每个班级至少一个名额，有多少种不同分配方案？

解：

C⁶₉=84

点评：

将n个相同的元素分成m份，每份至少一个元素，可以用m-1块隔板，插入n个元素排成一排的n-1个空隙中，所有分法为

变式：7个相同的小球，任意放入4个不同的盒子中，每个盒子至少有一个小球的不同放法有多少种？

（2）其中一分或几分中可以含有0个元素

例题：10个三好学生名额分到7个班级，有多少种不同分配方案？

解：

C⁶₁₆=8008

点评：

将n个相同的元素分成m份，并未提及每份至少含有一个元素，即可以含有0个元素的情况，这时用“元素数(n)+隔板数(m-1)”为总的元素数，分成4份，所有分法为C^m-1_n+m-1。

变式：7个相同的小球，任意放入4个不同的盒子中，不同放法有多少种？

8.不同元素平均分配法：

例1：将6本不同的书，平均分成三份的分法有多少种？

解：

C²₆C²₄C²₂/A³₃=15

点评：

对于平均分堆问题，是与顺序无关的，所以组合数相乘后要除以

A^m_m,其中m表示均分的组数。很多同学不理解为什么要除以组数的阶乘，举个例子，三个不同的苹果，分成三份，总共有几种分法？很显然只有一种，计算式子为C¹₃C¹₂C¹₁/A³₃，而不是C¹₃C¹₂C¹₁，这样就会比较好理解一些。

变式：将10名同学平均分成5个组，总共有多少种分法？

例2：将6本不同的书，分成三份，一份有4本，另外两份各1本的分法有多少种？

解：

C⁴₆.(C¹₂C¹₁/A²₂)=15

点评：

对于非均分的问题，只需要组合数相乘，如果题目中即含有均分问题又含有非均分问题(如上面例2)，组合数相乘之后只需要除以均分组数的阶乘。

变式：8本不同的书分成三份，其中1份2本，另外两份各3本，有多少种不同的分法？

9.先选后排法：

例题：将6本不同的书，平均分给3名同学的分法有多少种？

解：

(C²₆C²₄C²₂/A³₃).A³₃=90

点评：

这类题目属于排列组合的混合问题，遵循的最基本的规则为先选后排，即先分组后排序。

变式1：8本不同的书分给3名同学，其中1名同学2本，另外两人3本，有多少种不同的分法？

变式2：有5个不同的小球，装入4个不同的盒内，每盒至少装一个球，共有多少不同的装法？

变式3：将6本不同的书分给甲乙丙三个人，每人至少一本的分法有多少种？

10.合理分类法：

例题：某高校从某系的10名优秀毕业生中选4人分别到西部四城市参加中国西部经济开发建设，其中甲同学不到银川，乙不到西宁，共有多少种不同派遣方案？

解：

(1)甲乙均未被选中：A⁴₈

(2)甲被选中乙未被选中：C³₈C¹₃A³₃

先从除了甲乙两人以外的8个人中选三人，且甲被选中，现在已经选择了4个人，因为甲不能去银川，所以从另外三个地方选一个，其余三个人全排列。

(3)乙被选中甲未被选中：C³₈C¹₃A³₃

(4)甲乙均被选中：C²₈(A⁴₄-A³₃-A³₃+A²₂)

先从除了甲乙两人以外的8个人中选两人，且甲，乙都被选中，现在已经选择了4个人，4个人全排列A⁴₄之后，要减去甲在银川的A³₃（不管乙的位置)，再减去乙在西宁A³₃的（不管甲的位置)。那为什么最后还要再加上A²₂呢？因为甲在银川的时候，存在乙可能在西宁的情况；同样乙在西宁的时候，存在甲在银川的情况，因此多减了一次甲在银川乙在西宁的情况，因此要再加上A²₂。

点评：

元素多，取出的情况也多种，可按结果要求分成不相容的几类情况分别计数，最后总计。

变式1：从6名运动员中选出4人参加4×100米接力赛，如果甲不跑第一棒，乙不跑第四棒，共有多少种不同的参赛方案？

变式2：在一次演唱会上共有10名演员，其中8人能唱歌，5人能跳舞，现将演出一个2人唱歌2人伴舞的节目，总共有多少种选派的方法。

11.排除法：

例题：以正方体的顶点为顶点的四面体总共有多少种？

解：

C⁴₈-6-6=58

从下图正方体可以看出，同一个面的四个顶点，是不能组成四面体的，要排除，总共有6种可能.

另外从下图正方体还可以看出，对角面上的四个顶点，也是不能组成四面体的，要排除，总共也有6种可能

点评：

在选取的总数中，只有一部分合条件，可以从总数中减去不符合条件数，即为所求.

变式1：四面体的顶点和各棱中点共10个点，从中取4个不共面的点，不同的取法有多少种？

变式2：从4台甲型和5台乙型电视机中任取3台，其中至少要甲型和乙型电视机各一台，则不同的取法共有多少种？