[理工] 離散 排容

看板Grad-ProbAsk作者 (Clonsey)時間8年前 (2017/12/10 20:30), 8年前編輯推噓2(2推 0噓 4→)
留言6則, 3人參與, 8年前最新討論串3/4 (看更多)
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
推
12/10 20:38, 8年前 , 1F
第一題我的想法跟你一樣
12/10 20:38, 1F
※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 21:02:49
推
12/10 21:09, 8年前 , 2F
第一題答案給錯了吧
12/10 21:09, 2F
感謝樓上大大們!
→
12/10 21:42, 8年前 , 3F
他是直接用棋盤多項式幹下去吧
12/10 21:42, 3F
→
12/10 21:45, 8年前 , 4F
而且你用排容去算第二項答案是5*5!/(2!2!)
12/10 21:45, 4F
→
12/10 21:49, 8年前 , 5F
這題我自己做的時候還不是很會用rook polynomial
12/10 21:49, 5F
→
12/10 21:49, 8年前 , 6F
所以我是排容硬幹的 XD
12/10 21:49, 6F
對, 那個括號是城堡多項式的結果, 現在知道原因了,禁位的種數也有可能會重複! 感謝! ※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 21:53:40 ※ 編輯: clonsey1314 (1.163.181.227), 12/10/2017 23:31:25
‣ 更多 clonsey1314 的文章
文章代碼(AID): #1QBIZEn8 (Grad-ProbAsk)
‣ 更多 clonsey1314 的文章
文章代碼(AID): #1QBIZEn8 (Grad-ProbAsk)