放球问题

· · 个人记录

### 盒相同，球相同，允许空 设 $f(i, j)$ 表示 $i$ 个球，$j$ 个盒子的方案数，有 $$f(i, j) = f(i - j, j) + f(i, j - 1)$$ 由于球是不同的，所以我们不能单独考虑每个球的状态。这 $i$ 个球，要么每个都要放，也就是 $f(i - j, j)$，要么是至少一个不放，也就是 $f(i, j - 1)$。 最后答案是 $f(n, m)$。 ### 盒相同，球相同，不许空 我们提前取出 $n$ 个球不放，于是方案数就是上一问的 $f(n - m, m)$。 ### 盒相同，球不同，允许空 设 $f(i, j)$ 表示 $i$ 个球，$j$ 个盒子的放置 ### 盒相同，球不同，不许空 ### 盒不同，球相同，允许空 ### 盒不同，球相同，不许空 ### 盒不同，球不同，允许空 ### 盒不同，球不同，不许空