小球盒子模型

相同的球(n)，相同的盒子(m)，允许一部分为空，求方案数。

首先这个是有递推的式子的。考虑两种情况，第一种是先给每一个盒子装一个苹果先，第二种是有一个盘子不装苹果。\(f[i][j]\)=\(f[i-j][j]+f[i][j-1]\)。特别的，我们有：j>i的时候，\(f[i][j]=f[i][i]\)。边界条件是，i=0或者j=1的时候，\(f[i][j]=1\)。

for(int i=0;i<=N;++i){
        for(int j=1;j<=M;++j){
            if(j==1||i==0)f[i][j]=1;
            else if(j>i) f[i][j]=f[i][i];
            else f[i][j]=(f[i-j][j]+f[i][j-1])%MOD;
        }
    }

相同球，相同的盒子，不允许为空，求方案数。

先每一个盒子放一个，然后就转化成上一个问题了。即，答案不为0时，答案是\(f[n-m][m]\)。

球相同，盒子不同。不允许空，求方案数。

其实这个说到底就是一个插板的问题。答案就是C(n-1,m-1)。

球相同，盒子不同，允许空，求方案数。

这个其实可以看做是多放了m个球之后，非空的情况。C(n-1+m,m-1)。

球不同，盒子相同。不允许空，求方案数。

这就是第二类Stirling数的定义，下面给出其递推的求法。

S[0][0]=1;
    for(int i=1;i<=5000;++i){
        for(int j=1;j<=i;++j)S[i][j]=(1ll*S[i-1][j-1]+1ll*j*S[i-1][j])%MOD;
    }

球不同，盒子相同。允许空，求方案数。

枚举一下空几个盒子就行了。\(ans=\sum_{i=1}^nS(n,i)\)。这个式子在组合数学中还有一个名字叫bell数。

球不同，盒子不同，不允许空，求方案数。

就是球不同盒子相同再乘上一个\(m!\)。

球不同，盒子不同，允许空，求方案数。

最简单的来了，答案是：\(m^n\)。