發新話題
打印

排列組合-遊戲停止的方法數

推到噗浪
推到臉書
遊戲停止的充要條件,即某時刻甲與乙共移動5塊地磚。
因此,可與 5 分割成若干個"1,2,3"之和做聯想,依題意,次序不同(如 2+3 與 3+2)視為不同。


例如,
5 = 2 + 3 對應: 甲移動2,乙移動3,結束。
5 = 3 + 2 對應: 甲移動3,乙移動2,結束。
5 = 1 + 3 + 1 對應: 甲移動1,乙移動1,甲移動3,結束(奇數個分割時,甲多走一次)。


5 分割成若干個正整數之和的方法有:
C(4,0) + C(4,1) + C(4,2) + C(4,3) + C(4,4) = 2⁴ = 16種。
扣掉不屬於{1,2,3}之分割: (5),(4 + 1),(1 + 4) 共3種。
因此有 16 - 3 = 13 種。


[我猜 "15" 大概是由 C(4,1) + C(4,2) + C(4,3) + C(4,4) = 2⁴-1 = 15 得出,忘了扣除不合的: (4 + 1),(1 + 4)。]


註: 對於正整數 n>1,將 n 分割為 m 個 (m≤n) 正整數之和 (次序不同視為不同)的方法數有 C(n-1,m-1) 種 (在 n-1 個間隔放入 m-1 個隔板)。或者用 H(m,n-m) = C(n-1,n-m) 亦同。




在下不是數學老師,有錯敬請指正。



TOP

發新話題