放球模型

未分类

---

$n$个球放入$m$个盒子,细分为球是否相同,盒子是否相同,是否可以有空盒,总共有$8$种情况.

1.球相同,盒子不同,不可以空盒.
用隔板法,$n$个球放成一排,总共有$n-1$个空隙,在这$n-1$个空隙中放入$m-1$个隔板,就能把球分为$m$份.所以方案数是$C_{n-1}^{m-1}$.假设第i个盒子的球数是$x_i$,那么就是需要满足$(\sum_{i=1}^mx_i)=n,x_i\geq 1$.

2.球相同,盒子不同,可以空盒.
和1.类似.设第i个盒子的球数是$x_i$,要求$(\sum_{i=1}^mx_i)=n,x_i\geq0$,令$y_i=x_i+1$,就有$(\sum_{i=1}^my_i)=n+m,y_i\geq 1$,这个就是用1.中的情况,答案就是$C_{n+m-1}^{m-1}$.

3.球相同,盒子相同,可以空盒.
考虑$dp$,设$dp(i,j)$表示$i$个球放入$j$个盒子的方案数.

$$dp(i,j)=dp(i-j,j)+dp(i,j-1),i\geq j \\dp(i,j)=dp(i,j-1),i<j$$
初始化$dp(0,0)=1,dp(0,i)=1,dp(i,0)=0,i\geq 1$

4.球相同,盒子相同,不可以空盒.
这种情况下,如果$n<m$显然$ans=0$,否则在每个盒子中放一个球,然后就转化成3.中的问题,$ans=dp(n-m,m).$

5.球不同,盒相同,不可以空盒.

$$dp(i,j)=dp(i-1,j-1)+j*dp(i-1,j),i\geq j$$
初始化$dp(i,i)=1,i\ge 0.$
$dp(n,m)$被称为第二类斯特林数,再介绍一下容斥做法:
$$dp(n,m)=\frac{1}{m!}\sum_{i=0}^mC_m^i(-1)^i(m-i)^n$$

6.球不同,盒相同,可以空盒.
根据5.中的结论$ans=\sum_{i=0}^m dp(n,i).$

7.球不同,盒不同,可以空盒.
显然$ans = m^n$.

8.球不同,盒不同,不可以空盒.
跟5.中情况类似,$ans=dp(n,m)*m!$.