容斥

容斥原理的一般化：

　　对于两个关于集合的函数\(f(S)\)和\(g(S)\)，若

\[f(S)=\sum\limits_{T\subseteq S}g(T)\]

　　那么有

\[g(S)=\sum\limits_{T\subseteq S}(-1)^{\left |S\right |-\left |T \right |}f(T)\]

　　类似的形式有

\[f(S)=\sum\limits_{T\supseteq S }g(T)\Rightarrow g(S)=\sum\limits_{T\supseteq S}(-1)^{\left |S\right |-\left |T \right |}f(T)\]

错位排列：

　　递推公式\(1\)：

\[D_n=(n-1)*(D_{n-1}+D_{n-2})\]

　　递推公式\(2\)：

\[D_n=(-1)^n+n*D_{n-1}\]

　　通项公式：

\[D_n=n!\sum\limits_{i=1}^n \frac{(-1)^i}{i!}\]