請問離散課本3-45頁例29的(a)小題
一組字母:SURREPTITIOUS
問:exactly three pairs of consecutive identical letters?
我的方法是: (C是指組合公式，P是排列公式)
先拿掉兩組不可排在一起的字串:C(5,2)
接著將三組一定要排在一起的字串綁定跟剩下三個獨立字母作排列:6!
然後兩組不可排在一起的字串插空隙:P(7,4)/2!2!
除掉兩個2!是因為有兩對字母一樣，
所以最後算法變這樣:
C(5,2)*(P(7,4)/2!2!)=1512000
而老師排容解出來的答案為5846400
我知道我大概有地方沒考慮到，
所以想請問怎麼單純地用排列和組合解出此題
4 則留言:
你的盲點在於P(7,4)那兒：
想要達成題目的要求，並不需要選出四個空位，即使只有一個空位，只要排成OXOX或XOXO也可行。
感謝助教，一語道破我的盲點
其實我上面也打錯了，應該是
C(5,2)*(6!*P(7,4)/2!2!)
根據助教告訴我的不需要空出四個空位
我把算式修改如下
C(5,2)*(6!*P(7,2)/2!*P(9,2)/2!)
我的想法是不讓四個字母去找空隙
而是先讓兩個同樣的字母找空隙
這兩個字母找完後，再把另外兩個同樣的字母插入空隙(因前面兩字母，現在有九個空隙)
答案算出來為:5443200
雖然已經接近答案了，不過還是錯的
請問這樣的想法，問題又出在哪裡呢
P(7,2)有問題，因為兩個相同的字母有可能可以同時放在一個空隙裡面，例如XXX00XXX
兩個"0"放在同一個縫隙裡面，接下來再插入另外兩個相同的字母"*"，變成XXXX0*0XX*XXX，這樣也是合法的，你的方法數就會比較少，就是少了這種狀況
感謝Janja大，又替我找出了一個盲點
我把您說的情況考慮了進去，修改算式為
P(7,2)/2!*P(9,2)/2!+P(7,1)*P(8,1)
在將上式結果乘上6!和C(5,2)
後面多加了P(7,1)*P(8,1)
主要是加入兩個會排在同一個空隙的情況，
綁定他們讓他們排在同一個空隙為:P(7,1)
然後再讓另外兩個字母，一個一定要排在他們的中間隔開他們，另外一個再插空隙
此為P(8,1)
答案算出來也跟排容一樣:5846400
張貼留言