错排

错排:

公式:a[i]=(i-1)*(a[i-1]+a[i-2])

链接:https://blog.csdn.net/achesong/article/details/87387024

错排公式的原形为D(n) = n! (1/0! - 1/1! + 1/2! - 1/3! - ….. + (-1)^n/n!),当n很大时计算就很不方便。一个供参考的简化后的公式是D(n) = [n!/e+0.5] ,其中e是自然对数的底,[x]为x的整数部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
证明:
由于1/e = e^(-1) = 1/0! - 1/1! + 1/2! - 1/3! - ..... + (-1)^n/n! + Rn(-1),
其中Rn(-1)是余项,等于(-1)^(n+1) * e^u / (n+1)!,且u∈(-1, 0).
所以,D(n) = n! * e^(-1) - (-1)^(n+1) * e^u / (n+1), u∈(-1, 0).
而|n! Rn| = |(-1)^(n+1) * e^u / (n+1)| = e^u / (n+1) ∈ (1/[e(n+1)], 1/(n+1)),可知即使在n=1时,该余项(的绝对值)也小于1/2
因此,无论n! Rn是正是负,n! / e + 1/2的整数部分都一定与M(n)相同。
对于比较小的n,结果及简单解释是:
D(0) = 0(所有的元素都放回原位、没有摆错的情况)
D(1) = 0(只剩下一个元素,无论如何也不可能摆错)
D(2) = 1(两者互换位置)
D(3) = 2(ABC变成BCA或CAB)
D(4) = 9
D(5) = 44
D(6) = 265
D(7) = 1854
D(8) = 14833
D(9) = 133496
D(10) = 1334961

---------------- The End ----------------
0%