一个供参考的简化后的公式是D(n) = [n!/e+0.5] ,其中e是自然对数的底,[x]为x的整数部分。
证明:
由于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
扩展资料
用容斥原理也可以推出错排公式:
正整数1, 2, 3, ……, n的全排列有 n! 种,其中第k位是k的排列有 (n-1)! 种;当k分别取1, 2, 3, ……, n时,共有n*(n-1)!种排列是至少放对了一个的,由于所求的是错排的种数,所以应当减去这些排列;但是此时把同时有两个数不错排的排列多排除了一次,应补上。
在补上时,把同时有三个数不错排的排列多补上了一次,应排除;……;继续这一过程,得到错排的排列种数为
D(n) = n! - n!/1! + n!/2! - n!/3! + … + (-1)^n*n!/n! = ∑(k=2~n) (-1)^k * n! / k!,
即D(n) = n! [1/0! - 1/1! + 1/2! - 1/3! + 1/4! + ... + (-1)^n/n!].
其中,∑表示连加符号,k=2~n是连加的范围;0! = 1,可以和1!相消。
参考资料来源:百度百科-错排公式
错排公式的原形为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/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) = 1(所有的元素都放回原位、没有摆错的情况)
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