第一类斯特林数
\[\large \begin{bmatrix}n\\ m\end{bmatrix}=(n-1)\begin{bmatrix}n-1\\ m\end{bmatrix}+\begin{bmatrix}n-1\\ m-1\end{bmatrix}
\]
其为将 \(n\) 个元素划分为 \(m\) 个轮换的方案数。递推式即为考虑最后一个元素是否作为一个新轮换。
\(\begin{bmatrix}n\\ i\end{bmatrix}\) 是恰好有 \(i\) 个轮换的排列数，因此有：
\[\large \sum_{i=0}^n \begin{bmatrix}n\\ i\end{bmatrix}=n!
\]
与幂的关系：
\[\large x^{\overline{n}}=\sum_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i
\]
归纳法证明：
\[\large\begin{aligned}
x^{\overline{n-1}}&=\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\ i\end{bmatrix}x^i (x+n-1)x^{\overline{n-1}}&=(x+n-1)\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\ i\end{bmatrix}x^i x^{\overline{n}}&=(n-1)\sum_{i=0}^{n-1}\begin{bmatrix}n-1\\ i\end{bmatrix}x^i+\sum_{i=1}^{n}\begin{bmatrix}n-1\\ i-1\end{bmatrix}x^i x^{\overline{n}}&=\sum_{i=0}^{n}\begin{bmatrix}n\\ i\end{bmatrix}x^i \\end{aligned}
\]
考虑将 \(x^{\overline{n}} = (-1)^n(-x)^{\underline{n}}\) 代入到 \(x^{\overline{n}}=\sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}x^i\) 中，并将 \(x\) 换为 \(-x\)，得：
\[\large\begin{aligned}
(-1)^nx^{\underline{n}} &= \sum\limits_{i=0}^n\begin{bmatrix}n\\ i\end{bmatrix}(-x)^i x^{\underline{n}} &= \sum\limits_{i=0}^n(-1)^{n-i}\begin{bmatrix}n\\ i\end{bmatrix}x^i \end{aligned}
\]
第二类斯特林数
\[\large \begin{Bmatrix} n \\m \end{Bmatrix}=m\begin{Bmatrix} n-1 \\m \end{Bmatrix}+\begin{Bmatrix} n-1 \\m-1 \end{Bmatrix}
\]
其为将 \(n\) 个元素划分为 \(m\) 个子集的方案数。递推式即为考虑最后一个元素是否作为一个新子集。
与幂的关系：
\[\large x^n = \sum_{i=0}^n \begin{Bmatrix} n \\i \end{Bmatrix} x^{\underline{i}}
\]
归纳法证明：
\[\large\begin{aligned}
\large x^{n-1} &= \sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} x^{\underline{i}} \large x^n &= x\sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} x^{\underline{i}} \large x^n &= \sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} ix^{\underline{i}} +\sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} (x-i)x^{\underline{i}} \large x^n &= \sum_{i=0}^{n-1} \begin{Bmatrix} n-1 \\i \end{Bmatrix} ix^{\underline{i}} +\sum_{i=1}^n \begin{Bmatrix} n-1 \\i-1 \end{Bmatrix} x^{\underline{i}} \large x^n &= \sum_{i=0}^n \begin{Bmatrix} n \\i \end{Bmatrix} x^{\underline{i}} \\end{aligned}
\]
考虑将 \(x^{\underline{n}} = (-1)^n(-x)^{\overline{n}}\) 代入到 \(x^n = \sum\limits_{i=0}^n \begin{Bmatrix} n \\i \end{Bmatrix} x^{\underline{i}}\) 中，并将 \(x\) 换为 \(-x\)，得：
\[\large\begin{aligned}
\large (-x)^n &= \sum_{i=0}^n (-1)^i\begin{Bmatrix} n \\i \end{Bmatrix} x^{\overline{i}} \large x^n &= \sum_{i=0}^n (-1)^{n-i}\begin{Bmatrix} n \\i \end{Bmatrix} x^{\overline{i}} \\end{aligned}
\]
联系
反转公式：
\[\large\begin{aligned}
\sum_i(-1)^{n-i}\begin{bmatrix}n\\ i\end{bmatrix}\begin{Bmatrix}i\\ m\end{Bmatrix}=[n=m] \sum_i(-1)^{n-i}\begin{Bmatrix}n\\ i\end{Bmatrix}\begin{bmatrix}i\\ m\end{bmatrix}=[n=m] \end{aligned}
\]
求法
斯特林数
原文：https://www.cnblogs.com/lhm-/p/14191011.html
