浅谈排列组合

Bc2_Ch1ckenPr1nce · 2026-04-30 14:57:27 · 算法·理论

说明

由于篇幅原因，大部分例题不放代码。

排列组合基础

Part 0：前置知识

• 中学数学。

Part 1：什么是组合数学？

1.1：定义

组合数学是研究“离散对象的选择、排列、分配”的数学分支，核心是计数——不重复、不遗漏地计算满足条件的方案数，是算法竞赛中“计数类问题”的核心解题工具。

与代数、几何不同，组合数学不关注“数值运算”或“图形性质”，而是关注“离散结构的存在性、计数、构造”，比如：从 n 个物品中选 k 个有多少种选？n 个人排队有多少种排法？这些都是组合数学的核心问题。

人话就是搞排列组合的。

1.2：一些经典问题

• 从 n 个元素中选 k 个进行排列的方案数;
• 从 n 个元素中选 k 个不考虑顺序的方案数;
• 计算至少满足一个条件的方案数;
• 卡特兰数、错位排列。

Part 2：加法和乘法原理

所有组合计数问题，本质上就是应用了加法和乘法原理，可以说加法和乘法原理是组合计数的基本原理。

加法和乘法原理也是所有组合计数问题中最简单的原理。

2.1：加法原理

若完成一件事情，有 k 类不同的方法，每类方法都能完整的完成这一件事。令第 i 种方法有 m_i 种方式，则完成事情的总方法数是：

例子：若做一道饭菜有 4 种方法先洗菜，3 种方法先热油，则做这一道饭菜有 4 + 3 = 7 种方法。

2.2：乘法原理

若完成一件事情，有 k 个步骤，每个步骤都不能完整的完成这一件事。令第 i 个步骤有 m_i 种方式，则完成事情的总方法数是：

例子：小 M 想去旅游，要先开车到高铁站（3 条路线）再坐高铁到目的地（5 条路线），再从目的地打车到酒店（2 条路线），则他有 3 \times 5 \times 2 = 30 条路线从家里到酒店。

Part 3：排列问题

3.1：排列的定义

从 n 个不同的元素中，选出 k 个元素，并按照一定的顺序排成一列，这样的一列叫做一个“排列”。

所有这样的排列的个数，叫做“排列数”，记为 A_n^k（或者 P_n^k）。

特别的，当 k = n 时，A_n^k = A_n^n = n!，也就是全排列。

3.2：排列数公式

首先在 n 个元素中选一个数有 n 种选法。选完之后，就只剩下 n - 1 个数了，只有 n - 1 种选法，以此类推。

换而言之，第 k 次选择有 n - k + 1 种选法。

根据乘法原理：

变形（分子分母同乘 (n - k)!），得：

即：

Part 4：组合问题

4.1：组合的定义

从 n 个不同的元素中，选出 k 个元素，不考虑顺序，组成一组，这样的一组叫做一个“组合”。

所有这样的组合的个数叫做“组合数”。

4.2：组合数公式

众所周知，排列就是组合加上一个先后的顺序。

所以我们可以按如下方法推导公式：

• 从 n 个元素中选 k 个元素，不考虑顺序，有 C_n^k 种组合；
• 对于每一种组合，将 k 个元素进行全排列，有 A_k^k = k! 种排列方式；
• 所有组合的全排列，恰好等于从 n 个元素中选 k 个元素的排列数，即 A_n^k。

所以，我们便得到 A_n^k = C_n^k \cdot A_k^k。

变形，得：

4.3：组合数的基础性质

性质 1（对称性）：

性质 2：

性质 3（吸收恒等式）：

前三个性质的证明比较简单，都是直接代入即可。

性质 4（组合数递推公式）：

证明：

从 n 个元素中选 k 个，可分为两种情况:

• 包含某个特定元素：此时需要从剩下的 n - 1 个元素中选 k - 1 个，方案数为 C_{n - 1}^{k - 1}；
• 不包含这个特定元素：此时需要从剩下的 n - 1 个元素中选 k 个，方案数为 C_{n - 1}^k。

根据加法原理，总方案数为两种情况之和，即：

性质 5（hockey-stick 恒等式）：

证明：

我们巧妙的运用性质 4（C_n^k = C_{n - 1}^{k - 1} + C_{n - 1}^k）。

排列组合进阶

Part 0：前置知识

• 排列组合基础。

Part 1：多重集的排列数

1.1：定义

多重集：记为 S = \{c_1 \cdot a_1,\ c_2 \cdot a_2,\ \cdots,\ c_k \cdot a_k\}。

其中，a_i 为元素，c_i 为每一种元素出现的次数。显然，总元素即为：n = c_1 + c_2 + \cdots + c_k。

可重全排列：将多重集的所有元素排成一列，相同元素交换位置不算新排列，求总方案数。

1.2：公式推导

1. 假设所有 n 个元素都不同，全排列数为 n!；
2. 第 i 种元素有 c_i 个相同的，它们内部的 c_i! 种排列是重复的；
3. 所有重复的排列都要剔除，因此除以所有 c_i!。

综上，公式为：

Part 2：隔板法（插板法）

2.1：无限可重组合

问题：有 k 种不同元素，每种可以选任意多次，从中选 n 个元素，不考虑顺序，求方案数。

这个问题一看就非常难 /jk，所以我们充分运用转化思想。

设选第 i 种元素 x_i 个，则 x_1 + x_2 + \cdots + x_k = n（x_i \ge 0），那么答案就是解的个数了。

接下来，我们使用隔板法推理。

假设我们有 n 个相同的小球，需要分成 k 组。那么，我们就可以凭空想象出 k - 1 个隔板，这些隔板就是来分隔每一组的。加上板子后，我们放置物品的位置总共有 n + k - 1 个，我们需要选择 k - 1 个位置放上隔板。

这样就很简单了，答案便为 C_{n + k - 1}^{k - 1}。

而且，这个知识与生成函数有着关联，它就是 (1 + x + x^2 + \cdots)^k 中 x^n 项的系数。

2.2：有限可重组合

问题：有 k 种不同元素，每 i 种至少要选 c_i 次，从中选 n 个元素，不考虑顺序，求方案数。

嗯，可以说是双倍经验。

先来讨论，如果每一种元素至少选一个（即 x_i \ge 1）的情况。我们可以这样思考：如何将条件变为无限可重组合？

很简单，令 x_i' = x_i - 1，这样就保证了 x_i' \ge 0。然后我们套一下原来的方程，就变成：

变形，得：

答案即为 C_{n - k + k - 1}^{k - 1} = C_{n - 1}^{k - 1}。

接下来就可以从特殊问题推导一般问题。由于每一个元素最多可以选 c_i 次，所以对于每一个 i \in [1, n]，都有 x_i \ge c_i。

令 x_i' = x_i - c_i，得：

变形，得：

于是得到答案：\displaystyle C_{n - \sum c_i + k - 1}^{n - \sum c_i}。

2.3：不相邻排列

问题：在 1 至 n 的自然数中选 k 个，求这 k 个数中任何两个数都不相邻的组合数量。

令选出的数为 a_1 < a_2 < \cdots < a_k，则 a_{i + 1} - a_i \ge 2。

再令 b_i = a_i - (i - 1)，则新数列 \{b_k\} 是无相邻限制的严格单调上升数列

由于 b_k = a_k - (k - 1) \le n - k + 1，所以问题等价于在 1 至 n - k + 1 的自然数中任选 k 个不同的数。

答案即为 C_{n - k + 1}^k。

补充：不相邻选数问题本质是隔板法（插板法）的逆向应用。

Part 3：二项式定理

3.1：公式推导

在竞赛中，有一个经典的问题：求 (a + b)^n 的展开式。

怎么求？相信可爱的我们一定会先这样，然后运用我们敏锐的观察力：

哦！系数组成一个杨辉三角，直接做完了。

但是，竞赛中的感性观察不一定是对的，我们需要详细证明。

对于每一个 (a + b)，我们都可以选择 a 或者 b 来与 (a + b)^{n - 1} 相乘。那么，a^ib^{n - i} 项的系数就是在 n 个选择里选择了 i 个 a 和 n - i 个 b 的方案数，即为 C_n^i。当然，也可以使用数学归纳法。

于是，我们便得到了二项式定理：

把系数提出来后，我们便得到了杨辉三角。

3.2：定理的应用

应用 1（二项式系数和）：

证明 1：

在二项式定理中，令 a = b = 1，则：

应用 2（奇数项和与偶数项和相等）：

证明 2：

在二项式定理中，令 a = 1，b = -1，则：

展开并移项，得：

由于组合数的性质，等式两边均为 \frac{2^n}{2} = 2^{n - 1}。

Part 4：多重集的组合数

由于这一部分涉及到了容斥，所以放在最后来讲。

问题：对于可重集 S = \{c_1 \cdot a_1,\ c_2 \cdot a_2,\ \cdots,\ c_k \cdot a_k\}。设 n = \sum_{i = 1}^{k} c_i，对于任意整数 r \le n，从 S 中取出 r 个元素组成一个多重集（不考虑顺序），求产生的不同多重集的数量。

此问题等价于：有 k 种不同元素，每 i 种最多可以选 c_i 次，从中选 r 个元素，不考虑顺序，求方案数。

首先本题本质也是是求方程：

的非负整数解数量，只不过有 0 \le x_i \le c_i。

先抛开上限限制，答案就为 C_{r + k - 1}^{k - 1}。 这个式子会包含所有合法情况，也会包含所有选超上限的非法情况，比如某一类物品选了 c_i + 1 个及以上，我们需要把这些非法方案全部删掉。

一开始我们直接用总无限制方案数，里面混着：完全合法的方案，第一种超标的方案，第二种超标的方案，第一种 + 第二种同时超标的方案……

现在第一步操作，我们把任意单独一种超标全部方案强行减掉，也就是减掉所有 x_1 \ge c_1 + 1 的方案，减掉所有 x_2 \ge c_2 + 1 的方案，以此类推。

但这里会出现重复扣除的问题：如果一套方案里第一种、第二种物品同时超标，它会在删第一种超标时被减一次，又在删第二种超标时被再减一次，等于被多减了一遍，本来只需要剔除一次，结果被扣了两次，所以必须把这类两个同时超标的方案重新加回来补偿。

继续往下推，如果存在三个物品同时超标，这套方案会在删单个超标时被减三次，在补两个超标时被加三次，整体相当于完全没删，依旧非法，所以需要再减掉三个同时超标的方案。

以此往复，就形成固定规律：钦定非法物品个数为奇数时做减法，钦定非法物品个数为偶数时做加法，这就是容斥原理的由来。

接下来处理任意一组被强制超标的集合，设选中的物品需要满足 x_i \ge c_i + 1，令 y_i = x_i - (c_i + 1)，满足 y_i \ge 0，代入原方程化简，剩余可自由分配的数量为 t = r - \sum (c_i + 1)，当 t \ge 0 时，该种非法情况的方案数为 C_{t + k - 1}^{k - 1}。当 t < 0 时，无法分配，对应方案数为 0。

一般情况下，题目有限制：k \le 20，可以用二进制 mask 枚举所有物品子集，每一个子集代表一组强制超标的物品，统计子集内元素个数，根据奇偶性加减对应组合数，全部累加后就是最终答案：

本节例题

P1866 编号

容易发现，当前面的兔子都给过编号 i，那么后面的兔子不能再编号为 i。

所以考虑从小到大排序。根据乘法原理，答案即为 a_i - i + 1 的乘积。为什么呢？因为之前选的编号已经包含在 [1, a_i] 了。也就是说，之前有 i - 1 个编号已经被占用。

P5520 [yLOI2019] 青原樱

这是典型的不相邻问题，我们使用插空法。

由于两支幼苗之间至少要有一个空位，所以 m 支幼苗之间必须有 m - 1 个空位。

那么，剩下的 n - (m - 1) = n - m + 1 个位置就可以随便乱放了。

然后，又因为剩下的位置是无序的，所以答案是 A_{n - m + 1}^m 而不是 C_{n - m + 1}^m。

P1313 [NOIP 2011 提高组] 计算系数

讲过的二项式定理。

使用递推式计算组合数，然后注意乘上系数 a, b 即可。

递推式：f_{i, j} = b \cdot f_{i - 1, j - 1} + a \cdot f_{i - 1, j}。

P2822 [NOIP 2016 提高组] 组合数问题

由于 n, m 很小，考虑用递推式计算 C_j^i \bmod k。

显然，如果模完后得到 0，那么有 k \mid C_j^i。

那接下来怎么办呢，暴力累加答案会爆炸。

其实这时候，二维前缀和就派上用场了，只需算完组合数后使用二维前缀和累加即可。

::::success[Code]

void Init() {
  for (int i = 0; i <= 2000; ++ i) {
    f[i][i] = f[i][0] = 1;
  }
  for (int i = 1; i <= 2000; ++ i) {
    for (int j = 1; j < i; ++ j) {
      f[i][j] = (f[i - 1][j - 1] + f[i - 1][j]) % k;
    }
  }
  for (int i = 1; i <= 2000; ++ i) {
    for (int j = 1; j <= 2000; ++ j) {
      ans[i][j] = ans[i][j - 1] + ans[i - 1][j] - ans[i - 1][j - 1];
      if (!f[i][j] && j <= i) {
        ++ ans[i][j];
      }
    }
  }
}

::::

P3197 [HNOI2008] 越狱

本题运用了计数问题的一种 trick。

可以发现，直接算有多少种状态可能发生越狱不好算，那么一个公式：总数 = 可能发生 + 不可能发生。

这个公式在计数问题中非常实用，当你发现直接算不好算是可以借助这个公式。

接下来就很简单了，因为有 m 种宗教，有 n 个房间，那么总数为 m^n。

然后考虑不发生越狱的情况。由于第一个房间宗教完全自由，所以有 m 种情况。后面的房间不能与前面的房间重合，所以有 m - 1 种情况。那么，不发生越狱总共有 m \cdot (m - 1)^n 种情况。

答案即为：m^n - m \cdot (m - 1)^n，快速幂计算即可。

U618070 【模版】多重集组合数

不知道怎么找到的这道题。

模板题，按照思路编写代码即可。

::::success[Code]

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ull = unsigned long long;

const int kMaxN = 3e5 + 10;
const ll kMod = 1e9 + 7;

ll k, r, f[kMaxN], inv[kMaxN], ans;

ll Qpow(ll a, ll b) {
  ll ans = 1;
  for (; b; b >>= 1) {
    if (b & 1) {
      ans = (__int128)ans * a % kMod;
    }
    a = (__int128)a * a % kMod;
  }
  return ans;
}

void Init() {
  f[0] = 1;
  for (ll i = 1; i < kMaxN; ++ i) {
    f[i] = (__int128)f[i - 1] * i % kMod;
  }
  inv[kMaxN - 1] = Qpow(f[kMaxN - 1], kMod - 2);
  for (int i = kMaxN - 2; i >= 0; -- i) {
    inv[i] = (__int128)inv[i + 1] * (i + 1) % kMod;
  } 
}

ll C(ll n, ll m) {
  if (n < m) {
    return 0;
  }
  __int128 res = 1;
  for (ll i = 0; i < m; ++ i) {
    res = res * (n - i) % kMod;
  }
  res = res * inv[m] % kMod;
  return (ll)res;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> k >> r, Init();
  if (!r) {
    return cout << "1\n", 0;
  }
  for (int i = 1; i <= k; ++ i) {
    cin >> f[i];
  }
  for (ll msk = 0, sum, c; msk < (1ll << k); ++ msk) {
    sum = 0;
    for (ll i = 1; i <= k; ++ i) {
      if (msk & (1ll << (i - 1))) {
        sum += f[i] + 1;
      }
    }
    c = C(r - sum + k - 1, k - 1);
    if (__builtin_popcount(msk) & 1) {
      ans = (ans - c + kMod) % kMod;
    } else {
      ans = (ans + c) % kMod;
    }
  }
  cout << ans << '\n';
  return 0; 
}

::::

P14639 【OIMO Round 1】世界线

此题涉及到简单容斥，但作者相信是个人应该就会吧 /jk。

设首位为 x，大于 x 有 p 个数，小于 x 有 q 个数，其余等值元素共 r 个，满足 p + q + r + 1 = n。大数只能放入不减序列，小数放入不增序列，等值元素必须整体归入一侧，保证单调性合法。

不计等值元素时，基础方案为 C_{p + q}^{p}。将 r 个等值元素分别并入两类序列，对应方案为 C_{n-1}^{p + r} 与 C_{n - 1}^{q + r}。两种情况存在重复统计，扣除重叠部分 C_{p + q}^{p} 即可。

最终单种首位贡献：

预处理组合数与数值计数，遍历所有取值累加答案即可。