第一类斯特林数 $\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}$ 表示上升幂。

考虑归纳证明，有

$$ \begin{equation}\begin{split} 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 \end{split}\end{equation} $$ ==== 运算 ==== === 第一类斯特林数$\cdot$行 ===

洛谷p5408

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