小目录：

一，容斥原理

二，子集反演

三，最值反演（$\textit{Min_Max}$容斥）

四，斯特林反演

五，单位根反演

---

前置概念

一，第一类斯特林数：

$\begin{bmatrix}n\\k\end{bmatrix}$

那个大的中括号叫做 轮换 ，意思是将$n$个元素划分成$k$集合，每个集合进行 圆排列 的方案数。

圆排列：将长度为$n$的序列连成一个环，不同的排列数。其实就是$P_n=(n-1)!$，这里P是圆排列

关于其有一个递推式

$\begin{bmatrix}n\\k\end{bmatrix}=\begin{bmatrix} n-1\\k-1 \end{bmatrix}+(n-1)\begin{bmatrix}n-1\\k\end{bmatrix}$

证明可以类似用组合数的方法，原来有$n-1$个元素，划分了$k-1$个集合的方案加上一个新加的集合贡献的方案。

有三个性质：

一，

$\sum_{i=0}^{n} \begin{bmatrix}n\\i\end{bmatrix}=n!$

写两种不同的排列，然后映射连边，组成环的个数就是划分集合的个数，然后依次类推，组成一个环的排列，两个环的排列。。。。

 

 

 

 如图就是$\begin{bmatrix}7\\3\end{bmatrix}$的图示了，其他的加和推广可以yy，比较好想。

二，

$x^{\underline{n}}=\sum_{i=0}^{n}(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i$

此柿子可以用归纳法证明，详见我的学长链接里Lrerain的博客。

其中$\underline{n}$是表示降幂，同理$\overline{n}$表示升幂

三，

x^{\overline{n}}=\sum_{i=0}^{n}\begin{bmatrix}n\\i\end{bmatrix}x^i

同样的，这里就不证明了。

这几条性质可以解决升幂变化通幂再变化升幂或者降幂等等的转化，比较好用

有其是组合数里面的那种降幂。

二，第二类斯特林数：

$\begin{Bmatrix}n\\k\end{Bmatrix}$

表示$n$个元素划分为$k$个集合的方案数。

比上一个好理解。。。。

通项公式：

$\begin{Bmatrix}n\\m\end{Bmatrix}=\sum_{i=0}^{m}\frac{(-1)^{m-i}i^n}{i!(m-i)!}$

递推式：

$\begin{Bmatrix}n\\k\end{Bmatrix}=\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+k\begin{Bmatrix}n-1\\k\end{Bmatrix}$

同样有几个性质。

一，

$k^n=\sum_{i=0}^{k}\begin{Bmatrix}n\\i\end{Bmatrix}i!\binom{k}{i}=\sum_{i=0}^{k}\begin{Bmatrix}n\\i\end{Bmatrix}k^{\underline{i}}$

 

 

 二，

 

 

 

 这两个过于难打，就直接粘贴了，上面的柿子化简可得下式。

---

前置知识完毕，$L_AT^EX$显然已经打废了。。。。