本文首先介绍排列和组合的定义，然后通过各种案例介绍了常用的方法，如隔板法、插空法等。
1 定义
1.1 排列数
从 $n$ 个不同元素中取出 $k$ 个元素的排列数：
$$ A_n^k := n \cdot (n - 1) \cdot (n -k + 1) = \frac{n!}{ (n - k)! }, \quad k \leq n $$
1.2 组合数
从 n 个不同元素中取出 k 个元素的组合数：在排列数的基础上除去同一组数重复出现的排列数。
$$ C_n^k := \frac{A_n^k}{k!} = \frac{n!}{k! (n-k)!}, \quad k \leq n $$
2 实战
2.1 分步乘法原理
由 0、1、2、3、4、5 可以组成多少个没有重复数字的五位奇数？
解答：个位数只能选 1、3、5，即 $C_3^1$，万位数不能为 0，因此由 $C_4^1$ 中选择，中间三位数在剩余的四个数中任选三个进行排列即可，有 $A_4^3$ 种选择，根据分步乘法原理可得答案 $C_3^1 \times C_4^1 \times A_4^3=288$。
2.2 分类加法原理
旅行社有豪华游 5 种，普通游 4 种，某单位欲从中选择 4 种，且豪华游和普通游至少各一种的选择有多少种？
解答：根据要求，允许的情况有 “1 豪华 3 普通”、“2 豪华 2 普通”、“3 豪华 1 普通”，三种分别有 $C_5^1 \times C_4^3$、$C_5^2 \times C_4^2$、$C_5^3 \times C_4^1$ 种选择，根据分类加法原理，三种选择数相加可得 120。另解：$C_9^4 - C_5^4 - C_4^4$。
2.3 相邻问题与捆绑法
问题 1：有三个女生四个男生站在一排，要求女生必须相邻，男生必须相邻（即一个人左右两边至少有一个是他的同性），一共有多少种排法？
解答：显然，女生和男生需要分别抱团（各自捆绑成为一个整体），一共有两个整体，因此整体而言有 $A_2^2$ 种排列。在每个整体内部，各有 $A_3^3$ 和 $A_4^4$ 中排列（松绑），因此一共有 $A_2^2 \times A_3^3 \times A_4^4$ 种。
问题 2：A、B、C、D、E 五人站一排，AB 必须相邻且 B 必须在 A 的右边，则一共有多少种排法？
解答：$A_4^4$。不用松绑。
问题 3：A、B、C、D、E 五人站一排， B 必须在 A 的右边，则一共有多少种排法？
解答：
-
方法一：全排列之后去除 B 在 A 的左边的个数，即
$A_5^5 / A_2^2$； -
方法二：使用下面讲到的插空法。首先 C、D、E 三个人的全排列为
$A_3^3$，三个人左右一共留下 4 个空位，A 和 B 可以相邻也可以不相邻，因此从四个空位中选择一个或两个均可，即$C_4^1+C_4^2=10$，所以答案为$A_3^3×10=60$。
2.4 相离问题与插空法
5 名母亲带领 5 个孩子拍照，孩子不相邻的站法有多少种？
解答：5 名母亲一共有 $A_5^5$ 种排列，留下了 6 个空位，一个空位中不能有超过 1 个孩子，因此是 $A_6^5$ 种排法，因此答案为 $A_5^5 \times A_6^5$。
2.5 相离与相邻综合
问题 1：3 名男生和 4 名女生排队站一排，求排队方法种数。
- 男女各站一起（男生必须相邻、女生必须相邻）：
$A_2^2 \times A_3^3 \times A_4^4$。 - 男生必须站一起：男生捆绑，
$A_3^3 \times A_5^5$。 - 男生不能相邻：插空，
$A_4^4 \times A_5^3$。 - 男女各不相邻：男女生各自以对方为桩插空，
$A_3^3 \times A_4^4$。
问题 2：8 个节目种有 2 个唱歌、3 个舞蹈、3 个曲艺，求编排方法数。
- 一个唱歌开头，一个唱歌结尾：
$A_2^2 \times A_6^6$。 - 两个唱歌不相邻：
$A_6^6 \times A_7^2$。 - 两个唱歌相邻且三个舞蹈不相邻：
$A_4^4 \times A_5^3 \times A_2^2$。
2.6 相同元素分组与隔板法
问题 1：10 各运动员分给 7 个班，每班至少一个，有多少种分配方案？
解答：首先，这是一个分配问题，不关心每个班分到的谁，只关心每个班分到几个人。因此使用组合数。10 个班一共有 9 个可以插入 6 个板子的空档（最外面两个非法），因此答案为 $C_9^6$。可总结，$n$ 个元素分成 $m$ 份，分配方案一共有 $C_{n-1}^{m-1}$ 种。
问题 2：将 6 个相同的小球放入 4 个盒子，求分配方案种数。
- 每个盒子都不为空：直接
$C_5^3$。 - 恰有一个空盒子：首先随意插入两个板子
$C_5^2$，最后一个板子的插入要产生一个空盒，因此只能选最左外侧、最右外侧或者前两个板子所在的位置，即$C_4^1$，所以答案为$C_5^2 \times C_4^1$。 - 恰有两个空盒子：
-
思路 1：首先随意插入一个板子
$C_5^1$，然后在三个可选的位置中选择两个（$C_3^2$）或一个（$C_3^1$）插入剩下的两个板子，因此答案为$C_5^1 \times (C_3^2 + C_3^1)$。 -
思路 2：首先选择两个不为空的盒子
$C_4^2$，然后问题变成了将 6 个小球放入 2 个盒子，直接$C_5^1$，因此答案为$C_4^2 \times C_5^1$。
-
2.7 平均分组问题 / 不同元素分组与除量法
问题 1：6 本不同的书平均分成 3 堆，每堆 2 本共有多少种分法？
解答：如果直接 $C_6^2 \times C_4^2 \times C_2^2$ 的话，会造成重复计算。例如，(AB, CD, EF)和 (AB, EF, CD) 其实是一样的，因为堆没有编号，当我们使用 $C_6^2 \times C_4^2 \times C_2^2$ 时，不自觉地给三个堆排了序。因此需要除以相同量的策略种数，答案为 $C_6^2 \times C_4^2 \times C_2^2 / A_3^3$。
问题 2：将 13 个球队分成 3 组，一组 5 个队，其他两组 4 个队，有多少种分法？
解答：队数相同的两组需要去掉排序，因此答案为 $C_{13}^5 \times C_8^4 \times C_4^4 / A_2^2$。
问题 3：高三年级一共有 6 个班，现从外地转入 4 名学生，要安排到该年级的两个班级且每个班级安排 2 名，一共有几种安排方法？
解答：首先相当于四个不同元素分成两组，使用除量法可得 $C_4^2 \times C_2^2 / A_2^2$ 种，然后将这两个组作为两个整体安排到 6 个班中，即 $A_6^2$，所以答案为 $A_6^2 \times C_4^2 \times C_2^2 / A_2^2$。
问题 4：6 本不同的书，分为 3 组，求分配方法个数。
- 每组 2 本：这是平均分组，因此得
$C_6^2 \times C_4^2 \times C_2^2 / A_3^3$。 - 一组 1 本，一组 2 本，一组 3 本：没有重复数量的分组，直接
$C_6^1 \times C_5^2 \times C_3^3$。 - 一组 4 本，两外两组各 1 本：这是部分平均分组，因此得
$C_6^4 \times C_2^1 \times C_2^1 / A_2^2$。
2.8 选排问题与先取后排法
问题 1：四个不同的球放入编号为 1、2、3、4 的四个盒子中，恰有一个空盒的放法有多少种？
解答：因为球不同，所以不能使用隔板法。分析可知满足条件的放法必须有某个盒子放两个球，某两个盒子放一个球，最后一个盒子没有球。先从 4 个球里面选择两个 $C_4^2$ 放入某个盒子中，然后通过 “三个被选中的盒子的全排列” 确定 (2, 1, 1, 0) 对应的盒子编号，即 $A_4^3$，因此答案为 $C_4^2 \times A_4^3$，这里用到了 “先选择后排序” 的思路。
问题 2：9 名运动员，其中男 5 名，女 4 名，有多少种混合双打的分组方法？
解答：首先需要各选择两人，即 $C_5^2 \times C_4^2$，然后男 1 有两种选择（女 1 或女 2，$A_2^2$），男 1 的选择确定后男 2 的选择自动确定，因此答案为 $C_5^2 \times C_4^2 \times A_2^2$。
问题 3：电视台有 8 个节目准备分两天播出，每天播出 4 个，其中某电视剧和某专题报道必须在第一天播出，某谈话节目必须在第二天播出，供有多少种播出方案？
解答：不妨将 8 个节目分别记为 ABCDEFGH，必须在第一天播出的是 AB，必须在第二天播出的是 C，则第一天还需要在剩下的 5 个节目中选择 2 个（$C_5^2$），然后第一天的节目全排列 $A_4^4$；第二天在剩余的 3 个节目中选 3 个，然后全排列，即 $C_3^3 \times A_4^4$，因此答案为 $C_5^2 \times A_4^4 \times C_3^3 \times A_4^4$。
问题 4：用数字 1、2、3、4、5、6 组成没有重复数字的四位数，其中个位、十位和百位上的数字之和位偶数的四位数共有多少个？
解答：对于 “个十百” 这三个位置，要么是那个全是偶数，要么一个偶数两个奇数，即 $C_3^3 + C_3^1 C_3^2$ 种组合，然后对这三个数排序（$A_3^3$），最后，千位数从剩余的 3 个里面选择一个，即 $C_3^1$，所以答案为 $(C_3^3 + C_3^1 \times C_3^2 ) \times A_3^3 \times C_3^1$。
转载申请
本作品采用 知识共享署名 4.0 国际许可协议 进行许可，转载时请注明原文链接。您必须给出适当的署名，并标明是否对本文作了修改。