box-and-ball.md

排列组合 球盒问题 - TueAug5 2025

豆包真好用（以后完全记住了就按自己的理解重写一次）

豆包的原始回答

“球盒问题”是组合数学中的经典模型，核心是根据“球是否相同”“盒子是否相同”“盒子是否可空”三个维度分类，共8种基础情况（部分可通过转化简化）。其中，第二类斯特林数正是这类问题中的重要工具，我们逐一梳理如下：

核心分类维度

• 球的性质：相同（不可区分）/ 不同（可区分）
• 盒子的性质：相同（不可区分）/ 不同（可区分）
• 盒子状态：可空（允许空盒）/ 不可空（每个盒子至少1个球）

8 种基础情况的解法

1. 球不同，盒子不同，可空

每个球独立选择盒子，共 $k^n$ 种方法。

2. 球不同，盒子不同，不可空

需排除“至少有一个空盒”的情况，用容斥原理或斯特林数转化：

• 公式：$k! \cdot S(n,k)$（$S(n,k)$ 为第二类斯特林数，见下文）。
• 原理：先按“盒子相同”的方式分（即 $S(n,k)$），再对k个盒子排列（乘以 $k!$）。

3. 球不同，盒子相同，可空

等价于“将n个不同球分成最多k个非空子集”（空盒不影响，因盒子不可区分），方法数为 $\sum_{i=1}^{\min(n,k)} S(n,i)$（对1到k个非空子集求和）。

4. 球不同，盒子相同，不可空

这正是第二类斯特林数的定义：$S(n,k)$ 表示将n个不同的球放入k个相同的非空盒子的方法数。

• 例如：$S(3,2)=3$（对应“1+2”的分法：{a|b,c}, {b|a,c}, {c|a,b}）。

5. 球相同，盒子不同，可空

用隔板法：将n个相同球和k-1个“虚拟隔板”共 $n+k-1$ 个元素排列，选k-1个位置放隔板，方法数为 $\binom{n+k-1}{k-1}$。

6. 球相同，盒子不同，不可空

先每个盒子放1个球（用掉k个球），剩余 $n-k$ 个球按“可空”处理，方法数为 $\binom{(n-k)+k-1}{k-1} = \binom{n-1}{k-1}$（要求 $n \geq k$，否则为0）。

7. 球相同，盒子相同，可空

等价于“将n拆成最多k个非负整数的和”（不计顺序），属于整数分拆问题，方法数记为 $\sum_{i=1}^{\min(n,k)} p(n,i)$（$p(n,i)$ 表示将n拆成i个正整数的分法数）。

8. 球相同，盒子相同，不可空

等价于“将n拆成恰好k个正整数的和”（不计顺序），即整数分拆数 $p(n,k)$（要求 $n \geq k$，否则为0）。

三、斯特林数的角色

斯特林数分为两类，均与“球盒问题”相关：

• 第一类斯特林数（无符号）$s(n,k)$：表示将n个不同的球放入k个相同的非空“循环盒子”（即排成k个非空循环排列）的方法数。
• 第二类斯特林数 $S(n,k)$：如前文所述，是“球不同、盒子相同、不可空”的核心解，也是其他相关问题（如“球不同、盒子不同、不可空”）的基础。

简言之，第二类斯特林数是“球不同、盒相同、不可空”的直接答案，而其他情况需结合排列、隔板法或整数分拆求解。