排容原理(I.E.P.)

2014-10-25 6:00 am
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.

Sol: 84


請列過程,簡短精確說明,不要將解題過程複雜化。
更新1:

此題能否使用「亂序(derangement) +其餘限制」 解題?

更新2:

...PIE

回答 (2)

2014-10-25 8:51 am
✔ 最佳答案
Choosing two positions from LATO for 2P, it will be C(4,2) methods. Then, arrange the LATO for the rest four positions,
and exclude tow of the four letters in their original positions,
this leads to 4! – C(2,1)3! + C(2,2)2! So, the net way for the required rearrangement is C(4,2)( 4! – C(2,1)3! + C(2,2)2!) = 84
2014-10-25 6:47 pm
[法一] 令
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!


收錄日期: 2021-04-27 21:28:38
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20141024000015KK06802

檢視 Wayback Machine 備份