相異物分相同箱之組合問題

令 7 個相異球存放於三個箱子,每箱均可存 7 球,亦可留空箱,則

(1)先將 7 球視為相同物的情況下進行量之分配法加以分配,則此時共有 8種存放法.(7,0,0)-(6,1,0)-(5,2,0)-(5,1,1)-(4,3,0)-(4,2,1)-(3,3,1)-(3,2,2)

(2)

(7,0,0) : C(7,7)=1

(6,1,0) : C(7,6)xC(1,1)=7

(5,2,0) : C(7,5)xC(2,2)=21

(5,1,1) : C(7,5)xC(2,1)xC(1,1)=21

(4,3,0) : C(7,4)xC(3,3)=35

(4,2,1) : C(7,4)xC(3,2)=105

(3,3,1) : C(7,3)xC(4,3)x1/2=70

(3,2,2) : C(7,3)xC(4,2)x1/2!=105

合計:1+7+21+21+35+105+70+105=365 (種)

C(n+m-1,m-1)

[想法]

假設今天 n = 5 m = 3 (隨便設的兩個數字, 為了方便想像)

可以把這個問題想成有 5個不同顏色的球用 2個相同的火柴棒隔開

結果可能是

3顆球 火柴棒 1顆球 火柴棒 1顆球

或者是

火柴棒 2顆球 火柴棒 3顆球

你可以發現

火柴棒把球隔成 3堆

像第一個例子是 (3,1,1)

第二個例子是 (0,2,3)

就可以把這個例子想成

3個丟到箱子 1個丟到箱子 另1個也丟到另一個箱子

因為箱子是同樣的 所以 3 1 1 跟 1 3 1 或 1 1 3 是一樣的情況也要考慮排除

這樣的話 算式就會是 (5+3-1) ! / (3-1) ! (5- (3-1)) !

= 7! / 2! 3! = C (7,2)

那如果推到 n ,m

n個相異物用 m-1個箱子隔開, 就會分成 m 堆

所以可以知道,

原先您所提的問題

就會是 (n+m-1) ! / (m-1) ! (n-(m-1)) !

所以等於 C(n+m-1, m-1)