组合计数：多重集排列、错排与圆排列

多重集（multiset）：允许元素重复出现的集合。记作 {a₁·x₁, a₂·x₂, …, aₖ·xₖ}，表示元素 xᵢ 出现了 aᵢ 次，元素总数为 n = a₁ + a₂ + ⋯ + aₖ。例如 {2·A, 3·B} 表示 2 个 A 和 3 个 B。

等价关系（equivalence relation）：集合 S 上的二元关系 ~ 若同时满足 ① 自反性：a ~ a；② 对称性：a ~ b ⟹ b ~ a；③ 传递性：a ~ b 且 b ~ c ⟹ a ~ c，则称为等价关系。

等价类与划分：对 S 中的元素 a，所有与 a 等价的元素构成 等价类 [a]。等价关系把 S 切成若干个互不相交的等价类，其并集正是 S —— 这叫 S 的一个划分。反过来，任意一个划分也唯一确定一个等价关系（"同属一块"）。

多重集的排列（可重排列）：把 n 个元素（其中有重复）排成一列，不同的排列数为 n! / (a₁!·a₂!·⋯·aₖ!)。

多重集的组合（可重组合）：从 k 类元素中一共取出 n 个（每类可重复取任意多个），方案数为 C(n + k − 1, k − 1) = C(n + k − 1, n)。

圆排列：n 个不同元素围成一个圆（只考虑相对顺序，旋转视为同一种），方案数为 (n − 1)!。项链排列（还允许翻转）方案数为 (n − 1)! / 2（n ≥ 3）。

错排列（derangement / 更列）：n 个元素的全排列中，满足"每个元素都不在自己原位置"的排列数，记作 Dₙ。前几项为 D₁ = 0，D₂ = 1，D₃ = 2，D₄ = 9，D₅ = 44，D₆ = 265，D₇ = 1854。

两组核心公式：

Dₙ = (n − 1)(Dₙ₋₁ + Dₙ₋₂)    Dₙ = n! · Σ_{i=0}^{n} (−1)ⁱ / i!

"两个 A 交换一下不还是同一种编号吗？"这句话听上去理所当然，但要在数学上严谨，需要引入等价关系这个概念。

等价关系的三条性质（初赛常考，务必背熟）：

等价类的两大性质：① 任意两个等价类要么完全相同，要么完全不相交；② 所有等价类的并集恰好是整个集合 S。这就是"划分"的含义。

再看两个等价关系的例子，帮助建立直觉：

关键洞察：所有"除以某个数"的计数公式，本质上都是"总数 ÷ 每个等价类的大小"。当每个等价类大小相同时（这叫"群作用"），除法一句话就能搞定；而当等价类大小不同时（比如错排里的各种情况），就必须用容斥或递推 —— 这就是本讲的第二条主线。

定理：设多重集含 k 类元素，第 i 类有 aᵢ 个，总数 n = Σaᵢ。则把它排成一列的不同排列数为

n! / (a₁! · a₂! · ⋯ · aₖ!)

推导（两种常见思路，都要会）：

这 6 个排列可以完整列出来，方便核对：

经典例子 MISSISSIPPI：这个单词里有 M × 1、I × 4、S × 4、P × 2，共 11 个字母。不同排列数 =

11! / (1! · 4! · 4! · 2!) = 39916800 / (1 × 24 × 24 × 2) = 39916800 / 1152 = 34650

所以 MISSISSIPPI 可以排出 34650 个不同的排列（含它自己）。

多项式系数：正因为这个公式形如多项式的展开系数，它也常被记作 n! / (a₁!⋯aₖ!) = C(n; a₁, a₂, …, aₖ)，称为多项式系数。当 k = 2 时，它就退化成了二项式系数 C(n, a₁) —— 这一点在下一讲会再次用到。

解题步骤（代码实现）：因为结果往往要对质数取模，所以要用"阶乘 + 逆元"：

const int MAXN = 1000010;
const ll MOD = 1000000007;
ll fac[MAXN], ifac[MAXN];

ll qpow(ll b, ll e) {
    ll r = 1 % MOD; b %= MOD;
    while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
    return r;
}
void init() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % MOD;
}
// 求 n! / (a[0]! * a[1]! * ... ) mod MOD
ll multisetPerm(ll n, const vector<ll> &a) {
    ll res = fac[n];
    for (ll ai : a) res = res * ifac[ai] % MOD;
    return res;
}

问题：从 k 类元素中一共取出 n 个（每类可以取任意多个，允许取 0 个），有多少种不同的取法？"不同"指的是各类取出的数量组合不同，与顺序无关。

举个具体的例子：把 10 个相同的苹果分给 3 个人，每人可以一个都不分到，有多少种分法？

隔板法的想法：把问题画成"10 个苹果排成一行，用 2 根竹签把它们分成 3 段"。第一段给第 1 个人，第二段给第 2 个人，第三段给第 3 个人。于是：

转化过程：原来有 10 个苹果，现在加入 2 个"竹签位"，一共 12 个位置。这 12 个位置里任选 2 个放竹签（其余 10 个位置放苹果），每一种选法恰好对应一种分法。所以方案数是 C(12, 2) = 66。

三个常见变形（考试里经常出现）：

例：把 10 个相同苹果分给 3 人，每人至少 1 个。先各给 1 个，剩 7 个用隔板法：C(7 + 3 − 1, 3 − 1) = C(9, 2) = 36。也可以直接用"至少取 1 个"的公式 C(n − 1, k − 1) = C(9, 2) = 36 ✓

另一类重要问题：不相邻的组合。从 1, 2, 3, …, n 中选出 k 个数，要求任意两个都不相邻，方案数是 C(n − k + 1, k)。

推导思路：设选出的数是 x₁ < x₂ < ⋯ < xₖ。由于两两不相邻，有 xᵢ ≥ x_{i−1} + 2。做变换 yᵢ = xᵢ − (i − 1)，则 y 严格递增（yᵢ ≥ y_{i−1} + 1），且 1 ≤ y₁ < y₂ < ⋯ < yₖ ≤ n − k + 1。所以方案数是"从 n − k + 1 个数里选 k 个"——即 C(n − k + 1, k)。

例：从 1 到 10 中选 3 个两两不相邻的数，方案数 = C(10 − 3 + 1, 3) = C(8, 3) = 56。验证思路：把 1..10 划分成"选中位置的左邻空位"，可以枚举验证确实等于 56。

圆排列：n 个不同的元素围成一个圆圈，只考虑"相对顺序"，整体旋转视为同一种排列，方案数为 n! / n = (n − 1)!。

为什么除以 n：把圆剪开成一条线，有 n 个可能的"剪口"（从每个人前面剪开），得到的 n 个线性排列恰好都是同一个圆排列的不同展开。所以 n 个线性排列对应 1 个圆排列，圆排列数 = n! / n。

项链排列：如果不仅允许旋转，还允许整体翻转（比如项链翻个面还是同一条项链，手链、钥匙链同理），那么等价类还要再合并一倍。当 n ≥ 3 时，翻转不会与任何旋转重合，所以等价类大小变成 2n，方案数为：

n! / (2n) = (n − 1)! / 2

例：6 颗不同颜色的珠子串成一条项链，方案数 = 5! / 2 = 120 / 2 = 60。

常见变体：

一个容易混的点：圆桌题里如果座位是固定编号的（比如"1 号位到 8 号位"），那么坐法就是普通的 8!，不需要除 8 —— 因为坐在 1 号位和坐在 2 号位是不同的坐法。只有"座位没有编号、只有相对顺序"时才是圆排列。

定义：n 个元素的全排列中，如果存在一个排列使得每个元素都不在自己的原位置，就称它是这 n 个元素的一个错排列。错排列的个数记作 Dₙ（也叫"更列数"或 derangement）。

约定 D₀ = 1（空排列唯一）、D₁ = 0（1 个元素只能放回原位）。前几项为：

以 n = 3 为例验证：全部 6 个排列中，123 有三个不动点、132 有一个（1）、213 有一个（3）、231 有零个、312 有零个、321 有一个（2）。所以 D₃ = 2 ✓

递推式与推导：考虑元素 1 最终去了位置 k（k ≠ 1，共 n − 1 种选择）。接着分两类：

容斥公式（通项）：换一个角度，用容斥原理也能直接算出 Dₙ。

推广：恰好 k 个元素在原位的排列数——先选出哪 k 个元素不动（C(n, k) 种），剩下的 n − k 个元素必须全部错排（Dₙ₋ₖ 种）：

方案数 = C(n, k) · Dₙ₋ₖ

例：n = 4 的排列中恰好有 1 个元素在原位的方案数 = C(4,1) × D₃ = 4 × 2 = 8。暴力枚举验证：24 个排列里，恰好 0 个原位的有 9 个、恰好 1 个的有 8 个、恰好 2 个的有 6 个、恰好 4 个的有 1 个，合计 9 + 8 + 6 + 0 + 1 = 24 ✓（恰好 3 个不可能：3 个不动就意味着第 4 个也必然不动）。

题意：给定元素总数 n 与 k 类元素各有多少个（a₁, a₂, …, aₖ，满足 Σaᵢ = n），求这些元素的不同排列数，结果对质数 10⁹+7 取模。

分析：直接套公式 n! / (a₁!a₂!⋯aₖ!)。由于要取模，除法要换成乘逆元，所以需要预处理阶乘与阶乘逆元。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1000010;
const ll MOD = 1000000007;
ll fac[MAXN], ifac[MAXN];

ll qpow(ll b, ll e) {
    ll r = 1 % MOD; b %= MOD;
    while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
    return r;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);      // 费马小定理求一次逆元
    for (int i = MAXN - 2; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % MOD;
}

int main() {
    init();
    int n, k; cin >> n >> k;
    vector<ll> a(k);
    for (int i = 0; i < k; i++) cin >> a[i];

    ll ans = fac[n];
    for (int i = 0; i < k; i++) ans = ans * ifac[a[i]] % MOD;
    cout << ans << endl;
    return 0;
}

输入: 4 2
      2 2          （2 个 a、2 个 b）
输出: 6
验算: 4! / (2! * 2!) = 24 / 4 = 6  ✓
      6 个排列：aabb、abab、abba、baab、baba、bbaa

输入: 11 4
      1 4 4 2      （M × 1、I × 4、S × 4、P × 2）
输出: 34650
验算: 11! / (1! * 4! * 4! * 2!) = 39916800 / 1152 = 34650  ✓

输入: 6 3
      2 2 2        （aabbcc）
输出: 90
验算: 6! / (2! * 2! * 2!) = 720 / 8 = 90  ✓

三个易错点：① 分母写成"所有重复次数的乘积的阶乘"（比如 6!/(2+2+2)!），正确写法是"每个重复次数各自取阶乘再相乘"；② 忘记预处理逆元，直接用除法（取模运算里不能直接除）；③ 阶乘表开到 MAXN 但 n 可能超过，导致越界。

时间复杂度：预处理 O(MAXN)，每次查询 O(k)。因为 ifac 只求了一次逆元再用前缀积递推，所以常数很小 —— 这是所有"组合数取模"题目的标准写法。

题意：求 1 到 n 的排列中，恰好有 m 个位置 i 满足 pᵢ = i 的排列个数，答案对 10⁹+7 取模。多组询问。

分析：这是"恰好 k 个不动点"模型的标准应用。分两步：

① 选出哪 m 个元素在原位：从 n 个位置中选 m 个，方案数 C(n, m)。

② 让剩下的 n − m 个元素全部错排：方案数 Dₙ₋ₘ。

两步相乘即为答案：C(n, m) · D_{n−m}。注意特判 m > n 时答案为 0，n − m = 1 时 D₁ = 0。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1000010;
const ll MOD = 1000000007;
ll fac[MAXN], ifac[MAXN], D[MAXN];

ll qpow(ll b, ll e) {
    ll r = 1 % MOD; b %= MOD;
    while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
    return r;
}

ll C(ll n, ll m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    // 预处理阶乘与逆元
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % MOD;

    // 预处理错排表
    D[0] = 1; D[1] = 0;
    for (int i = 2; i < MAXN; i++)
        D[i] = (i - 1) * ((D[i - 1] + D[i - 2]) % MOD) % MOD;

    int T; cin >> T;
    while (T--) {
        ll n, m; cin >> n >> m;
        if (m > n) { cout << 0 << endl; continue; }
        cout << C(n, m) * D[n - m] % MOD << endl;
    }
    return 0;
}

输入:
4
4 1
4 0
5 0
6 2

输出:
8
9
44
135

逐项验算：
n=4, m=1: C(4,1) * D3 = 4 * 2   = 8     ✓（暴力枚举 24 个排列，恰好 1 个不动点的有 8 个）
n=4, m=0: C(4,0) * D4 = 1 * 9   = 9     ✓（D4 = 9）
n=5, m=0: C(5,0) * D5 = 1 * 44  = 44    ✓（D5 = 44）
n=6, m=2: C(6,2) * D4 = 15 * 9  = 135   ✓（C(6,2) = 6!/(2!*4!) = 15）

组合数一定要算准：上面最后一组里 C(6,2) = 15（不是 5），这个 3 倍的差别直接决定答案对错。常见组合数速记：C(5,2)=10，C(6,2)=15，C(6,3)=20，C(7,2)=21，C(7,3)=35，C(8,3)=56，C(8,4)=70，C(10,2)=45，C(10,3)=120。

三个易错点：① C(n, m) 的下标写错（比如写成 C(m, n)）；② 错排表的下标写成 D[m]（应该是 D[n−m]）；③ 忘记特判 m > n，导致下标越界。

复杂度：预处理 O(MAXN)（同时打阶乘表与错排表），每组询问 O(1)。这是多组询问类计数题的标准做法。

题意：给定 n（n ≥ 3）与类型 t。t = 1 表示"围成一圈"（旋转等价），输出 (n−1)!；t = 2 表示"串成项链"（旋转 + 翻转等价），输出 (n−1)! / 2。结果对质数 10⁹+7 取模。

分析：圆排列直接算 (n−1)!；项链再乘一个 inv(2) = (p+1)/2（因为 2 在模奇素数下可逆）。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;

ll qpow(ll b, ll e) {
    ll r = 1 % MOD; b %= MOD;
    while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
    return r;
}

int main() {
    ll n; int t; cin >> n >> t;

    // 先算 (n-1)!  mod MOD
    ll ans = 1 % MOD;
    for (ll i = 1; i <= n - 1; i++) ans = ans * (i % MOD) % MOD;

    if (t == 2) ans = ans * qpow(2, MOD - 2) % MOD;   // 项链：再除以 2
    cout << ans << endl;
    return 0;
}

输入: 8 1     （8 人围成一圈）
输出: 5040
验算: (8-1)! = 7! = 5040  ✓

输入: 6 2     （6 颗不同珠子串成项链，可翻转）
输出: 60
验算: (6-1)! / 2 = 120 / 2 = 60  ✓

输入: 5 1     （5 人围圆桌）
输出: 24
验算: 4! = 24  ✓

输入: 4 2     （4 颗珠子串成手链）
输出: 3
验算: (4-1)! / 2 = 6 / 2 = 3  ✓
（4 颗珠子 a,b,c,d 的手链：abcd、abdc、acbd 三种，其余都是这三种的旋转或翻转）

"固定一个人"的等价写法：圆排列题更常见的做法是先让 1 号固定在最上方，剩下 n − 1 个人线性排列，直接得 (n−1)!。这样写代码更直观，也避免了"除以 n"时对取模的担心（虽然除以 n 也可以用逆元处理）。

四个易错点：

① 混淆"圆桌有没有编号"：如果座位是固定编号的（"1 号位到 8 号位"），答案就是 8!，不需要除以 8；

② 项链忘记除以 2，或者反过来把"圆桌"也除以 2（如果题目说"合照时左右可以互换"，那才需要）；

③ 除以 2 时不能用整数除法（在取模的意义下要先转成乘逆元）；

④ n = 2 的项链边界：2 颗珠子时 (2−1)!/2 = 1/2 不是整数，公式失效（此时旋转与翻转重合）。题目一般会给 n ≥ 3 的限制，如果没有，需要特判。

输入 n 与 k，回答三类问题：① 把 n 个相同的球放进 k 个不同的盒子（盒可空）；② 每个盒子至少 1 个；③ 每个盒子至多 r 个。分别输出方案数对 10⁹+7 取模。

数据范围：1 ≤ n, k ≤ 10⁶，1 ≤ r ≤ 10⁶。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 4000010;               // n+k 可能到 2*10^6，留足余量
const ll MOD = 1000000007;
ll fac[MAXN], ifac[MAXN];

ll qpow(ll b, ll e) {
    ll r = 1 % MOD; b %= MOD;
    while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
    return r;
}
ll C(ll n, ll m) {
    if (m < 0 || m > n || n < 0) return 0;
    return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}
int main() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % MOD;

    ll n, k, r; cin >> n >> k >> r;

    // ① 盒可空
    ll a1 = C(n + k - 1, k - 1);
    // ② 每盒至少 1 个
    ll a2 = (n >= k) ? C(n - 1, k - 1) : 0;
    // ③ 每盒至多 r 个（容斥）
    ll a3 = 0;
    for (ll j = 0; j * (r + 1) <= n; j++) {
        ll term = C(k, j) * C(n - j * (r + 1) + k - 1, k - 1) % MOD;
        if (j & 1) a3 = (a3 - term + MOD) % MOD;
        else a3 = (a3 + term) % MOD;
    }
    cout << a1 << " " << a2 << " " << a3 << endl;
    return 0;
}

输入 T 组 (n, m)，每组输出 1..n 的排列中"至少有 m 个元素在原位"的排列个数，对 10⁹+7 取模。

数据范围：T ≤ 10⁵，1 ≤ n ≤ 10⁶。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000010;
const ll MOD = 1000000007;
ll fac[MAXN], ifac[MAXN], D[MAXN];

ll qpow(ll b, ll e) {
    ll r = 1 % MOD; b %= MOD;
    while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
    return r;
}
ll C(ll n, ll m) {
    if (m < 0 || m > n) return 0;
    return fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    ifac[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) ifac[i] = ifac[i + 1] * (i + 1) % MOD;
    D[0] = 1; D[1] = 0;
    for (int i = 2; i < MAXN; i++) D[i] = (i - 1) * ((D[i - 1] + D[i - 2]) % MOD) % MOD;

    int T; cin >> T;
    while (T--) {
        ll n, m; cin >> n >> m;
        if (m > n) { cout << 0 << endl; continue; }
        ll ans;
        if (m <= n - m + 1) {
            // 补集形式：n! − Σ_{k=0}^{m−1} C(n,k)·D_{n−k}，共 m 项
            ans = fac[n];
            for (ll k = 0; k < m; k++) ans = (ans - C(n, k) * D[n - k] % MOD + MOD) % MOD;
        } else {
            // 直接形式：Σ_{k=m}^{n} C(n,k)·D_{n−k}，共 n−m+1 项
            ans = 0;
            for (ll k = m; k <= n; k++) ans = (ans + C(n, k) * D[n - k]) % MOD;
        }
        cout << ans << endl;
    }
    return 0;
}

输入 n 个人与若干"等价声明"（每次声明两个人必须相邻），按"圆桌就座、旋转视为同一种"计数。若声明互相冲突则输出 −1。请设计算法并说明如何处理"相邻限制 + 循环等价"这两件事。

数据范围：2 ≤ n ≤ 10⁵，声明数 ≤ n。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int MAXN = 100010;

int fa[MAXN], sz[MAXN], deg[MAXN];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

ll qpow(ll b, ll e) {
    ll r = 1 % MOD; b %= MOD;
    while (e) { if (e & 1) r = r * b % MOD; b = b * b % MOD; e >>= 1; }
    return r;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) fa[i] = i, sz[i] = 1;

    for (int t = 0; t < q; t++) {
        int u, v; cin >> u >> v;
        deg[u]++; deg[v]++;
        if (deg[u] > 2 || deg[v] > 2) { cout << "-1" << endl; return 0; }  // 出现分叉
        int ru = find(u), rv = find(v);
        if (ru == rv) { cout << "-1" << endl; return 0; }        // 出现环
        fa[ru] = rv; sz[rv] += sz[ru];
    }

    // 统计块数，并累乘每块的翻转系数
    ll m = 0, coef = 1;
    for (int i = 1; i <= n; i++) {
        if (find(i) != i) continue;
        m++;
        if (sz[i] >= 2) coef = coef * 2 % MOD;
    }

    if (m == 1) { cout << 1 << endl; return 0; }   // 全体成一条链，围成圈只有 1 种

    // (m-1)! 部分
    ll ans = coef;
    for (ll i = 1; i <= m - 1; i++) ans = ans * (i % MOD) % MOD;
    cout << ans << endl;
    return 0;
}

拓展 1：多重集排列加上"不相邻"限制 —— 插空法

公式 n!/(a₁!⋯aₖ!) 只管"有多少个不同的排列"，但如果加上"某一类元素不能相邻"的限制，就要换招。

例：用 3 个 A 和 3 个 B 组成串，要求没有两个 A 相邻，有多少种？

插空法（先排其他，再插入空隙）：先把 3 个 B 排好，有 3!/3! = 1 种（B 彼此相同）。3 个 B 之间有 4 个空隙（含两端）：

_ B _ B _ B _

把 3 个 A 放进这 4 个空隙中，每个空隙最多放 1 个（否则 A 相邻），方案数 = C(4, 3) = 4。

验证：4 个串分别是 ABABAB、ABABBA、ABBABA、BABABA —— 恰好 4 个，且每个里都没有相邻的 A ✓

拓展 2：项链计数的一般框架 —— 从"除以 2n"到 Burnside 引理

我们把 n 颗不同珠子的项链数写成 n!/(2n)，本质上是"总数 ÷ 每个等价类的大小"，而这个除法的合法性依赖于"每个等价类大小相同"。

这个条件什么时候会失效？当珠子可以着色、颜色数量有限时，"每个等价类大小相同"就不一定成立了 —— 有些着色方案具有旋转或翻转对称性。

例：2 颗珠子各涂红或蓝，能做出多少种不同的手链？用 n!/(2n) 会得到 2²/4 = 1，显然错了（至少能做出"同色"和"异色"两种）。问题出在"双红"和"双蓝"这两种着色方案在旋转下不变，它们的等价类大小只有 1 而不是 4。

Burnside 引理给出了正确的做法：

轨道数 = (1/|G|) · Σ_{g ∈ G} |Fix(g)|

其中 G 是"允许的对称操作"构成的群（项链对应二面体群 D_n，共 2n 个元素），Fix(g) 是在操作 g 下保持不变的所有方案集合。

用 2 颗珠子验证：G 有 4 个元素（不动、旋转 180°、两种翻转），4 种着色方案中：不动固定 4 种，旋转 180° 固定 2 种（双红、双蓝），两种翻转也各固定 2 种。所以轨道数 = (4 + 2 + 2 + 2)/4 = 10/4 = 2.5。这里出现了 2.5 —— 因为 n = 2 时二面体群只有 2 个元素（旋转 180° 与翻转重合），修正后为 (4 + 2)/2 = 3，即"双红、双蓝、一红一蓝"三种 ✓

与我们的公式的关系：当所有珠子颜色各不相同（或者说珠子本身可分辨）时，没有非平凡的对称操作能固定任何方案，于是 Burnside 引理退化成 n!/(2n) —— 这就是本讲的项链公式。Burnside 是它的"完全体"，属于 NOI 及以上的内容，这里先建立直观印象即可。

拓展 3：从错排到一般的"禁位排列"

错排要求"每个元素都不在自己的位置上"。如果禁区不是整齐的"对角线"，而是一个任意的"禁位表"，该怎么算？

问题：n 个元素排到 n 个位置上，某些"元素—位置"组合被禁止（称为禁位），求合法排列数。

解法（容斥 + 棋盘多项式）：设 rᵢ 表示"从禁位表中选出 i 个互不同行也不同列的格子"的方案数（称为禁位棋盘的 i 阶棋盘多项式系数）。则：

合法排列数 = Σ_{i=0}^{n} (−1)ⁱ · rᵢ · (n − i)!

经典应用：夫妻问题（ménage problem）——n 对夫妻围圆桌就座，要求夫妻不相邻。先把女士们排成圆（2·(n−1)! 种，因为可以左右两种方向），再把男士插入空隙并避开"不能与妻子相邻"的禁位。这时的禁位棋盘是阶梯形的，rᵢ 需要用专门的递推计算 —— 这是错排问题最著名的推广之一。

思考1：为什么多重集排列可以"直接除以某个数"，而错排不能也用类似的方法（比如"除以某个数"）解决？两者的根本差别在哪里？

思考2：公式 n! / (a₁!a₂!⋯aₖ!) 的结果一定是整数吗？请给出两种不同的证明。

思考3：圆排列有"固定一个人"的技巧（固定 1 号在正上方，剩下 (n−1)! 种）。这个技巧能直接用在项链排列上吗？为什么项链还要额外除以 2？