NOIP 提高组初赛 · NOIP 2007 提高组初赛试题 第 21 题

给定 $n$ 个有标号的球，标号依次为 $1,2,\dots,n$。将这 $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=7,r=4$ 时，$S(7,4)=$ _____________。

这题考第二类斯特林数，核心是递推：S(n,k)=S(n-1,k-1)+k×S(n-1,k)。拿到题别急着套公式，先想清楚‘多一个球怎么放’：要么单独成盒，要么插进已有r个盒子里，两种情况加起来就是递推式。

学生最容易把‘相同盒子’看成‘不同盒子’，顺手用组合数C(n,r)或者第一类斯特林数去凑，结果完全跑偏。还有不少人死记硬背递推式却不懂物理意义，导致计算时把k乘错位置，或者把S(6,3)和S(6,4)的值记混。另外，题目强调‘不允许空盒’，如果误以为可以有空盒，就会多算一堆情况，比如把单球成盒的情况漏掉或重复。

这道题考查的是第二类斯特林数，也就是把n个有标号球放入r个相同盒子且不允许空盒的方法数。很多同学看到‘相同盒子’和‘有标号球’就慌，其实这就是第二类斯特林数的标准定义，记作S(n,r)。

命题人特别喜欢在这种概念题里挖坑：一是混淆‘相同盒子’和‘不同盒子’，二是把递推式记错符号，三是忽略‘非空’条件。这道题给的是S(7,4)，数据不算大，但直接硬算容易出错，必须用递推。

递推式怎么来的？想象现在有n-1个球已经分好r个非空盒，再加第n个球。

• 情况1：第n个球单独成一个新的空盒。因为盒子相同，只要从r个盒子里挑一个‘原来有球’的盒子，把第n个球放过去，就变成r个盒子里有n个球。这对应S(n-1,r-1)。
• 情况2：第n个球放进已有的r个盒子里。每个已有球的盒子里都能放，共r种选择，所以是r×S(n-1,r)。

两种情况互斥且覆盖所有可能，于是S(n,r)=S(n-1,r-1)+r×S(n-1,r)。

现在代入n=7,r=4： S(7,4)=S(6,3)+4×S(6,4)。

我们需要S(6,3)和S(6,4)。 先算S(6,3)=S(5,2)+3×S(5,3)。 S(5,2)=S(4,1)+2×S(4,2)。S(4,1)=1（4球1盒只有1种），S(4,2)=7（题中已给）。所以S(5,2)=1+14=15。 S(5,3)=S(4,2)+3×S(4,3)。S(4,2)=7，S(4,3)=6（4球3盒：每盒至少一球，只能是2+1+1的分配，选哪两球同盒C(4,2)=6）。所以S(5,3)=7+18=25。 于是S(6,3)=15+3×25=15+75=90。

再算S(6,4)=S(5,3)+4×S(5,4)。 S(5,4)=S(4,3)+4×S(4,4)。S(4,3)=6，S(4,4)=1。所以S(5,4)=6+4=10。 于是S(6,4)=25+4×10=25+40=65。

最后S(7,4)=90+4×65=90+260=350。

易错点再强调一遍：别把S(6,3)和S(6,4)记反，也别把递推式里的r写成n-1。另外，题目要求‘不允许空盒’，如果误以为可以有空盒，就会把S(n,r-1)那部分多算进去，结果肯定不对。

从考频看，第二类斯特林数在NOIP提高组初赛里出现过7次，属于中等偏上频率的考点，尤其近几年计数题越来越喜欢结合递推和组合意义，比如2023、2024年都考了类似结构。这类题往往不考死记硬背，而是考你对‘多一个元素怎么放’的直觉。

预测的话，未来命题大概率会继续在‘相同盒子+有标号球’这个组合上玩花样，比如改成r个不同盒子（那就变成r!×S(n,r)），或者加限制条件（如某两个球必须同盒）。但核心还是递推式，只要抓住‘单独成盒’和‘插入已有盒’两种情形，基本就不会翻车。