首先，对于D(n)，有1~n这样n个元素错排，所以对于第一个元素①，它现在可能的位置有(n-1)个，倘若它在第k个元素的位置上，对于第k个元素而言，它所在的位置就有两种可能—第一种，它处在非第一个元素①位置上，所以对于接下来的排列就相当于是n-1个元素的错排，即D(n-1);第二种，它处在第一个元素①的位置上，所以在排列D(n)中有两个元素找到了位置，那么接下来的队列就相当于是n-2个元素的错排。因此，对于D(n)都有D(n)=(n-1)*(D(n-1)+D(n-2))【特殊的，D(1)=0，D(2)=1】。
容斥定理
正整数1,2, 3, ……, n的全排列有 n! 种，其中第k位是k的排列有 (n-1)! 种；当k分别取1, 2, 3, ……, n时，共有n*(n-1)!种排列是至少放对了一个的，由于所求的是错排的种数，所以应当减去这些排列；但是此时把同时有两个数不错排的排列多排除了一次，应补上；在补上时，把同时有三个数不错排的排列多补上了一次，应排除；……；继续这一过程，得到错排的排列种数为D(n) = n! – n!/1! + n!/2! – n!/3! + … + (-1）^n*n!/n!= ∑(k=2~n) (-1)^k * n! / k! 或者 
为方便起见，设D(k) = k! N(k), k = 1, 2, …, n,
则N(1) = 0, N(2) = 1/2.
n ≥ 3时，n! N(n) = (n-1) (n-1)! N(n-1) + (n-1)! N(n-2)
即 nN(n) = (n-1) N(n-1) + N(n-2)
于是有N(n) – N(n-1) = – [N(n-1) – N(n-2)] / n = (-1/n) [-1/(n-1)] [-1/(n-2)]…(-1/3) [N(2) – N(1)] = (-1)^n / n!.
因此
N(n-1) – N(n-2) = (-1)^(n-1) / (n-1)!,
N(2) – N(1) = (-1)^2 / 2!.
相加，可得
N(n) = (-1)^2/2! + … + (-1)^(n-1) / (n-1)! + (-1)^n/n!
因此
D(n) = n! [(-1)^2/2! + … + (-1)^(n-1)/(n-1)! + (-1)^n/n!].
此即错排公式。
递推代码
long long rc[maxn];
inline void get_cp()
{
rc[0]=1ll;
for(int i=2;i<=n;i++)
rc[i]=(i-1)*(rc[i-2]+rc[i-1])%mod;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/201347.html原文链接：https://javaforall.net
