球盒模型是组合数学中研究分配问题的经典模型，根据球是否可区分、盒是否可区分、是否允许空盒等条件组合出不同场景。以下是12种常见场景及其证明概要。
分类体系
- 球: 可区分(D) / 不可区分(U)
- 盒: 可区分(D) / 不可区分(U)
- 空盒: 允许(E) / 不允许(N)
采用(D/U, D/U, E/N)标记法，共2×2×2=8种基本场景，加上4种额外限制场景。
1. (D, D, E) - 可区分球，可区分盒，允许空盒
场景: n个不同球放入m个不同盒，盒可空
公式: ( m^n )
证明: 每个球有m种独立选择，乘法原理即得。
2. (D, D, N) - 可区分球，可区分盒，不允许空盒
场景: n个不同球放入m个不同盒，每盒至少1球（n≥m）
公式: ( m! \cdot S(n, m) )
证明:
- 先将n球分成m个非空子集（无序）: ( S(n, m) ) 种（第二类斯特林数）
- 将m个子集分配到m个有标号盒: ( m! ) 种
- 相乘即得
3. (D, U, E) - 可区分球，不可区分盒，允许空盒
场景: n个不同球放入m个相同盒，盒可空
公式: ( \sum_{k=1}^{m} S(n, k) ) （当m≥n时，为Bell数( B_n )）
证明:
- 实质是划分成至多m个非空子集
- 对k=1到m求和，( S(n, k) )表示分成恰好k个非空子集的方法数
4. (D, U, N) - 可区分球，不可区分盒，不允许空盒
场景: n个不同球放入m个相同盒，每盒至少1球（n≥m）
公式: ( S(n, m) )
证明: 直接对应n元集划分为m个非空子集（无序）的定义。
5. (U, D, E) - 不可区分球，可区分盒，允许空盒
场景: n个相同球放入m个不同盒，盒可空
公式: ( \binom{n+m-1}{m-1} )
证明: 经典"星与条"模型。n个球用星号*表示，插入m-1个分隔条|划分到m盒：
排列( \underbrace{*****}{n} \underbrace{||...|} )，总位置n+m-1，选m-1位置放分隔条。
6. (U, D, N) - 不可区分球，可区分盒，不允许空盒
场景: n个相同球放入m个不同盒，每盒至少1球（n≥m）
公式: ( \binom{n-1}{m-1} )
证明: 先每盒放1球，剩余n-m球用场景5方法分配：
(\binom{(n-m)+m-1}{m-1} = \binom{n-1}{m-1})
7. (U, U, E) - 不可区分球，不可区分盒，允许空盒
场景: n个相同球放入m个相同盒，盒可空
公式: ( p(n, \leq m) = \sum_{k=1}^{m} p(n, k) )
其中( p(n, k) )是将n划分为恰好k个正整数的划分数
证明: 对应整数拆分问题，盒数不超过m的拆分总数。
8. (U, U, N) - 不可区分球，不可区分盒，不允许空盒
场景: n个相同球放入m个相同盒，每盒至少1球（n≥m）
公式: ( p(n, m) )
证明: 直接对应将整数n拆分为恰好m个正整数的划分数。
9. 至多1球每盒，允许空盒 (D, D)
场景: n个不同球放入m个不同盒，每盒至多1球（m≥n）
公式: ( P(m, n) = \frac{m!}{(m-n)!} )
证明: 第一个球有m选择，第二个有m-1，...，第n个有m-n+1，即排列数。
10. 至多1球每盒，不允许空盒 (D, D)
场景: n个不同球放入m个不同盒，每盒恰好1球（m=n）
公式: ( n! )
证明: 即n个球的全部排列，每个盒分配一个不同的球。
11. 至多1球每盒 (U, D)
场景: n个相同球放入m个不同盒，每盒至多1球（m≥n）
公式: ( \binom{m}{n} )
证明: 从m盒中选出n盒各放一球即可。
12. 无限容量但指定每盒容量不同
场景: n个相同球放入m个不同盒，第i盒容量为( c_i )
公式: 生成函数系数：( [x^n] \prod_{i=1}^{m} (1+x+...+x^{c_i}) )
证明: 每盒贡献因子( \sum_{j=0}^{c_i} x^j )，乘积中( x^n )系数即分配方法数。
总结表
| 序号 | 球 | 盒 | 空盒 | 限制条件 | 计数公式 |
|---|---|---|---|---|---|
| 1 | D | D | 允许 | 无 | ( m^n ) |
| 2 | D | D | 不允许 | 无 | ( m! \cdot S(n, m) ) |
| 3 | D | U | 允许 | 无 | ( \sum_{k=1}^{m} S(n, k) ) |
| 4 | D | U | 不允许 | 无 | ( S(n, m) ) |
| 5 | U | D | 允许 | 无 | ( \binom{n+m-1}{m-1} ) |
| 6 | U | D | 不允许 | 无 | ( \binom{n-1}{m-1} ) |
| 7 | U | U | 允许 | 无 | ( \sum_{k=1}^{m} p(n, k) ) |
| 8 | U | U | 不允许 | 无 | ( p(n, m) ) |
| 9 | D | D | 允许 | 每盒≤1球 | ( P(m, n) ) |
| 10 | D | D | 不允许 | 每盒=1球 | ( n! ) |
| 11 | U | D | 允许 | 每盒≤1球 | ( \binom{m}{n} ) |
| 12 | U | D | 允许 | 容量限制 | 生成函数系数 |
符号说明:
- ( S(n, m) ): 第二类斯特林数
- ( p(n, m) ): 整数拆分函数
- ( P(m, n) ): 排列数
- ( \binom{a}{b} ): 组合数
这些模型覆盖了组合分配问题的主要类型，在概率论、统计物理、计算机科学等领域有广泛应用。