这是一份关于**错位排列（Derangement）**的精编讲义。包含了直观定义、递推公式证明、通俗解释以及一个可以直接运行的 HTML 动画演示代码。

---

# 错位排列 (Derangement) 讲义

## 1. 什么是错位排列？

想象一个生活场景：
有 $n$ 位同学参加聚会，每人带了一份礼物。如果交换礼物后，**每位同学拿到的都不是自己带来的那一份**，这种情况就称为 $n$ 个元素的**错位排列**。

通常用 $D\_n$ 表示 $n$ 个元素的错位排列数。

*   $n=1$: 只有1人，他必须拿自己的礼物。$D\_1 = 0$。
*   $n=2$: 两人 A, B。只能 B 拿 A 的，A 拿 B 的。$D\_2 = 1$。
*   $n=3$: 三人 A, B, C。可能的排列有 (B, C, A) 和 (C, A, B)。$D\_3 = 2$。
*   $n=4$: 经过计算，$D\_4 = 9$。

---

## 2. 核心公式与证明

### A. 递推公式（最直观的理解）
$D\_n = (n-1)(D\_{n-1} + D\_{n-2})$

**证明（通俗分步）：**
假设有 $n$ 个人，编号为 $1, 2, \dots, n$。
1.  **第一步**：让第 $1$ 号人先选，他不能选自己的礼物，所以他有 $n-1$ 种选择。假设他选了 $k$ 号人的礼物。
2.  **第二步**：现在看 $k$ 号人，他有两种选择：
    *   **情况 1**：$k$ 号人正好选了 $1$ 号人的礼物。
        这时 $1$ 和 $k$ 互相交换了礼物。剩下的 $n-2$ 个人只需要进行错位排列即可。方案数为 $D\_{n-2}$。
    *   **情况 2**：$k$ 号人不选 $1$ 号人的礼物。
        这时我们可以把“第 $1$ 号人的礼物”暂时看作是“第 $k$ 号人的原物”。此时剩下 $n-1$ 个人（包括 $k$），每个人都有一个“禁选”目标。方案数为 $D\_{n-1}$。
3.  **结论**：根据加法和乘法原理，$D\_n = (n-1)(D\_{n-1} + D\_{n-2})$。

---

### B. 通项公式（容斥原理证明）
$D\_n = n! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$

**证明简述：**
1.  所有排列的总数是 $n!$。
2.  减去“至少有一个人拿对”的情况，加上“至少有两个人拿对”的情况（容斥原理）...
3.  $D\_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \dots$
4.  展开组合数 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ 后化简即可得到上述公式。

---

## 4. 重点总结与记忆技巧

1.  **口诀**：一零，二一，三二，四九，五四四。
    *   $D\_1 = 0$
    *   $D\_2 = 1$
    *   $D\_3 = 2$
    *   $D\_4 = 9$
    *   $D\_5 = 44$
2.  **快速判断**：
    如果题目问“$n$ 个人恰好有 $k$ 个人拿对”，其计算方法是：
    *   先选出拿对的 $k$ 个人：$\binom{n}{k}$
    *   剩下的 $n-k$ 个人全错位：$D\_{n-k}$
    *   总方案 = $\binom{n}{k} \times D\_{n-k}$

3.  **概率极限**：
    当 $n$ 趋于无穷大时，错位排列的概率 $P = \frac{D\_n}{n!}$ 趋近于 $\frac{1}{e} \approx 0.368$。这意味着在一场巨大的交换礼物活动中，大约有 $36.8\%$ 的概率所有人都会拿错。

这是一份关于错位排列（Derangement）的精编讲义。包含了直观定义、递推公式证明、通俗解释以及一个可以直接运行的 HTML 动画演示代码。

错位排列 (Derangement) 讲义

1. 什么是错位排列？

想象一个生活场景：有 $n$ 位同学参加聚会，每人带了一份礼物。如果交换礼物后，每位同学拿到的都不是自己带来的那一份，这种情况就称为 $n$ 个元素的错位排列。

通常用 $D_n$ 表示 $n$ 个元素的错位排列数。

$n=1$: 只有1人，他必须拿自己的礼物。$D_1 = 0$。
$n=2$: 两人 A, B。只能 B 拿 A 的，A 拿 B 的。$D_2 = 1$。
$n=3$: 三人 A, B, C。可能的排列有 (B, C, A) 和 (C, A, B)。$D_3 = 2$。
$n=4$: 经过计算，$D_4 = 9$。

2. 核心公式与证明

A. 递推公式（最直观的理解）

$D_n = (n-1)(D_{n-1} + D_{n-2})$

证明（通俗分步）： 假设有 $n$ 个人，编号为 $1, 2, \dots, n$。 1. 第一步：让第 $1$ 号人先选，他不能选自己的礼物，所以他有 $n-1$ 种选择。假设他选了 $k$ 号人的礼物。 2. 第二步：现在看 $k$ 号人，他有两种选择： * 情况 1：$k$ 号人正好选了 $1$ 号人的礼物。这时 $1$ 和 $k$ 互相交换了礼物。剩下的 $n-2$ 个人只需要进行错位排列即可。方案数为 $D_{n-2}$。 * 情况 2：$k$ 号人不选 $1$ 号人的礼物。这时我们可以把“第 $1$ 号人的礼物”暂时看作是“第 $k$ 号人的原物”。此时剩下 $n-1$ 个人（包括 $k$），每个人都有一个“禁选”目标。方案数为 $D_{n-1}$。 3. 结论：根据加法和乘法原理，$D_n = (n-1)(D_{n-1} + D_{n-2})$。

B. 通项公式（容斥原理证明）

$D_n = n! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \dots + \frac{(-1)^n}{n!} \right)$

证明简述： 1. 所有排列的总数是 $n!$。 2. 减去“至少有一个人拿对”的情况，加上“至少有两个人拿对”的情况（容斥原理）... 3. $D_n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \dots$ 4. 展开组合数 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ 后化简即可得到上述公式。

4. 重点总结与记忆技巧

口诀：一零，二一，三二，四九，五四四。
- $D_1 = 0$
- $D_2 = 1$
- $D_3 = 2$
- $D_4 = 9$
- $D_5 = 44$
快速判断：如果题目问“$n$ 个人恰好有 $k$ 个人拿对”，其计算方法是：
- 先选出拿对的 $k$ 个人：$\binom{n}{k}$
- 剩下的 $n-k$ 个人全错位：$D_{n-k}$
- 总方案 = $\binom{n}{k} \times D_{n-k}$
概率极限：当 $n$ 趋于无穷大时，错位排列的概率 $P = \frac{D_n}{n!}$ 趋近于 $\frac{1}{e} \approx 0.368$。这意味着在一场巨大的交换礼物活动中，大约有 $36.8\%$ 的概率所有人都会拿错。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com