第一、二类斯特林数与斯特林反演

两个递推的初始条件都是$S(0,0)=1$ ## 第一类斯特林数 把$n$个**不同**元素分成$m$个**相同**环排列的方案数 ### 递推求法 $$ \begin{bmatrix}n\\m\end{bmatrix}=\begin{bmatrix}n-1\\m-1\end{bmatrix}+(n-1)\times \begin{bmatrix}n-1\\m\end{bmatrix} $$ ### 快速求一行 有这个式子 $$ x^{\underline{n}}=\sum_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}x^i $$ 和这个式子 $$ x^{\overline{n}}=\sum_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}x^i $$ 然后就可以直接分治$NTT$求了 ### 一个重要式子 $$ n!=\sum_{i=0}^{n}\begin{bmatrix}n\\i\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} $$ ### 快速求一行 $$ \sum_{i=0}^n\begin {Bmatrix} n \\ i\end {Bmatrix}x^i=e^{-x}\sum_{i=0}^{n}\frac{i^n}{i!}x^i $$ 直接卷积就行了 ### 一个重要式子 可以普通多项式转下降幂多项式 $$ n^m=\sum_{i=0}^{m}\begin {Bmatrix} m \\ i\end {Bmatrix}i!\binom{n}{i}=\sum_{i=0}^{m}\begin {Bmatrix} m \\ i\end {Bmatrix}n^{\underline i} $$ 下降幂多项式一个重要的公式 $$ \color{red}{\binom{n}{k}k^{\underline{m}}=\binom{n-m}{k-m}n^{\underline m}} $$ ### 另一个重要式子 $$ \begin {Bmatrix} n \\ m\end {Bmatrix}=\frac{1}{m!}\sum_{i=0}^m(-1)^{m-i}\binom{m}{i}i^n $$ 即容斥 考虑分成$i$个集合的方案 ## 斯特林反演 $$ f(n)=\sum_{k=0}^n\begin {Bmatrix} n \\ k\end {Bmatrix}g(k)\Longleftrightarrow g(n)=\sum_{k=0}^n(-1)^{n-k}\begin{bmatrix}n\\k\end{bmatrix}f(k) $$ $$ f(n)=\sum_{k=n}^\infty \begin {Bmatrix} k \\ n\end {Bmatrix}g(k)\Longleftrightarrow g(n)=\sum_{k=n}^\infty(-1)^{k-n}\begin{bmatrix}k\\n\end{bmatrix}f(k) $$ ### 雅礼集训[方阵] 给出一个$(n×m)$大小的矩形，每个位置可以填上$[1,c]$中的任意一个数，要求填好后任意两行互不等价且任意两列互不等价，两行或两列等价当且仅当对应位置完全相同，求方案数 首先考虑只有行不相同的答案 是$g(m)=(c^m)^{\underline{n}}$ 然后设答案为$f(m)$表示$m$列行列互不相等的答案 那么考虑枚举$g$的列有$i$个等价类 $$ g(m)=\sum_{i=0}^{m}\begin {Bmatrix} m \\ i\end {Bmatrix}f(i) $$ 根据斯特林反演 得到 $$ f(m)=\sum_{i=0}^m(-1)^{m-i}\begin{bmatrix}m\\i\end{bmatrix}g(i) $$