球盒问题

约 317 个字 22 行代码 预计阅读时间 1 分钟

$n$ 个球，放入 $m$ 个盒中,共8种情况

球同，盒不同，无空箱

$C(n-1,m-1)$

使用插板法：$n$ 个球中间有 $n-1$ 个间隙，现在要分成 $m$ 个盒子，而且不能有空箱子，所以只要在 $n-1$ 个间隙选出 $m-1$ 个间隙即可

球同，盒不同，允许空箱

$C(n+m-1,m-1)$

如果给每个盒子一个球，就可以把问题转化为不能空的情况了,就相当于 $n+m$ 个小球放入 $m$ 个盒子且不能空

球不同，盒相同，无空箱

第二类斯特林数 $\begin{Bmatrix}n\\ m\end{Bmatrix}$

const int N=5e3+3;
ll S[N][N];
void cal()
{
    S[0][0]=1;
    for(int i=1;i<N;++i)
    {
        for(int j=1;j<=i;++j)
            S[i][j]=S[i-1][j-1]+(ll)j*s[i-1][j];
    }
}

球不同，盒相同，允许空箱

$\sum\limits_{i=1}^m\begin{Bmatrix}n\\ i\end{Bmatrix}$

枚举使用的箱子的个数

球不同，盒不同，无空箱

$m!\times \begin{Bmatrix}n\\ m\end{Bmatrix}$

给盒子定义顺序

球不同，盒不同，允许空箱

$m^n$

每个球都有 $m$ 种选择

球同，盒同，无空箱

等同于把一个正整数n拆分成m个正整数之和的方案数，即分拆数的k部分拆 $p(n,m)$

const int N=5e3+3;
ll p[N][N];
void cal()
{
    p[0][0]=1;
    for(int i=1;i<N;++i)
    {
        for(int j=1;j<=i;++j)
            p[i][j]=p[i-j][j]+p[i-1][j-1];
    }
}

球同，盒同，允许空箱

等同于把一个正整数拆分成几个正整数之和的方案数，即分拆数 $p(n)=\sum\limits_{i=1}^m p(n,i)$