查看“︁错排问题”︁的源代码

'''错排问题'''是[[组合数学]]中的问题之一。考虑一个有<math>n</math>个元素的[[排列]]，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个'''错排'''。 <math>n</math>个元素的错排数记为<math>D_n</math>或<math>!n</math>。 研究一个排列错排个数的问题，叫做'''错排问题'''或称为'''更列问题'''。

最早研究错排问题的是[[尼古拉一世·伯努利|尼古拉·伯努利]]和[[欧拉]]，因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本，如在写信时将<math>n</math>封信装到<math>n</math>个不同的信封里，有多少种全部装错信封的情况？又比如四人各写一张贺年卡互相赠送，有多少种赠送方法？自己写的贺年卡不能送给自己，所以也是典型的错排问题。

==定義==
記<math>D_n</math>為<math>\{1,2,\dots,n\}</math>上沒有不動點的排列(即<math>\phi: \{1,2,\dots,n\} \to \{1,2,\dots,n\}, \ \phi(i) \ne i,\ \forall 1 \le i \le n</math>)的個數，<math>D_n</math>的值如下：（由<math>n=1</math>起）

: 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... <ref>{{cite OEIS|A000166|name=Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.}}</ref>

不難發現，這個數列有一個[[規律]]，

<math>D_n=nD_{n-1}+(-1)^n</math>。

例如有<math>n</math>封收件人不同的信，隨機放入<math>n</math>個寫了收件人地址的信封中寄出，求沒有一個收件人收到他所應接收的信的機率。當<math>n=4</math>，設四封信為ABCD，則在<math>4! = 24</math>個排列之中，只有9個是錯排，即<math>!4 = 9</math>：

: BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA

所以其機率為

<math> \frac{9}{24} = 37.5\% </math>。

==历史==
18世纪的法国数学家[[尼古拉一世·伯努利|尼古拉·伯努利]]（1687-1759年）是最早考虑这个问题的人。之后欧拉也开始对这个问题感兴趣，并称之为“组合数学中的一个奇妙问题”（拉丁文：{{lang|la|''a quaestio curiosa ex doctrina combinationis''}}），并独立解决了这个问题<ref name="HD">{{cite book | title = Triumph der Mathematik: hundert berühmte Probleme aus zwei Jahrtausenden mathematischer Kultur | author =  Heinrich Dörrie |publisher =  Courier Dover Publications  | language = en | year = 1965 }}第19-21页</ref>。

==研究错排问题的方法==
===枚举法===
对于情况较少的排列，可以使用[[枚举法]]<ref>{{Cite book | author =卢开澄、卢华明 | title =《组合数学》 | url =https://archive.org/details/isbn_9787302139614 | publisher = 清华大学出版社 |ISBN =730213961X |  language= zh-hans }}</ref>。
*当n=1时，全排列只有一种，不是错排，D<sub>1</sub> = 0。
*当n=2时，全排列有两种，即1、2和2、1，后者是错排，D<sub>2</sub> = 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是错排，D<sub>3</sub>=2。用同样的方法可以知道D<sub>4</sub>=9。
*最小的几个错排数是：D<sub>1</sub> = 0，D<sub>2</sub> = 1，D<sub>3</sub>=2，D<sub>4</sub> = 9，D<sub>5</sub> = 44，D<sub>6</sub> = 265，D<sub>7</sub> = 1854。<ref name="puzzles">{{cite book | title =Famous puzzles of great mathematicians | url =https://archive.org/details/famouspuzzlesofg0000petk | author = Miodrag Petković | publisher =American Mathematical Soc. | year =2009 | isbn =9780821848142 | language = en  }}第184-186页</ref>

===递推数列法===
对于排列数较多的情况，难以采用枚举法。这时可以用递归思想推导错排数的[[遞迴關係式]]。

显然D<sub>1</sub>=0，D<sub>2</sub>=1。当n≥3时，不妨设n排在了第k位，其中k≠n，也就是1≤k≤n-1。那么我们现在考虑k的情况。
*当k排在第n位时，除了n和k以外还有n-2个数，其错排数为D<sub>n-2</sub>。
*当k不排在第n位时，那就會剩下n-1個空位(原本n個位置扣掉第k位)和n-1個數字，在排除了排在第k位的n後，由於k不在第n位，等價於把第n個空位改名為k的錯排問題。其错排数为D<sub>n-1</sub>。
所以当n排在第k位时共有D<sub>n-2</sub>+D<sub>n-1</sub>种错排方法，又k有从1到n-1共n-1种取法，我们可以得到：
:D<sub>n</sub>=(n-1)(D<sub>n-1</sub>+D<sub>n-2</sub>) <ref name="HD"/>

在上面我们得到

D<sub>n</sub>=(n-1)(D<sub>n-1</sub>+D<sub>n-2</sub>)

从这个公式中我们可以推出D<sub>n</sub>的通项公式，方法如下：

为书写方便，记D<sub>n</sub> = n!M<sub>n</sub>，则M<sub>1</sub> = 0, M<sub>2</sub> = <math>\frac{1}{2}</math>

当n大于等于3时，由

D<sub>n</sub> = (n-1)(D<sub>n-1</sub> + D<sub>n-2</sub>)，

即

<math>n! M_n = (n-1)(n-1)!M_{n-1} +(n-1)(n-2)! M_{n-2} =n! M_{n-1} - (n-1)!M_{n-1} +(n-1)! M_{n-2}</math>。

所以，<math>n M_n - n M_{n-1} =-M_{n-1} + M_{n-2} </math>。

于是有 <math>M_n - M_{n-1}=-\frac{1}{n}(M_{n-1}-M_{n-2})=...=(-\frac{1}{n})(-\frac{1}{n-1})...(-\frac{1}{3})(M_2-M_1)=(-1)^n\frac{1}{n!}.</math>

所以
:<math>\begin{align} 
M_{n}-M_{n-1}&=(-1)^{n}\frac{1}{n!} \\
M_{n-1}-M_{n-2}&=(-1)^{(n-1)}\frac{1}{(n - 1)!} \\ 
\vdots \quad &= \quad \vdots \\
M_2-M_1 &= (-1)^2\frac{1}{2!} \\
\end{align}</math>

将上面式子分边累加，得

<math>M_n=(-1)^2\frac{1}{2!}+(-1)^3\frac{1}{3!}...+(-1)^{n}\frac{1}{n!}.</math>

因此，我们得到错排公式

<math>D_n=n!M_n=n!(\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}).</math>

==多项式模拟==
<math>x_1,x_2,...,x_n</math>错排，<math>x_1</math>需排在<math>x_2,x_3,...,x_n</math>、<math>x_2</math>需排在<math>x_1,x_3,...,x_n</math>如此类推。

记<math>s=\sum_{r=1}^n x_r</math>，错排结果为<math>\displaystyle \prod_{r=1}^n (s-x_r)</math>中<math>\displaystyle \prod_{r=1}^n x_r</math>的系数

记<math>a_r=(-1)^r\sum x_1x_2...x_r</math>为[[基本对称多项式]]，

<math>\displaystyle \prod_{r=1}^n (s-x_r)=\sum_{r=0}^n a_r s^{n-r}=\sum_{r=2}^n a_r s^{n-r}</math>

从<math>a_r</math>选出<math>x_1,x_2,...,x_r</math>，然后从<math>s^{n-r}</math>选出<math>x_{r+1},x_{r+2},...,x_n</math>，组成<math>\displaystyle \prod_{r=1}^n x_r</math>

从<math>a_r</math>选出r个x有<math>C_r^n</math>种可能，从<math>s</math>选出其余的n-r个x有

<math>\frac{(n-r)!}{1!1!...1!}=(n-r)!</math>

种可能

:<math>\displaystyle \sum_{r=2}^n (-1)^r C_r^n (n-r)!=n!\sum_{r=2}^n \frac{(-1)^r}{r!} </math>

==简化公式==
错位排列数的公式可以简化为：<math>D_n= \left\lfloor  \frac{n!}{e}+0.5  \right\rfloor, </math>

其中的 <math>\lfloor n \rfloor </math> 为[[取整函数|高斯取整函数]]（小于等于 ''n'' 的最大整数）<ref>{{cite book
| title =Mathematical problems and proofs: combinatorics, number theory, and geometry
| url =https://archive.org/details/mathematicalprob0000kisa
|author =Branislav Kisačanin
|publisher = Springer
|year = 1998
|isbn = 9780306459672
| language = en
}}第43-44页</ref>。

这个简化公式可以由之前的错排公式推导出来。事实上，考虑[[指数函数]]在 0 处的[[泰勒公式|泰勒展开]]：
:<math>\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}</math>

所以，<math> \frac{n!}{e} - D_n = n!\,R_n</math>。其中 ''R<sub>n</sub>'' 是泰勒展开的餘项，''c'' 是介于 0 和 1 之间的某个实数。''R<sub>n</sub>'' 的[[绝对值]]上限为
:<math> |R_n| \leqslant  \frac{ e^0 }{(n+1)!}  = \frac{1}{(n+1)!}  </math>
:<math>\Big| \frac{n!}{e} - D_n \Big| \leqslant  \frac{ n! }{(n+1)!}  = \frac{1}{(n+1)}  </math> 
当 n≥2 时，<math>\frac{1}{(n+1)}  </math> 严格小于 0.5，所以 <math>D_n=n!\left(\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}\right)</math> 是最接近 <math>\frac{n!}{e}</math> 的整数，可以写成
:<math>D_n= \left\lfloor  \frac{n!}{e}+0.5  \right\rfloor. </math>

==参考资料==
{{reflist}}

[[Category:组合数学]]