Re: [其他] rook polynomial
※ 引述《wsx02 ()》之銘言：
: (1) Find the number of ways 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
: 它的rook polynomial = 1 + 8x + 24x^2 + 36x^3 + 29x^4 + 12x^5 + 2x^6
: 字母視為相異時 排列數 = 1*6! - 8*5! + 24*4! - 36*3! + 29*2! -12*1! + 2*0!
: 最後結果在除以2! 因為兩個P相同
: (2) http://ppt.cc/bePg
: 它的rook polynomial = 1 + 8x + 20x^2 + 17x^3 + 4x^4
: 方法數 = 1*5! - 8*4! + 20*3! - 17*2! + 4*1!
: 請問為什麼一題是從(最高次方)!開始 另一題是(最高次方+1)!開始?
: 差異在哪邊呢? 還是書上有解錯? 謝謝
我想你可能有點誤解~~~
舉個簡單例子好了::
現有甲乙丙三人排成一列，要求甲不能排在第一位，問有幾種排法??
我想答案很清楚是 3! － 2! = 4
(全部) (甲排首)
用棋子多項式的話，禁區只有一個方格，所以它的 rook polynomial 為
1+x
只有這樣，最高次數為 1 ，但是計算時還是
1*3! － 1*2!
運用棋子多項式，計算出禁區之後，接著用排容原理，
(全部排列)-(有一個在禁區)+(有兩個在禁區)-(有三個在禁區)+......
而 x^k 的係數就是有 k 個在禁區的總方法數。
第一個所需要的階乘數跟棋子多項式的次數沒有關係。
回到你所提出的問題
第一題，因為總共有 6 個字母，所以全部排列數是 6! ，
有一個在禁區，表示剩下 5 個任意排列為 5! ，依此類推......
第二題，因為只有 4 女但有 5個男的，所以假想有另一名女的，
這個女的就沒有任何限制，因此全部排列就是 5! ，依此類推......
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.162.85.12
※ 編輯: oldblackwang 來自: 1.162.85.12 (05/22 17:29)
推
05/22 19:28, , 1F
05/22 19:28, 1F