算法讲义：放球问题 (Twelvefold Way) 汇总

在组合数学中，将 $n$ 个球放入 $m$ 个盒子的问题，根据球是否相同、盒子是否相同、是否允许空盒，可以划分为 8 种基本情况。

核心模型分类表

1. 球不同，盒不同

1.1 允许为空 (Case 6.3)

每个球都有 $m$ 种独立的选择。 - 公式：$m^n$

1.2 不允许为空 (Case 6.5)

先将 $n$ 个不同球分成 $m$ 个非空集合（相同盒子），由于盒子不同，需要全排列。 - 公式：$m! \cdot S_2(n, m)$

2. 球不同，盒相同

2.1 不允许为空 (Case 6.4)

即第二类斯特林数 $S_2(n, m)$。表示将 $n$ 个不同元素划分为 $m$ 个非空子集的方案数。 - 递推公式：$S_2(n, m) = S_2(n-1, m-1) + m \cdot S_2(n-1, m)$ - 含义：新球要么新开一个盒子，要么放入已有的 $m$ 个盒子的其中一个。

2.2 允许为空 (Case 6.6)

枚举最终使用了多少个盒子。 - 公式：$\sum_{i=1}^m S_2(n, i)$ - 注：当 $m=n$ 时，结果为贝尔数 $B_n$。

3. 球相同，盒不同（隔板法）

3.1 不允许为空 (Case 6.7)

在 $n$ 个球产生的 $n-1$ 个间隙中插入 $m-1$ 个隔板。 - 公式：$\binom{n-1}{m-1}$

3.2 允许为空 (Case 6.8)

方法一（虚物法）：借 $m$ 个球过来，每个盒子分一个，最后再拿走。等价于 $n+m$ 个球不允许为空放进 $m$ 个盒子。 方法二（多项式）：等价于 $x_1 + x_2 + \dots + x_m = n$ 的非负整数解。 - 公式：$\binom{n+m-1}{m-1}$

4. 球相同，盒相同（整数拆分）

4.1 允许为空 (Case 6.1)

等价于将整数 $n$ 拆分为不超过 $m$ 个整数的和。 - 状态定义：$f(n, m)$ 为方案数。 - 转移方程：$f(n, m) = f(n-m, m) + f(n, m-1)$ - $f(n, m-1)$：至少有一个盒子为空。 - $f(n-m, m)$：每个盒子都至少放了一个球，先把 $m$ 个盒子铺满。

4.2 不允许为空 (Case 6.2)

先把 $m$ 个盒子各放一个球，剩下的 $n-m$ 个球随意放。 - 公式：$f(n-m, m)$

5. 代码实现技巧（C++）

第二类斯特林数 (Stirling Number 2)

long long S2[101][101];
void init_stirling(int n, int m) {
    for (int i = 0; i <= n; i++) S2[i][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            S2[i][j] = (S2[i-1][j-1] + j * S2[i-1][j]);
        }
    }
}

整数拆分 (Integer Partition)

long long dp[101][101];
void init_partition(int n, int m) {
    for (int i = 0; i <= m; i++) dp[0][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i >= j) dp[i][j] = dp[i-j][j] + dp[i][j-1];
            else dp[i][j] = dp[i][j-1];
        }
    }
}

总结口诀

1. 球异盒异：看幂次。
2. 球异盒同：斯特林。
3. 球同盒异：隔板法。
4. 球同盒同：数拆分。
5. 空盒不空：先占位。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com