都是数学题
直接抄LH的课件啦...
做到有关的题目会更新
分成m段,n-1个空选m-1个放隔板 ,$C_n-1^{m-1}$
$(1)$ 加入m个球变成不允许空
$(2)$ m-1个隔板和球放在一起,从中选m-1个做隔板
$C_{n+m-1}^{m-1}$
就是整数划分问题啊...n个数写成m个数的和的形式的方案数
$ f[i][j]=f[i-1][j-1]+f[i-j][j] $
有1的话就是$ f[i-1][j-1]$,没有1的话就拿出j个1先放上再分剩下的,$f[i-j][j]$
或者直接写暴力转移然后化简
$ \sum_{j=1}^mf[n][j] $
第二类斯特林数:n个不同的元素分成m个集合的方案数
$ S(i,j)=S(i-1,j-1)+S(i-1,j)*j $
考虑一个元素可以放入一个空集合或者已经有元素的集合
枚举非空盒子数量
$ \sum_{j=1}^mS(n,j) $
盒子全排列标号就行了
$S(n,m)*m!$
不能简单的全排列标号,因为空盒子标号没有意义
所以枚举非空盒子数量的时候乘上个组合数和全排列标号
$ \sum_{j=1}^m{S(n,j)*C_{m}^{j}*j!} $
拿出球后会留下空
把选的拿出来,剩下n-m个球n-m+1个空(包括两端),再把拿出来的m个插到空里去
$ C_{n-m+1}^{m}$
来源: