我的算法书 - 组合计数模板题目

一句话算法

组合计数题先判断“谁不同、谁相同、顺序算不算”，再决定用排列、组合、隔板法还是 Stirling 数。

问题模型

本文整理几类最常见的球盒模板题：

不同球放入不同盒，每个盒子最多一个球。
不同球放入相同非空盒，每个盒子可以多个球。
相同球放入不同非空盒。
相同球放入不同盒，允许空盒。

这些题看起来都像“把球放盒子”，但答案完全不同。原因是：方案是否相同，取决于球和盒子的身份是否重要。

核心直觉

如果盒子有名字，盒子位置就是方案的一部分；如果盒子没有名字，交换两个盒子的内容不应该得到新方案。

如果球有编号，必须记录每个球去了哪里；如果球完全相同，只需要记录每个盒子里有几个球。

这四个判断比公式更重要。

模板一：不同球，不同盒，每盒最多一个

有五个不同的球 1,2,3,4,5，放到三个不同的盒子 a,b,c 里，每个盒子只能放一个球，问有多少种不同放法？

固定盒子顺序为：

a b c

一次放法可以写成：

1 2 3

表示：

a 放 1
b 放 2
c 放 3

因为盒子不同，a 放 1, b 放 2 和 a 放 2, b 放 1 是不同方案。

所以问题等价于：从 $5$ 个不同球中有序选出 $3$ 个。

答案：

P(5,3)=5\times4\times3=60

一般地， $n$ 个不同球放入 $m$ 个不同盒，每盒最多一个，且 $m\le n$ ：

P(n,m)=\frac{n!}{(n-m)!}

模板二：不同球，相同非空盒

有五个不同的球 1,2,3,4,5，放到三个相同的盒子里，每个盒子非空，问有多少种不同放法？

这就是第二类 Stirling 数：

S(5,3)

它表示把 $5$ 个不同元素划分成 $3$ 个非空无标号集合。

按盒子大小分类

三个非空盒子的大小只能是：

1,1,3
1,2,2

情况一：1,1,3

先选出放入三球盒的三个球：

C_5^3=10

剩下两个球各自单独成盒。因为盒子相同，两个单球盒交换不产生新方案。

这一类有 $10$ 种。

情况二：1,2,2

先选出单球盒里的球：

C_5^1=5

剩下 $4$ 个球要分成两个大小为 $2$ 的无标号盒：

\frac{C_4^2}{2}=3

所以这一类有：

5\times3=15

总答案：

10+15=25

这也等于：

S(5,3)=25

代码实现

枚举验证 25 种方案

当盒子相同时，不能直接给盒子编号，否则会重复计数。

枚举时采用一个唯一表示：

球按 1,2,3,...,n 的顺序处理。
新盒子只能按第一次出现的顺序创建。
每个划分只会被输出一次。

代码如下：

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

输入：

5 3

输出会列出 $25$ 种方案，前几行形如：

   1: [ 1 2 3 ] [ 4 ] [ 5 ]
   2: [ 1 2 4 ] [ 3 ] [ 5 ]
   3: [ 1 2 ] [ 3 4 ] [ 5 ]

最后一行编号为 25，和公式计算一致。

模板三：相同球，不同非空盒

有 $n$ 个相同球，放到 $m$ 个不同盒子里，每个盒子至少一个，问有多少种放法？

设第 $i$ 个盒子里放 $x_i$ 个球，则：

x_1+x_2+\cdots+x_m=n,\quad x_i\ge 1

这是普通隔板法。

把 $n$ 个球排成一排，中间有 $n-1$ 个空隙。要分成 $m$ 个非空段，只需要从 $n-1$ 个空隙中选 $m-1$ 个隔板位置。

答案：

C_{n-1}^{m-1}

模板四：相同球，不同盒，允许空盒

有 $n$ 个相同球，放到 $m$ 个不同盒子里，盒子可以为空，问有多少种放法？

设：

x_1+x_2+\cdots+x_m=n,\quad x_i\ge 0

令：

y_i=x_i+1

则：

y_1+y_2+\cdots+y_m=n+m,\quad y_i\ge 1

转成非空模型后，答案是：

C_{n+m-1}^{m-1}

这就是“先给每个盒子虚拟补一个球”的等效法。

算法步骤

处理球盒计数题时，按下面顺序判断：

球是否有编号。
盒子是否有编号。
盒子是否必须非空。
每个盒子是否最多一个球。
盒子相同时，确定唯一表示，避免重复计数。

常见对应关系：

模型	公式
不同球，不同盒，每盒最多一个	$P(n,m)$
不同球，相同非空盒	$S(n,m)$
不同球，不同非空盒	$m!S(n,m)$
相同球，不同非空盒	$C_{n-1}^{m-1}$
相同球，不同盒，允许空盒	$C_{n+m-1}^{m-1}$

算法证明

不同球相同盒为什么用 Stirling 数

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

不同球对应不同元素；相同盒对应无标号集合；每盒非空对应每个集合非空。

因此不同球放入相同非空盒的方案数就是 $S(n,m)$ 。

隔板法证明

对 $x_1+\cdots+x_m=n,\ x_i\ge1$ ：

先把 $n$ 个相同球排成一行。
相邻球之间共有 $n-1$ 个缝。
从这些缝中选出 $m-1$ 个放隔板。
隔板把球切成 $m$ 段，每段非空。

选隔板位置和非空分配方案一一对应，所以答案是：

C_{n-1}^{m-1}

允许空盒时，通过 $y_i=x_i+1$ 与非空模型一一对应，所以答案是：

C_{n+m-1}^{m-1}

复杂度分析

直接用公式计算单个排列数或组合数：时间复杂度 $O(m)$ 。
Pascal 递推预处理组合数：时间复杂度 $O(n^2)$ ，空间复杂度 $O(n^2)$ 。
Stirling 数 DP：时间复杂度 $O(nm)$ ，空间复杂度 $O(nm)$ 或 $O(m)$ 。
输出所有 Stirling 划分：输出规模为 $S(n,m)$ ，时间复杂度至少为 $O(nS(n,m))$ 。

测试用例

不同球，不同盒

输入模型：

n = 5, m = 3

答案：

不同球，相同非空盒

输入：

5 3

枚举程序输出 $25$ 行方案。

相同球，不同非空盒

输入模型：

n = 5, m = 3

答案：

C_4^2=6

对应分配：

应用分类详解

球盒模板的本质是“对象如何分配到容器中，以及哪些分配算同一种”。

一、安排位置

典型模式： 位置有编号，每个位置最多放一个对象。

识别信号： 座位、名次、排列、不同位置。

核心建模： 不同球放入不同盒，每盒最多一个，用排列数。

二、无名分组

典型模式： 把不同对象分成若干组，组之间没有名字。

识别信号： 分组、不区分组的顺序、每组非空。

核心建模： 不同球放入相同非空盒，用第二类 Stirling 数。

三、整数分配

典型模式： 分配相同物品，只关心每个盒子的数量。

识别信号： 苹果、糖果、金币、每人至少一个、允许为零。

核心建模： 相同球放入不同盒，用隔板法或非负整数解。

经典例题

1. 盒子与球

luogu-P1287

不同球放入相同非空盒，是第二类 Stirling 数模板题。

2. 组合的输出

luogu-P1157

从 $n$ 个不同元素中选 $m$ 个，不考虑顺序，可以看作不同球放入相同盒，每盒一个。

3. 放苹果

noiopenjudge-ch0202/666/

相同苹果放入相同盘子，盒子也相同，需要转成整数划分模型。

参考

本书球盒模型：enumeration_permutaion_combination/ball_and_box/index.md
本书第二类 Stirling 数：enumeration_permutaion_combination/ball_and_box/stirling_number.md
本书排列与组合：math/combinatorics/combinatorics/index.md