小球与盒子的爱恨情仇

$n$ 个球，$m$ 个盒子，仅考虑简单的每个盒子是否可以空盒。

计数需要注意真正决定一个方案是否存在的到底是什么（考虑如何区别两个方案）

球相同，盒子不同：

• 可以有空盒：$n$ 个球和 $m-1$ 个隔板的含相同元素的排序问题；先放球
• 不可以有空盒：由于盒子内球无序且球相同，可以提前放球；将 $m-1$ 个隔板放入 $n-1$ 个空隙中的选择问题。

球不同：

• 盒子相同，不能有空盒
  • 第二类 Stiring 数定义为将 $n$ 个物体划分成 $m$ 个非空的没有区别的集合的方法数，有递推公式
  $$f(i,j)=f(i-1,j)\cdot j+f(i-1,j-1)$$考虑添加一个球的放置位置，常规的递推为 $O(nm)$，可以使用快速傅里叶变换加速
• 盒子相同，可以有空盒。利用上一种情况枚举空盒生成 j 个非空组。Bell 数
• 盒子不同，不能有空盒。直接对盒子集合全排序即可。
• 盒子不同，可以空盒：
  • 以球的视角进行分配，由乘法原理有 $m^n$ 种方法。
  • 枚举空盒，生成 j 个非空组（先生成组再分配），并将这 j 个飞空组与 m - j 个空组分配入 m 个不同的盒子

球相同，盒子相同：

• 可以空盒：等价于自然数拆分问题，有递推公式如下：$$f(n,m)=\{\begin{array}{l}f(n,n),n<m\\ f(n-m,m)+f(n,m-1),n>m\end{array}$$考虑当前是否所有盒子都满了的两种情况
• 不可以有空盒：由于球相同，事先放球即可