题目

刘新宇老师前不久在“图灵社区:同构——分红包问题”中给出:

高个子舅舅春节回家,想给三个可爱的孩子小明、小强、小红一些红包用来买过年的玩具。他准备了6个红包,每个里面10元钱。每个小朋友肯定能得到红包,但不一定均分。问一共有几种发的方法。

...

作为扩展,这里有一个思考题:如果可以允许有小朋友没有得到红包,有几种分法?怎样能得到优雅直观的思路?

这个扩展问题是:

三个小朋友分六个红包,共有多少种分法。

解答(方法一)

假设每个小朋友都有无数个分身,从这无数个小朋友中选出六个小朋友,每人领取一个红包,共有

H(3, 6) = C(3+6-1, 6) = C(8, 6) = 28

种分法。这里的 H(n, k) 表示从 n 个允许重复的对象中取出 k 个的组合数,C(n, k) 表示从 n 个对象中取出 k 个的组合数,见“图灵社区:允许重复的组合”。

如果是 n 个小朋友分 k 个红包,显然共有 H(n, k) = C(n+k-1, k) 种分法。

解答(方法二)

按照刘新宇老师在他的文章的评论中给出的思路,同构到珍珠项链问题:

  • 6 颗珍珠,7 段丝线:— o — o — o — o — o — o —

第一刀可以切在这 7 段丝线中的任何一段上,所以第一刀有 7 种切法,切完后变为 8 段丝线:

  • 例如,第一刀切在第 1 段丝线上:— | — o — o — o — o — o — o —

第二刀可以切在这 8 段丝线中的任何一段上,所以第二刀有 8 种切法,切完后变为 9 段丝线:

  • 例如,第二刀切在第 4 段丝线上:— | — o — o — | — o — o — o — o —

第一刀左边的珍珠数就是小明得到的红包数,两刀之间的珍珠数就是小强得到的红包数,第二刀右边的珍珠数就是小红得到的红包数。在上述例子中,小明、小强、小红得到的红包数依次为:0, 2, 4。

由于交换第一刀和第二刀的位置得到的结果是相同的,所以共有 7 x 8 / 2 = 28 种方法。