把上课的一些吓死人的柿子都记下来了。什么时候用得上不知道，反正先放着。
第一类斯特林数
\(\begin{bmatrix}n\\m\end{bmatrix}\) 表示将 \(n\) 个元素分成 \(m\) 个圆排列的方案数。
递推式：
\(\begin{bmatrix}n\\m\end{bmatrix} = \begin{bmatrix}n - 1\\m - 1\end{bmatrix} + (n - 1)\begin{bmatrix}n - 1\\m\end{bmatrix}\)
第二类斯特林数
\(\begin{Bmatrix}n\\m\end{Bmatrix}\) 表示把 \(n\) 个不同元素划分成 \(m\) 个互不区分的非空子集的方案数。
递推式：
\(\begin{Bmatrix}n\\m\end{Bmatrix}=\begin{Bmatrix}n - 1\\m - 1\end{Bmatrix} + m\begin{Bmatrix}n - 1\\m\end{Bmatrix}\)
一个性质：
\(x^n=\sum\limits_{k=0}^{n} \begin{Bmatrix}n\\ k\end{Bmatrix} x^{\underline{k}}\)
二项式反演
\(g_n = \sum\limits_{i = 0}^{n} \dbinom{n}{i} f_i\iff f_n = \sum\limits_{i = 0}^{n} (-1)^{n-i}\dbinom{n}{i} g_i\)
\(g_k=\sum\limits_{i=k}^n \dbinom i k f_i \iff f_k=\sum\limits_{i=k}^n (-1)^{i-k} \dbinom i k g_i\)
子集反演
\(g(S)=\sum\limits_{T\subset S}f(T)\iff f(S)=\sum\limits_{T\subset S}(-1)^{|S|-|T|}g(T)\)
（ \(g(S)\) 表示所有子集值的和，\(f(S)\) 表示一个子集的值。）
min-max容斥
\(\max(S) = \sum\limits_{T \subset S} (-1)^{|T| + 1} \min(T)\)
\(\min(S) = \sum\limits_{T \subset S} (-1)^{|T| + 1} \max(T)\)
（ \(max(S)\) 表示集合内所有元素最大值，\(min(S)\) 表示最小值。）
对于期望同样适用。
扩展（第k大第k小）：
\(\operatorname{kth-max}(S)=\sum\limits_{T\subset S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\min (T)\)
\(\operatorname{kth-min}(S)=\sum\limits_{T\subset S}(-1)^{|T|-k}\binom{|T|-1}{k-1}\max (T)\)
斯特林反演
\(f_n = \sum\limits_{i=0}^n \begin{Bmatrix} \ n \ \\ \ i \ \end{Bmatrix} g_i \iff g_n = \sum\limits_{i=0}^n (-1)^{n-i} \begin{bmatrix} \ n \ \\ \ i \ \end{bmatrix} f_i\)
\(f_n = \sum\limits_{k=n}^{inf} \begin{Bmatrix} \ k \ \\ \ n \ \end{Bmatrix} g_k \iff g_n = \sum\limits_{k=n}^{inf} (-1)^{k-n} \begin{bmatrix} \ k \ \\ \ n \ \end{bmatrix} f_k\)
和二项式反演差不多。
单位根反演
\([n|k] = \frac1n\sum\limits_{i=0}^{n-1} \omega^{ik}_ n\)
令 \(F(x)=\sum\limits_{i=0}^m f_ix^i\) :
则有 \(\sum\limits_{k=0}^m[n|k]f_k=\frac{1}{n}\sum\limits_{i=0}^{n-1}F(\omega_n^i)\)
标签：begin,end,bmatrix,limits,一看,sum,柿子,Bmatrix,一些 From： https://www.cnblogs.com/StevenZC/p/17993113