整理自Richard A.Brualdi的《组合数学》

如果定义全排列 1~n， 那么 一个排列满足 任意的i都满足a[i]!=i，称之为错位排列。 定义集合元素个数为n的错位排列个数为\(D_n\) 比如这些问题: 一个聚会上，10位绅士查看他们的帽子。有多少种方式使得这些绅士中没有人能够拿到他们最开始的帽子？ 把一个单词打乱，多少种可能新单词和旧单词每一位都不一样? 诸如此类。

错位排列有两种递推公式 第一: \(D_n = (n-1)(D_{n-1}+D_{n-2})\) 第二: \(D_n = nD_{n-1}+(-1)^{n}\)

其中1,2式子均满足\(D_1 = 0,D_2 = 1\)

下面给出《组合数学》中的证明: 假设\(n >=3\)，考虑\(\{1,2...,n\}\)的\(D_n\)个错位排列 来看看第一个位置的情况: 它可以是除1以外的任何数字，那么一共有\(n-1\)种情况并且每一种情况所产生的排列数都应该相同，我们设为\(d_n\) 也就是说 \(D_n = (n-1)d_n\) 现在来看看\(d_n\): 因为第1个位置可以是除1以外的任何数，并且产生排列数相同。 出于方便，我们假设第1个位置的数是2: 确定了第一个位置之后我们发现只需要讨论第二个位置是不是1这是一个特殊的点。

如果第2个位置是1，那接下来的\(n-2\)个位置等价于n个元素中有两个元素调换了位置。 那我们可以把他们踢出去，他们已经不影响问题了。 而剩下的元素将继续进行错位排列，也就是 \(D_{n-2}\)。

如果第2个位置不是1，这时候来重新陈述一下问题： 第2个位置不能是1，第3个位置不能是3，第4个位置不能是4.....第n个位置不能是n 这个问题是不是似曾相识? 是的,又是一个错排，这个错排只少了一个位置，所以他是\(D_{n-1}\)。

得到:\(d_n = D_{n-1}+D_{n-2}\) 联立之前的式子就是\(D_n = (n-1)(D_{n-1}+D_{n-2})\) 再将这个式子不断地递归求解就会得出\(D_n = nD_{n-1}+(-1)^{n}\)

先直接给出结论(uysy这个也没啥用，时间复杂度也是O(n)的) \(D_n = n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+...(-1)^n\frac{1}{n!})\) 这个问题需要用到容斥定理的一个结论。 之后在容斥定理的总结中给出(莫比乌斯反演真的看不懂啊* ^ *)