错排问题

维基百科,自由的百科全书
跳转至: 导航搜索

错排问题组合数学中的问题之一。考虑一个有n个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排n个元素的错排数记为Dn。 研究一个排列错排个数的问题,叫做错排问题或称为更列问题

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

定義[编辑]

組合數學,錯排是指沒有元素出現在自己原本位置的排列。即是說存在沒有不動點的雙射\phi: S \to S, \ \phi(i) \ne i,\ \forall 1 \le i \le n

\phi(n)的值如下:(由n=1起:)

0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... [1]

例如有n封寫好了的信,收件人不同,胡亂放入n個寫了地址的信封中,寄出,求沒有一個收件人收到他所應接收的信的機率。當n=4,在4! = 24個排列之中,只有9個是錯排:

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

所以有關機率為9/24 = 37.5%

历史[编辑]

18世纪的法国数学家尼古拉·伯努利(1687-1759年)是最早考虑这个问题的人。之后欧拉也开始对这个问题感兴趣,并称之为“组合数学中的一个奇妙问题”(拉丁文:a quaestio curiosa ex doctrina combinationis),并独立解决了这个问题[2]

研究错排问题的方法[编辑]

枚举法[编辑]

对于情况较少的排列,可以使用枚举法[3]

  • 当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.[4]

递推数列法[编辑]

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

显然D1=0,D2=1。当n≥3时,不妨设n排在了第k位,其中k≠n,也就是1≤k≤n-1。那么我们现在考虑第n位的情况。

  • 当k排在第n位时,除了n和k以外还有n-2个数,其错排数为Dn-2
  • 当k不排在第n位时,那么将第n位重新考虑成一个新的“第k位”,这时的包括k在内的剩下n-1个数的每一种错排,都等价于只有n-1个数时的错排(只是其中的第k位会换成第n位)。其错排数为Dn-1

所以当n排在第k位时共有Dn-2+Dn-1种错排方法,又k有从1到n-1共n-1种取法,我们可以得到:

Dn=(n-1)(Dn-1+Dn-2) [2]

在上面我们得到Dn=(n-1)(Dn-1+Dn-2) 从这个公式中我们可以推出Dn的通项公式,方法如下:

为书写方便,记Dn = n!Mn,则M1 = 0, M2 = \frac{1}{2}

当n大于等于3时,由Dn = (n-1)(Dn-1 + Dn-2),即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}。 所以,n M_n - n M_{n-1} =-M_{n-1} + M_{n-2}

于是有 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!}.

所以

\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}

将上面式子分边累加,得M_n=(-1)^2\frac{1}{2!}+(-1)^3\frac{1}{3!}...+(-1)^{n}\frac{1}{n!}.

因此,我们得到错排公式D_n=n!M_n=n!(\frac{1}{2!}-\frac{1}{3!}+...+(-1)^n\frac{1}{n!}).

多项式模拟[编辑]

x_1,x_2,...,x_n错排,x_1需排在x_2,x_3,...,x_nx_2需排在x_1,x_3,...,x_n如此类推。

s=\sum_{r=1}^n x_r,错排结果为\displaystyle \prod_{r=1}^n (s-x_r)\displaystyle \prod_{r=1}^n x_r的系数

a_r=(-1)^r\sum x_1x_2...x_r基本对称多项式\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}

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

a_r选出r个x有C_n^r种可能,从s选出其余的n-r个x有\frac{(n-r)!}{1!1!...1!}=(n-r)!种可能

\displaystyle \sum_{r=2}^n (-1)^r C_n^r (n-r)!=n!\sum_{r=2}^n \frac{(-1)^r}{r!}

简化公式[编辑]

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

其中的 \lfloor n \rfloor 高斯取整函数(小于等于 n 的最大整数)[5]

这个简化公式可以由之前的错排公式推导出来。事实上,考虑指数函数在 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.

参考资料[编辑]

  1. ^ OEIS:A000166
  2. ^ 2.0 2.1 Heinrich Dörrie. Triumph der Mathematik: hundert berühmte Probleme aus zwei Jahrtausenden mathematischer Kultur. Courier Dover Publications. 1965 (英文). 第19-21页
  3. ^ 卢开澄、卢华明. 《组合数学》. 清华大学出版社. ISBN 730213961X (简体中文). 
  4. ^ Miodrag Petković. Famous puzzles of great mathematicians. American Mathematical Soc. 2009. ISBN 9780821848142 (英文). 第184-186页
  5. ^ Branislav Kisačanin. Mathematical problems and proofs: combinatorics, number theory, and geometry. Springer. 1998. ISBN 9780306459672 (英文). 第43-44页