2009-12-07

[離散] 排列組合

Find the number of way to arrange the letters in LAPTOP so that none
of the letters L,A,T,O is in its original position and the letter P is not in the
third or sixth position


請問怎麼列式子，想用亂序or排容去做，但覺得考慮的都不夠周延



答案是給84


謝謝
於

9 則留言:

  1. AIdrifter2009年12月7日 晚上11:51

    我比較賤一點
    因為P不在3 or 6的位置
    我把這句話等價於 P不在5 or6的位置
    這樣我會比較好想

    然後因為P不在5or6的位置
    所以他在前4個
    用C4取2 取前面4個
    因為一樣 所以不用乘2!
    接下來就要考慮LATO
    有沒有重複的人在裡面了 總共有3種情形

    ie 現在剩下 T O的空位
    一種可能是TO坐在TO位置
    第二種可能是TO不坐在TO位置
    這樣就是
    D2*2!+2!*2!
    至於第三種就是最討厭的
    還有一種可能是T or O其中一個在裡面的 幸好只有兩個位子(TO) 所以不用考慮太多
    剩下TL TA OA OL 這四個會坐在TO的情形 在TO位置上 他們只有一種可能
    而右邊2個位置 就可以隨便排囉 於是
    4*2!

    所以總共是

    C4取2*(D2*2!+2!*2!+4*2!)


    哀 其實這題我是事後諸葛
    如果有更好想法希望大家能提出來
    坦白講考試我有辦法想這麼細簡直是見鬼了 一一"
    偷偷告訴你
    我第一次算忘記考慮第三種情形

    回覆刪除
  2. 線代離散助教(wynne)2009年12月8日 凌晨12:42

    [法一] 令
    a1 : P 在第 3 個位置
    a2 : P 在第 6 個位置
    a3 : L 在第 1 個位置
    a4 : A 在第 2 個位置
    a5 : T 在第 4 個位置
    a6 : O 在第 5 個位置
    N(!a1!a2...!a6) = s0 - s1 + s2 - s3 + s4 - s5 + s6
    = 6!/2! - (2*5! + 4*5!/2!)
    + (c(4,2)4!/2! + (c(6,2)-c(4,2))4!)
    - (c(4,3)3!/2! + (c(6,3)-c(4,3))3!)
    + (c(4,4)2!/2! + (c(6,4)-c(4,4))2!)
    - 6 + 1
    = 84

    [法二]
    令 Dn 為 n 個 positions 之亂序,
    則總數就是 (D6 - 2*D5 - D4)/2!
    = (265-88-9)/2! = 84

    這裡我想法上是先把兩個 P 視為不同, 式子中的D6是全部的字母先做亂序排列, 2*D5 代表的是恰一個 P 跑到另一個 P 的位置, D4 就是指那兩個 P 互換位置, 而最後因為要除掉P的排列重複算的部分, 所以除以2!

    回覆刪除
  3. AIdrifter2009年12月8日 凌晨1:01

    覺得法二超棒的XD

    請問另一個P跑到另一個P這句話
    可以當作一個留在原位嗎?
    是我中文解讀問題啦
    因為想說P都相同跑過去好像沒差

    回覆刪除
  4. 線代離散助教(wynne)2009年12月8日 凌晨1:27

    算的時候因為那個數會是一樣的, 所以這樣想ok, 不過在寫法上就不能那樣說明, 因為我一開始是假設大家都做亂序了再去扣的, 所以理論上不應該有人留在自己的位置上

    回覆刪除
  5. Chesley2009年12月8日 上午11:44

    謝謝兩位熱心幫忙~~

    考試時感覺只能用排容硬做，不過我自己寫的時候，排容還是有漏~~XD

    回覆刪除
  6. Chesley2009年12月8日 晚上8:14

    不好意思，想在請問用排容解法

    因為我列出來的不一樣，但不知道錯在哪

    N(!a1!a2...!a6) = s0 - s1 + s2 - s3 + s4 - s5 + s6
    = 6!/2! - (2*5! + 4*5!/2!)
    +(c(4,2)*4!/2! + c(4,1)c(2,1)*4! + c(2,2)*4!)
    +........-6+1

    主要是第二行列出來的跟助教差很多

    看不懂助教這邊

    (c(4,2)4!/2! + (c(6,2)-c(4,2))4!)

    後面為什麼是 c(6,2)-c(4,2) 4!

    我想法是要挑出兩個
    P不挑 P挑一 P挑二
    感覺影響的只有差在要不要 /2!


    不知道要怎麼想才對

    回覆刪除
  7. 線代離散助教(wynne)2009年12月9日 凌晨12:27

    c(4,2)4!/2! + (c(6,2)-c(4,2))4! 前面的部分是在考慮從a3,a4,a5,a6中取兩個使其成立的情況, 後面的則是在算有a1或a2成立時的情況: c(6,2)-c(4,2)指的是在a1,...,a6中任取兩個成立, 再扣掉我們前面已經算過的 a3,a4,a5,a6 中取兩個成立的個數, 這樣就會是有取到a1或a2的所有可能, 最後剩下的就是 4 個字母做排列 (因為後面這邊是已經抽掉至少一個P了, 所以剩下的 4 個字母不管有沒有 P 都會是全相異, 不用除以 2!)

    這題用排容的確是容易考慮欠周, 所以我自己也是覺得用亂序會比較方便做

    回覆刪除
  8. Chesley2009年12月11日 下午2:09

    結果還是亂序好想~~

    謝謝

    回覆刪除
  9. changyau chen2009年12月27日 晚上8:25

    提供另外一個解法。
    大陸人叫做「正行列式解決瓶頸指派問題」。有興趣可以自己找找。下面舉個例題：有五對夫婦一起為成圓圈，但是規定男女必須相間而且同一對夫婦不得相鄰，請問有多少種排法？

    這題目不用正行列式不好做。不過正行列式如果超過五階，很難用筆算，所以考試的時候也未必派的上用場。

    但是如果用程式來算，這是最好的辦法。因為解法很固定，不需要任何靈感，傻傻的列式子就可以。

    回覆刪除