

当小球遇上盒子

Copyright

前置知识¶

组合数 ：从 $n$ 个物品里选出 $m$ 个物品进行组合的方案数。

$C_{n}^{m}=\frac{n!}{m!\cdot (n-m)!}$

排列数：从 $n$ 个物品里选出 $m$ 个物品进行排列的方案数。

$A_{n}^{m}=\frac{n!}{(n-m)!}$

圆排列：一个 $n$ 个元素构成的集合，从中选出 $m$ 个元素构成一个环的方案数。

$Q_{n}^{m}=\frac{A_{n}^{m}}{m}$

第一类斯特林数：用 $n$ 个元素组成 $m$ 个环的方案数。

$s_{n}^{m}=s_{n-1}^{m-1}+(n-1)\cdot s_{n-1}^{m}$

第二类斯特林数：把一个大小为 $n$ 的集合划分成 $m$ 个非空集合的方案数，集合内部无序。

$S_{n}^{m}=S_{n-1}^{m-1}+m\cdot S_{n-1}^{m}$

就是把 $n$ 个球分成 $m$ 份，每一份不能为空，插 $m−1$ 个板即可。

$ans=C_{n-1}^{m-1}$

把 $n$ 个球分成 $m$ 份，每一份可以为空，再增加 $m$ 个球，插 $m-1$ 个板，每一份再拿走一个球即可。

$ans=C_{n+m-1}^{m-1}$

对于每一个球，你都可以放到[1,m]的任意一个位置,由于球不同，所以球与球之间是独立的。

$ans=m^{n}$

相当于把 $n$ 个元素的集合划分成 $m$ 份，也就是第二类斯特林数

$ans=S_{n}^{m}$

这个做法时间复杂度是 $O(n^{2})$ 的

其实这个就是问题5的答案除以 $m!$ 。

公式表示是

$ans=m!\cdot S_n^m$

因为可以有空盒，我们可以枚举每次一共用了几个盒子，然后把相应的第二类斯特林数加起来就可以了

$ans=\sum_{i=0}^{m}S[n][i]$

这种数也叫Bell数。

Bell数的定义：第 $n$ 个Bell数表示集合[1,2,3,...,n]的划分方案数

$B_{n}=\sum_{m=1}^{n}S[n][m]$

设f[n][m]表示 $n$ 个球放到 $m$ 个盒子里的方案数

$if(n==0||m==1) f[n][m]=1$

$if(n < m) f[n][m]=f[n][n]$

$$if(n>=m) f[n][m]=f[n−m][m]+f[n][m−1] $$ 如果球比盒子多，分为放满和不放满两种情况讨论
等价于自然数拆分问题

我们首先在所有的盒子中放一个球，就转化成了问题7

$ans=f[n−m][m]$

（有兴趣的同学请自行搜索“母函数/生成函数”）