第一类斯特林数 $\begin{bmatrix}n\\ k\end{bmatrix}$ 表示将 $n$ 个不同元素构成 $m$ 个圆排列的数目。

$$\begin{bmatrix}n\\ k\end{bmatrix}=\begin{bmatrix}n-1\\ k-1\end{bmatrix}+(n-1)\begin{bmatrix}n-1\\ k\end{bmatrix}\tag{1}$$

考虑新加入的数 $n$，要么单独成环，要么插入到其他环中，其中插入方式有 $n-1$ 种。

$$x^{\overline n}=\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i\tag{2}$$

其中 $x^{\overline n}$ 表示上升幂。

考虑归纳证明，有

$$x^{\overline {n+1}}=x^{\overline n}(x+n)=(x+n)\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}x^i=\sum_{i=0}^{n+1} \left(\begin{bmatrix}n\\ i-1\end{bmatrix}+n\begin{bmatrix}n\\ i\end{bmatrix}\right)x^i=\sum_{i=0}^{n+1} \begin{bmatrix}n+1\\ i\end{bmatrix}x^i$$

$$x^{\underline n}=\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}(-1)^{n-i}x^i\tag{3}$$

其中 $x^{\underline n}$ 表示下降幂。

考虑归纳证明，有

$$x^{\underline {n+1}}=x^{\underline n}(x-n)=(x-n)\sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}(-1)^{n-i}x^i=\sum_{i=0}^{n+1} \left(-\begin{bmatrix}n\\ i-1\end{bmatrix}-n\begin{bmatrix}n\\ i\end{bmatrix}\right)(-1)^{n-i}x^i=\sum_{i=0}^{n+1} \begin{bmatrix}n+1\\ i\end{bmatrix}(-1)^{n+1-i}x^i$$

洛谷p5408

$$\begin{bmatrix}n\\ i\end{bmatrix}(0\le i\le n)$$