用分圆桌的故事理解第一类斯特林数

你是不是想过这样的问题：班上有 N 个同学，要分成 M 个小组，每个小组的同学围成一个圆圈坐下（圆圈旋转后相同只算一种坐法），一共有多少种分法？这就是第一类斯特林数要解决的事情。它用符号 s(n, m) 表示，也叫“无符号第一类斯特林数”，专门用来计算“把 n 个不同的人排成 m 个非空圆桌”的方案数。

1. 先搞懂“圆排列”

在学第一类斯特林数之前，必须明白什么叫“圆排列”。
如果有 3 个人 A、B、C 坐在一张圆桌上，顺时针看座位顺序是 A→B→C，但旋转一下座位，变成 B→C→A，这其实还是同一种坐法（因为大家只是相对位置没变，绝对位置不重要）。
所以三个人围一桌，不同的坐法只有：

A 左边是 B，右边是 C（即顺时针 A-B-C）
A 左边是 C，右边是 B（即顺时针 A-C-B）

总共 2 种。计算方法是 (n-1)! = (3-1)! = 2。
如果只有 1 个人坐一桌，圆排列只有 1 种（一个人无所谓旋转）。
如果 2 个人坐一桌，两个人对面坐，旋转后还是相同，所以也只有 1 种（(2-1)! = 1）。

2. 第一类斯特林数的定义

s(n, m) 表示：把 n 个不同的人 放入 m 个相同的圆桌（圆桌之间没有区别，只关心哪些人坐一起，以及每个桌内的圆排列），每个圆桌至少坐一个人，一共有多少种方案。

例如：n=3, m=2，把 A、B、C 分成 2 个圆桌。
可能的方案（圆桌内顺序只考虑相对位置）：

一桌坐 {A, B}（圆排列只有 1 种，因为两人一桌只有一种相对顺序），另一桌坐 {C}（1 种）。
一桌坐 {A, C}，另一桌坐 {B}。
一桌坐 {B, C}，另一桌坐 {A}。

所以 s(3,2) = 3。

再比如 n=4, m=2，我们可以通过递推公式算出来 s(4,2)=11。
（后面会展示如何一步步计算）

3. 递推公式：新来一个人，怎么办？

第一类斯特林数有一个非常直观的递推公式：

s(n,m) = s(n-1, m-1) + (n-1) \times s(n-1, m)

故事版理解：
现在已经分好了 n-1 个人，要再加入第 n 个人（我们叫他“小明”）。小明有两种选择：

自己开一个新圆桌
这样原来的 n-1 个人已经组成了 m-1 个圆桌，小明单独一桌，变成 m 个桌。方案数就是 s(n-1, m-1)。
加入已有的某个圆桌
原来有 n-1 个人，分成了 m 个圆桌。小明可以插进任意一个圆桌里，并且他可以坐在任意一个人左边（因为圆排列中，插入到某个人左边就决定了新顺序）。
一共有 (n-1) 个“左边”位置（因为原来有 n-1 个人，每个人左边都可插入）。
所以方案数是 (n-1) × s(n-1, m)。

把这两种情况加起来，就是 s(n, m)。

边界条件：

s(0,0) = 1（0 个人 0 个桌，只有一种“什么都不做”的方案）。
s(n,0) = 0 当 n > 0（有人的话必须有桌子）。
s(0,m) = 0 当 m > 0（没人的话不可能有桌子）。
如果 m > n，s(n,m) = 0（人不够分那么多桌）。

4. 手动算一个例子（n=4, m=2）

我们用递推从底层开始算。

先准备一些基础值：

s(1,1) = s(0,0) + 0 * s(0,1) = 1 + 0 = 1（一个人一桌，只有1种）
s(2,1) = s(1,0) + 1 * s(1,1) = 0 + 1×1 = 1（两个人一桌，圆排列只有1种）
s(2,2) = s(1,1) + 1 * s(1,2) = 1 + 0 = 1（两人各自一桌）
s(3,1) = s(2,0) + 2 * s(2,1) = 0 + 2×1 = 2（三人一桌，圆排列有2种）
s(3,2) = s(2,1) + 2 * s(2,2) = 1 + 2×1 = 3（之前算过）
s(3,3) = s(2,2) + 2 * s(2,3) = 1 + 0 = 1（三人各一桌，只有1种）

现在算 s(4,2)： s(4,2) = s(3,1) + 3 * s(3,2) = 2 + 3×3 = 11。

所以把 4 个不同的人分成 2 个圆桌，有 11 种不同坐法。你可以试着列举验证一下，会很有趣。

5. 用 C++ 实现快速计算

动态规划是计算斯特林数最常用的方法。我们用一个二维数组 dp[i][j] 表示 s(i, j)。按递推公式从小往大填表即可。

注意：斯特林数增长非常快，要使用 long long（或更大类型如 unsigned long long），避免溢出。

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

// 函数：计算第一类斯特林数表，返回整个 dp 表（0..n, 0..k）
vector<vector<long long>> stirling1(int n, int k) {
    // dp[i][j] 表示 s(i, j)
    vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 0));

    dp[0][0] = 1;  // 0个人0个圆桌，一种方案

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k && j <= i; j++) {
            // 递推公式：s(i,j) = s(i-1,j-1) + (i-1) * s(i-1,j)
            dp[i][j] = dp[i - 1][j - 1] + (i - 1) * dp[i - 1][j];
        }
    }
    return dp;
}

int main() {
    // 计算 n=5, k=3 的情况
    auto res = stirling1(5, 3);
    cout << "s(5,3) = " << res[5][3] << endl;  // 应该输出 35

    // 也可以输出一个小的表格看看
    cout << "\n第一类斯特林数表 (n=0..5, m=0..5):\n";
    auto full = stirling1(5, 5);
    for (int n = 0; n <= 5; n++) {
        for (int m = 0; m <= n; m++) {
            cout << full[n][m] << "\t";
        }
        cout << endl;
    }
    return 0;
}

运行结果：

s(5,3) = 35

第一类斯特林数表 (n=0..5, m=0..5):
1	
0	1	
0	1	1	
0	2	3	1	
0	6	11	6	1	
0	24	50	35	10	1

注意表格中每行第一个是 s(n,0)=0 (n>0)，第六行（n=5）的前几个数是 0, 24, 50, 35, 10, 1。

6. 常见错误与提醒

错误	说明	正确做法
忘记初始化 `dp[0][0]=1`	没有起点，后面全错	必须一开始设置边界
循环时 `j` 没有限制 `j <= i`	当 `j > i` 时 `s(i,j)=0`，但计算 `dp[i-1][j]` 会越界	用 `for (int j=1; j<=k && j<=i; j++)`
用 `int` 存储结果	斯特林数很快超过 21 亿（int 范围），例如 s(10,5)=42525 没问题，但 s(15,7) 已经约 4.3e9	使用 `long long` 或 `unsigned long long`
混淆了无符号与有符号斯特林数	这里是无符号第一类斯特林数，也有带符号版本（含 (-1)^{n-m}），但绝大多数竞赛题考的是无符号	看清楚题目描述
递推公式写错符号	容易写成 `dp[i][j] = dp[i-1][j] + i * dp[i-1][j-1]`，但这是另一种递推（第二类斯特林数）	牢记：新人是自己开桌还是插入（插入有 n-1 种位置）

7. 生活中的更多例子

班级分组围圈讲故事：30 个同学分成 5 个小组，每组围成一个圈，有多少种分组方式？就是 s(30,5)。
夏令营篝火晚会：20 个小朋友要围成 3 堆篝火，每堆至少 1 人，坐法旋转相同算一种，就是 s(20,3)。
圆桌会议：公司 8 个部门的代表参加会议，但要分成 2 个圆桌讨论，每个圆桌内部座位顺序只有相对重要，方案数为 s(8,2)= ？

8. 相关数学知识与扩展

第二类斯特林数 S(n,m)：把 n 个不同元素放入 m 个相同盒子（盒子无顺序，且盒子内元素无顺序），常用在集合划分问题。
贝尔数 B(n)：n 个不同元素划分成任意多个非空子集的方法总数，正好是 S(n,0)+S(n,1)+...+S(n,n)。
上升幂与下降幂：第一类斯特林数可以用来将普通幂转换为下降幂（或上升幂）的线性组合，例如： $x^{\underline{n}} = x(x-1)\dots(x-n+1) = \sum_{k=0}^n s(n,k) x^k \quad (\text{带符号版本})$ 这在组合恒等式和概率计算中非常有用。

学会了第一类斯特林数，你手中的组合计数工具又增加了一把利器。不妨自己写个程序输出 s(10,5) 试试，再手动验算一下递推的正确性吧！

例题精讲