https://zhuanlan.zhihu.com/p/133818995
递推公式
f[n]=(n-1)*(f[n-1]+f[n-2])
证明（这也配叫证明？？？
第n个元素可以在前n-1个元素都是错排的情况下与其中一个元素交换位置（n不在就有的错排）
有(n-1)*f[n-1]种方案
第n个元素还可以在前n-2个元素错排，有一个元素在自己位置上时，两个元素换一换（n来了产生的新错排）
有（n-1)*f[n-2]种方案
为什么不考虑两个元素在自己的位置上然后三个元素换一换呢？
你会发现不管怎么换一定是有一个元素和n换了位置，其余元素互相换了位置，，，被前两种情况包含了啦
当然也有别的理解
通项公式
f[n]=n!-n!/1!+n!/2!-n!/3!+…+(-1) n n!/n!
要求错排先求出不错排（？），再用全部的减去不错排
全部的很好求啊，n!嘛
不错排……
分为1个数在自己的位置上，2个数在自己的位置上，3个数在自己的位置上……,n个数都在自己的位置上（其余随便排）等情况？
所以它们分别是C1nAn-1n-1,C2nAn-2n-2,C3nAn-3n-3……CnnAn-nn-n？
所以直接加起来就行嘛？
并不……
它们之间有包含关系，，，
这就用到容斥原理（奇加偶减）啦~
不错排=1个数的-2个数的+3个数的……
带入公式化简一下就好了（不想写了www）
当然不会容斥原理也没有关系
那个式子得出来的实际是>=1个数在自己的位置上，>=2个数在自己的位置上……
直观地表示为
1+2+3+……+n
2+3+……+n
3+……+n
可以发现上下两个式子作差再加起来就好了~