** 众所周知,小球和盒子是一对相爱相杀的好基友，他们的每一次出现都会让本蒟蒻十分痛苦。 下面本蒟蒻将总结一下之前见过的类型 **
1.球相同，盒子不同，不能有空盒
这类题可以用隔板法来做，等价于在n个数,之间插入m-1个板，将其分为m组。
$ans=c_{n-1}^{m-1}$
2.球相同，盒子不同，可以有空盒
这个类型其实是上一个类型的翻版，由于隔板法不能有空盒，所以我们先在每一个盒子里放一个小球。然后就等价于将$n+m$各元素放到$m$个盒子里。
$ans=c_{n+m-1}^{m-1}$
3.球不同，盒子不同，可以有空盒
对于每一个球，你都可以放到$1-m$ 的任意一个位置,由于球不同，所以球与球之间是独立的。由乘法原理得：
$ans=m^n$
4.球不同，盒子不同，不可以有空盒
我们可以用捆绑法将一些小球捆绑成一个小球，这道题可以等价为将$n-m+1$个小球当成一个大球，然后求$m$个球一共有多少种排列。
$ans=c_{n}^{n-m+1}*A_{m}^{m}$
当然我们也可以用容斥原理来做，可以有空盒的情况一共有$m^n$，我们减去有一个一定为空盒的情况$c_{m}^{1}*(m-1)^n$，再加上有两个一定为空盒的情况$c_{m}^{2}(m-2)^n$
$$ans=\sum_{k=0}^{m}(-1)^kc_{m}^{k}*(m-k)^n$$（奇加偶减）
其实它还可以由第二类斯特林数推得$ans=m!*s(n,m)$
5.球不同，盒子相同，不能有空盒
对于这个问题有一种神奇的东西叫做第二类斯特林数
$s(n,m)$ 表示n个不同的球，放入m个无区别的盒子，不允许盒子为空。
$$ s(i,j)=s(i-1,j-1)+s(i-1,j)*j $$ $O(n^2)$
$$s(n,m)=\frac{1}{m!}*\sum_{k=0}^{m}(-1)^k(^m_k)(m-k)^n$$ $O(m)$
注：$\frac{1}{m!}$是用来将有序变成无序的（盒子不同变为相同）
6.球不同，盒子相同，可以有空盒
因为可以有空盒，我们可以枚举每次一共用了几个盒子，然后把相应的第二类斯特林数加起来就可以了
$$ans=\sum_{i=1}^{m}s(n,i)$$
7.球相同，盒子相同，可以有空盒
$f(n,m)$表示将n个数放到m个集合中的方案数。
$f(i,1)=1;f(0,i)=1;$
$if(i<j) f(i,j)=f(i,i);$
$ else\ f(i,j)=f(i-j,j)+f(i,j-1) $
8.球相同，盒子相同，不能有空盒
有点类似于第一、二种情况之间的关系。
我们先假设在每一个盒子里都放上了一个球，就跟上面的情况一样了。
$ans=f(n-m,m)$
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/d4bcd452.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！