问题背景
错排问题（Derangement）是组合数学中的经典难题：将 $n$ 个不同的元素重新排列，使得没有任何一个元素出现在其原始位置上，这样的排列称为错排。问：$n$ 个元素的错排总数是多少？
例如，对于 ${1, 2, 3\
}$，其所有排列为：
– $(1, 2, 3)$ — 1在位置1，不是错排
– $(1, 3, 2)$ — 1在位置1，不是错排
– $(2, 1, 3)$ — 3在位置3，不是错排
– $(2, 3, 1)$ — 没有错位 ✓
– $(3, 1, 2)$ — 没有错位 ✓
– $(3, 2, 1)$ — 2在位置2，不是错排
因此 $n=3$ 时的错排数为 $2$。
错排问题在密码学、统计学、通信协议等领域都有实际应用。本文将用三种方法求解错排数，并给出Java实现。
核心算法思路
方法一：容斥原理
设 $A_i$ 表示”第 $i$ 个元素在其原始位置上”的事件。我们要求的是所有 $A_i$ 都不发生的排列数。
根据容斥原理：
$$D_n = n! – \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! – \cdots + (-1)^n\binom{n}{n}0!$$
$$D_n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}$$
方法二：递推公式
考虑第 $n$ 个元素的位置：
– 假设第 $n$ 个元素与第 $k$ 个元素交换位置（$k$ 有 $n-1$ 种选择）
– 如果第 $k$ 个元素去了位置 $n$，则剩余 $n-2$ 个元素需要错排：$D_{n-2}$
– 如果第 $k$ 个元素不去位置 $n$，则剩余 $n-1$ 个元素需要错排（把位置 $n$ 视为第 $k$ 个元素的”原始位置”）：$D_{n-1}$
由此得到递推公式：
$$D_n = (n-1) \times (D_{n-1} + D_{n-2})$$
边界条件：$D_0 = 1, D_1 = 0$
方法三：动态规划
由递推公式可以直接写出动态规划实现，时间复杂度 $O(n)$，空间复杂度可以优化到 $O(1)$。
Java 完整实现
import java.math.BigInteger;
import java.util.*;
/**
* 错排问题求解器
* 提供三种解法：容斥原理、递推公式、动态规划
* 支持大整数运算（n较大时）
*/
public class DerangementSolver {
// ========== 方法一：容斥原理 ==========
/**
* 使用容斥原理计算错排数
* D_n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)
* @param n 元素个数
* @return 错排数
*/
public static BigInteger derangementInclusionExclusion(int n) {
if (n < 0) return BigInteger.ZERO;
if (n == 0) return BigInteger.ONE;
// 计算 n!
BigInteger factorial = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
factorial = factorial.multiply(BigInteger.valueOf(i));
}
// 容斥求和
BigInteger sum = BigInteger.ZERO;
BigInteger factK = BigInteger.ONE; // k!
for (int k = 0; k <= n; k++) {
if (k > 0) {
factK = factK.multiply(BigInteger.valueOf(k));
}
// 符号 (-1)^k
BigInteger sign = (k % 2 == 0) ? BigInteger.ONE : BigInteger.ONE.negate();
// n! / k! = n! * (k!)^(-1)，但这里用整数除法
BigInteger term = factorial.divide(factK);
sum = sum.add(sign.multiply(term));
}
return sum;
}
// ========== 方法二&三：递推/动态规划 ==========
/**
* 使用递推公式计算错排数（大整数版本）
* D_n = (n-1) * (D_{n-1} + D_{n-2})
* @param n 元素个数
* @return 错排数
*/
public static BigInteger derangementRecurrenceBig(int n) {
if (n < 0) return BigInteger.ZERO;
if (n == 0) return BigInteger.ONE;
if (n == 1) return BigInteger.ZERO;
BigInteger dp0 = BigInteger.ONE; // D_0
BigInteger dp1 = BigInteger.ZERO; // D_1
BigInteger dpi = BigInteger.ZERO;
for (int i = 2; i <= n; i++) {
// D_i = (i-1) * (D_{i-1} + D_{i-2})
dpi = dp1.add(dp0).multiply(BigInteger.valueOf(i - 1));
dp0 = dp1;
dp1 = dpi;
}
return dp1;
}
/**
* 使用递推公式计算错排数（long版本，n <= 20时安全）
* @param n 元素个数
* @return 错排数
*/
public static long derangementRecurrenceLong(int n) {
if (n < 0) return 0;
if (n == 0) return 1;
if (n == 1) return 0;
long dp0 = 1; // D_0
long dp1 = 0; // D_1
long dpi = 0;
for (int i = 2; i <= n; i++) {
dpi = (i - 1) * (dp1 + dp0);
dp0 = dp1;
dp1 = dpi;
}
return dp1;
}
// ========== 生成具体错排排列 ==========
/**
* 生成 n 个元素的所有错排排列
* 使用回溯法，适合 n <= 8 的情况
* @param n 元素个数
* @return 所有错排列表
*/
public static List<int[]> generateAllDerangements(int n) {
List<int[]> result = new ArrayList<>();
int[] perm = new int[n];
boolean[] used = new boolean[n + 1];
backtrack(0, n, perm, used, result);
return result;
}
private static void backtrack(int pos, int n, int[] perm, boolean[] used, List<int[]> result) {
if (pos == n) {
result.add(perm.clone());
return;
}
for (int num = 1; num <= n; num++) {
if (used[num]) continue;
// 错排条件：第pos个位置不能放数字pos+1（因为数字从1开始）
if (num == pos + 1) continue;
used[num] = true;
perm[pos] = num;
backtrack(pos + 1, n, perm, used, result);
used[num] = false;
}
}
// ========== 近似公式与概率分析 ==========
/**
* 使用近似公式计算错排数
* 当 n 较大时，D_n ≈ n! / e
* @param n 元素个数
* @return 近似错排数（double类型）
*/
public static double derangementApproximation(int n) {
double factorial = 1.0;
for (int i = 2; i <= n; i++) {
factorial *= i;
}
return factorial / Math.E;
}
/**
* 计算随机排列是错排的概率
* 当 n -> ∞ 时，概率趋近于 1/e ≈ 36.8%
* @param n 元素个数
* @return 错排概率
*/
public static double derangementProbability(int n) {
BigInteger d = derangementRecurrenceBig(n);
BigInteger fact = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
fact = fact.multiply(BigInteger.valueOf(i));
}
return d.doubleValue() / fact.doubleValue();
}
// ========== 辅助方法 ==========
/**
* 打印排列
*/
public static void printPermutation(int[] perm) {
System.out.print("(");
for (int i = 0; i < perm.length; i++) {
System.out.print(perm[i]);
if (i < perm.length - 1) System.out.print(", ");
}
System.out.println(")");
}
/**
* 验证是否为错排
*/
public static boolean isDerangement(int[] perm) {
for (int i = 0; i < perm.length; i++) {
if (perm[i] == i + 1) return false;
}
return true;
}
// ==================== 主程序 ====================
public static void main(String[] args) {
System.out.println("=== 错排问题求解演示 ===\n");
// 1. 计算小规模错排数
System.out.println("方法一：容斥原理");
System.out.println("方法二：递推公式");
System.out.println("n\t容斥原理\t递推公式\t近似值(n!/e)");
System.out.println("-".repeat(60));
for (int n = 0; n <= 10; n++) {
BigInteger d1 = derangementInclusionExclusion(n);
BigInteger d2 = derangementRecurrenceBig(n);
double approx = derangementApproximation(n);
System.out.printf("%d\t%s\t%s\t%.2f%n", n, d1.toString(), d2.toString(), approx);
}
// 2. 展示递推过程
System.out.println("\n=== 递推关系演示 ===");
System.out.println("递推公式: D_n = (n-1) * (D_{n-1} + D_{n-2})");
System.out.println("边界条件: D_0 = 1, D_1 = 0");
long dp0 = 1, dp1 = 0;
System.out.println("D_0 = " + dp0);
System.out.println("D_1 = " + dp1);
for (int i = 2; i <= 8; i++) {
long dpi = (i - 1) * (dp1 + dp0);
System.out.printf("D_%d = %d * (%d + %d) = %d%n", i, i - 1, dp1, dp0, dpi);
dp0 = dp1;
dp1 = dpi;
}
// 3. 生成所有错排（n=4）
System.out.println("\n=== n=4 时的所有错排 ===");
List<int[]> allDer = generateAllDerangements(4);
System.out.println("错排总数: " + allDer.size());
for (int[] perm : allDer) {
printPermutation(perm);
}
// 4. 概率分析
System.out.println("\n=== 错排概率分析 ===");
System.out.println("当 n 增大时，随机排列是错排的概率趋近于 1/e ≈ " + String.format("%.6f", 1.0 / Math.E));
for (int n : new int[]{1, 2, 3, 5, 10, 20, 50}) {
double prob = derangementProbability(n);
System.out.printf("n=%d\t概率=%.6f%n", n, prob);
}
// 5. 大整数演示
System.out.println("\n=== 大数错排数 ===");
for (int n : new int[]{20, 50, 100}) {
BigInteger d = derangementRecurrenceBig(n);
System.out.println("D_" + n + " 的位数: " + d.toString().length());
System.out.println("D_" + n + " 的前50位: " + d.toString().substring(0, Math.min(50, d.toString().length())));
}
}
}
算法复杂度分析
容斥原理：
– 时间复杂度：$O(n)$，需要计算 $n!$ 和容斥求和
– 空间复杂度：$O(1)$（不考虑大整数的存储开销）
递推公式 / 动态规划：
– 时间复杂度：$O(n)$
– 空间复杂度：$O(1)$（使用滚动数组优化）
回溯生成所有错排：
– 时间复杂度：$O(n!)$，需要枚举所有排列并筛选
– 空间复杂度：$O(n)$，递归栈深度
关键结论与扩展
- 递推关系：$D_n = (n-1)(D_{n-1} + D_{n-2})$ 是最实用的计算方法，$O(n)$ 时间即可求出任意 $D_n$。
- 近似公式：当 $n \geq 10$ 时，$D_n \approx n!/e$ 的误差小于 $0.01\%$，且 $D_n = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$ 给出了精确的整数公式。
- 概率意义：随机一个排列是错排的概率约为 $36.8\%$，且与 $n$ 几乎无关（只要 $n \geq 5$）。
- 扩展问题：
- 部分错排：恰好有 $k$ 个元素在正确位置上的排列数 = $\binom{n}{k} D_{n-k}$
- ménage 问题：圆桌夫妇问题，是错排问题的扩展
- 子阶乘：错排数记为 !n 或 $D_n$，称为子阶乘
总结
错排问题展示了组合数学中多种方法的统一：容斥原理提供封闭形式，递推公式提供高效计算，动态规划提供工程实现。而错排数与 $e$ 的深刻联系（$D_n \approx n!/e$）则是离散数学与连续分析之间优美桥接的典范。理解错排问题，不仅能掌握组合计数的核心技巧，更能体会到数学各领域之间的内在和谐。
