排列与组合学习笔记

· · 算法·理论

前言

总概

本文章将会向你讲解排列与组合的基本知识和综合运用。

会从定义、问题导入、解决方法、经典例题、总结等方面讲解。

前置知识

加法计数原理和乘法计数原理会在附录进行讲解。

排列

定义

排列的定义为：从给定的 n 个不同元素中，取出指定个数为 m(m \le n) 的元素进行排序。

排列的重点在于要进行排序，与元素顺序有关。

排列相当于是选择后再排序。

排列数的定义为从给定的 n 个不同元素中，取出指定个数为 m(m \le n) 的元素所有排列的个数。

我们用 A_n^m 表示如上定义。

问题导入

现在有 5 个元素，分别为 a,b,c,d,e。要求从这 5 个元素中任取两个排成列的所有可能的个数。

我们之前可能通过暴力枚举来解决问题：

(a,e) (b,e) (c,e) (d,e)
(a,d) (b,d) (c,d) (e,d)
(a,c) (b,c) (d,c) (e,c)
(a,b) (c,b) (d,b) (e,b)
(b,a) (c,a) (d,a) (e,a)

其中 (x,y) 表示排列所构成的二元组，可以发现，一共有 20 种可能。

但是我们也可以通过乘法计数原理解决：

我们分 2 次选择，第一次显然有 5 种选法，第二次时，由于第一次选择了一个，所以第二次只有 5 - 1 = 4 种选法了。

然后由乘法计数原理得出，一共有 5 \times 4 = 20 种不同的选法。

这样子以来，我们就可以用 A_5^2 = 20 来表示这个结果。

如果这道题变成要求从这 5 个元素中任取三个排成列的所有可能的个数该怎么做呢？

我们还是可以通过暴力枚举，但是画图太麻烦了，但也可以得出一共有 60 种，这种办法并不适用于数据大的排列。

然后再尝试通过乘法计数原理解决：

我们第一次可以选 5 个，但是第二次选的时候只能选 5 - 1 = 4 个，第三次选的时候只能选 4 - 1 = 3 个，然后总共就有 5 \times 4 \times 3 = 60 种。

我们用 A_5^3 = 60 来表示上述结果。

排列的求法

对于 A_n^m 来说，我们将它抽象成选元素，即从 n 个元素种选 m 个所有排列的个数。

我们第一次可以选 n 个，第二次可以选 n-1 个，第三次可以选 n-2 个，以此类推。然后根据乘法计数原理就可以得出以下公式：

A_n^m=n(n-1)(n-2)\dots(n-m+1)

那么我们变换再化简一下，也就得到了：

\\ =\frac{n!}{(n-m)!}

我们就得出了求 A_n^m 的公式。

组合

定义

组合的定义为：从给定的 n 个不同元素中，取出指定个数为 m(m \le n) 的元素不进行排序。

组合的重点在于要不进行排序，与元素顺序无关。

组合相当于是选择的结果。

组合数的定义为从给定的 n 个不同元素中，取出指定个数为 m(m \le n) 的元素所有组合的个数。

我们用 C_n^m 表示如上定义。

问题导入

现在有 5 个元素，分别为 a,b,c,d,e。要求从这 5 个元素中任取两个组合的所有可能的个数。

注意到，刚才是排列，现在是组合，我们先把刚才的暴力枚举的表拿出来：

(a,e) (b,e) (c,e) (d,e)
(a,d) (b,d) (c,d) (e,d)
(a,c) (b,c) (d,c) (e,c)
(a,b) (c,b) (d,b) (e,b)
(b,a) (c,a) (d,a) (e,a)

可以发现，有些二元组对于组合来说是重复了的。

例如 (a,b) 和 (b,a) 就是相同的，也就是说，每一组数对于组合来说重复了 2 次。

首先，我们用 C_5^2 来表示上述的答案，那么怎么求呢？

我们刚才知道，每个数对于组合来说重复了 2 次，所以我们就可以得到：

C_5^2 = \frac{A_5^2}{2} = 10

如果这道题变成要求从这 5 个元素中任取三个组合的所有可能的个数该怎么做呢？

我们从上文知道，要求排列数，就是 A_5^3 = 60 即可，但是如何求组合呢？

我们就要看每组数对于组合来说重复了几次，也就是求这个三元组可以组成多少种排列，即 A_3^3。

所以对于 C_5^3 来说，答案就为：

C_5^3 = \frac{A_5^3}{A_3^3} = \frac{60}{6} = 10

组合的求法

我们首先了解全排列：

对于 A_n^m 来说，若 n = m 则这个排列数就是全排列。

要求组合数，最重要的就是知道对于组合来说重复的个数。

若取出 m 个元素，那么重复的次数就是这 m 个元素所组成的排列数，也就是 A_m^m。不难发现，重复的次数就是 m 的全排列。

所以就可以得到以下公式:

C_n^m = \frac{A_n^m}{A_m^m}

再将它展开和化简，就可以得到最后的公式了：

C_n^m &= \frac{n(n-1)(n-2)\dots(n-m+1)}{m!}\\ &= \frac{n!}{m!(n-m)!} \end{aligned}

这就是我们想要的公式了。

经典例题

做题之前

我们已经了解了排列与组合的基本知识，现在让我们来做一些题，巩固一下知识吧！

我们要了解在什么时候用排列，在什么时候用组合。

有序的安排我们使用排列；无序的选择我们使用组合。因为排列是有序的，而组合是无序的。

排列和组合的单独应用

从 8 名学生中挑选 1 人搬东西，挑选 1 人帮老师接水，挑选 1 人接送老师，共有几种不同方案？

看到挑选，也就是选择，我们使用组合。

挑选 1 人搬东西，也就是从 8 个人中选择 1 个人，即 C_8^1 为答案。

挑选 1 人帮老师接水，也就是从 7 个人中选择 1 人，因为刚才选走了一个人，所以现在只有 7 个。即 C_7^1 为答案。

挑选 1 人接送老师，也就是从 6 个人中选择 1 人，因为刚才选走了两个人，所以现在只有 6 个。即 C_6^1 为答案。

然后根据乘法计数原理计算最终答案：

ans = C_8^1 \times C_7^1 \times C_6^1 = 336

但是这一道题就不可以用排列吗？当然可以！

我们将题看成将 8 名学生安排到 3 个任务里面去，这不就是 A_8^3 吗？

我们通过计算可以得出这和刚才的答案是一样的！

ans = A_8^3 = \frac{8!}{(8-3)!} = 336

排列与组合的综合应用

有 3 个苹果和 3 个香蕉，现在选择 2 个苹果和 2 个香蕉，每天吃一个水果，问有多少种安排方法。

我们一步一步看问题，看到先选择，就用组合。

从 3 个苹果中选 2 个，也就是 C_3^2；从 3 个香蕉中选 2 个，也是 C_3^2。

然后我们看见安排方法，就用排列。

我们将问题抽象为，将这 4 个水果安排进 4 天的位置里面，也就是 A_4^4。

最后就可以运用乘法计数原理求出答案：

ans = C_3^2 \times C_3^2 \times A_4^4 = 216

排列与组合的逆向思考

从 3 名社恐和 5 名社牛中挑选 1 人搬东西，挑选 1 人帮老师接水，挑选 1 人接送老师，要求至少要有 1 名社恐，共有几种不同方案？

这一题相比前面的题多了一个要求，考虑解决这个要求。

我们采用排列的思想，也就是将问题抽象成：将 8 个人放进 3 个任务里面，要求至少 1 名社恐。

但是如何解决这个要求呢？我们正面思考的话，对于这个要求来说，可能会有 1 个或 2 个或 3 个社恐，非常麻烦。所以我们考虑逆向思考。

要求至少有 1 名社恐，逆向思考就是没有社恐呗，也就是全是社牛。也就是 A_5^3

而我们只用拿全部排列数减去全是社牛的排列数，不就是有社恐的排列数吗？

总共的排列数可以求出来，即 A_8^3 为答案；而全是社牛的排列数已经求了出来，所以这题的答案就出来了：

ans = A_8^3 - A_5^3 = 276

排列与组合的特殊元素问题

有 6 个人甲、乙、丙、丁、戊、己排成一横排，最左方只能是甲或者是乙，且最右端不能是甲，问有多少种排列方法。

这一题除了要求排列方法，还有要求，并且甲的事最多，所以从甲入手。

由题可得，甲只能在 1 号位至 5 号位之间，但是当甲再 1 号位的时候与再 2 至 5 号位时是不同的，所以对甲进行分类讨论。

当甲在 1 号位时，就可以将问题抽象为将乙、丙、丁、戊、己放进后面的 5 个位置，即 A_5^5 为答案。

当甲不在 1 号位时，即在 2 至 5 号位时，可以抽象为将甲安排进这 4 个位置，即 A_4^1 为答案。

因为甲不在 1 号位上，所以乙就必须在 1 号位上，这样才满足条件。

然后就是将丙、丁、戊、己放进剩余的 4 个位置，也就是 A_4^4 为答案。

最后的甲不在 1 号位的总方案数就为 A_4^1 \times A_4^4。

那么最后只要将两种情况加起来就是总方案数了：

ans = A_5^5 + A_4^1 \times A_4^4 = 216

有 5 个人甲、乙、丙、丁、戊排成一横排，甲不能站在两端，丙要和丁相邻，问有多少种不同的排列方法。

这一题除了有位置要求之外，丙还要和丁相邻，我们可以先处理这个条件。

我们将丙和丁看成一个元素，再和甲、乙和戊排队，所以只剩下了 4 个位置。

但是计算之前，我们发现丙和丁是可以交换位置的，因为丙和丁之间也要排队，所以事先要求出 A_2^2 的值。

我们再来看另一个条件，也就是甲不能在两端，那么说明甲只能在 2 号位或者 3 号位，因为一共就 4 个位置。那么甲要在这两个位置之中选择一个，也就是 C_2^1。

然后就只剩下了戊、丙丁和乙，也就是将这 3 个元素（我们将丙丁看作了一个元素）安排进这 3 个位置里面，即 A_3^3。

最后我们通过乘法计数原理求出答案即可：

ans = A_2^2 \times C_2^1 \times A_3^3 = 24

有 6 个人甲、乙、丙、丁、戊、己排成一横排，甲乙必须相邻，丙丁不能相邻，问有多少种不同的排列方法。

这一题除了有捆绑问题还有不相邻的要求，我们想考虑捆绑。

我们将甲和乙看作一个元素，那么就有 A_2^2 种排列方法。

再和戊和己排队，也就是将 3 个元素放进 3 个位置里面，也就是 A_3^3 种排列方式。

我们再来考虑不相邻的要求，我们假设甲乙、戊、己排队之后是下面的样子：

那么要使丙丁不相邻，那么他们两个就只能在画横线的空位上面，这样就不会相邻了。

这里共有 4 个横线，也就是将两个人安排进 4 个位置，即 A_4^2 为答案。

最后运用乘法计数原理求出答案即可：

ans = A_2^2 \times A_3^3 \times A_4^2 = 144

排列与组合的排列数字问题

现有 6 个数字从 0 到 5，问这 6 个数字能组成的不相同的四位偶数的个数。

看见这道题之后，发现这和前面的题都不一样，但是先别慌。

看见了四位偶数，可以得到 2 个信息：

那么这道题不就变成了排队类型的问题吗？看见数字 0 的事情最多，所以从 0 入手。

我们类比上面的位置问题，分类讨论数字 0 的位置在末尾和不在末尾的两种情况。

若数字 0 在末尾的位置，那么现在就是将其余的 5 个数字放进还剩的 3 个位置里面，即 A_5^3。

若数字 0 不在末尾的位置，也就是末尾是 2 或 4 的情况。那么我们就要将 2 或 4 安排进 1 个位置里面，也就是 A_2^1 了。

我们还注意到首位不能是 0 这个数字，所以也就是将 5-1=4 个数安排进 1 个位置，即 A_4^1 了。注意这 4 个数中不含数字 0。

最后就只剩了 2 个位置，也就是将剩下的 4 个数放进 2 个位置里面，即 A_4^2 了。

然后运用乘法计数原理求出这种情况的答案，也就是 A_2^1 \times A_4^1 \times A_4^2 这个值。

最后的答案就是将这两种情况加起来即可：

ans = A_5^3 + A_2^1 \times A_4^1 \times A_4^2 = 156

总结

排列与组合其实说简单也不简单，说难其实也难，所以多做题有助于提升对这类题型的敏感度，所以这里有一些课后思考题：