当小球遇上盒子

steven7 · 2018-11-08 10:10:55 · 个人记录

众所周知,小球和盒子是一对相爱相杀的好基友，他们的每一次出现都会让本蒟蒻十分痛苦。 下面本蒟蒻将总结一下之前见过的类型

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=m!*s(n,m)

5.球不同，盒子相同，不能有空盒

• 对于这个问题有一种神奇的东西叫做第二类斯特林数

• #### 注：$\frac{1}{m!}$是用来将有序变成无序的（盒子不同变为相同）

6.球不同，盒子相同，可以有空盒

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

• ans=\sum_{i=1}^{m}s(n,i)

7.球相同，盒子相同，可以有空盒

• 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)