组合数之小球与盒子

· · 个人记录

组合数公式：

C ^ {m}_ {n} = \frac {n!}{m!(n - m)!}

组合数也可以由递推(杨辉三角)求出.

C ^ {m}_{n} = C^{m - 1} _ {n - 1} + C^{m}_{n - 1}

好了让我们来看题：

很久很久以前，有n个球，m个盒子.

1.球相同，盒子不同，不能有空盒

我们经过一波巧妙地的分析之后，发现这个问题的实质就是把 n 个小球分为 m 组（不能空），然后就这么转化成了一个组合数问题.

ans = C^{m - 1}_{n - 1}

其实这就是一个插板法，就是在 n 个小球的 n-1 个空隙当中刚好插入 m-1 个板子，即恰好分为不为空的 m 组.

因为盒子不相同，所以(1,2)和(2,1)是不同的.

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

对于每个盒子，我们都给他一个球，那么上一个问题就和这问题一样了，所以我们可以看做自己有 n+m 个小球，然后我们在排列完之后在每一组都删去一个小球，这样就能枚举出有空盒的情况了。于是答案为

ans = C^{m - 1}_{n + m - 1}

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

对于每一个球，你都可以放到 1~m 的任意一个位置,由于球不同，所以球与球之间是独立的。因为每个球有 m 种情况，所以我们得出

ans = m ^ n

4.球不同，盒子相同，不能有空盒

对于这个问题有一种神奇的东西叫做第二类斯特林数（不是加特林）.

在数学领域，斯特林数分为第一类斯特林数和第二类斯特林数，我们在这里只说第二种.

第二类斯特林数（简称为S2）的定义为将n个物体划分成k个非空的没有区别的集合的方法数，大致就是把 n 个不同的小球放入m个相同的盒子中（且盒子不能为空）的方案数。递推公式为

S2[i][j] = S2[i - 1][j] * j + S2[i - 1][j - 1]

(

我们可以这样理解：对于一个$S2[i][j]$，你接下来要再放一个小球，你可以放到前$j$个盒子里，方案数为$j * S2[i][j]$，也可以放到下一个盒子里，方案数为 $S2[i][j+1]

于是我们就可以得出上面的递推公式了，代码如下：

    int n = read(),m = read();
    S2[0][1] = 1;
    for(int i = 0;i <= n;i++){
        for(int j = 1;j <= i;j++){
            S2[i][j] = (S2[i - 1][j] * j + S2[i - 1][j - 1]);
        }
    }
    cout<<S2[n][m]<<endl;

这个公式是O( n^ 2)的，斯特林数还有一个公式.

S2(n,m) = \frac {1} {m!} * \sum_{k = 0}^m(-1)^k(^m_k)*(m - k)^n

如果集合没有非空的限制，方法有m^n种.

我们枚举为空的盒子，可得出(^m_k) * (m - k)^n这部分是多出来的.

但可能会重复，我们需要套一个容斥即 (-1)^n.

最后除一个m!消掉有序性，如果不除就是有序的.

据说可以用FFT（快速傅里叶变换）加速，但是我太菜了不会，于是不提.

5.球不同，盒子也不同，不能有空盒

事实上这种情况与上面唯一的不同就是有序性，我们只需要在那个公式里不除m!，即在第二类斯特林数上乘上一个m!就可以了.

ans = m! * S2[n][m]

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

因为可以有空盒，我们可以枚举每次一共用了几个盒子，然后把相应的第二类斯特林数加起来就可以了.

ans = \sum^{m}_{i = 1}S2[n][j]

似乎这种数的名字叫做贝尔数.

Bell数的定义：第n个Bell数表示集合{1,2,3,...,n}的划分方案数.

看起来是不是和第二类斯特林数有点像.

可以说贝尔数就是其对应的第二类斯特林数之和.

贝尔数的相应公式为B_{n+ 1} = \sum^n_{k = 0}(^n_k)B_k，即枚举包含最后一个元素的集合大小.

也可以通过对应的第二类斯特林数求和得到，公式如下.

B_n = \sum^n_{k = 1} S2(n,k)

7.球相同，盒子相同，可以有空盒

设f[n][m]为n个球放到m盒子里的方案数.

如果只有一个盘子或者没有小球，方案数自然为1.

如果小球比盒子要少，小球肯定是放不满盒子的，由于盒子相同，可以得到转移f[i][j]=f[i - j][j] + f[i][j - 1].

总结上面三种情况就可以得出转移方程了，代码如下

    int n = read(),m = read();
    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(i < j) f[i][j] = f[i][i];   
            else if(i >= j) f[i][j] = f[i - j][j] + f[i][j - 1];
        }
    }
    printf("%d\n",f[n][m]);

8.球相同，盒子相同，不能有空盒

有点类似于第一、二种情况之间的关系.

我们先假设在每一个盒子里都放上了一个球，就跟上面的情况一样了..

ans = f[n - m][m]