跳转至

斯特林数

Stirling 数(子集划分)

根据例题来讲解:
(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^3S_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}

评论