User:Avit4799/沙盒3

考虑一个有n个元素的排列，若一个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排。研究一个排列错排个数的问题，叫做错排问题或称为更列问题。我们把n个元素的错排数记为D_n。如，四人各写一张贺年卡互相赠送，有多少种赠送方法？此题中自己写的贺年卡不能送给自己，所以是典型的错排问题。此时D₄=9。

研究错排问题的方法

枚举法

对于情况较少的排列，我们可以使用枚举法。

• 当n=1时，全排列只有一种，不是错排，D₁=0。
• 当n=2时，全排列有两种，即1、2和2、1，后者是错排，D₂=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₃=2。我们用同样的方法可以知道D₄=9。

递推数列法

对于排列数较多的情况，难以采用枚举法，我们可以推导出错排数的递推公式。

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

• 当k排在第n位时，除了n和k以外还有n-2个数，其错排数为D_n-2。
• 当k不排在第n位时，那么将包括k在内的剩下n-1个数错排，其错排数为D_n-1。

所以当n排在第k位时共有D_n-2+D_n-1种错排方法，又k有从1到（n-1）共（n-1）种取法，我们可以得到： D_n=(n-1)(D_n-1+D_n-2)

错排公式

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

为书写方便，我们记D_n=n!M_n

则M₁=0,M₂=${\frac {1}{2}}$

当n大于等于3时，由D_n=(n-1)(D_n-1+D_n-2)，即n!M_n=(n-1)(n-1)!M_n-1+(n-1)(n-2)!M_n-2=(n-1)(n-1)!M_n-1+(n-1)!M_n-2

所以，nM_n=(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!}}$

所以$M_{n-1}-M_{n-2}=(-1)^{n-1}{\frac {1}{(n-1)!}}$

$M_{2}-M_{1}=(-1)^{2}{\frac {1}{2!}}$

累加，得$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!}})$

简化公式

我们在这里提供一个求错排数的简化公式，证明略。

$D_{n}=[{\frac {n!}{e}}+0.5]$，其中的[x]为高斯函数。