学习笔记：组合数学之放球问题

· · 个人记录

组合数学之放球问题&&斯特林数

本文我学习笔记，自我保存，如有不当请指正。//其实我自己都不是很熟（恼）

要求问题是有n个球放入m个盒子中。看似很简单的问题，其实暗藏玄机。

问题分为8种情况。

1.球相同，盒相同，可空。

对于这种情况，没有什么固定的公式，不过可以使用dp来解决。

定义dp[i][j]表示i个球放到j个盒子的放法。对于dp[i][j]有两种转移方案

第一是使新盒子空着，在其他盒子里添加一个球，即为dp[i-j][j]并继承dp[i][j-1] (前提是满足i>=j)。

第二是使新盒子为空，即为dp[i][j-1] (前提是满足i<j)

总结下来dp[i][j]=\left\{\begin{aligned}dp[i-j][j]+dp[i][j-1](i>=j)\\ dp[i][j-1](i<j)\end{aligned}\right.

//伪代码
int dp[N][N];
for(int j=1;j<=m;j++){
    dp[0][j]=1;
    dp[1][j]=1;
}
for(int i=2;i<=n;i++){
    for(int j=1;j<=m;j++){
        if(i>=j)dp[i][j]=dp[i-j][j]+dp[i][j-1];
        else dp[i][j]=dp[i][j-1];
    }
}

2.球相同，盒相同，不可空。

因为没有空盒，所以先在每个盒子里放一个球，问题就变成了第一种情况，但是是求dp[n-m][m]。

3.球相同，盒不同，不可空。

很明显，前提是n>m。这里我们使用插板法求解问题，即在n个球之间插入m-1个板。

画图可得，n个球间有n-1个空隙，而m-1个板将球划分为m个小集合。 所以答案即为：C(n-1,m-1),换一种写法就是\frac{(n-1)!}{(m-1)!*(n-m)!}

4.球相同，盒不同，可空。

假设m个盒子里已经放入了各一个小球，则共有n+m个小球。那么问题就转化成了上面那种情况。

利用插板法求解，n+m-1个空隙中m-1个板将球划分为m个小集合。 所以答案为：C(n+m-1,m-1)换一种写法就是\frac{(n+m-1)!}{(m-1)!*(n)!}

在介绍第五种情况之前，我们先引入一个前置知识——斯特林数

斯特林数(Stirling)分为两类。第一类斯特林数和第二类斯特林数，用于解决不同的问题。（这里只是浅谈，因为深入了我也搞不懂了）

第一类斯特林数解决的是环上的问题。

定义S(n,m)表示 将n个不同物品排成m个圆排列的方案，简单来说就是成环的放球问题。

通常也使用dp的思想转移。(正常情况下圆排列的方案数位(n-1)!)

考虑第n个元素。若n-1个元素构成了m-1个圆排列，那么第n个元素独自构成一个圆排列,方案数为

S(n-1,m-1)

若n-1个元素构成了m个圆排列，那么第n个元素插入这m个排列中，有n-1种放法，方案数为

S(n-1,m) * (n-1)

综上所述，我们得出转移方程为

S(n,m)=(n-1)*S(n-1,m)+S(n-1,m-1)

第二类斯特林数解决的是我们求的问题。定义S(n,m)表示把n个不同物品放入m个集合中的方案数。不同于圆排列，集合是不考虑次序的。同样，我们考虑第n个元素。

若n-1个元素构成了m-1个集合，则第n个元素单独构成集合，方案数为

S(n,m-1)

若n-1个元素构成了m个集合，那么将n个元素插入其中则有m种方式，所以方案数为

S(n-1,m)*m

综上所述，我们得出转移方程为

S(n,m)=S(n-1,m-1)+m*S(n-1,m)

现在我们就得到了我们所需要的内容，若想了解更多，建议百度（

以下的S均代表第二类斯特林数！！！

5.球不同，盒不同，可空

这是最简单的一种情况了，小学生都会了（？

对于m个盒子，都有n种选择，所以方案数为m^n种

6.球不同，盒相同，不可空

这里就是我们刚刚讲的第二类斯特林数，n个物品放入m个盒子，方案数为S(n,m)。转移方程见上文。其中，当n=m时，S(n,m)=1，当n<m时,S(n,m)=0

7.球不同，盒不同，不可空

同样考虑n个物品放入m个盒子中。不同于上一种情况的是盒子不同了。但是没有什么大问题。考虑球按照盒相同的情况摆放，而m个盒子进行全排列即m!种，所以方案数为S(n,m)* m!

8.球不同，盒相同，可空

同样离不开斯特林数。因为盒子可空，所以我们考虑n个球放入1至m个盒子的情况，方案数为其总和

\sum_{i=1}^{m}S(n,i)

组合数的求法就讲完了，代码实现靠你自己了

再次声明，本文为学习笔记，自我保存用，仅供参考。

资料引用：百度百科。

特别鸣谢学长hycc。