从n个球当中,取出k个球,k个球允许重复出现,问有几种可能。
解答:
假设现在有编号的n个球,每一个编号的球有个,那么会有等式:
,现在问题就转化为该等式一共有多少解
?
这里使用间隔法,即使用(n-1)个分隔符分隔得到n个空间,使得每一个空间之和为k.
假设这里一共有5个球,取3次,那么需要4个分隔符去隔开3个球,这里我们用1代替。
但是很显然,当中每一个数都有可能等于0,所有我们需要凑n个0出来,如图所示:
0_0_0_0_1_1_1_0,这里3个1与5个0一共有(3+5-1)个间隔,需要选择(5-1)个分隔符即可以求出等式的解:
即:
或者
参考资料:
(1)https://zh.wikipedia.org/wiki/%E7%B5%84%E5%90%88#%E9%87%8D%E8%A4%87%E7%B5%84%E5%90%88%E7%90%86%E8%AB%96%E8%88%87%E5%85%AC%E5%BC%8F
(2)https://blog.csdn.net/qq_41035681/article/details/100607712