Re: [中學] 排列組合
※ 引述《farewell324 ()》之銘言：
: 題目如下：
: 有兩個鄰近小鎮在接下來的七天要分別停水2天
: 但兩小鎮不能同時停水、任一小鎮也不能連續兩天停水
: 請問共有幾種安排停水的方式？
: 我的做法就土法煉鋼的討論
: 但萬一數字放大應該就非常困擾
: 想請教有沒有適合的想法與做法
: 謝謝！
設總共有 n 天，A小鎮要停水 a 天，B小鎮要停水 b 天
兩小鎮不能同一天停水，任一小鎮不能連續兩天停水
令 x = n - a - b
則這個題目實際上就是 a個A b個B x個X 的排列組合 不能AA或BB
先排一排a個A 會產生 2個邊邊空位 和 a-1個中間空位
接著要排X進去 X不見得也不需要把A隔開
以下根據中間空位會剩幾個來分情況：
假設中間空位會剩d個 被填滿的中間空位會有c = a - 1 - d個
選擇哪些中間空位被填滿 有 C(a-1, c) 種可能
x個X要排進c個中間空位(至少一個)和2個邊邊空位(至少零個)
這是重複排列 H(c+2, x-c) = C(x+1, x-c)
全部排完之後 總共會有a+x個A或X
所以會有 2個邊邊空位 d個AA空位 以及 a+x-1-d = c+x 個普通中間空位
現在要排B進去 B必須要把A隔開 不能同時塞兩個B進去
d個AA空位都要各塞一個B 因此會剩下b-d個B 要塞 c+x+2個空位
總共有 C(c+x+2, b-d) = C(c+x+2, x+1+a-b) 個選法
看來以上的選法都沒有d 所以我們用c來加總 c的範圍是0到a-1
答案是 SUM_(c=0)^(a-1) C(a-1, c) C(x+1, x-c) C(c+x+2, x+1+a-b)
丟進計算機跑出generalized hypergeometric function 我看還是不要化簡好了
現在 a=2, b=2, x=3, c從0加到1
C(1, 0) C(4, 3) C(5, 4) + C(1, 1) C(4, 2) C(6, 4) = 4*5 + 6*15 = 110
--
嗯嗯ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1476423530.A.05A.html
→
10/15 00:15, , 1F
10/15 00:15, 1F
討論串 (同標題文章)
