两个递推的初始条件都是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)