错排问题是组合数学中的问题之一。考虑一个有
个元素的排列,若一个排列中所有的元素都不在自己原来的位置上,那么这样的排列就称为原排列的一个错排。
个元素的错排数记为
或
。 研究一个排列错排个数的问题,叫做错排问题或称为更列问题。
最早研究错排问题的是尼古拉·伯努利和欧拉,因此历史上也称为伯努利-欧拉的装错信封的问题。这个问题有许多具体的版本,如在写信时将
封信装到
个不同的信封里,有多少种全部装错信封的情况?又比如四人各写一张贺年卡互相赠送,有多少种赠送方法?自己写的贺年卡不能送给自己,所以也是典型的错排问题。
记
为
上没有不动点的排列(即
)的个数,
的值如下:(由
起)
- 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, ... [1]
不难发现,这个数列有一个规律,
。
例如有
封收件人不同的信,随机放入
个写了收件人地址的信封中寄出,求没有一个收件人收到他所应接收的信的几率。当
,设四封信为ABCD,则在
个排列之中,只有9个是错排,即
:
- BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA
所以其几率为
。
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。那么我们现在考虑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) [2]
在上面我们得到
Dn=(n-1)(Dn-1+Dn-2)
从这个公式中我们可以推出Dn的通项公式,方法如下:
为书写方便,记Dn = n!Mn,则M1 = 0, M2 =
当n大于等于3时,由
Dn = (n-1)(Dn-1 + Dn-2),
即
。
所以,
。
于是有
所以
![{\displaystyle {\begin{aligned}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{aligned}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/66eed270adf73a9b0dd9e04cfd2eb0eaa8893666)
将上面式子分边累加,得
因此,我们得到错排公式
错排,
需排在
、
需排在
如此类推。
记
,错排结果为
中
的系数
记
为基本对称多项式,
从
选出
,然后从
选出
,组成
从
选出r个x有
种可能,从
选出其余的n-r个x有
种可能
![{\displaystyle \displaystyle \sum _{r=2}^{n}(-1)^{r}C_{r}^{n}(n-r)!=n!\sum _{r=2}^{n}{\frac {(-1)^{r}}{r!}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/6f0c948a399f10351b438cea0dff53786f5672cd)
错位排列数的公式可以简化为:
其中的
为高斯取整函数(小于等于 n 的最大整数)[5]。
这个简化公式可以由之前的错排公式推导出来。事实上,考虑指数函数在 0 处的泰勒展开:
![{\displaystyle {\begin{aligned}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{aligned}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/8fb2363dad1abc226dd74b8d954e4ce13b87c898)
所以,
。其中 Rn 是泰勒展开的余项,c 是介于 0 和 1 之间的某个实数。Rn 的绝对值上限为
![{\displaystyle |R_{n}|\leqslant {\frac {e^{0}}{(n+1)!}}={\frac {1}{(n+1)!}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/561074342de749f9ea37688bcc5216a8fab52bae)
![{\displaystyle {\Big |}{\frac {n!}{e}}-D_{n}{\Big |}\leqslant {\frac {n!}{(n+1)!}}={\frac {1}{(n+1)}}}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/dd3e7321adfd1e5427bffd3cc494cfc8c041a148)
当 n≥2 时,
严格小于 0.5,所以
是最接近
的整数,可以写成
![{\displaystyle D_{n}=\left\lfloor {\frac {n!}{e}}+0.5\right\rfloor .}](https://backend.710302.xyz/https/wikimedia.org/api/rest_v1/media/math/render/svg/e7f45e127b95e9f72ddf2ee1ff92a3d81f38a5dc)