前言

众所周知，其实，我是在考古的时候……
偶然发现了这篇完成了 $\frac{1}{1145141919810}$ 的分享。
这玩意儿 CSP-2023 初试之前就该更惹。
终于，在我的不懈努力之下，它被延迟了 114514 天才发布 awa.

分讨

1. $n$ 个相同的球，放入 $k$ 个相同的盒子，盒子不允许为空。

   • 作为一只柯学家，我要加强练习DP。（
   • 设 $dp_{i,j}$ 为 $i$ 个球放入 $j$ 个盒子里（允许为空）的方案数。
   • 则转移方程为：$dp_{i,j}=dp_{i,j-1}+dp_{i-j,j}$
   • 可分为有空盒子以及没有空盒子两种情况：
     • 有空盒子：$dp_{i,j-1}$（加入一个空盒子）。
     • 没有空盒子：$dp_{i-j,j}$（每个盒子放一个，剩下的就是相似子问题
   • 答案即为 $dp_{n,k}-dp_{n,k-1}$。
   • 可以从集合的角度感性理解一下。

2. $n$ 个相同的球，放入 $k$ 个相同的盒子，盒子允许为空。

   • 状态定义和转移方程见上一条（原理相同）。
   • 根据定义，答案即为 $dp_{n,k}$。

3. $n$ 个相同的球，放入 $k$ 个不同的盒子，盒子不允许为空。

   • 隔板问题。
   • 由于所有球相同，可以把 $n$ 个球排成一排，中间有 $n-1$ 个空隙，而需要分成 $k$ 份，所以要插入 $k-1$ 个板子把它们隔开。
   • 这是经典的隔板问题，方案数为 $C_{n-1}^{k-1}$。

4. $n$ 个相同的球，放入 $k$ 个不同的盒子，盒子允许为空。

   • 等价于$n+k$ 个相同的球，放入 $k$ 个不同的盒子，盒子不允许为空的问题。
   • 由于盒子不允许为空，所以显然每个盒子里面有 $1$ 个以上的球。
   • 那么把每一个盒子里拿走一个球，总共拿走了 $k$ 个球，剩下 $n$ 个球。
   • 此时可能出现盒子为空的情况，也就是原本要解决的问题。
   • 即答案为 $C_{n+k-1}^{k-1}$。
   • PS：这种未知转化为已知的思维，在 xxs 数学中经常出现，可以巧妙地解决很多问题，就算在 OI 界也是一个相当炸裂的存在。

5. $n$ 个不同的球，放入 $k$ 个相同的盒子，盒子不允许为空。

   • OIer 们最喜欢的板子题。
   • 亿眼鉴定为第二类斯特林数（Stirling 数）。

   • 定义：将 $n$ 个数划分为 $k$ 个非空子集的方案数。

   • 这正是本题所求，至于如何求解自己上网搜（bushi）。
   • 感觉看着有点像 DP？我们定义它的值为：$S_{n,k}$。
   • 对于第 $n$ 个球，可以新开一个盒子，也可以放在已有盒子。
   • 由此写出递推式：$S_{n,k}=S_{n-1,k-1}+S_{n-1,k} \times k \ \ (1 \leq k \leq n)$。
   • 预处理：$S_{0,0} = 1, \ S_{0,i} = 0$
   • 根据定义，答案为 $S_{n,k}$。

6. $n$ 个不同的球，放入 $k$ 个相同的盒子，盒子允许为空。

   • 你说得对。但是我不玩原神和崩铁。
   • 这不是和上一条是一样的吗？
   • 答案显然就是 $\sum_{i=1}^{k} S_{n,k}$。

7. $n$ 个不同的球，放入 $k$ 个不同的盒子，盒子不允许为空。

   • 你说得对。但是我还是不玩原神。
   • 还是一样 awa，只是盒子不同而已。
   • 答案显然是 $S_{n,k} \times k!$，因为可以换盒子，就乘上一个选盒子方案数。

8. $n$ 个不同的球，放入 $k$ 个不同的盒子，盒子允许为空。

   • 显然对于 $n$ 个球，每个都有 $k$ 种放置方式。
   • 所以答案为 $k^n$。

后记

好久没发帖子惹，所以来水一波。