題目

劉新宇老師前不久在“圖靈社區:同構——分紅包問題”中給出:

高個子舅舅春節回家,想給三個可愛的孩子小明、小強、小紅一些紅包用來買過年的玩具。他準備了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 種方法。