说到盒子与球,这是一个典型的排列组合问题。
从最简单的问题引入,在很多数学书中,都有这样一个问题。
给定n个不同的盒子和m个相同的小球,求把这些小球都装入盒子,并且保证所有的盒子都不为空的方法有多少种?
这道题目是一个简单的数学问题,从数学方法就可以解决了,不管你是用插板法还是什么七七八八的办法,总之,这道题目还是比较简单的。
这里,我顺便介绍一种不定方程的方法。
假定第一个盒子中有x1个小球,第2个盒子有x2个小球……第i个盒子有xi个小球,一直到最后一个盒子。这样可以得到一个简单的不定方程
即 x1+x2+……xi+……xn=m;
而题目所要求的也就是该方程的正整数解。这样,可以假象有m个1,有m-1个空位,需要在中间添加n-1个加号,于是,最后的方案就应该是C(m-1,n-1)。
下面是vijos上面的一道题目。这里简单的做一下解析。描述如下
N个盒子排成一行(1<=N<=20)。你有A个红球和B个蓝球。0 <= A <= 15, 0 <= B <= 15。球除了颜色没有任何区别。你可以将球放进盒子。一个盒子可以同时放进两种球,也可以只放一种,也可以空着。球不必全部放入盒子中。编程计算有多少种放置球的方法?
输入格式
一行n,a,b 用空格分开
输出格式
一行,代表方案总数。
Sample input
2 1 1
Sample output
9
拿到这道题目,需要处理的就是红球和蓝球的区别了,实际上为了避开这个条件,可以考虑用乘法原理,即最后的答案应该是放红球的方案总数乘以放蓝球的方案总数。这样第一个难点,也就是解决不同球的问题就被解决了。
第二个问题就是题目要求的是可以不放满的问题,为了解决这个问题,我们可以假设存在一个这样的盒子,它放的是前面盒子中没有放入的小球,也就是让他完全变成了n+1个盒子,这样也就避开了小球可以全部不放入的问题了。
这时候,也就是x1+x2+……xi+……xn+xn+1=m的非负整数解的个数了,和上述例题中提到的正整数解是有区别的。
下面解决最后一个难点,为了解决这个非负整数解的问题,我们可以把等式两边同时加上一个n+1,很多人会问,加上这个有什么用呢?O(∩_∩)O~,别急,不妨把这n+1平均分给一个未知数,这样就变成了x1+1……xi+1了,而实际上这样一做,这题就解决了。不会还不懂把!! 不懂的把x+1设为y;
所以这道题目最后的答案应该是c(n+a,n)*c(n+b,n);
这道题目,也可以用递推来实现,这样说把
用f[K][I,J]表示前k个盒子,放了i个红球和j个蓝球的方案总数,这样可以得到一个递推式
f[K][I,j]=f[k-1][a,b]+f[I,j];
解释一下,前k个盒子放入i个红球和j个蓝球的方案总数,应该等于Σf[K-1][a,b],也就是前k-1个盒子放入1个、2个、3个……红球和蓝球。
边界条件是 f[0][i][j]=1; 注意上面的a和b应该是从0开始循环的。
还有一种情况,就是盒子相同,球不同的问题,并且盒子不允许有空(具体表现为球的个数大于盒子的个数(m>n),并且,m是不同的,上面的例子是n是不同的)。
这个问题是第二类斯特林数,只能用递推实现了,存数学是无法解决的。
用f[i][j]表示i个小球放入放入前j个盒子的不同方法。那么递推公式应该是
F[I][J]=F[I-1][J]*j+f[I-1][J-1];
解释一下:把i个小球放入j个盒子的方案总数等价于第j个盒子本来是空的,把第i个小球放入(f[i-1][j-1]),或者是原来前j个盒子每个盒子都不是空的,那么根据乘法原理应该有(f[i-1][j]*j)的方案总数。
那么第二类斯特林数列的原版题目,vijos上也有,描述如下
笨笨要从他面前的瓮,也就是所谓的大坛子里面捉足够数量乌龟……呃……鳖出来那去卖~~
大坛子里的鳖是可以无限捉的,谁叫这些鳖在瓮里面啊~但是笨笨只需要n只鳖就够了。
现在有m个瓮在笨笨面前,他要从这些瓮中捉鳖出来,每个瓮至少捉一只鳖。
因为鳖太多了,所以笨笨想知道,他有多少种方法从这些瓮中捉鳖去卖。(这两者有关系吗?)
输入有多行,每行两个数n,m(0<=n,m<=100)。
输出有多行,每行对应一个输入,每行输出一个捉鳖方法总数
Sample input
6 3
3 2
Sample output
90
3
这道题是需要高精度的,只不过我们要做的是先把所有的情况求出来,最后在读数输出(换句话说,读数输出的时候也就是在查表);
上面的例题,讲的是,小球不同,而盒子相同的问题。
后来我在做到vijos上又发现一题,是盒子不同,小球也不同的问题了。(当然,这里不允许有盒子是空)
等等,说到这里,我觉得有必要解释一下为什么要盒子不允许有空的问题了,很简单,如果盒子允许有空,也就没必要做了,不是在假象一个盒子,而是用乘法原理直接ac了,由于每个盒子的不同,所以对应的没个小球都有n种方法,所以,也就有m^n种方案了。
实际上,这也是一道斯特林数的一个应用,上面的例子说到了盒子相同而球不同的方案,这道题目把它改成了球也不同,盒子也不同了。实际上,我们在遇到这道题目的时候可以假设一下,假设箱子相同,那么最后的答案会是多少?求出了这个答案,最后只要乘以一个箱子的全排列也就ok了。这里,我曾经问过为什么不能是小球的全排列,最后在用插板法啊!!
呵呵,后来把这问题也弄明白了! 注意到这里,我们用的是盒子包含了球,也就是说盒子是在外面的,这样保证了最后乘以盒子的全排列才能保证结果的正确性。如果是乘以球的全排列会出现重复的问题,举个例子来说,假设有2个小球和一个箱子,把这两个小球放进箱子的方案个数是1种(不用笔就可以推出来了,就是把2个球都扔到盒子里啊);如果,我们乘以小球的全排列,最后的答案也就是2了,为什么会造成这种情况呢?我们可以分析一下盒子的里面放入小球的情况。同一个盒子放入1 2 和放入 2 1(这里的1 2表示小球的编号)是同一种方案,所以会发生重复,这也就是我在前面提到的,盒子包含了小球的,所以乘以小球的全排列才会是正确的,而小球的全排列会在盒子的内部出现重复计算的情况。这道题目在vijos上也有,这里就不做分析了。
剩下最后的一种情况没有说了,也就是不管是盒子还是小球都是相同的。
为了解决这个问题,我们可以保证所有的盒子中小球放入的是一个不下降的一个序列,也就是说,放入盒子的小球数目分别是x1 x2 x3……xn;且保证x1<=x2<=x3……<=xn,这样就可以避免小球相同的问题了。
实际上,这道题目是我们非常熟悉的一道题目,也就是数的划分,可以这样假象一下,把要划分的数n看成n个一样的小球,把需要划分成的集合个数m看成是m个箱子,这样也就和这道题目基本相同了。
关于方程,就是f[i][j]=f[i-1][j-1]+f[i-j][j]
实际上有裸搜也是可以过的,我有试过。
上面的很多问题都没有提到盒子为空或者是允许有小球不全部放入盒子中的问题,这些都无关紧要,因为在第一例子中我都已经阐明了做法,大致都是一样的,所以这里就不做诠释了。