【欧拉计划】一个组合问题

Balls_Banner
Standard

前几天又开始刷欧拉计划,遇到一道很有意思的题,把它化简之后,核心在于解这样一个组合问题:

一个袋子里有4个红球、2个蓝球,按顺序从中取出不多于2个球,问有多少种结果?(计取出顺序,且认为同色球都相同)

全部列出来就知道共有6种组合,分别是r, b, rr, rb, br, bb。

推广到一般情形,即:

有 $m$ 种不同的元素,分别有 $n_1, n_2, \ldots , n_m$ 个,其中 $n=n_1+n_2+\ldots+n_m$ 。现在要从中取出不多于 $L$ 个,问有多少种可能的取法?

对于 $m=2, n_1=4, n_2=2, L=2$ 的情形,结果是6。

那对于一般的情形,又该如何计算这个值呢?

下面我将给出两种解答这个问题的思路:第一种是我当时解答这个问题的思路,第二种则是在论坛里看到的高人的解答。

Continue reading