n个球放入m个盒子问题总结

· · 个人记录

### 1. 球同，盒子同，可以空 $f(n,m)=f(n,m-1)+f(n-m,m)

边界 f(1,k)=1,f(k,1)=1,f(0,k)=1

两种操作，第一种，不进行任何操作，直接多一个盒子；第二种，每一个盒子加一个球

答案为 f(n,m)

2. 球同，盒子同，不可以空

答案为 f(n-m,m) ，方程同 1

即先将每个盒子先放入 1 个球，在将剩下的 n-m 个球放入 m 个盒子中，此时的盒子可以为空

3. 球同，盒子不同，不可以空

答案为 \dbinom{n-1}{m-1}

考虑插板法，n 个球中有 n-1 个空隙，需要将球分成 m-1 组，就是找 m-1 个空隙

4. 球同，盒子不同，可以空

答案为 \dbinom{n+m-1}{m-1}

也是考虑插板法,先给 m 个盒子都先放入 1 个球，这样剩下的 n 个球就可以随便放，所以是将 n+m-1 个球放入 m-1 个盒子中的方案

5. 球不同，盒子同，不可以空

S(n,m)=S(n-1,m)\times m+S(n-1,m-1)

边界 S(k,k)=1(k\ge1),S(k,0)=0(k\ge0)

直接上第二类斯特林数，两种情况，第一种，将一个球放入任意一个盒子中,即为 S(n-1,m) \times m ；第二种，为将一个球放入一个新的盒子中，即为 S(n-1,m-1)

答案为 S(n,m)

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

答案为 \sum\limits_{i=0}^m S(n,i)

就是对第 5 种情况进行求和，枚举放的盒子个数即可

7. 球不同，盒子不同，不可以空

答案为 S(n,m) \times m!

因为盒子不同，所以盒子可以任意排列，就是第 5 种情况的答案再乘上 m 种盒子的所有排列情况

8. 球不同，盒子不同，可以空

答案为 m^n

每个球有 m 种选法

部分内容来自大佬总结