专栏文章

【笔记】排列与组合学习笔记

ccollegiate
算法·理论参与者 6已保存评论 7

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
7 条
当前快照
1 份
快照标识符
@miql4p65
此快照首次捕获于
2025/12/04 06:35
3 个月前
此快照最后确认于
2025/12/04 06:35
3 个月前
查看原文

前言

总概

本文章将会向你讲解排列与组合的基本知识和综合运用。
会从定义、问题导入、解决方法、经典例题、总结等方面讲解。

前置知识

  • 有一定的数学思维能力和理解能力
  • 加法计数原理
  • 乘法计数原理
  • 阶乘
加法计数原理和乘法计数原理会在附录进行讲解。

排列

定义

排列的定义为：从给定的 nn 个不同元素中，取出指定个数为 m(m≤n)m(m \le n) 的元素进行排序。
排列的重点在于要进行排序，与元素顺序有关。
排列相当于是选择后再排序。
排列数的定义为从给定的 nn 个不同元素中，取出指定个数为 m(m≤n)m(m \le n) 的元素所有排列的个数。
我们用 AnmA_n^m 表示如上定义。

问题导入

现在有 55 个元素，分别为 a,b,c,d,ea,b,c,d,e。要求从这 55 个元素中任取两个排成列的所有可能的个数。
我们之前可能通过暴力枚举来解决问题：
(a,e)(a,e)(b,e)(b,e)(c,e)(c,e)(d,e)(d,e)
(a,d)(a,d)(b,d)(b,d)(c,d)(c,d)(e,d)(e,d)
(a,c)(a,c)(b,c)(b,c)(d,c)(d,c)(e,c)(e,c)
(a,b)(a,b)(c,b)(c,b)(d,b)(d,b)(e,b)(e,b)
(b,a)(b,a)(c,a)(c,a)(d,a)(d,a)(e,a)(e,a)
其中 (x,y)(x,y) 表示排列所构成的二元组，可以发现，一共有 2020 种可能。
但是我们也可以通过乘法计数原理解决：
我们分 22 次选择，第一次显然有 55 种选法，第二次时，由于第一次选择了一个，所以第二次只有 5−1=45 - 1 = 4 种选法了。
然后由乘法计数原理得出，一共有 5×4=205 \times 4 = 20 种不同的选法。
这样子以来，我们就可以用 A52=20A_5^2 = 20 来表示这个结果。
如果这道题变成要求从这 55 个元素中任取三个排成列的所有可能的个数该怎么做呢？
我们还是可以通过暴力枚举，但是画图太麻烦了，但也可以得出一共有 6060 种，这种办法并不适用于数据大的排列。
然后再尝试通过乘法计数原理解决：
我们第一次可以选 55 个，但是第二次选的时候只能选 5−1=45 - 1 = 4 个，第三次选的时候只能选 4−1=34 - 1 = 3 个，然后总共就有 5×4×3=605 \times 4 \times 3 = 60 种。
我们用 A53=60A_5^3 = 60 来表示上述结果。

排列的求法

对于 AnmA_n^m 来说，我们将它抽象成选元素，即从 nn 个元素种选 mm 个所有排列的个数。
我们第一次可以选 nn 个，第二次可以选 n−1n-1 个，第三次可以选 n−2n-2 个，以此类推。然后根据乘法计数原理就可以得出以下公式：
Anm=n(n−1)(n−2)…(n−m+1)A_n^m=n(n-1)(n-2)\dots(n-m+1)
那么我们变换再化简一下，也就得到了：
=n!(n−m)!\\ =\frac{n!}{(n-m)!}
我们就得出了求 AnmA_n^m 的公式。

组合

定义

组合的定义为：从给定的 nn 个不同元素中，取出指定个数为 m(m≤n)m(m \le n) 的元素不进行排序。
组合的重点在于要不进行排序，与元素顺序无关。
组合相当于是选择的结果。
组合数的定义为从给定的 nn 个不同元素中，取出指定个数为 m(m≤n)m(m \le n) 的元素所有组合的个数。
我们用 CnmC_n^m 表示如上定义。

问题导入

现在有 55 个元素，分别为 a,b,c,d,ea,b,c,d,e。要求从这 55 个元素中任取两个组合的所有可能的个数。
注意到，刚才是排列，现在是组合，我们先把刚才的暴力枚举的表拿出来：
(a,e)(a,e)(b,e)(b,e)(c,e)(c,e)(d,e)(d,e)
(a,d)(a,d)(b,d)(b,d)(c,d)(c,d)(e,d)(e,d)
(a,c)(a,c)(b,c)(b,c)(d,c)(d,c)(e,c)(e,c)
(a,b)(a,b)(c,b)(c,b)(d,b)(d,b)(e,b)(e,b)
(b,a)(b,a)(c,a)(c,a)(d,a)(d,a)(e,a)(e,a)
可以发现，有些二元组对于组合来说是重复了的。
例如 (a,b)(a,b) 和 (b,a)(b,a) 就是相同的，也就是说，每一组数对于组合来说重复了 22 次。
首先，我们用 C52C_5^2 来表示上述的答案，那么怎么求呢？
我们刚才知道，每个数对于组合来说重复了 22 次，所以我们就可以得到：
C52=A522=10C_5^2 = \frac{A_5^2}{2} = 10
如果这道题变成要求从这 55 个元素中任取三个组合的所有可能的个数该怎么做呢？
我们从上文知道，要求排列数，就是 A53=60A_5^3 = 60 即可，但是如何求组合呢？
我们就要看每组数对于组合来说重复了几次，也就是求这个三元组可以组成多少种排列，即 A33A_3^3。
所以对于 C53C_5^3 来说，答案就为：
C53=A53A33=606=10C_5^3 = \frac{A_5^3}{A_3^3} = \frac{60}{6} = 10

组合的求法

我们首先了解全排列：
对于 AnmA_n^m 来说，若 n=mn = m 则这个排列数就是全排列。
要求组合数，最重要的就是知道对于组合来说重复的个数。
若取出 mm 个元素，那么重复的次数就是这 mm 个元素所组成的排列数，也就是 AmmA_m^m。不难发现，重复的次数就是 mm 的全排列。
所以就可以得到以下公式:
Cnm=AnmAmm 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}
这就是我们想要的公式了。

经典例题

做题之前

我们已经了解了排列与组合的基本知识，现在让我们来做一些题，巩固一下知识吧！
我们要了解在什么时候用排列，在什么时候用组合。
有序的安排我们使用排列；无序的选择我们使用组合。因为排列是有序的，而组合是无序的。

排列和组合的单独应用

从 88 名学生中挑选 11 人搬东西，挑选 11 人帮老师接水，挑选 11 人接送老师，共有几种不同方案？
看到挑选，也就是选择，我们使用组合。
挑选 11 人搬东西，也就是从 88 个人中选择 11 个人，即 C81C_8^1 为答案。
挑选 11 人帮老师接水，也就是从 77 个人中选择 11 人，因为刚才选走了一个人，所以现在只有 77 个。即 C71C_7^1 为答案。
挑选 11 人接送老师，也就是从 66 个人中选择 11 人，因为刚才选走了两个人，所以现在只有 66 个。即 C61C_6^1 为答案。
然后根据乘法计数原理计算最终答案：
ans=C81×C71×C61=336ans = C_8^1 \times C_7^1 \times C_6^1 = 336
但是这一道题就不可以用排列吗？当然可以！
我们将题看成将 88 名学生安排到 33 个任务里面去，这不就是 A83A_8^3 吗？
我们通过计算可以得出这和刚才的答案是一样的！
ans=A83=8!(8−3)!=336ans = A_8^3 = \frac{8!}{(8-3)!} = 336

排列与组合的综合应用

有 33 个苹果和 33 个香蕉，现在选择 22 个苹果和 22 个香蕉，每天吃一个水果，问有多少种安排方法。
我们一步一步看问题，看到先选择，就用组合。
从 33 个苹果中选 22 个，也就是 C32C_3^2；从 33 个香蕉中选 22 个，也是 C32C_3^2。
然后我们看见安排方法，就用排列。
我们将问题抽象为，将这 44 个水果安排进 44 天的位置里面，也就是 A44A_4^4。
最后就可以运用乘法计数原理求出答案：
ans=C32×C32×A44=216ans = C_3^2 \times C_3^2 \times A_4^4 = 216

排列与组合的逆向思考

从 33 名社恐和 55 名社牛中挑选 11 人搬东西，挑选 11 人帮老师接水，挑选 11 人接送老师，要求至少要有 11 名社恐，共有几种不同方案？
这一题相比前面的题多了一个要求，考虑解决这个要求。
我们采用排列的思想，也就是将问题抽象成：将 88 个人放进 33 个任务里面，要求至少 11 名社恐。
但是如何解决这个要求呢？我们正面思考的话，对于这个要求来说，可能会有 11 个或 22 个或 33 个社恐，非常麻烦。所以我们考虑逆向思考。
要求至少有 11 名社恐，逆向思考就是没有社恐呗，也就是全是社牛。也就是 A53A_5^3
而我们只用拿全部排列数减去全是社牛的排列数，不就是有社恐的排列数吗？
总共的排列数可以求出来，即 A83A_8^3 为答案；而全是社牛的排列数已经求了出来，所以这题的答案就出来了：
ans=A83−A53=276ans = A_8^3 - A_5^3 = 276

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

  • 位置问题

有 66 个人甲、乙、丙、丁、戊、己排成一横排，最左方只能是甲或者是乙，且最右端不能是甲，问有多少种排列方法。
这一题除了要求排列方法，还有要求，并且甲的事最多，所以从甲入手。
由题可得，甲只能在 11 号位至 55 号位之间，但是当甲再 11 号位的时候与再 22 至 55 号位时是不同的，所以对甲进行分类讨论。
当甲在 11 号位时，就可以将问题抽象为将乙、丙、丁、戊、己放进后面的 55 个位置，即 A55A_5^5 为答案。
当甲不在 11 号位时，即在 22 至 55 号位时，可以抽象为将甲安排进这 44 个位置，即 A41A_4^1 为答案。
因为甲不在 11 号位上，所以乙就必须在 11 号位上，这样才满足条件。
然后就是将丙、丁、戊、己放进剩余的 44 个位置，也就是 A44A_4^4 为答案。
最后的甲不在 11 号位的总方案数就为 A41×A44A_4^1 \times A_4^4。
那么最后只要将两种情况加起来就是总方案数了：
ans=A55+A41×A44=216ans = A_5^5 + A_4^1 \times A_4^4 = 216

  • 捆绑问题

有 55 个人甲、乙、丙、丁、戊排成一横排，甲不能站在两端，丙要和丁相邻，问有多少种不同的排列方法。
这一题除了有位置要求之外，丙还要和丁相邻，我们可以先处理这个条件。
我们将丙和丁看成一个元素，再和甲、乙和戊排队，所以只剩下了 44 个位置。
但是计算之前，我们发现丙和丁是可以交换位置的，因为丙和丁之间也要排队，所以事先要求出 A22A_2^2 的值。
我们再来看另一个条件，也就是甲不能在两端，那么说明甲只能在 22 号位或者 33 号位，因为一共就 44 个位置。那么甲要在这两个位置之中选择一个，也就是 C21C_2^1。
然后就只剩下了戊、丙丁和乙，也就是将这 33 个元素（我们将丙丁看作了一个元素）安排进这 33 个位置里面，即 A33A_3^3。
最后我们通过乘法计数原理求出答案即可：
ans=A22×C21×A33=24ans = A_2^2 \times C_2^1 \times A_3^3 = 24

  • 插空问题

有 66 个人甲、乙、丙、丁、戊、己排成一横排，甲乙必须相邻，丙丁不能相邻，问有多少种不同的排列方法。
这一题除了有捆绑问题还有不相邻的要求，我们想考虑捆绑。
我们将甲和乙看作一个元素，那么就有 A22A_2^2 种排列方法。
再和戊和己排队，也就是将 33 个元素放进 33 个位置里面，也就是 A33A_3^3 种排列方式。
我们再来考虑不相邻的要求，我们假设甲乙、戊、己排队之后是下面的样子：
那么要使丙丁不相邻，那么他们两个就只能在画横线的空位上面，这样就不会相邻了。
这里共有 44 个横线，也就是将两个人安排进 44 个位置，即 A42A_4^2 为答案。
最后运用乘法计数原理求出答案即可：
ans=A22×A33×A42=144ans = A_2^2 \times A_3^3 \times A_4^2 = 144

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

现有 66 个数字从 00 到 55，问这 66 个数字能组成的不相同的四位偶数的个数。
看见这道题之后，发现这和前面的题都不一样，但是先别慌。
看见了四位偶数，可以得到 22 个信息：
  • 末尾数字只能是 00 或 22 或 44 这三个
  • 首位数字不能是 00 这个数字
那么这道题不就变成了排队类型的问题吗？看见数字 00 的事情最多，所以从 00 入手。
我们类比上面的位置问题，分类讨论数字 00 的位置在末尾和不在末尾的两种情况。
若数字 00 在末尾的位置，那么现在就是将其余的 55 个数字放进还剩的 33 个位置里面，即 A53A_5^3。
若数字 00 不在末尾的位置，也就是末尾是 22 或 44 的情况。那么我们就要将 22 或 44 安排进 11 个位置里面，也就是 A21A_2^1 了。
我们还注意到首位不能是 00 这个数字，所以也就是将 5−1=45-1=4 个数安排进 11 个位置，即 A41A_4^1 了。注意这 44 个数中不含数字 00。
最后就只剩了 22 个位置，也就是将剩下的 44 个数放进 22 个位置里面，即 A42A_4^2 了。
然后运用乘法计数原理求出这种情况的答案，也就是 A21×A41×A42A_2^1 \times A_4^1 \times A_4^2 这个值。
最后的答案就是将这两种情况加起来即可：
ans=A53+A21×A41×A42=156ans = A_5^3 + A_2^1 \times A_4^1 \times A_4^2 = 156

总结

排列与组合其实说简单也不简单，说难其实也难，所以多做题有助于提升对这类题型的敏感度，所以这里有一些课后思考题：
  • 求方程 x1+x2+x3+x4=8x_1+x_2+x_3+x_4=8 的正整数解的个数
  • 现有 66 个数字从 00 到 55，问这 66 个数字能组成的不相同的五位奇数的个数
  • 55 名运动员分配 33 个项目，每个运动员至少分配 11 个项目，每个项目至少分配 11 名运动员，求不同方案的种数。

评论

共 7 条评论，欢迎与作者交流。

正在加载评论...