NOIP 普及组初赛 · NOIP 2007 普及组初赛试题 第 21 题

（子集划分）将 $n$ 个数 $(1,2,\dots,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)$，再分这两种情况对原固定的数进行分析。）

别直接硬算，这道题的核心是第二类斯特林数的递推：考虑第 n 个数，要么它单独成组（剩下 n-1 个数分 r-1 组），要么它加入已有的 r 组之一（剩下 n-1 个数分 r 组）。抓住这个逻辑，从 S(4,2) 和 S(4,3) 往上推几步就能秒杀。

最容易栽跟头的地方是递推公式里那个乘数 r。很多学生看到 S(n-1,r-1) + S(n-1,r) 就以为直接相加，忘了后面那项必须乘以 r，因为第 n 个数可以放进 r 个不同的子集里，每种放法都算一种新划分。另外，计算 S(5,3) 时容易把 7+18 算错，或者在 S(6,3) 时把 15+75 算成 90 以外的数，再就是边界条件 S(n,n)=1 记不住，导致递推链条从第一步就断了。

这道题考的是组合数学里的第二类斯特林数，记作 S(n,r)，它的定义就是把 n 个不同元素划分成 r 个非空子集的方案数。题目给出的例子 S(4,2)=7 就是典型的划分问题，比如把 4 个数分成 2 组，可以是 1 个单元素组和 3 个元素组，或者 2 个 2 元素组，加起来正好 7 种。现在要算 S(6,3)，直接把 6 个数全摆出来数太容易漏，得用递推。递推公式是 S(n,r) = S(n-1,r-1) + r × S(n-1,r)。这个公式怎么来的？想象第 n 个数，它只有两种命运：要么它自己单独成一组，那剩下的 n-1 个数就得凑够 r-1 组，方案数就是 S(n-1,r-1)；要么它不单独成组，而是加入已有的 r 组里的某一组，这时候剩下的 n-1 个数已经分好了 r 组，而第 n 个数有 r 种选择（放进哪一组都算不同的划分），所以这部分贡献是 r × S(n-1,r)。这两个情况互斥且覆盖所有可能，加起来就是总数。

既然公式清楚了，咱们就按提示，从已知的小数据开始往上推。题目给了 S(4,2)=7，那 S(4,3) 呢？用公式：S(4,3) = S(3,2) + 3 × S(3,3)。S(3,3) 很简单，3 个数分 3 组，每组一个，只有 1 种，即 S(3,3)=1。S(3,2) 可以算一下：S(3,2) = S(2,1) + 2 × S(2,2)。S(2,1)=1，S(2,2)=1，所以 S(3,2)=1+2=3。代回去，S(4,3)=3+3×1=6。现在有了 S(4,2) 和 S(4,3)，就能算 S(5,2) 和 S(5,3) 了。S(5,2) = S(4,1) + 2 × S(4,2)。S(4,1) 是 4 个数全放一组，只有 1 种，所以 S(5,2)=1+2×7=15。S(5,3) = S(4,2) + 3 × S(4,3) = 7 + 3×6 = 25。最后一步，目标 S(6,3) = S(5,2) + 3 × S(5,3) = 15 + 3×25 = 15 + 75 = 90。答案就是 90。

这里特别要提醒的是，递推公式里那个乘数 r 绝对不能丢。很多同学会惯性思维，看到加法就以为两项直接加，结果 S(6,3) 算成 15+25=40 之类的，那就完全错了。另外，计算过程中 S(5,3) 的 7+18 如果按错顺序或者乘法做加法，也会得到错误中间值。还有，S(n,n) 永远等于 1，这是递推的基石，如果记不住，S(3,3) 算成 0 或者别的，后面全崩。从命题角度看，这类题喜欢考你递推公式的变形应用，或者给你中间某一步的值让你反推，本质还是考察对“第 n 个元素单独成组”和“加入已有组”这两种情形的分类讨论能力。考频上看，计数原理在历年 CSP 和 NOIP 初赛里出现非常频繁，题库里 36 道题，2019 年突然来了 6 题，2024、2025 年各 5 题，说明这个知识点是高频考点，而且出题人很爱在递推细节里挖坑，比如乘数 r 的位置、边界条件的取值。基于这个趋势，未来大概率还会出类似的斯特林数递推题，或者把递推公式稍微包装一下，比如让你求 S(n,r) 的某种线性组合，或者给定 S(n-1,r-1) 和 S(n-1,r) 让你求 S(n,r) 的表达式。虽然目前数据不足以精确预测下一年的题目形式，但可以肯定的是，只要掌握了递推公式和分类思想，这类题基本就是送分题。所以，拿到题先别慌，想想第 n 个数在哪，按公式一步步推，细心算乘法，就能稳稳拿到这 90 分。