Alioth_ 的博客

Alioth_ 的博客

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

posted on 2019-06-22 08:47:57 | under 知识点 |

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