错排问题，这个问题的背景可能有多种表述方式，将其形式化，可表为：将 1 至 n 这 n 个数字排列，使得每个数字不出现在其所在序号的位置上，问所有可能的排列数。详见 wiki

对于这一问题的「官方」解法是这样的：考虑编号为 1 的数字，显然它有 \(n-1\) 个可能的位置。假定它出现在 i 位置上，那么分两种情况考虑：

  1. \(i\) 号数字出现在 1 位置上，则问题缩减为 \(n-2\) 个数字错排的情况；
  2. \(i\) 号数字出现在非 1 位置上。这里出现了一个精妙的想法：对于 \(i\) 号数字来说，它「不允许」出现在 1 位置上，而其他的各元素 \(2, 3, ..., i-1, i+1, ..., n\) 不允许出现在各自的编号位置上——所以，\(i\) 号元素个其他元素的地位是等价的——问题化归为 \(n-2\) 个数字错排的情况。

综上，可以得到递推公式，\(D(n)=(n-2)(D(n-1)+D(n-2)), n\ge 3\)。当然，初始条件为 \(D(1)=0, D(2)=1\)。

另一种也比较容易想到的方法是这样的：对于所有可能的排列，减去其中出现矛盾的情况。

  • 若只有 1 个数字出现了矛盾（在它的位置上），共有 \(C_n^1\) 种可能，对于剩下的每个元素都处于非自己的位置上，即划归为 \(n-1\) 时的问题；
  • 若有 2 个数字出现矛盾，共有 \(C_n^2\) 种可能，对其他元素进行错排，即 \(n-2\) 时的情况；...
  • 若有 \(n-2\) 个数字出现矛盾，共有 \(C_n^{n-2}\) 种可能，对其他元素进行错排，即 \(2\) 时的情况；
  • 注意到，不可能恰好只有 \(n-2\) 个数字出现矛盾（最后那个数字只能在它的位置上），因此最后再减去 1，即所有元素在它的位置上的情况。

综上，递推公式为 \(D(n)=n!-C_n^1D(n-1)-C_n^2D(n-2)-...-C_n^{n-2}D(2)-1, n\ge 3\)，初始条件和上种解法一致。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from scipy.special import comb
import math


def derangement_1(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    return (n-1) * (derangement_1(n-1)+derangement_1(n-2))


def derangement_2(n):
    if n == 1:
        return 0
    if n == 2:
        return 1
    der = math.factorial(n)
    for i in range(n-1, 1, -1):
        der -= comb(n, n-i) * derangement_2(i)
    return int(der-1)


m = 15
for i in range(2, m):
    print(derangement_1(i), end=" ")
print()
for i in range(2, m):
    print(derangement_1(i), end=" ")

结果为

1
2
1 2 9 44 265 1854 14833 133496 1334961 14684570 176214841 2290792932 32071101049 
1 2 9 44 265 1854 14833 133496 1334961 14684570 176214841 2290792932 32071101049

可见，两种计算方法是一致的。