斯特林数

斯特林数有两族，回答的是不同的计数问题。第二类斯特林数 ${\binom{n}{k}}$ 把 $n$ 个带标签的元素分成 $k$ 个非空、无标签组；第一类的无符号斯特林数 $[\binom{n}{k}]$ 数 $n$ 个元素的排列中恰有 $k$ 个循环。两者下标相同也不能互换。

四个人分成两组

四个人分成两个都非空、组名不区分的团队，共有 ${\binom{4}{2}} = 7$ 种：把一个人单独成组有 4 种，把两人和两人分组有 $(\binom{4}{2}) / 2 = 3$ 种，合计 7。若团队叫“甲”和“乙”，每种无标签分法可给两个组分配名字，有 $2! {\binom{4}{2}} = 14$ 种；这也是从四人到两种组名的满射数。

把新元素放进去的递推

考虑编号 $n$ 的新元素。若它单独成组，余下 $n - 1$ 人分成 $k - 1$ 组；若它加入已有组，余下先分成 $k$ 组，再在 $k$ 组里选一组。因此 ${\binom{n}{k}} = {\binom{n - 1}{k - 1}} + k {\binom{n - 1}{k}} .$ 初值 ${\binom{0}{0}} = 1$ ，对 $n > 0$ 有 ${\binom{n}{0}} = 0$ 。代入 $n = 4, k = 2$ 得 ${\binom{3}{1}} + 2 {\binom{3}{2}} = 1 + 2 \cdot 3 = 7$ 。另从满射的容斥数法有 $k! {\binom{n}{k}} = \sum_{j = 0}^{k} (- 1)^{j} (\binom{k}{j}) (k - j)^{n}$ ；两条公式可相互验算。

第一类数则按新元素是否独立成一个循环分类：独立时有 $[\binom{n - 1}{k - 1}]$ 种；否则把它插入已有排列的 $n - 1$ 个循环边之后，有 $(n - 1) [\binom{n - 1}{k}]$ 种。因此 $[\binom{n}{k}] = [\binom{n - 1}{k - 1}] + (n - 1) [\binom{n - 1}{k}]$ 。例如 $[\binom{3}{2}] = 3$ ，对应三个选择哪两人组成二循环。文献中第一类还常采用带符号约定，使用前须核对括号形状和符号。

参考资料与相关词条

MIT 18.212：斯特林数讲义。
相关：排列与组合、容斥原理、可重复排列与组合。