2023/04/错排

定义

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

递推公式

第一步

把第$n$个元素放在一个位置，比如位置k,一共有$n-1$种放法。

第二步

放编号为k的元素，此时有两种情况。

1. 把它放到位置n
2. 第k个元素不把它放到位置n

讨论情况1，当第k个元素放在位置n后，还剩有 $n-2$ 个元素，它们进行错排有D(n-2)种方法。

再讨论情况2，当第k个元素不放在位置n，这是，对于未排的 $n-1$个元素，有D(n-1)种方法。

此时可得到公式

$$\begin{aligned} D(1)&=0\\D(2)&=1\\ D(n)&=(n-1)\cdot[D(n-2)+D(n-1)] \end{aligned}$$ $$\begin{aligned} D(n)&=n!-\frac{n!}{1!}+\frac{n!}{2!}+\cdots+(-1)^n\times\frac{n!}{n!}\\ &=\sum\limits_{k=3}^{n}(-1)^k\cdot\frac{n!}{k!} \end{aligned}$$