第二类 Stirling 数

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

  • 组合数学
  • Stirling 数
  • 动态规划
  • 枚举

一句话算法

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

问题模型

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

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

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

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

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

核心直觉

考虑编号最大的球 n。

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

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

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

如果 n 不单独成盒，那么先把 n-1 个球分成 m 个非空盒子。虽然盒子整体没有名字，但在一个具体方案里有 m 个盒子可以加入，所以有 mS(n−1,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) S(n,m)=S(n-1,m-1)+mS(n-1,m)

计算顺序：

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

算法证明

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

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

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

复杂度分析

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

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

代码实现

计数模板：

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;
}

方案枚举模板：

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;
}

测试用例

计数输入：

4 2

计数输出：

7

枚举输入：

3 2

枚举输出：

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

应用分类详解

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

一、无标号分组

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

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

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

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

二、满射计数

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

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

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

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

三、最多分成 m 组

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

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

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

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

经典例题

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

参考