算法专题讲义：放球问题 (Twelvefold Way) 详解

在组合数学与算法竞赛中，将 $n$ 个球放入 $m$ 个盒子是一类极其经典的计数问题。根据球是否相同、盒子是否相同以及是否允许有空盒，该问题可细分为 8 种核心情况。

本讲义将对这 8 种分类进行逐一剖析，给出详尽的数理推导、直观实例、巩固练习以及完整的 C++11 代码实现。

核心模型总览表

一、球不同，盒不同

1.1 允许空盒

1. 数理推导

每个球都是独立的、不同的。由于盒子也是不同的，对于任意一个球，它都可以自由选择放入 $m$ 个盒子中的任意一个。 根据乘法原理，总方案数为： $$\underbrace{m \times m \times \dots \times m}_{n \text{ 个}} = m^n$$

2. 实例直观

• 输入：$n = 3$ 个不同的球（标号 $1, 2, 3$），$m = 2$ 个不同的盒子（标号 $A, B$）。
• 计算：$2^3 = 8$ 种。
• 具体方案：
  1. $A: {1, 2, 3}, B: {}$
  2. $A: {1, 2}, B: {3}$
  3. $A: {1, 3}, B: {2}$
  4. $A: {2, 3}, B: {1}$
  5. $A: {1}, B: {2, 3}$
  6. $A: {2}, B: {1, 3}$
  7. $A: {3}, B: {1, 2}$
  8. $A: {}, B: {1, 2, 3}$

3. 巩固练习

练习题 1：有 4 个不同的任务分配给 3 台不同的服务器处理，每台服务器可分配任意数量的任务（可空闲）。求总分配方案数。 * 解析：每个任务有 3 种选择，方案数为 $3^4 = 81$。

1.2 不允许空盒

1. 数理推导

因为不允许空盒，且盒子不同。我们可以分两步进行： 1. 分组：先忽略盒子的差异，把 $n$ 个不同的球分成 $m$ 个非空的无标号集合。这正是第二类斯特林数 $S_2(n, m)$ 的定义。 2. 分配：将这 $m$ 个无标号的集合分配到 $m$ 个不同的盒子中。由于盒子是有差异的，故有 $m!$ 种分配方式。

根据乘法原理，总方案数为： $$Ans = m! \cdot S_2(n, m)$$

2. 实例直观

• 输入：$n = 3$ 个不同球（$1, 2, 3$），$m = 2$ 个不同盒（$A, B$），无空盒。
• 计算：$2! \cdot S_2(3, 2) = 2 \times 3 = 6$ 种。
• 具体方案：对应 1.1 节实例中扣除包含空集的 2 种方案（第 1 种与第 8 种），余下 6 种。

3. 巩固练习

练习题 2：5 名志愿者分配到 3 个不同的社区进行服务，要求每个社区至少分配 1 人。求分配方案数。 * 解析：$3! \cdot S_2(5, 3) = 6 \times 25 = 150$ 种。

二、球不同，盒相同

2.1 不允许空盒（第二类斯特林数）

1. 数理推导与递推式

由于盒子没有区别且不能为空，这等价于将 $n$ 个有标记元素划分为 $m$ 个无标记非空子集的方案数，即第二类斯特林数 $S_2(n, m)$。

递推关系推导： 考虑最后一个球（第 $n$ 个球）： 1. 独自成组：第 $n$ 个球单独占据一个盒子。此时需要将前 $n-1$ 个球放入其余 $m-1$ 个盒子中，方案数为 $S_2(n-1, m-1)$。 2. 加入已有组：前 $n-1$ 个球已经放满了 $m$ 个盒子，第 $n$ 个球选择其中一个盒子加入。由于已经放了球的 $m$ 个盒子在放入第 $n$ 个球前相互是有区别的（因为里面的球集合不同），第 $n$ 个球有 $m$ 种选择，方案数为 $m \cdot S_2(n-1, m)$。

因此，递推公式为： $$S_2(n, m) = S_2(n-1, m-1) + m \cdot S_2(n-1, m)$$ 边界条件： * $S_2(0, 0) = 1$ * $S_2(i, 0) = 0 \quad (i > 0)$ * $S_2(i, i) = 1$

2. 实例直观

• 输入：$n = 4$ 个不同球（$1, 2, 3, 4$），$m = 2$ 个相同盒子，无空盒。
• 计算：$S_2(4, 2) = S_2(3, 1) + 2 \cdot S_2(3, 2) = 1 + 2 \cdot 3 = 7$ 种。
• 具体方案：
  1. ${1, 2, 3} \cup {4}$
  2. ${1, 2, 4} \cup {3}$
  3. ${1, 3, 4} \cup {2}$
  4. ${2, 3, 4} \cup {1}$
  5. ${1, 2} \cup {3, 4}$
  6. ${1, 3} \cup {2, 4}$
  7. ${1, 4} \cup {2, 3}$

3. 巩固练习

练习题 3：将 4 把不同的钥匙放入 3 个完全相同的包中，每个包至少放一把。 * 解析：求 $S_2(4, 3) = S_2(3, 2) + 3 \cdot S_2(3, 3) = 3 + 3 \times 1 = 6$。

2.2 允许空盒

1. 数理推导

由于盒子是相同的，若允许空盒，则意味着我们可以选择将这 $n$ 个不同的球放入 $1$ 个、 $2$ 个、…… 直至 $m$ 个盒子中（其余盒子留空）。 因此，总方案数是实际使用的盒子数从 $1$ 到 $m$ 的第二类斯特林数之和： $$Ans = \sum_{i=1}^m S_2(n, i)$$ (注：当 $m \ge n$ 时，该式等于贝尔数 $B_n$，即 $n$ 个不同元素集合划分的总数)

2. 实例直观

• 输入：$n = 3$ 个不同球（$1, 2, 3$），$m = 2$ 个相同盒子，允许空盒。
• 计算：$\sum_{i=1}^2 S_2(3, i) = S_2(3, 1) + S_2(3, 2) = 1 + 3 = 4$ 种。
• 具体方案：
  • 使用 1 个盒子：${1, 2, 3}$
  • 使用 2 个盒子：${1, 2} \cup {3}$，${1, 3} \cup {2}$，${2, 3} \cup {1}$

3. 巩固练习

练习题 4：4 本不同的书随意放入 3 个相同的抽屉中（允许有些抽屉空着）。 * 解析：$\sum_{i=1}^3 S_2(4, i) = S_2(4,1) + S_2(4,2) + S_2(4,3) = 1 + 7 + 6 = 14$。

三、球相同，盒不同

本类问题通常使用经典工具——隔板法 (Stars and Bars)。

3.1 不允许空盒

1. 数理推导

我们将 $n$ 个相同的球排成一排，球与球之间形成 $n-1$ 个空隙。 由于不允许空盒，我们需要在这些空隙中插入 $m-1$ 个隔板，将球分成 $m$ 组。由于盒子是有区别的（例如第 $i$ 组分配给第 $i$ 个盒子），每一种插板方案都唯一对应一种分配方案。 因为每个空隙最多只能插一块板，所以是从 $n-1$ 个位置中选择 $m-1$ 个位置插板。 $$Ans = \binom{n-1}{m-1}$$

2. 实例直观

• 输入：$n = 4$ 个相同球（$\bullet \bullet \bullet \bullet$），$m = 3$ 个不同盒子（$A, B, C$），无空盒。
• 计算：$\binom{4-1}{3-1} = \binom{3}{2} = 3$ 种。
• 图形化理解（$\bullet | \bullet | \bullet\bullet$ 等）：
  1. $\bullet | \bullet | \bullet\bullet \implies (1, 1, 2)$
  2. $\bullet | \bullet\bullet | \bullet \implies (1, 2, 1)$
  3. $\bullet\bullet | \bullet | \bullet \implies (2, 1, 1)$

3. 巩固练习

练习题 5：分 7 个相同的苹果给 3 个小朋友，要求每个小朋友至少分得 1 个。 * 解析：$\binom{7-1}{3-1} = \binom{6}{2} = 15$。

3.2 允许空盒

1. 数理推导

如果允许空盒，相当于求解方程： $$x_1 + x_2 + \dots + x_m = n \quad (x_i \ge 0)$$ 非负整数解的个数。

虚物法（借球法）推导： 为了套用“不允许空盒”的结论，我们向每个盒子“借” 1 个虚拟球（共借 $m$ 个球）。此时我们共有 $n + m$ 个相同的球。 我们将这 $n+m$ 个球分配给 $m$ 个盒子，且要求每个盒子至少分到一个球。 当分配完毕后，我们再从每个盒子中收回 1 个球。此时部分盒子持有的球数会变为 $0$，这便与原问题（允许空盒，放 $n$ 个球）形成了一一对应。 代入不为空公式： $$Ans = \binom{(n+m)-1}{m-1} = \binom{n+m-1}{m-1}$$

2. 实例直观

• 输入：$n = 2$ 个相同球，$m = 3$ 个不同盒子，允许空盒。
• 计算：$\binom{2+3-1}{3-1} = \binom{4}{2} = 6$ 种。
• 具体方案：对应 $(x_1, x_2, x_3)$ 三元组： $(2,0,0), (0,2,0), (0,0,2), (1,1,0), (1,0,1), (0,1,1)$

3. 巩固练习

练习题 6：有 5 个相同的计算节点，需要分配给 3 个不同的用户使用，允许有的用户分配到 0 个。 * 解析：$\binom{5+3-1}{3-1} = \binom{7}{2} = 21$。

四、球相同，盒相同

本类问题等价于整数拆分 (Integer Partition) 问题。

4.1 允许空盒

1. 数理推导与递推式

将 $n$ 个相同的球放入 $m$ 个相同的盒子，且允许空盒。这在数论中等价于将非负整数 $n$ 拆分为不超过 $m$ 个非负整数之和的方案数（不计顺序）。 我们定义状态 $f(n, m)$ 为该问题的解。

转移方程分析： 对于 $f(n, m)$，我们可以基于“是否有盒子留空”将方案划分为两个互斥的集合： 1. 至少存在一个空盒：既然至少有一个盒子是空的，我们可以将这个空盒子拿走。此时的方案数等价于将 $n$ 个球放入 $m-1$ 个盒子中，即 $f(n, m-1)$。 2. 没有空盒：既然每个盒子都至少有 1 个球，我们可以先在每个盒子中各放 1 个球（共消耗 $m$ 个球）。此时剩下的 $n-m$ 个球可以任意放入这 $m$ 个盒子中，方案数等价于 $f(n-m, m)$。

根据加法原理，递推关系为： $$f(n, m) = f(n, m-1) + f(n-m, m)$$

边界条件与特殊情况： * $f(0, m) = 1$：$0$ 个球放任何数量的盒子都只有 $1$ 种不放的方案。 * $f(n, 1) = 1$：所有球只能挤进同一个盒子。 * 当 $n < m$ 时，$f(n-m, m)$ 无物理意义（不可能分满所有盒子），此时 $f(n, m) = f(n, n)$。

2. 实例直观

• 输入：$n = 4$ 个相同球，$m = 3$ 个相同盒子，允许空盒。
• 计算： $$f(4, 3) = f(4, 2) + f(1, 3)$$ 而 $f(1, 3) = f(1, 1) = 1$。 $$f(4, 2) = f(4, 1) + f(2, 2) = 1 + (f(2, 1) + f(0, 2)) = 1 + (1 + 1) = 3$$ 所以 $f(4, 3) = 3 + 1 = 4$。
• 具体方案（整数拆分）：
  1. $4 = 4$
  2. $4 = 3 + 1$
  3. $4 = 2 + 2$
  4. $4 = 2 + 1 + 1$

3. 巩固练习

练习题 7：将 5 个相同的硬币放入 3 个相同的存钱罐中，允许有存钱罐为空。 * 解析：求 $f(5, 3)$： $f(5, 3) = f(5, 2) + f(2, 3)$ 其中 $f(2, 3) = f(2, 2) = f(2, 1) + f(0, 2) = 1 + 1 = 2$。 $f(5, 2) = f(5, 1) + f(3, 2) = 1 + (f(3, 1) + f(1, 2)) = 1 + (1 + 1) = 3$。 总方案数为 $3 + 2 = 5$ 种。（拆分为：$5$, $4+1$, $3+2$, $3+1+1$, $2+2+1$）

4.2 不允许空盒

1. 数理推导

因为不允许空盒，且球和盒子均相同。 我们可以先在 $m$ 个盒子中各放入 1 个球。此时剩余 $n-m$ 个相同的球，要放入 $m$ 个相同的盒子中，允许空盒。 这直接转化为 4.1 节的模型，方案数为： $$Ans = f(n-m, m)$$

2. 实例直观

• 输入：$n = 5$ 个相同球，$m = 3$ 个相同盒子，无空盒。
• 计算：$f(5-3, 3) = f(2, 3) = f(2, 2) = 2$ 种。
• 具体方案：
  1. $5 = 3 + 1 + 1$
  2. $5 = 2 + 2 + 1$

3. 巩固练习

练习题 8：把 6 个相同的苹果分成 3 堆，每堆至少有 1 个。 * 解析：等价于 $f(6-3, 3) = f(3, 3) = f(3, 2) + f(0, 3) = 2 + 1 = 3$ 种。（拆分为：$4+1+1$, $3+2+1$, $2+2+2$）

五、C++11 算法实现

以下程序完整实现了上述所有 8 种算法逻辑。采用 C++11 标准编写，并集成了高精度防溢出处理（对于大组合数、斯特林数和拆分数的动态规划递推）。

#include <iostream>
#include <vector>
#include <numeric>
#include <stdexcept>

class TwelvefoldWay {
private:
    int max_n;
    int max_m;
    std::vector<std::vector<long long>> C;   // 组合数表
    std::vector<std::vector<long long>> S2;  // 第二类斯特林数表
    std::vector<std::vector<long long>> dp;  // 整数拆分表

    void init_combination() {
        C.assign(max_n + max_m + 1, std::vector<long long>(max_n + max_m + 1, 0));
        for (int i = 0; i <= max_n + max_m; ++i) {
            C[i][0] = 1;
            for (int j = 1; j <= i; ++j) {
                C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
            }
        }
    }

    void init_stirling() {
        S2.assign(max_n + 1, std::vector<long long>(max_m + 1, 0));
        S2[0][0] = 1;
        for (int i = 1; i <= max_n; ++i) {
            for (int j = 1; j <= max_m; ++j) {
                if (j == 1 || j == i) {
                    S2[i][j] = 1;
                } else if (j < i) {
                    S2[i][j] = S2[i - 1][j - 1] + j * S2[i - 1][j];
                }
            }
        }
    }

    void init_partition() {
        dp.assign(max_n + 1, std::vector<long long>(max_m + 1, 0));
        for (int j = 0; j <= max_m; ++j) {
            dp[0][j] = 1;
        }
        for (int i = 1; i <= max_n; ++i) {
            for (int j = 1; j <= max_m; ++j) {
                if (i >= j) {
                    dp[i][j] = dp[i - j][j] + dp[i][j - 1];
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
    }

public:
    TwelvefoldWay(int n, int m) : max_n(n), max_m(m) {
        init_combination();
        init_stirling();
        init_partition();
    }

    // 1.1 球不同，盒不同，允许空
    long long case1_1(int n, int m) {
        long long res = 1;
        for (int i = 0; i < n; ++i) {
            res *= m;
        }
        return res;
    }

    // 1.2 球不同，盒不同，不允空
    long long case1_2(int n, int m) {
        if (n < m) return 0;
        long long fact = 1;
        for (int i = 1; i <= m; ++i) fact *= i;
        return fact * S2[n][m];
    }

    // 2.1 球不同，盒相同，不允空
    long long case2_1(int n, int m) {
        if (n < m) return 0;
        return S2[n][m];
    }

    // 2.2 球不同，盒相同，允许空
    long long case2_2(int n, int m) {
        long long sum = 0;
        int limit = std::min(n, m);
        for (int i = 1; i <= limit; ++i) {
            sum += S2[n][i];
        }
        return (n == 0) ? 1 : sum;
    }

    // 3.1 球相同，盒不同，不允空
    long long case3_1(int n, int m) {
        if (n < m) return 0;
        if (n == 0 && m == 0) return 1;
        return C[n - 1][m - 1];
    }

    // 3.2 球相同，盒不同，允许空
    long long case3_2(int n, int m) {
        if (n == 0 && m == 0) return 1;
        return C[n + m - 1][m - 1];
    }

    // 4.1 球相同，盒相同，允许空
    long long case4_1(int n, int m) {
        return dp[n][m];
    }

    // 4.2 球相同，盒相同，不允空
    long long case4_2(int n, int m) {
        if (n < m) return 0;
        return dp[n - m][m];
    }
};

int main() {
    // 假设最大球数为 10，最大盒子数为 5
    int n = 6;
    int m = 3;

    TwelvefoldWay solver(n, m);

    std::cout << "球数 n = " << n << ", 盒数 m = " << m << "\n\n";
    std::cout << "【1. 球不同，盒不同】" << "\n";
    std::cout << "  - 允许空 (1.1): " << solver.case1_1(n, m) << "\n";
    std::cout << "  - 不允空 (1.2): " << solver.case1_2(n, m) << "\n\n";

    std::cout << "【2. 球不同，盒相同】" << "\n";
    std::cout << "  - 不允空 (2.1): " << solver.case2_1(n, m) << " (第二类斯特林数)" << "\n";
    std::cout << "  - 允许空 (2.2): " << solver.case2_2(n, m) << "\n\n";

    std::cout << "【3. 球相同，盒不同】" << "\n";
    std::cout << "  - 不允空 (3.1): " << solver.case3_1(n, m) << " (隔板法)\n";
    std::cout << "  - 允许空 (3.2): " << solver.case3_2(n, m) << "\n\n";

    std::cout << "【4. 球相同，盒相同】" << "\n";
    std::cout << "  - 允许空 (4.1): " << solver.case4_1(n, m) << " (整数拆分)\n";
    std::cout << "  - 不允空 (4.2): " << solver.case4_2(n, m) << "\n";

    return 0;
}

终极大纲速记诀窍

1. 球异盒异幂和排：允许空是幂次（$m^n$），不允许空是排列乘以斯特林数（$m! S_2$）。
2. 球异盒同斯特林：盒子相同，自然抹去排列，直接采用斯特林数（$S_2$），空盒则做前缀和。
3. 球同盒异隔板法：无空盒，空隙插板 $\binom{n-1}{m-1}$；有空盒，虚物借球 $\binom{n+m-1}{m-1}$。
4. 球同盒同数拆分：完全退化成最纯粹的数字分解。利用递推式 $f(n, m) = f(n-m, m) + f(n, m-1)$ 解决。

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