【算法介绍】排列组合问题汇总

文章总览：远行雪杖的清晨

排列组合，这是初赛题目和复赛数学题目中必不可少的一部分，同时也是大多数计数类 DP 的重难点所在。其特点就是各种题目百出不厌，千变万化，让人措不及防，但是实际上中国有句古话叫做“万变不离其宗”，排列组合的问题也是有一定套路可言的。本篇文章旨在总结大多数类型的排列组合基础模型以及使用方式，排列组合问题计算时几个常见的思考方向，等等等。下为文本大纲：

1. 组合数基础
2. 二项式定理
3. 隔板法基础
4. 组合数例题
5. 排列数基础
6. 错位排列
7. 圆排列
8. 多重集合排列
9. 康托展开
10. 排列组合综合应用

组合基础：便携炉具的正午

• 组合数基础
• 二项式定理
• 隔板法基础

组合数基础推导

组合数大家绝对不陌生，组合数指的就是 $n$ 个数里面选出 $m$ 个，不考虑取出的顺序，有几种取法，这个取法的方法数量就是大家常见的 $C_n^m$。

举个最常见的例子，我有 $6$ 个数字，我要从中选出 $3$ 个，那么他表示成刚刚的符号就是 $C_6^3$，但是问题是如何计算呢？非常显然的，如果我们考虑取数的顺序，那么计算出来的就是排列数，我们划去排列即可。

具体的，第一个数字有 $6$ 种取法，第二个数字就少了一个变成 $5$ 种，第三个更少是 $4$ 种取法。那么如果考虑顺序的话，其实就是有 $6\times 5\times 4$ 种取法。但是说过组合数是不考虑顺序的，这时候就会发现我们重复计算了答案。比如说我们取出了 a b c，那么组合意义下与其等价的排列们 a c b, b a c, b c a, c a b, c b a 都是被多次计算的，也就是说一共有 $6$ 个排列，每六个排列单独计算为一次，那么答案就应该是 $6\times 5\times 4\div 6$ 。

观察这个计算的过程，可以提取出一个凝练的计算公式：

$$C_n^m=\frac{n!}{m!(n-m)!}$$

这个就是组合数的基础计算公式，推广的话放在组合例题里面讲解，有非常多的变式。

友情链接：

Math Combinatorial Counting (I) | 祝馀宫

二项式定理简介

关于二项式定理，其实讲的是这样一件事：对于一个二项式 $(x+y)^n$ 我可以将其展开为公式：

$$(x+y)^n=\sum_{i=0}^nC_n^i x^iy^{n-i}=C_n^0y^n+C_n^1xy^{n-1}+\dots+C_n^nx^n$$

这是为什么呢？非常显然的来讲，对于二项式 $(x+y)^n$ 来讲，本质上就是 $n$ 个 $(x+y)$ 相乘。那么每一项的由来，其实都是二项式中的项两两组合得到的，举个常见的例子：

$$(a+b)(c+d)=ac+ad+bc+bd$$

那么其实转化成组合数问题，每一项都是一个两项之间选一项的问题，或者说若干个球选多少个，我们可以把每一项都看作一个球，如果选择了这一项的球，就说明这一项选择 $x$ 否则表示选择 $y$，那么就是组合数的问题了。显然的一共有 $n$ 个球，$x$ 的次数就是选了这么多个，其系数就应该为 $C_n^i$ 其中 $i$ 为 $x$ 的次数。

那么其实二项式系数其实可以用来表示组合数，对于二项式系数 $\binom{n}{k}$ 表示二项式的次数为 $n$ 的时候第 $k+1$ 项的系数，即 $\binom n k=C_n^k$，一般来讲用二项式系数表示组合数也是非常常见的。

与二项式定理联系非常紧密的一个数形结合经典问题，就是杨辉三角，我们可以简单的观察一下杨辉三角与二项式系数的关系：

$$\boxed{ \begin{array}{c|c} \tt{Pascal's\ Triangle} & \tt{Binomial\ (Coefficients)} \\ \begin{array}{c} 1\\ 1\quad 1\\ 1\quad 2\quad 1\\ 1\quad 3\quad 3\quad 1\\ 1\quad 4\quad 6\quad 4\quad 1 \end{array} & \begin{aligned} (a+b)^0&=1\\ (a+b)^1&=a+b\\ (a+b)^2&=a^2+2ab+b^2\\ (a+b)^3&=a^3+3a^2b+3ab^2+b^3\\ (a+b)^4&=a^4+4a^3b+6a^2b^2+4ab^3+b^4 \end{aligned} \end{array} }$$

非常显然的注意到二项式 $(a+b)^k$ 的系数就对应了杨辉三角第 $k+1$ 行的数字。这也是关于计算组合数的一个非常重要的方式，因为众所周知杨辉三角有个结论是，每一行的第一个和最后一个都是 $1$，其他的都是它上面两个数字之和。关于二项式定理的证明，其实我还在另一篇文章中写过其他方法，可以看一下：

友情链接：

Math Combinatorial Counting (I) | 祝馀宫 - The Binomial Theorem

隔板法经典问题

另外一种小学数学就学过的组合数类型问题就是隔板法，具体的问题可以是下面这样的：

放球问题：有 $n$ 个球，$m$ 个盒子，要把所有球放到盒子里，且盒子不能为空，盒子是没有区别的，球也是没有区别的。

直接考虑放不放盒子非常难以计算，这时候就需要使用隔板法思想了。大致思路就是：注意到盒子难以计算，但是因为球没有区别，我们可以随意调换位置，那么一定可以调换出一种位置使得不存在不连续的球属于同一个盒子。然后其实就是在于寻找干个不同盒子的段中间的空隙。接下来就是很简单了，$n$ 个球共有 $n-1$ 个空隙，$m$ 个盒子只需要 $m-1$ 个间隔就可以分出 $m$ 段，那么用组合数学计算就是 $C_{n-1}^{m-1}$。

与这个放球问题类似的，还有一个进阶版本，也是非常经典的一个问题。与刚刚问题不同的是，现在我们的盒子可以为空了。如果还按照刚刚的做法，这时候每一个空位可以存在多个板子，这样就不能用组合数计算。那么这时候该怎么办呢？

非常简单的，因为这个问题与上一个问题最大的区别就是盒子可以为空了，那么这时候就是很简单的往每一个盒子里面放一个球，这样的话又能保证每一个盒子都可以为空了。那么和上一题一样，这个问题的计算方式就是 $C_{n+m-1}^{m-1}$ 。

组合例题：雪崩信标的午后

• 组合数例题

组合数的计算

组合数的计算方式，有下面两种简单的，就是基于上面所谓的基础推导和二项式定理或者说杨辉三角计算。按照基础推导的公式计算的话，我们可以处理小范围内（在 $O(n)$ 可处理范围内）的所有组合数在模 $P$ 意义下的值。杨辉三角呢可以处理更小范围内（在 $O(n^2)$ 可处理范围内）的所有组合数在模 $P$ 意义下的值。

这两种方法的有缺点是，一个范围大但是代码编写难度较高，杨辉三角编码非常简单而且常用。除了这两种常用的做法还有一种叫做 Lucas 定理的做法，他是每次计算的单个组合数，但是可以处理的范围非常大，不过要求模数 $P$ 必须得是素数，exLucas 可以不是素数，这个我可能会单独开一个文章讲。

接下来放一下两个做法的代码，先是杨辉三角：

const int MAX_N = 1000;
int C[MAX_N + 1][MAX_N + 1];

void init_comb() {
    for (int i = 0; i <= MAX_N; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % MOD;
        }
    }
}

然后是递推计算：

const int MAX_N = 1e6;
int fact[MAX_N + 1], inv_fact[MAX_N + 1];

long long pow_mod(long long a, int b, int mod) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

void init() {
    fact[0] = 1;
    for (int i = 1; i <= MAX_N; ++i) 
        fact[i] = 1LL * fact[i - 1] * i % MOD;
    inv_fact[MAX_N] = pow_mod(fact[MAX_N], MOD - 2, MOD);
    for (int i = MAX_N - 1; i >= 0; --i) 
        inv_fact[i] = 1LL * inv_fact[i + 1] * (i + 1) % MOD;
}

int comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return 1LL * fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

这是关于组合数的基本计算。

组合数的变形

关于组合数公式的变形，常见的就是下面几个，接下来我们要尝试一一证明，这回基本上涵盖纯组合数问题的大多数题型。

$$\boxed{\begin{array}{c|c} \tt Number & \tt Formulation\\ 1. & k\dbinom n k = n\dbinom{n-1}{k-1}\\ 2. & \sum\limits_{k=1}^nk\dbinom{n}{k}=n2^{n-1}\\ 3. & n\sum\limits_{k=1}^{n}\dbinom{n-1}{k-1}=n2^{n-1}\\ 4. & \sum\limits_{k=1}^nk^2\dbinom{n}{k}=n(n+1)2^{n-2}\\ 5. & \sum\limits_{k=0}^n\dbinom{n}{k}^2=\dbinom{2n}{n} \end{array}}$$

1. 关于第一个变式，我们可以直接套公式得到答案：

   $$\begin{aligned} k\binom{n}{k} &= n\binom{n-1}{k-1}\\ k\cdot \cfrac{n!}{k!(n-k)!} &= n\cdot\cfrac{(n-1)!}{(k-1)!(n-k)!}\\ \cfrac{n!}{(k-1)!(n-k)!}&=\cfrac{n!}{(k-1)!(n-k)!} \end{aligned}$$

2. 第二个变式也很简单，我们可以轻松注意到第二个变式 $\sum$ 计算的部分和第一个变式有着非常高的相似性，所以直接带入到第二个变式中，得到：

   $$\begin{aligned} \sum_{k=1}^nk\binom{n}{k}&= \sum_{k=1}^nn\binom{n-1}{k-1}\\ &=n\sum_{k=1}^n\binom{n-1}{k-1}\\ &=n\sum_{k=0}^{n-1}\binom{n-1}{k}\\ &=n2^{n-1} \end{aligned}$$

3. 第三个变式和第二个变式的推导有重合，不再赘述。

4. 第四个变式从代数上理解的话，大概是这样的，还是注意到可以提取出一个第一变式形式的式子，然后一路化简可以变成下面这样：

   $$\begin{aligned} \sum_{k=1}^nk^2\binom{n}{k} &=\sum_{k=1}^nk\cdot k\binom{n}{k}\\ &=\sum_{k=1}^nk\cdot n\binom{n-1}{k-1}\\ &=n\sum_{k=1}^n\left((k-1)\binom{n-1}{k-1}+\binom{n-1}{k-1}\right)\\ &=n\sum_{k=1}^n\left((k-1)\binom{n-1}{k-1}\right)+n\sum_{k=1}^n\binom{n-1}{k-1}\\ &=n\sum_{k=2}^n\left((n-1)\binom{n-2}{k-2}\right)+n2^{n-1}\\ &=n(n-1)\sum_{k=2}^n\binom{n-2}{k-2}+n2^{n-1}\\ &=n(n-1)2^{n-2}+n2^{n-1}\\ &=n(n+1)2^{n-2} \end{aligned}$$

5. 第五个变形和上面的都不太一样。似乎不在能用百试不爽的变式一得到答案了，那么我们就回归本源，从二项式系数开始搞定这道题目。首先考虑二项式系数 $\binom{2n}{n}$ 可以如何表示：

   $$(1+x)^{2n}=\sum_{m=0}^{2n}\binom{2n}{m}x^m$$

   那么根据乘方的基本运算我们可以把它拆开来：

   $$(1+x)^{2n}=(1+x)^n(1+x)^n=\left(\sum_{k=0}^n\binom{n}{k}x^k\right)\left(\sum_{l=0}^n\binom{n}{l}x^l\right)$$

   这两个多项式的值显然相等，所以对应次数项的系数也应该相等，考虑第 $n$ 项是怎么样的。因为单项式相乘，同未知数次数相加，系数相乘，可以得到下式：

   $$\sum_{\substack{k,l\ge 0\\k+l=n}}\binom{n}{k}\binom{n}{l}=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}$$

   又由于组合数的对称性：

   $$\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}=\sum_{k=0}^n\binom{n}{k}^2$$

   然后对于二项式 $(1+x)^{2n}$ 的第 $n$ 次项的系数，显然就是 $\binom{2n}{n}$ 所以相等，该变式成立。

组合数的例题

这里给出两个例题思考一下。

例题　壹

一个班里有 $n$ 个人，要从其中选出一些候选人（没有数量限制），并从候选人中选出两个班干部职位，一个人可以同时拥有多个职位。问一共有多少种不同的班干部选法和候选人选法。

这题有两种思考的方向，我们可以先考虑选择候选人，那么就根据加法公式：

$$\sum_{k=1}^n\binom{n}{k}k^2$$

枚举候选人的数量，然后取的个数就是 $\binom{n}{k}$，然后 $k$ 个人中，由于一个人可以有多个职位，所以直接 $k^2$ 就可以了。然后我们发现这个就是上面的变式四。

第二种思考方向是考虑先选班干部，我们分类讨论一下：

1. 如果两个班干部职位给同一个人，那么剩下人选中或者没有选中都不重要了，只要这个人被选中即可。

   $$n\sum_{k=0}^{n-1}\binom{n-1}{k}=n2^{n-1}$$

2. 如果两个班干部职位不是同一个人，那么还是只需要保证候选人中有这两个人，其他的人候不候选无所谓：

   $$n(n-1)\sum_{k=0}^{n-2}\binom{n-2}{k}=n(n-1)2^{n-2}$$

根据加法原理，答案为 $n2^{n-1}+n(n-1)2^{n-2}=n(n+1)2^{n-2}$，这个就是最终答案，其实也是变式四另一个角度的证明方法，用于帮助理解变式四。

例题　贰

一个班有 $n$ 个男生，$n$ 个女生，要从中选出 $n$ 个人，有几种选法？

这个问题有人直接上来说 $\binom{2n}{n}$ 确实，这是一个做法，直接考虑组合即可。

但是从另一个角度上来讲，我们还是可以枚举男生或者女生选区的人数，那么另外一群人就也可以计算：

$$\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}=\sum_{k=0}^n\binom{n}{k}^2$$

其实这也是变式五另一个角度的证明，因为上面变形的时候会有一点抽象。

排列基础：露营篝火的薄暮

• 排列数基础
• 错位排列
• 圆排列
• 多重集合排列
• 康托展开

排列数基础介绍

排列数其实应该放在组合数之前讲的，因为这个好像比组合数还要基础，不过由于这里对于排列的拓展比组合要多，所以就放在了组合后面。

关于排列的基础大家绝对不陌生，我有 $10$ 个人要排名次，拍到前三名的话，就是 $10\times 9\times 8$，前五名的话就是 $10\times 9\times 8\times 7\times 6$，总而言之，每选一个，选择会减少，而且是有顺序区别的。对于一个排列数来说，$P_n^m$ 或者 $A_n^m$ 都是常见的表达方式，表示从 $n$ 个人中选择 $m$ 个出来排列的方法数。

从上面举的例子，也就不难看出排列数的计算公式应该是：

$$P_n^m=\frac{n!}{(n-m)!}$$

这个应该不必我赘述，接下来看拓展。

错位排列的计算

错位排列，简称错排。如果我们有一个标准答案比如说 1 2 3，如果我们能构造出一个排列，其中没有任何同一位置的元素相同，那么这就是一个合法的错排。对于这个例子来说，错排只有 3 2 1 一个。错牌中的元素只能是从 $1$ 到它的长度互不相同的这些数。

了解了什么时错排，我们可以思考如何计算错排。一个比较简单的想法是递推，我们来回顾一下这个经典的做法。

设 $dp[i]$ 表示长度为 $i$ 序列的错排数量，假设已经处理出了 $1\sim i-1$，现在要计算 $dp[i]$。那么我们可以假设把第 $i$ 个数字放在 $j\in[1,i)$ 位置上，那么这个被顶掉的 $j$ 其实有两个选择：放在 $i$ 的位置上和继续参与错排。那么对应的其递推公式就应该是：

$$dp[i]=(i-1)\times(dp[i-2]+dp[i-1])$$

这就是错位排列的计算。

圆排列求解方法

圆排列是一个罕见的概念，我们把一些循环的排列被称为本质相同的圆排列，比如说下面这样：

非常显然的，对于一个元素互不相同的排列来说，他在圆盘上的循环只会有 $n$ 种，所以原排列的计算方式应该是 $(n-1)!$ 种。

圆排列一般来说就是出现在圆环桌子的问题上，题目一般来说会强调忽略本质相同的圆排列。

例题　叁

有 $5$ 对夫妇和 $A,B$ 共 $12$ 人参加一场婚宴，他们被安排在一张 $12$ 个座位的圆桌就餐，要求每对夫妻都相邻坐，$A,B$ 不相邻，甲、乙太太是闺蜜又要相邻坐，如果旋转之后相同算一种坐法，一共有多少种安排方法？

由于甲乙太太相邻，所以他们两个捆在一起，可以互相交换位置，那么就是 $2$ 种坐法，而甲乙先生必须坐在太太旁边所以他们别无选择。然后剩下来还有 $3$ 对夫妇，直接排列 $3!$ 种，别忘了夫妇之间还可以换位置，额外要乘以 $2^3$。然后还有 $A,B$ 两个人，这两个人可以随机的插在除了甲乙之间的任意一对夫妇中间，所以是 $P_4^2$ 种，最终答案为 $1156$ 种坐法。

如果题目没有说旋转座位后相同，或者强调了旋转作为后不同，我们只需要知道一个排列对应一套圆排列就是 $n$ 个，乘上 12 即可。

多重集合排列题

所谓多重集合排列，就是一个集合，他里面有很多种相同的元素，然后用它来排列算。一般来讲我们限制排列中的元素都是不相同的，但是这个多重集合会有相同的元素，所以不能直接计算了。

但是其实一想也不难，假设有 $r_1$ 个 $a_1$，$r_2$ 个 $a_2$ …… $r_k$ 个 $a_k$。那么要求这个多重集合的元素其实非常简单，我们知道一共 $n$ 个元素，我们假设所有元素先不相同，那么就是有 $n!$ 种排列。另外呢？由于其中有相同的元素，那么他们之间相对的前后顺序，都是不必要的，这也就意味着，最后的答案应该是：

$$\cfrac{n!}{r_1!\times r_2!\times r_3!\times \cdots\times r_k!}$$

这就是多重集合的排列，但是很简单。关于多重排列的例题，一会再综合例题中会讲到一个有意思的，敬请期待。

康托展开的推导

关于康托展开，是一个非常有趣的知识点，它的作用在于计算一个排列之前有多少个排列，也就可以用于计算某一个排列排在第几个，相对的还可以计算排名第几的排列是谁。这里的排名是基于字典序意义下的排名。

首先放出关于计算一个排列之前有多少排列的公式：对于一个长度为 $n$ 的排列，他之前有 $X$ 个排列，其中 $a$ 数组表示第 $i$ 个位置的右边比当前位置小的数字的个数。

$$X=a_1(n-1)!+a_2(n-2)!+\cdots+a_n0!$$

这是为什么呢？可以想一下，对于第一个数字来说，右边每一个比它小的数字意味着什么？当那些比他们小的数字在第一个的时候，字典序永远都比当前排列小，所以剩下的数字不论怎么排都可以，这就是 $a_1(n-1)!$ 的含义，一样的，其他几项都是这样，这就计算出了某一个排列以前的排列个数，那么排名只要在此次基础上加一即可。

举个例子，对于长度为 $4$ 的排列 2 4 1 3 来说，其对应的 $a$ 数组为 1 2 0 0 带到公式里就是：

$$X=1\times 3!+2\times 2!+0+0=14$$

那么这个排列就排名 $15$，想要验证的可以自己枚举一下（绝对不是因为我懒

康托展开的逆展开，也就是已知排名求排列，其实就是和刚刚一样，倒过来。比如说我们要求 $5$ 的排列中字典序排在第 $107$ 的排列，那么按照刚刚的思路就是这样的。在这个排列之前应该有 $106$ 个排列，然后我们一路计算下去，设有一个数字备选序列 $[1,2,3,4,5]$ ：

• $106\div 4!=4\dots\dots10$，这时候 $a_1=4$ 然后就说明当前数字是 $5$，备选序列 $[1,2,3,4]$。
• $10\div3!=1\dots\dots4$，这时候 $a_2=1$ 说明当前数字是 $2$，备选序列 $[1,3,4]$。
• $4\div 2!=2\dots\dots0$，这时候 $a_3=2$ 说明当前数字是 $4$，备选序列 $[1,3]$。
• $0\div1!=0\dots\dots0$，这时候 $a_4=0$ 说明当前数字是 $1$，备选序列为 $[3]$。
• $3$ 即为最后一位数字。

那么这样就得到的排列的数量，这就是康托展开的逆展开，对于其正确性有这样的证明：

综合例题：极光红茶的新夜

• 排列组合综合应用

例题一：认人

题目传送门

在某校有一个女生队，队名叫RGB，但学生骆驼不知道RGB三个人具体谁是谁。

RGB 给他机会让他猜猜：
第一次猜：R是公主，G是草儿，B是月野兔；
第二次猜：R是草儿，G是月野兔，B是公主；
第三次猜：R是草儿，G是公主，B是月野兔；
……
可怜的骆驼第五次终于把RGB分清楚了。

可现在有 $n$ 个人，他要猜的次数可就多了，为了不为难骆驼，女生们只要求他答对一半或以上就算过关，请问有多少组答案能使他顺利过关。

非常简单，只要枚举答对多少人，剩下的错排即可。

long long ans = 0;
for(int i = ceil(1.0 * n / 2); i <= n; i++) {
    ans += dp[n - i] * C[n][i];
}
printf("%lld\n", ans + 1);

例题二：点蜡烛

题目传送门

在一排，有连续排列的 $n$ 个蜡烛。 这些蜡烛从左到右从 $1$ 到 $n$ 编号。
最初，有些蜡烛是点燃的。 旭旭想要点燃所有的蜡烛。
但下一步要点燃的蜡烛必须是已经点燃的蜡烛的旁边（左右）
他知道蜡烛的初始状态，并且想知道有多少种方法可以点燃所有蜡烛。
答案对 $1000000007$ 取模。

这个也非常显然，两边的空段只有一种方向，中间的空段可以选择方向，可以把每一个空段看作一个集合，若干个集合内部的顺序不能变，所以求出总共的方法数然后除以排列数，在乘上某一个部分选择方向的方法数即可。

sort(wz+1,wz+w+1);
int cs=1,cnt=0,cj=1;;
for(int i=2;i<=w;i++)
{
    if(wz[i]-1==wz[i-1]) continue;
    int l=pw(2,wz[i]-wz[i-1]-2);
    cnt+=wz[i]-wz[i-1]-1;cj=cj*l%inf;
    cs=cs*jc[wz[i]-wz[i-1]-1]%inf;
}
cnt+=wz[1]-1;cs=cs*jc[wz[1]-1]%inf;
cnt+=n-wz[w];cs=cs*jc[n-wz[w]]%inf;
int g=jc[cnt]*cj%inf*pw(cs,inf-2)%inf;
printf("%lld",g);

算法实战：测绘图纸的黎明

查看相关算法标签喵！

参考资料（以下排名不分先后）

• 517编程 - Online Judge
• 康托(Cantor)展开与逆展开理解与运用_康托展开-CSDN博客