上升幂和下降幂

\[x^{\underline{n}}=x(x-1)\cdots (x-n+1)\\x^{\overline {n}}=x(x+1)\cdots (x+n-1) \]

第一类斯特林数

\[\begin{bmatrix}n\\k\end{bmatrix}= \begin{bmatrix}n-1\\k-1\end{bmatrix}+ (n-1)\begin{bmatrix}n-1\\k\end{bmatrix} \]

第一类斯特林数表示 \(n\) 个数形成 \(m\) 个非空轮换的方案数。

当 \(n<k\) 时，\(\begin{bmatrix}n\\k\end{bmatrix} =0\) 。

当 \(n=k\) 或 \(k=1\) 时，\(\begin{bmatrix}n\\k\end{bmatrix}=1\) 。

当 \(k=0\) 且 \(n\ne 0\) 时，\(\begin{bmatrix}n\\k\end{bmatrix}=0\) 。特别地，\(\begin{bmatrix}0\\0\end{bmatrix}=1\) 。

第二类斯特林数

\[\begin{Bmatrix}n\\k\end{Bmatrix} =\begin{Bmatrix}n-1\\k-1\end{Bmatrix}+ k\begin{Bmatrix}n\\k\end{Bmatrix} \]

第二类斯特林数表示 \(n\) 个数形成 \(m\) 个非空集合的方案数。

当 \(n < k\) 时，\(\begin{Bmatrix}n\\k\end{Bmatrix}=0\) 。

当 \(n=k\) 或 \(k=1\) 时，\(\begin{Bmatrix}n\\k\end{Bmatrix}=1\) 。

当 \(k=0\) 且 \(n\ne 0\) 时，\(\begin{Bmatrix}n\\k\end{Bmatrix}=0\) 。特别地，\(\begin{Bmatrix}0\\0\end{Bmatrix}=1\) 。

斯特林数与幂

第一类斯特林数通常用于实现上升幂转普通幂

\[x^{\overline{n}}=\sum_{k=0}^{n}\begin{bmatrix}n\\k\end{bmatrix} x^{k} \]

可以使用递归来证明：

\[\ \ \ \ \sum_{k=0}^{n}\begin{bmatrix}n\\k\end{bmatrix} x^{k}\\ = \sum_{k=0}^{n}\begin{bmatrix}n-1\\k-1\end{bmatrix}x^{k} +(n-1)\sum_{k=0}^{n}\begin{bmatrix}n-1\\k\end{bmatrix} x^{k}\\ = \sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k-1\end{bmatrix}x^{k} +(n-1)\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix} x^{k}\\ = x\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k-1\end{bmatrix}x^{k-1} +(n-1)\sum_{k=0}^{n-1}\begin{bmatrix}n-1\\k\end{bmatrix} x^{k} \]

第二类斯特林数通常用于实现普通幂转下降幂

\[x^n=\sum_{k=0}^{n}\begin{Bmatrix}n\\k\end{Bmatrix}x^{\underline{k}} \]