形式陈述

第二类 Stirling 数 $\left\{\begin{smallmatrix}n\\k\end{smallmatrix}\right\}$$\left\{\begin{array}{c}n\\ k\end{array}\right\}$ 计数把 $n$$n$ 元有标号集合划分为 $k$$k$ 个非空无标号块的方法。它满足

$$ \left\{\begin{matrix}n\\k\end{matrix}\right\}=k\left\{\begin{matrix}n-1\\k\end{matrix}\right\}+\left\{\begin{matrix}n-1\\k-1\end{matrix}\right\}, $$$$\left\{\begin{array}{c}n\\ k\end{array}\right\}=k\left\{\begin{array}{c}n-1\\ k\end{array}\right\}+\left\{\begin{array}{c}n-1\\ k-1\end{array}\right\},$$

边界为 $\{0\brace0\}=1$$\{\genfrac{}{}{0ex}{}{\{0}{0\}=1}\}$、$\{n\brace0\}=0$$\{\genfrac{}{}{0ex}{}{\{n}{0\}=0}\}$（$n>0$$n>0$）。

直觉

观察最后一个元素：它要么加入已有的 $k$$k$ 个块之一，要么单独形成新块。

例子与边界

$\{3\brace2\}=3$$\{\genfrac{}{}{0ex}{}{\{3}{2\}=3}\}$，对应三种“一个单元素块加一个二元素块”的划分。它与第一类 Stirling 数不同，后者计数排列的循环。满射数为 $k!\{n\brace k\}$$\{\genfrac{}{}{0ex}{}{k!\{n}{k\}}\}$，因为给无标号块再安排 $k$$k$ 个目标标签。

推论与应用

第二类 Stirling 数用于集合划分、Bell 数、满射计数、有限差分和矩展开。

参考资料

• Richard P. Stanley, Enumerative Combinatorics, Vol. 1, 2nd ed., Cambridge University Press, 2011，Chs. 1–4。
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009，Parts A–B。