[理工] 離散 排容

[clonsey1314 (Clonsey)]

1. (台大工科)
26個不同英文字母排列, 有幾種排列是沒有"USA"和"SAP" pattern的?

答案給: 26! - 2 x 24! + 22!

我寫: 26! - 2 x 24! + 23!
想法是, 如果同時有"USA"和"SAP", 表示有"USAP", 所以同時擁有此2個pattern的排列數共26-4+1=23種
而答案是把2個pattern分開, 共26-6+2=22個不同物排列
請問是哪個正確?

2. (102中山電機)
Find the number of permutation of the letter x, x, y, y, z, z so that no x appears
in the first and second positions, no y appears in the third position, and no z
appears in the fifth and sixth positions.

答案:
1/(2!2!2!) x (6! - 10 x 5! + 36 x 4! - 56 x 3! + 36x 2! - 8 x 1!)

括號中是把6個字母當相異物的排列種數, 想問為甚麼可以直接先求完禁位排列數, 再除以相同物的排列數?
例如當第二項"10 x 5!", 當有一個在禁位, 這樣就只剩下2種相同物, 為何還要多除一個2! ?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.163.181.227
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1512909006.A.C48.html
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 20:35:08
推 TampaBayRays: 第一題我的想法跟你一樣
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 21:02:49
推 winiel559: 第一題答案給錯了吧
感謝樓上大大們!
→ TMDTMD2487: 他是直接用棋盤多項式幹下去吧
→ TMDTMD2487: 而且你用排容去算第二項答案是5*5!/(2!2!)
→ TMDTMD2487: 這題我自己做的時候還不是很會用rook polynomial
→ TMDTMD2487: 所以我是排容硬幹的 XD
對, 那個括號是城堡多項式的結果, 現在知道原因了,禁位的種數也有可能會重複! 感謝!
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 21:53:40
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 23:31:25