容斥原理推导错排通项公式

容斥原理推导错排通项公式
设Ai是第i个元素放在第i个位置上的排列数
_Ai表示Ai的补集
所以我们要求的就是-->如图

转化一下，它们其实是等价的

也就是

右边可以套容斥原理了
A1 U ... U An=n!-C(n,1)*(n-1)!+C(n,2)*(n-2)!-...=n!*(  sigema{2<=i<=n}  ((-1)^i) / i!  )