错排问题是组合数学中的问题之一。考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。 n个元素的错排数记为D_n或!n。 研究一个排列错排个数的问题，叫做错排问题或称为更列问题。
最早研究错排问题的是尼古拉·伯努利和欧拉，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。
定義
記D_n為\{1,2,\dots,n\}上沒有不動點的排列(即\phi: \{1,2,\dots,n\} \to \{1,2,\dots,n\}, \ \phi(i) \ne i,\ \forall 1 \le i \le n)的個數，D_n的值如下：（由n=1起）
: 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ...
不難發現，這個數列有一個規律，
D_n=nD_{n-1}+(-1)^n。
例如有n封收件人不同的信，隨機放入n個寫了收件人地址的信封中寄出，求沒有一個收件人收到他所應接收的信的機率。當n=4，設四封信為ABCD，則在4! = 24個排列之中，只有9個是錯排，即!4 = 9：
: BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA
所以其機率為
\frac{9}{24} = 37.5\% 。
历史
18世纪的法国数学家尼古拉·伯努利（1687-1759年）是最早考虑这个问题的人。之后欧拉也开始对这个问题感兴趣，并称之为“组合数学中的一个奇妙问题”（拉丁文：），并独立解决了这个问题。
研究错排问题的方法
枚举法
对于情况较少的排列，可以使用枚举法。
*当n=1时，全排列只有一种，不是错排，D1 = 0。
*当n=2时，全排列有两种，即1、2和2、1，后者是错排，D2 = 1。
*当n=3时，全排列有六种，即1、2、3；1、3、2；2、1、3；2、3、1；3、1、2；3、2、1，其中只有有3、1、2和2、3、1是错排，D3=2。用同样的方法可以知道D4=9。
*最小的几个错排数是：D1 = 0，D2 = 1，D3=2，D4 = 9，D5 = 44，D6 = 265，D7 = 1854。
递推数列法
对于排列数较多的情况，难以采用枚举法。这时可以用递归思想推导错排数的遞迴關係式。
显然D1=0，D2=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑k的情况。
*当k排在第n位时，除了n和k以外还有n-2个数，其错排数为Dn-2。
*当k不排在第n位时，那就會剩下n-1個空位(原本n個位置扣掉第k位)和n-1個數字，在排除了排在第k位的n後，由於k不在第n位，等價於把第n個空位改名為k的錯排問題。其错排数为Dn-1。
所以当n排在第k位时共有Dn-2+Dn-1种错排方法，又k有从1到n-1共n-1种取法，我们可以得到：
:Dn=(n-1)(Dn-1+Dn-2) 。
这个简化公式可以由之前的错排公式推导出来。事实上，考虑指数函数在 0 处的泰勒展开：
:\begin{align} e^{-1} &= 1 + \frac{\left( -1 \right)^1}{1!} + \frac{\left( -1 \right)^2}{2!} + \cdots + \left( -1 \right)^n\frac{1}{n!} + \frac{ e^{-c} }{(n+1)!} \left( c - 1 \right)^n \\
&= \frac{1}{2!}-\frac{1}{3!}+\cdots+\left(-1\right)^n\frac{1}{n!} + R_n \\
&= \frac{D_n}{n!} + R_n \\
\end{align}
所以， \frac{n!}{e} - D_n = n!\,R_n。其中 Rn 是泰勒展开的餘项，c 是介于 0 和 1 之间的某个实数。Rn 的绝对值上限为
: |R_n| \leqslant \frac{ e^0 }{(n+1)!} = \frac{1}{(n+1)!}
:\Big| \frac{n!}{e} - D_n \Big| \leqslant \frac{ n! }{(n+1)!} = \frac{1}{(n+1)}
当 n≥2 时，\frac{1}{(n+1)} 严格小于 0.5，所以 D_n=n!\left(\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}\right) 是最接近 \frac{n!}{e} 的整数，可以写成
:D_n= \left\lfloor \frac{n!}{e}+0.5 \right\rfloor.
参考资料
外部链接
评论 (0)