第一类斯特林数

定义

$S_1(n,m)$表示$n$个元素，形成$m$个环的方案数，记作$\begin{bmatrix}n\\m\end{bmatrix}$。

其中每个元素是不同的，每个环是相同的。

 

递推公式

从实际含义上去考虑，第一类斯特林数递推公式为：

$\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-1\\m-1\end{bmatrix}$。

接在原来的一个环中一个元素的后面，方案数即$(n-1)*\begin{bmatrix}n-1\\m\end{bmatrix}$

 

一些简单性质

1.第一类斯特林数第$n$行的和为$n!$，即

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

考虑$n!$，表示$n$个元素的排列。建立$i \rightarrow p_i$的置换，显然会形成若干个环。

这与第一类斯特林数在第$n$行的的一种方案是一一对应的。

 

2.第一类斯特林数的一个用途是用通常幂表示上升幂，有

$x^{\overline n}=\sum \limits_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}x^i$

证明可以通过数学归纳法。

当$n=0$，原式$x^{\overline 0}=1=x^0$显然成立。

$x^{\overline n}=\sum \limits_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}x^i$

设原式在$n$时成立，只要证原式在$n+1$时也成立。

左右同乘$x+n$可得，$x^{\overline n+1}=x^{\overline n}*(x+n)$

$=\sum \limits_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}x^i*(x+n)$

$=\sum \limits_{i=0}^{n+1} \begin{bmatrix}n+1\\i\end{bmatrix}x^i$

 

3.对于通常幂，显然有$x^n=(-x)^n*(-1)^n$

对于下降幂和上升幂，同样有

$x^{\overline n}=(-x)^{\underline n}*(-1)^n$

$x^{\underline n}=(-x)^{\overline n}*(-1)^n$

将该式代入$x^{\overline n}=\sum \limits_{i=0}^n \begin{bmatrix}n\\i\end{bmatrix}x^i$

整理可得用通常幂表示下降幂的式子

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

 

求法

对于同一行第一类斯特林数的求解，可以直接利用第二个性质。

对$x^{\overline n}$做分治$fft$即可。

这个做法的复杂度是$O(nlog^2n)$的，可以用一些做法优化到一个log，待补。

 

 

 

第二类斯特林数

定义

$S_2(n,m)$表示$n$个元素，形成$m$个集合的方案数，记作$\begin{Bmatrix}n\\m\end{Bmatrix}$。

其中每个元素是不同的，每个集合是相同的。

 

递推公式

从实际含义上去考虑，第二类斯特林数递推公式为：

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

分别对应形成新的集合，方案数即$\begin{Bmatrix}n-1\\m-1\end{Bmatrix}$。

加入任意一个已有的集合，方案数即$m*\begin{Bmatrix}n-1\\m\end{Bmatrix}$

 

一些简单性质

1.第二类斯特林数的一个用途是用下降幂表示通常幂，有

$x^n=\sum \limits_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix}x^{\underline i}$

证明(1) 通过数学归纳法，与第一类斯特林数的证明类似，这里略过。

证明(2) 考虑$x^n$的实际含义，将$n$个不同元素放入$x$个不同集合中。

有$x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}\binom{x}{i} i!$

因为第二类斯特林数中的集合是无差别的，所以最后应当乘上$i!$。

整理上式可得要证的式子，实际上这个含有组合数的公式也是有时候要化成的形式。

 

2.同样代入负数形式，可得用上升幂表示通常幂的形式，即

$x^n=\sum \limits_{i=0}^n \begin{Bmatrix}n\\i\end{Bmatrix}(-1)^{n-i}x^{\overline i}$。

 

 

求法

单点求解第二类斯特林数存在一种$O(n)$的容斥方法。

设共有n个不同元素，为了方便，设共有m个不同集合。

设$g_x$表示恰好$x$个集合为空的方案数。

设$f_x$表示钦定$x$个集合为空的方案数，有

$f_x=\binom{m}{x}(m-x)^n$

$f_x=\sum \limits_{i=x}^{m}\binom{i}{x}g_x$

由二项式反演得$g_x=\sum \limits_{i=x}^{m}(-1)^{i-x}\binom{x}{i}f_x$。

代入$x=0$，可得

$\begin{Bmatrix}n\\m\end{Bmatrix}=\frac{1}{m!}*\sum \limits_{i=0}^{m}(-1)^i\binom{m}{i}(m-i)^n$

拆一拆就发现这个玩意是个卷积式，所以求同一行第二类斯特林数可以做到$O(nlogn)$。