第二类斯特林数：把不同球分进相同盒子

这是什么？

第二类斯特林数（Stirling numbers of the second kind）是组合数学中一个非常实用的工具。它要解决的问题很简单：假设你有 n 个不同的球（比如红球、蓝球、黄球……每颗球都不一样），想把它们放进 m 个相同的盒子里，每个盒子不能是空的（至少一个球），问一共有多少种不同的分法？注意，盒子是相同的，意味着盒子没有标签，交换两个盒子的位置不算新方案。

这个数记作 S(n, m)（有时也写作 {n \choose m} 或 S(n, m)）。它看起来就像把一堆朋友分到几个小组（小组没有名称），或者把不同口味的糖果分到几个相同的盘子里，每个盘子至少有一颗糖。

关键概念拆解

1. 盒子相同 vs 盒子不同

很多同学会混淆“盒子相同”和“盒子不同”。咱们举个例子：

• 如果盒子不同（比如盒子A和盒子B），那么把红球放A、蓝球放B，和红球放B、蓝球放A，是两种不同的分法。
• 如果盒子相同，那么这两种分法其实是一样的，因为你交换两个盒子的位置，看起来还是同样的分组。

结论： 盒子相同会让方案数大大减少。第二类斯特林数专门处理盒子相同的情况。

2. 从一个小例子开始

考试时，有3个不同的小球（红、黄、蓝），想分到2个相同的盒子，每个盒子不能空。可能的分法只有以下三种：

• 盒子1：红、黄 ；盒子2：蓝
• 盒子1：红、蓝 ；盒子2：黄
• 盒子1：黄、蓝 ；盒子2：红

注意，我们不会说“盒子1里有红和黄、盒子2里有蓝”和“盒子1里有蓝、盒子2里有红和黄”是两种，因为盒子没有标签，两个盒子交换后是一样的。

所以 S(3,2) = 3。

3. 递推公式的直观理解

第二类斯特林数有一个非常重要的递推公式：

S(n, m) = S(n-1, m-1) + m × S(n-1, m)

这个公式怎么来的？想象你手头有 n-1 个球已经分好了，现在新来一个球（第 n 个球）。这个新球有两种选择：

• 自己开一个新盒子： 相当于前 n-1 个球已经分好了 m-1 个盒子（每个盒子非空），新球独自占一个盒子，方案数为 S(n-1, m-1)。
• 放进已有的某个盒子里： 前 n-1 个球已经分好了 m 个盒子（每个盒子非空），新球可以放进这 m 个盒子中的任意一个。注意，因为盒子相同，但盒子里的内容不同，所以放进不同盒子会产生不同方案，因此方案数为 m × S(n-1, m)。

把两种选择加起来，就得到了递推公式。

举个例子验证： 计算 S(4,2)

根据递推： S(4,2) = S(3,1) + 2 × S(3,2) S(3,1) = 1（3个球放1个盒子只有一种方法） S(3,2) = 3 所以 S(4,2) = 1 + 2×3 = 7。

你可以自己枚举一下4个不同球（比如红、黄、蓝、绿）放入2个相同盒子，看看是不是7种。

4. 边界条件（基础情况）

使用递推必须知道边界值：

• S(0,0) = 1（0个球放0个盒子，只有一种空方案）
• S(n,0) = 0（当 n>0 时，有球却无盒子，不可能）
• S(0,m) = 0（当 m>0 时，没球但有盒子，不可能）
• S(n,m) = 0 当 m > n（盒子比球多，每个盒子非空不可能）
• S(n,1) = 1（所有球放一个盒子）
• S(n,n) = 1（每个球单独一个盒子）

这些边界在编程时要注意初始化。

新手容易犯的错误

错误1：数组下标越界

递推时，dp[i][j] 只用到了 dp[i-1][j-1] 和 dp[i-1][j]，因此 j 的范围要注意：j 最大不能超过 i，且 j 不能为0（因为公式中 j=0 时 dp[i-1][j] 可能没有定义）。通常我们在循环里加上条件 j <= i 并且从 j=1 开始。

错误2：忘记取模或溢出

当 n 和 m 比较大时，S(n,m) 会增长极快（比如 S(20,10) 已经超过 10^10）。C++ 的 long long 只能存到约 9e18，所以对于较大的 n（比如 n>20），要使用高精度或者对一个大数取模（比如 mod 1e9+7）。本文示例用 long long，只适合 n ≤ 20 左右。

错误3：混淆组合数顺序

第二类斯特林数读作 “n 选 m”，但注意递推公式是 S(n-1,m-1) + m * S(n-1,m)，不要和组合数的递推 (C(n,k)=C(n-1,k-1)+C(n-1,k)) 搞混。组合数公式里系数是 1，这里第二项有 m。

完整可运行的 C++ 示例

下面代码可以计算从 0 到 n 的所有 S(i,j) 并打印，同时给出一个查询例子。

#include <iostream>
#include <vector>
using namespace std;

// 计算第二类斯特林数表，返回 dp[n][k] 即 S(n,k)
vector<vector<long long>> stirling2(int n, int k) {
    // dp[i][j] 表示 S(i,j)，初始化为0
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));
    dp[0][0] = 1; // S(0,0)=1
    for (int i = 1; i <= n; i++) {          // i 表示球的数量
        for (int j = 1; j <= k && j <= i; j++) { // j 表示盒子数量，不能超过球数
            // 递推公式：新球单独开盒子 + 放进已有m个盒子
            dp[i][j] = dp[i - 1][j - 1] + j * dp[i - 1][j];
        }
    }
    return dp;
}

int main() {
    int n = 5;          // 球的总数
    int m = 2;          // 盒子数
    auto table = stirling2(n, m);
    cout << "S(" << n << "," << m << ") = " << table[n][m] << endl; // 输出15

    // 也可以打印整张表（只打印有效部分）
    cout << "\n第二类斯特林数表 S(i,j) (i=0.." << n << ", j=0.." << m << "):\n";
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m && j <= i; j++) {
            cout << "S(" << i << "," << j << ")=" << table[i][j] << "  ";
        }
        cout << endl;
    }
    return 0;
}

输出结果：

S(5,2) = 15

第二类斯特林数表 S(i,j) (i=0..5, j=0..2):
S(0,0)=1  
S(1,0)=0  S(1,1)=1  
S(2,0)=0  S(2,1)=1  S(2,2)=1  
S(3,0)=0  S(3,1)=1  S(3,2)=3  
S(4,0)=0  S(4,1)=1  S(4,2)=7  
S(5,0)=0  S(5,1)=1  S(5,2)=15  

深入理解：生活中的例子

• 小组作业分组： 班上10个同学（不同人）分成3个小组（小组没有名字，只算哪几个人在一组），每个小组至少1人，有多少种分法？这就是 S(10,3)。
• 糖果分配： 有6种不同口味的糖果，装进4个相同的礼品袋，每个袋子至少有一种糖。分法数就是 S(6,4)。
• 游戏角色分组： 在游戏中给5个不同英雄（角色）分配3个相同的队伍，每个队伍至少一个英雄，有多少种组队方式？答案是 S(5,3)=25。

相关知识点指引

• 第一类斯特林数：处理把 n 个不同元素排成 m 个 环（循环排列）的方法数，记作 s(n,m) 或 c(n,m)。它们与第二类斯特林数有对称关系。
• 贝尔数：B(n) = S(n,1) + S(n,2) + ... + S(n,n)，表示把 n 个不同元素划分成任意多个非空子集的方法总数（即可以分任意个盒子，盒子不限数量）。
• 组合数 C(n,k)：从 n 个不同元素中选 k 个（不考虑顺序）。第二类斯特林数有时会用组合数符号表达，但含义完全不同。
• 递推与动态规划：这道题的递推本质是动态规划（DP），类似 0-1 背包的递推思想，是学习 DP 的经典入门题。

掌握了第二类斯特林数，你在面对“分组”问题时就能多一个有力的武器！下次再遇到分糖果、分小组，就可以拿出公式和代码轻松解决啦。