错排

1 信封问题

题目:luogu P1595: 信封问题。

有 nn 封不同的信和 nn 个对应的信封,每个信封恰好放一封信。要求每封信都不进入自己的信封,求方案数。

把信 ii 放入的信封编号记作 pip_i,则 pp 是 1∼n1\sim n 的一个排列,并且:

pi≠i(1≤i≤n). p_i\ne i\qquad(1\le i\le n).

这种没有元素留在原位的排列称为错排,方案数记作 DnD_n。例如 n=3n=3 时只有两种:

(2,3,1),(3,1,2). (2,3,1),\qquad(3,1,2).

这里禁止的是每个元素回到自己的位置。它与“排列不能和原排列完全相同”不同,后者只排除一个方案,答案是 n!−1n!-1。

2 分类递推

先固定信 11 放入信封 jj,其中 j≠1j\ne1,有 n−1n-1 种选择。接下来按信 jj 的去向分类。

2.1 两封信互换

若 pj=1p_j=1,即 1,j1,j 互相进入对方的信封,可以把这两封信和对应信封一起删掉。其余 n−2n-2 封信仍需全部装错,有 Dn−2D_{n-2} 种方案。

反过来,给任意一个剩余元素的错排补上 1↔j1\leftrightarrow j,都会得到且只得到一种本类方案。

2.2 不构成互换

若 pj≠1p_j\ne1,由于每个信封都恰好被使用一次,必有另一封信 kk 进入信封 11。此时 k≠1,jk\ne1,j,局部关系为:

k→1→j. k\to1\to j.

删去信 11 和信封 11,把信 kk 改放进信封 jj,即把这段关系接成 k→jk\to j。因为 k≠jk\ne j,不会产生新的原位元素,其余位置不变,得到 n−1n-1 个元素的错排。

例如 1→2→3→4→11\to2\to3\to4\to1,删去 11 后变为 2→3→4→22\to3\to4\to2:

删去错排环中的元素 1,将它前后的箭头重新连接,得到少一个元素的错排

这一步是可逆的:给定剩余元素的错排,找到进入信封 jj 的信 kk,把 k→jk\to j 改成 k→1→jk\to1\to j,就能唯一恢复原方案。因此本类方案数恰好是 Dn−1D_{n-1}。

2.3 递推式

两类互不重叠,并覆盖信 jj 的所有可能去向。对每个固定的 jj,共有 Dn−2+Dn−1D_{n-2}+D_{n-1} 种方案;再乘以 jj 的选择数,得到:

Dn=(n−1)(Dn−1+Dn−2)(n≥2). \boxed{D_n=(n-1)(D_{n-1}+D_{n-2})}\qquad(n\ge2).

边界为 D0=1,D1=0D_0=1,D_1=0。空排列只有一种;一个元素无法离开自己的位置。取 D0=1D_0=1 也使 D2=(2−1)(D1+D0)=1D_2=(2-1)(D_1+D_0)=1 正确成立。

nn 00 11 22 33 44 55
DnD_n 11 00 11 22 99 4444

3 代码实现

P1595 中 1≤n≤201\le n\le20,结果可以用 long long 保存。代码也保留了 n=0n=0 的数学边界。

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

const int maxn = 20 + 5;
ll d[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    d[0] = 1;  // 空排列只有一种,为递推和组合计数提供边界
    d[1] = 0;
    for (int i = 2; i <= n; ++i) {
        d[i] = (i - 1) * (d[i - 1] + d[i - 2]);
    }
    cout << d[n] << '\n';
    return 0;
}

时间、空间均为 O(n)O(n)。若只需要一个答案,也可以用两个变量保存前两项,将辅助空间降至 O(1)O(1)。

错排数增长很快,D20=895014631192902121D_{20}=895014631192902121,而 D21D_{21} 已超过有符号 6464 位整数范围。更大范围应按题意取模或使用高精度;要求取模时,直接在递推中取模即可,不需要除法。

4 恰好若干个原位元素

若要求恰好有 mm 个位置满足 pi=ip_i=i,先从 nn 个位置中选出这 mm 个固定位置,再让剩余元素全部错排,答案为:

(nm)Dn−m(0≤m≤n). \binom nm D_{n-m}\qquad(0\le m\le n).

不能让剩余元素任意排列,否则它们还可能产生新的固定位置,使总数超过 mm。

例如 n=3n=3 时,恰好有 0,1,2,30,1,2,3 个固定位置的方案数分别为 2,3,0,12,3,0,1,相加为 3!=63!=6。特别地:

  • m=nm=n 时,所有元素固定,答案为 D0=1D_0=1。
  • m=n−1m=n-1 时,只剩一个元素,它也只能留在原位,因此没有方案。
  • m>nm>n 时,答案为 00。

练习:luogu P4071: [SDOI2016] 排列计数。题目需要多次查询并取模,应预处理错排数和组合数所需的数据。

5 容斥表达式

也可以从所有 n!n! 个排列中排除含固定位置的排列。设 AiA_i 表示 pi=ip_i=i,固定任意 kk 个位置后,其余元素有 (n−k)!(n-k)! 种排列;选择这 kk 个位置有 (nk)\binom nk 种方法。

由 容斥原理 得到:

Dn=∑k=0n(−1)k(nk)(n−k)!. D_n=\sum_{k=0}^{n}(-1)^k\binom nk(n-k)!.

这里的交集只要求选中的位置固定,允许其他位置也固定;重复覆盖由容斥的正负号修正。这个式子适合解释“排除所有固定位置”,实际逐项计算时仍须注意阶乘的范围,不能用浮点近似代替精确计数。

6 相关题解

暂无相关题解