

斯特林数

第一类斯特林数（Stirling Number）

设有多项式 $x(x-1)(x-2) \cdots (x-n+1)$ ，它的展开式形如 $s_nx^n - s_{n-1}x^{n-1}+s_{n-2}x^{n-2}-\cdots$ 。

不考虑各项系数的符号，将 $x^r$ 的系数的绝对值记做 $s(n, r)$ ，称为第一类 Stirling 数。

$s(n, r)$ 也是把 $n$ 个不同的球排成 $r$ 个非空循环排列的方法数。

关于第一类斯特林数的性质可以阅读 Stirling Number of the First Kind 。

递推形式

$$s(n,r) = (n-1)s(n-1,r)+s(n-1,r-1),\ n > r \geq 1$$

考虑最后一个球，它可以单独构成一个非空循环排列，也可以插入到前面的某一个球的一侧。

若单独放，则有 $s(n-1,r-1)$ 种放法；若放在某个球的一侧，则有 $(n-1)s(n-1,r)$ 种放法。

第二类斯特林数（Stirling Number）

把 $n$ 个不同的球放到 $r$ 个相同的盒子里，假设没有空盒，则放球方案数记做 $S(n, r)$ ，称为第二类 Stirling 数。

关于第二类斯特林数的性质可以阅读 Stirling Number of the Second Kind 。

递推形式

$$S(n,r) = r S(n-1,r) + S(n-1,r-1),\ n > r \geq 1$$

考虑最后一个球，若它单独放一个盒子，有 $S(n-1,r-1)$ 种放法；若是和前面的某一个球放在同一个盒子里，则有 $r S(n-1,r)$ 种放法。

例题

（2007 普及）将 $n$ 个数 $（1，2，…，n）$ 分成 $r$ 个部分。每个部分至少一个数。将不同划分方法的总数记为 $S_n^r$ 。例如， $S_4^2=7$ ，这 7 种不同的划分方法依次为 $\{\ (1) , (234) \}\,\{\ (2) , (134) \}\,\{\ (3) , (124) \}\,\{\ (4) , (123) \}\,\{\ (12) , (34) \}\,\{\ (13) , (24) \}\,\{\ (14) , (23) \}$ 。当 $n=6，r=3$ 时， $S_6^3$ =（）

提示：先固定一个数，对于其余的 5 个数考虑 $S_5^3$ 与 $S_5^2$ ，再分这两种情况对原固定的数进行分析。

题解：在近几年算法竞赛中，递推算法越来越重要：

$$S_6^3=3 \times S_5^3 + S_5^2$$

$$S_5^3=3 \times S_4^3 + S_4^2$$

$$S_5^2=2 \times S_4^2 + S_4^1$$

第二类 stirling 数，显然拥有这样的性质：

$$S_n^m = m \times S_{n-1}^{m} + S_{n-1}^{m-1}$$

$$S_n^1 = 1,S_n^0 = 0,S_n^n = 1$$

而这些性质就可以总结成：

$$S_n^3 = \frac{1}{2} \times (3^{n-1}+1) - 2^{n-1}$$

习题

HDU3625

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论