2007-08-14

[離散][5.4生成函數法]關於導出Dn亂序遞迴

我想問的是
我的思考過程有沒有錯誤

首先假設N個物品要亂序好了

物品：1...i...n
位置：1...i...n

(1)
1放在i，i恰好放在1
的狀況下，只需要考慮剩下的n-2樣物品 --> Dn-2

(2)
1放在i，i沒放在1
的狀況下
相當於扣除物品1的 "n-1" 樣物品，以亂序方式擺在 "n-1" 個位置
如同 "n-1" 樣物品做亂序 --> Dn-1

到這邊為止不知道有沒有問題＠＠"？
於

3 則留言:

  1. Brian2007年8月14日 中午12:25

    應該是沒有錯~
    第二個在說清楚一點就是
    物品1放在位置i 然後物品i把位置1視為自然位置
    所以共有n-1個物品再做亂序
    如果我的想法有錯誤麻煩各位提出見解囉~

    回覆刪除
  2. 貴先生2007年8月15日 凌晨3:52

    作者跟elvis說的都沒錯,不過根據標題來看,生成函數解Dn重點應該是在用指數生成函數求出Dn的Close form那一段...

    回覆刪除
  3. 拉拉草2009年9月30日 中午12:51

    哈囉, 去年我也是黃老師的學生, 不過從來沒上過這邊, 剛剛在找亂序問題時無意間發現這邊, 便來留個言, 順便請教一個題目, 是關於"再"亂序好幾次的問題:
    有20個人, 20本書,
    每人每次借一本, 不重覆借,
    20次後的方法數.

    mail: s9862607@m98.nthu.edu.tw

    回覆刪除