都是数学题

直接抄LH的课件啦...

做到有关的题目会更新

n个乒乓球放到m个盒子里的方案数

1.球相同，盒子不同，不允许空

分成m段，n-1个空选m-1个放隔板 ，$C_n-1^{m-1}$

2.球相同，盒子不同，允许空

$(1)$ 加入m个球变成不允许空

$(2)$ m-1个隔板和球放在一起，从中选m-1个做隔板

$C_{n+m-1}^{m-1}$

3.球相同，盒子相同，不允许空

就是整数划分问题啊...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]$

或者直接写暴力转移然后化简

4.球相同，盒子相同，允许空

$ \sum_{j=1}^mf[n][j] $

5.球不同，盒子相同，不允许空

第二类斯特林数：n个不同的元素分成m个集合的方案数

$ S(i,j)=S(i-1,j-1)+S(i-1,j)*j $

考虑一个元素可以放入一个空集合或者已经有元素的集合

6.球不同，盒子相同，允许空

枚举非空盒子数量

$ \sum_{j=1}^mS(n,j) $

7.球不同，盒子不同，不允许空

盒子全排列标号就行了

$S(n,m)*m!$

8.球不同，盒子不同，允许空

不能简单的全排列标号，因为空盒子标号没有意义

所以枚举非空盒子数量的时候乘上个组合数和全排列标号

$ \sum_{j=1}^m{S(n,j)*C_{m}^{j}*j!} $

n个球选m个，不能选相邻的

拿出球后会留下空

把选的拿出来，剩下n-m个球n-m+1个空(包括两端)，再把拿出来的m个插到空里去

$ C_{n-m+1}^{m}$

整理一点与排列组合计数有关的问题

原文：http://www.cnblogs.com/candy99/p/6400735.html