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
謝謝
Research Space for Linear Algebra & Discrete Mathematics
9 則留言:
我比較賤一點
因為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!)
哀 其實這題我是事後諸葛
如果有更好想法希望大家能提出來
坦白講考試我有辦法想這麼細簡直是見鬼了 一一"
偷偷告訴你
我第一次算忘記考慮第三種情形
[法一] 令
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!
覺得法二超棒的XD
請問另一個P跑到另一個P這句話
可以當作一個留在原位嗎?
是我中文解讀問題啦
因為想說P都相同跑過去好像沒差
算的時候因為那個數會是一樣的, 所以這樣想ok, 不過在寫法上就不能那樣說明, 因為我一開始是假設大家都做亂序了再去扣的, 所以理論上不應該有人留在自己的位置上
謝謝兩位熱心幫忙~~
考試時感覺只能用排容硬做，不過我自己寫的時候，排容還是有漏~~XD
不好意思，想在請問用排容解法
因為我列出來的不一樣，但不知道錯在哪
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!
不知道要怎麼想才對
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!)
這題用排容的確是容易考慮欠周, 所以我自己也是覺得用亂序會比較方便做
結果還是亂序好想~~
謝謝
提供另外一個解法。
大陸人叫做「正行列式解決瓶頸指派問題」。有興趣可以自己找找。下面舉個例題：有五對夫婦一起為成圓圈，但是規定男女必須相間而且同一對夫婦不得相鄰，請問有多少種排法？
這題目不用正行列式不好做。不過正行列式如果超過五階，很難用筆算，所以考試的時候也未必派的上用場。
但是如果用程式來算，這是最好的辦法。因為解法很固定，不需要任何靈感，傻傻的列式子就可以。
張貼留言