我的算法书 - 第二类 Stirling 数

一句话算法

第二类 Stirling 数 $S(n,m)$ 数的是：把 n 个不同元素分成 m 个非空无标号集合的方案数。

问题模型

有 n 个不同的球，编号为 1..n；有 m 个相同的盒子，每个盒子可以放多个球，但不允许为空。问有多少种放法。

“盒子相同”表示盒子的顺序不重要。

例如 n = 3, m = 2 时，只有三种：

\{1,2\}\{3\},\quad \{1,3\}\{2\},\quad \{1\}\{2,3\}

这就是 $S(3,2)=3$ 。

核心直觉

考虑编号最大的球 n。

它在最终方案中只有两种角色：

自己单独成为一个盒子。
加入某个已经存在的盒子。

如果 n 单独成盒，那么剩下 n-1 个球要分成 m-1 个非空盒子，方案数是 $S(n-1,m-1)$ 。

如果 n 不单独成盒，那么先把 n-1 个球分成 m 个非空盒子。虽然盒子整体没有名字，但在一个具体方案里有 m 个盒子可以加入，所以有 $mS(n-1,m)$ 种。

算法步骤

定义 dp[i][j] = S(i,j)。

边界：

dp[0][0] = 1。
dp[i][0] = 0，i > 0。
dp[i][j] = 0，j > i。

转移：

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

计算顺序：

枚举 i = 1..n。
枚举 j = 1..min(i,m)。
使用上面的递推式更新 dp[i][j]。

算法证明

分类对象： 编号最大的球 n。

若 n 单独成盒，去掉这个盒子后，剩下 n-1 个球必须分成 m-1 个非空无标号盒，方案数为 $S(n-1,m-1)$ 。
若 n 不单独成盒，先把 n-1 个球分成 m 个非空无标号盒，再选择其中一个盒子放入 n。每个划分中有 m 个盒子可选，方案数为 $mS(n-1,m)$ 。
两类方案互不重叠：第一类中 n 所在盒大小为 1，第二类中 n 所在盒大小至少为 2。
任意合法方案中，n 必然属于这两类之一。

所以递推式完整且不重复。

复杂度分析

时间复杂度： $O(nm)$ 。
空间复杂度： $O(nm)$ 。如果只求计数，可以滚动数组优化到 $O(m)$ 。

如果要输出所有集合划分，时间复杂度至少是 $O(nS(n,m))$ 。

代码实现

计数模板：

C++

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

        #include <bits/stdc++.h>
using namespace std;

// Stirling number of the second kind:
// S(n, m) = ways to split n distinct objects into m non-empty identical boxes.
//
// Recurrence:
//   S(n, m) = S(n - 1, m - 1) + m * S(n - 1, m)

using int64 = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<int64>> dp(n + 1, vector<int64>(m + 1, 0));
    dp[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= min(i, m); ++j) {
            dp[i][j] = dp[i - 1][j - 1] + j * dp[i - 1][j];
        }
    }

    cout << dp[n][m] << '\n';
    return 0;
}

Python

C++ 版算法写在 main 里，Python 版抽成同参数同返回值的 stirling_second_count(n, m)。

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

        # 第二类斯特林数 S(n, m)：n 个互不相同的球放进 m 个非空无标号盒的方案数。
# 递推：S(n, m) = S(n - 1, m - 1) + m * S(n - 1, m)，边界 S(0, 0) = 1。
# 调用方保证 n >= 0、0 <= m <= n；m > n 时递推自然得到 0，m < 0 是 C++ 的未定义行为，
# 本文件不处理（会抛 IndexError）。C++ 用 long long 存表，n 稍大就溢出；Python int 任意精度。

type Table = list[list[int]]  # dp[i][j] 表示 S(i, j)


def stirling_second_count(n: int, m: int) -> int:
    # C++ 原版把整段递推写在 main 里（读 n, m 后打印 dp[n][m]）；
    # 这里按"模板无输入输出"的规范抽成同参数、同返回值的函数。
    dp: Table = [[0] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = 1

    for i in range(1, n + 1):
        # j 只需枚举到 min(i, m)：j > i 时 S(i, j) 恒为 0。
        for j in range(1, min(i, m) + 1):
            # 第 i 个球单独成盒（j-1 个盒装前 i-1 个）或放进已有 j 个盒之一。
            dp[i][j] = dp[i - 1][j - 1] + j * dp[i - 1][j]
    return dp[n][m]

方案枚举模板：

C++

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

        #include <bits/stdc++.h>
using namespace std;

// Enumerate all partitions of n distinct balls into m non-empty identical boxes.
// To avoid duplicates caused by identical boxes, box ids are created in order:
// ball 1 must be in box 1; when processing a new ball, it may go into any
// existing box, or open exactly the next new box.

int n, m;
vector<vector<int>> box_items;
int answer_count = 0;

void print_answer() {
    cout << setw(4) << ++answer_count << ": ";
    for (int i = 0; i < m; ++i) {
        cout << "[ ";
        for (int x : box_items[i]) cout << x << ' ';
        cout << "] ";
    }
    cout << '\n';
}

void dfs(int ball, int used_boxes) {
    if (ball == n + 1) {
        if (used_boxes == m) print_answer();
        return;
    }

    // Put this ball into an existing box.
    for (int i = 0; i < used_boxes; ++i) {
        box_items[i].push_back(ball);
        dfs(ball + 1, used_boxes);
        box_items[i].pop_back();
    }

    // Open a new box. It must be the next box id, which gives each partition
    // one canonical representation.
    if (used_boxes < m) {
        box_items[used_boxes].push_back(ball);
        dfs(ball + 1, used_boxes + 1);
        box_items[used_boxes].pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    if (n < m || m <= 0) {
        cout << 0 << '\n';
        return 0;
    }

    box_items.assign(m, {});
    box_items[0].push_back(1);
    dfs(2, 1);
    return 0;
}

Python

print_answer 保留原名但不再打印：方案快照收集进 res（模板规范要求无 I/O）。

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

        # 枚举把 n 个互不相同的球分成 m 个非空无标号盒的所有方案，球号 1 下标。
# 去重手段：1 号球固定在 1 号盒；每处理一个新球，要么放进已有的某个盒，要么新开
# 编号恰好为 used_boxes + 1 的盒——每个划分只有这一种规范表示，所以不会重复。
# 模块级全局量按下面顺序布置，再调用 dfs（等价于 C++ main 的初始化）：
#   stirling_second_enumerate.n = n
#   stirling_second_enumerate.m = m
#   stirling_second_enumerate.box_items = [[] for _ in range(m)]
#   stirling_second_enumerate.box_items[0].append(1)
#   stirling_second_enumerate.answer_count = 0
#   stirling_second_enumerate.res = []
#   stirling_second_enumerate.dfs(2, 1)   # 1 号球已在 1 号盒，从 2 号球继续
# 前置条件 n >= m >= 1（C++ main 对 n < m 或 m <= 0 直接输出 0 并返回，这段守卫
# 属于输入输出层，不进模板）。递归深度为 n，n 逼近 1e5 时需 sys.setrecursionlimit。

type Boxes = list[list[int]]  # 每个盒子里已放的球号
type Answers = list[Boxes]  # 所有划分的快照列表

n: int = 0
m: int = 0
box_items: Boxes = []
answer_count: int = 0
res: Answers = []


def print_answer() -> None:
    # C++ 原版在这里把当前划分直接 cout；模板不含输出，改为存一份深拷贝快照。
    global answer_count
    answer_count += 1
    res.append([box.copy() for box in box_items])


def dfs(ball: int, used_boxes: int) -> None:
    if ball == n + 1:
        if used_boxes == m:
            print_answer()
        return

    # 放进已有的某个盒子。
    for i in range(used_boxes):
        box_items[i].append(ball)
        dfs(ball + 1, used_boxes)
        box_items[i].pop()

    # 新开一个盒子，编号必须是下一个，这样才能保证每个划分只被枚举一次。
    if used_boxes < m:
        box_items[used_boxes].append(ball)
        dfs(ball + 1, used_boxes + 1)
        box_items[used_boxes].pop()

测试用例

计数输入：

4 2

计数输出：

枚举输入：

3 2

枚举输出：

   1: [ 1 2 ] [ 3 ]
   2: [ 1 3 ] [ 2 ]
   3: [ 1 ] [ 2 3 ]

应用分类详解

第二类 Stirling 数的本质是“不同元素划分成若干个非空无标号组”。

一、无标号分组

典型模式： 把 n 个不同对象分成 m 个组，组之间没有名字，每组至少一个。

识别信号： “分成 m 组”“组不区分顺序”“每组非空”。

核心建模： 每个组就是一个相同盒子，球是不同对象。

应用场景	经典题目	核心思路
盒子与球	luogu-P1287	直接计算 $S(n,m)$
学生无名分组	分组计数基础题	组没有编号，用 Stirling 数

二、满射计数

典型模式： n 个不同对象分配给 m 个有编号盒子，每个盒子非空。

识别信号： 盒子、颜色、房间、机器有名字，且每个都必须至少收到一个对象。

核心建模： 先按无名盒划分，再给 m 个盒子贴标签。

\text{满射数}=m!S(n,m)

应用场景	经典题目	核心思路
不同任务分给不同机器且每台有任务	满射模型	$m!S(n,m)$
不同球放入不同非空盒	球盒扩展	先分组再排列盒子标签

三、最多分成 m 组

典型模式： 不要求恰好 m 组，而是最多 m 组。

识别信号： “分成不超过 m 组”“允许有空盒且盒子相同”。

核心建模： 枚举实际非空盒数量。

\sum_{k=1}^{m}S(n,k)

经典例题

luogu-P1287 盒子与球：第二类 Stirling 数模板题。
不同元素无名分组：练习 $S(n,m)$ 的递推。
满射计数题：在 $S(n,m)$ 基础上乘以 $m!$ 。

参考

本书相关章节：球盒模型