刷算法题必备的数学考点汇总（2）

在算法学习中，数学主要分为「数论」与「组合计数」两大部分。相比「数论」，「组合计数」通常是作为一种计数思想与其他题型（例如「动态规划」）相结合，进行统一考察。

在上一篇文章中，我们已针对「数论」进行了讲解，本文将介绍「组合计数」。

排列组合

加法原理

若完成一个任务的方法有 n 类，其中第 i 类方法有

种不同的做法，则完成这个任务共有

种不同的做法。

乘法原理

若完成一个任务需要分 n 个步骤，其中第 i 个步骤有

种不同的做法，且这些做法互不干扰，则完成这个任务共有

种不同的做法。

排列数

从 n 个不同元素中依次取 m 个元素排成一列

，产生的不同排列的数量为：

上述公式可以这样理解：n 个人选 m 个人来排队，第一个位置可以选 n 个，第二个位置可以选 n - 1 个，以此类推，第 m 个位置可以选 n - m + 1 个。再根据乘法原理，便可得到上述公式。

另外需要注意，0! = 1。

组合数

从 n 个不同元素中任取 m 个元素组成一个集合

，产生的不同集合的数量为：

上述公式可以这样理解：n 个元素选 m 个组成一个集合，集合数量为

，其中每个集合均有 m! 种不同的排列方案。因此 n 个元素选 m 个组成一个排列，排列方案总数为

，由此可得上述公式。

组合数性质

组合数的性质较多，此处仅列举两个较为重要的性质进行讲解。

首先是「组合数递推公式」，即

。该公式可以这样理解：n 个元素选 m 个组成一个集合，若第 n 个元素取，则方案数为

；若不取，则方案数为

。再根据加法原理，即可得到该递推式。

其次是「二项式定理」，即

，该式可使用「数学归纳法」证明，此处不再赘述。

多重集问题

多重集是指包含重复元素的广义集合。设集合 S 是由

组成的多重集，其中

多重集的排列数

从集合 S 中选取 n 个元素组成排列，其数量为

，即集合 S 的全排列个数。

该式子可以这样理解：对于每一类

，其重复出现的次数为

因此在 n! 的基础上除以所有

即可得到上述答案。

多重集的组合数

从集合 S 中选取 r

个元素组成一个多重集，其方案数为

该式子可以这样理解：由于

因此该问题等价于在每一类

中选取

个元素，使得

的方案数。

转化后的问题可由「插板法」解决，假设当前共有 r + k - 1 个位置，现需在其中 k - 1 个位置插上一块分隔板，将原来的 r + k - 1 个位置分隔成 k 个区域，其中第 i 个区域的空位置数即为

。

由此可以得知

的方案数等价于 r + k - 1 个位置中选 k - 1 个位置插板的方案数，即答案为

常见计数模型

不相邻的排列

在 1 到 n 这 n 个自然数中选 k 个，使得 k 个数中任意两个数都不相邻的方案数共

个。

该问题等价于当前有蓝色小球 k 个，红色小球 n - k 个，现要将蓝色小球插入红色小球的间隙中，且每个间隙最多插入 1 个蓝色小球，共有多少种方案。

对于每一种插入方案，再插入完后对小球从左到右，从 1 开始编号，其中蓝色小球的编号就是原问题中选取的 k 个自然数。由于每个间隙最多插入 1 个蓝色小球，因此可以保证选取的 k 个数中任意两个都不相邻，即转换后的问题与原问题等价，由此可知总方案数为

个。

错位排列

n 个不同的小球，编号分别为 1 到 n，现在要将这 n 个小球进行排列，使得第 i 个位置上的小球，其编号不为 i，求排列方案数。

令 f[n] 表示 n 个小球的错排方案数，则思考 f[n] 可以由哪些状态一步转移过来？

假设当前编号为 n 的小球放在第 n 个位置，则 n 个球的错排只能从以下两种情况一步转移而来：

1. 前面 n - 1 个小球编号与位置均不同

2. 前面只有一个小球 i 的编号与位置相同

对于第一种情况，可以任选一个小球与第 n 个小球进行位置交换，使其满足错排要求，即

。

而对于第二种情况，可以令小球 i，n 交换来满足题意。由于 i 共有 n - 1 种可能，因此

综合上述两种情况，

，其中

。

圆排列

n 个人围成一圈，所有的圆排列数记为

对于每一个圆排列，从不同的位置断开，都可以变成一个新的排列，因此可知

，即

。

进一步延伸可知，从 n 个人中选 r 个人围成一圈，其圆排列数为

。

康托展开

康托展开可以在 O(n^2) 的时间复杂度内（可用树状数组优化到 O(nlogn)) 求得任意一个 n 个数的排列的排名。

此处将 n 个数的所有排列按字典序排序，任意一个排列的位次即为它的排名。例如排列 [2,4,3,5,1] 的字典序小于排列 [2,4,5,3,1]，则排列 [2,4,3,5,1] 的排名更小。

康托展开主要是一种算法思想，我们以排列 [2,5,3,4,1] 为例来进行阐述。

我们通过从左到右依次考虑各个位置的方式来计算答案。首先是第一个位置，不难发现排列 [2,5,3,4,1] 大于所有「以 1 开头的排列」，而以 1 开头的排列共有 4！个。

接下来考虑第二个位置，它大于所有「第一位与当前排列相同，而第二位小于 5 的排列」，由于 2 已经在第一位出现了，因此第二位可以为 1，3，4，即第二位所贡献的答案为 3*3！。

以此类推，最终答案为 1 + 4！+ 3*3！+ 2！+ 1 = 46，由于统计的是排名，因此最开头需要加上一个 1。

根据上述思想，我们即可通过依次考虑每一位的贡献计算一个排列的排名。

习题练习

62. 不同路径

题目描述

一个机器人位于一个 n x m 网格的左上角，即 (1,1)。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，即 (n,m)。

问总共有多少条不同的路径？

示例 1

输入: n = 2, m = 3输出: 3解释:从左上角开始，总共有 3 条路径可以到达右下角。1. 向右 -> 向右 -> 向下2. 向右 -> 向下 -> 向右3. 向下 -> 向右 -> 向右

示例 2

输入: n = 3, m = 7输出: 28

提示

题目数据保证答案小于等于 2* 10^9

解题思路

我们从「组合计数」的角度来考虑这道题，从（n,m）走到 (1,1)，每次只能向下或向右移动一步，因此不难发现，一共需要移动 n + m - 2 步，其中 n - 1 步向下，m - 1 步向右。

因此问题转化为在 n + m - 2 个位置中选 n - 1 个位置填入「向下」，其余位置填入「向右」的方案数，即最终答案为

代码实现

classSolution {public:int C[200][200];intCount(int m, int n) {if (n == 0 || m == n) return1;if (C[m][n]) return C[m][n];return (C[m][n] = Count(m-1, n) + Count(m-1, n-1)); }intuniquePaths(int m, int n) {return Count(m+n-2, n-1); }};

1359. 有效的快递序列数目

题目描述

给你 n 笔订单，每笔订单都需要快递服务。

请你统计所有有效的「收件/配送」序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。

由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。

示例 1

输入：n = 1输出：1解释：只有一种序列 (P1, D1)，物品 1 的配送服务（D1）在物品 1 的收件服务（P1）后。

示例 2

输入：n = 2输出：6解释：所有可能的序列包括：(P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。

(P1,D2,P2,D1) 是一个无效的序列，因为物品 2 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。

示例 3

输入：n = 3输出：90

提示

解题思路

该题有两种做法，分别是「动态规划」与「组合计数」。首先介绍「动态规划」的做法，令 f[i] 表示 i 笔订单的答案，则 f[i] 可从 f[i - 1] 转移而来。

对于 f[i - 1] 中的一个合法序列，其中共有 2(i - 1) 个元素，因此现需要将

和

插入其中，且满足

在

之前。

对于该问题，我们可以使用「插板法」的思想，即在 2(i - 1) 的基础上再加两个元素，即 2i。然后再在 2i 个元素中选取 2 个元素，前面的放

，后面的放

，因此共

种方案，即：

根据上述式子，递推即可得到答案。

另外我们还可以从「组合计数」的角度直接计算出 f[n] 的值。我们可以这样思考，若不要求

在

之前，则 n 笔订单共

种方案。

另外，f[n] 表示每个

都在

之前的方案数，因此我们考虑如何从 f[n] 推出

不难发现，对于 f[n] 中的每个序列，其中的

，

均可选择交换或者不交换来形成

中的一个序列，因此根据乘法原理，可以得到

即

其中

代码实现

classSolution {public:intcountOrders(int n) {longlong mod = 1e9+7, ans = 1;for (int i = 1; i <= n; i++) { ans = ans * i % mod; ans = ans * (2 * i - 1) % mod; }return ans; }};

60. 排列序列

题目描述

给出集合 [1，2，3，…，n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

"123""132""213""231""312""321"

给定 n 和 k，返回第 k 个排列。

示例 1

输入：n = 3, k = 3输出："213"

示例 2

输入：n = 4, k = 9输出："2314"

示例 3

输入：n = 3, k = 1输出："123"

提示

解题思路

该题给定排列的排名，返回原排列，是「康托展开」的逆问题。因此我们可以根据「康托展开」的思想，来反推「逆康托展开」的实现过程。

依然以 [2，5，3，4，1] 为例来进行算法阐述。根据前文可知，该排列的排名为 46，首先让 46 - 1 = 45，即有 45 个排列比当前排列小。

接下来计算排列的第一位数字，

即有 1 个数小于当前排列的第一位，因此第一位为 2，更新

计算第二位的数字，

即有 3 个数小于当前排列的第二位，除去第一位的 2，可知第二位为 5，更新

以此类推，可以得知原排列为 [2，5，3，4，1]。根据上述过程的思想，便可实现本题的「逆康托展开」。

代码实现

classSolution {public:stringgetPermutation(int n, int k){vector<int> fac(n + 1, 0), vis(n + 1, 0);string ans; fac[0] = 1, k--;for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i;for (int i = n; i >= 1; i--) {int now = k / fac[i-1]; k -= fac[i-1] * now;for (int j = 1; j <= n; j++) {if (now == 0 && !vis[j]) { ans += '0' + j; vis[j] = 1;break; }if (!vis[j]) now--; } }return ans; }};

总结

本文的总体框架如下，重点在于对上文中各个「组合计数」方法的掌握与理解。

文中算法大多为「组合计数」的基础算法，大家日后刷题遇到时可以及时巩固相关知识点，祝大家刷题愉快！

BY /

本文作者：Gene_Liu

编辑&版式：霍霍