理解错位排列的递推公式 D(n)=(n−1)×(D(n−1)+D(n−2))

一、错位排列的定义

错位排列（记为$D(n)$）是指：将$n$个元素重新排列，使得每个元素都不在其原始位置（例如，礼物不能装回原盒子）。

二、递推公式的推导过程

假设我们有n个元素（编号$1\sim n$），每个元素i不能放在位置$i$。我们聚焦于第一个元素（元素1）的位置选择，再分情况讨论剩余元素的排列方式。

1. 第一步：元素$1$的位置选择

元素1不能放在位置1，因此有(n−1)种选择（例如，放在位置$k$，其中k∈{2,3,…,n}）。

2. 第二步：分情况讨论元素$k$的位置

当元素1放在位置$k$后，我们需要考虑元素$k$的位置（元素$k$不能放在位置$k$，因为位置$k$已被元素$1$占据），此时分为两种情况：

情况1：元素$k$放在位置$1$

• 元素$1$和元素$k$交换了位置（元素$1$在位置$k$，元素$k$在位置$1$）。
• 剩余需要处理的元素是2∼k−1和k+1∼n，共(n−2)个元素。
• 这些剩余元素的位置限制不变（每个元素$i$仍不能放在位置$i$），因此这种情况的排列数等于D(n−2)（$n-2$个元素的错位排列数）。

情况2：元素$k$不放在位置1

• 元素$1$在位置$k$，但元素$k$不能放在位置$1$（情况2的条件），也不能放在位置$k$（原始限制）。
• 此时，我们可以将元素$k$视为“新的元素$1$”（因为它现在不能放在位置$1$，而位置$1$是元素$1$的原始位置）。
• 剩余需要处理的元素是2∼n（共$n-1$个元素），它们的位置限制变为：
  • 元素$i$（$,k$）不能放在位置$i$（原始限制）；
  • 元素k不能放在位置$1$（“新的原始位置”）。
• 这相当于n−1个元素的错位排列（每个元素都不能放在其“新的原始位置”），因此这种情况的排列数等于D(n−1)（n−1个元素的错位排列数）。

3. 第三步：合并两种情况

元素1有(n−1)种位置选择（即$k$的可能值），每种选择对应上述两种情况。因此，总的错位排列数为： D(n)=(n−1)×(D(n−1)+D(n−2))