错排问题,这个问题的背景可能有多种表述方式,将其形式化,可表为:将 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

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