Re: [理工] [離散]-遞迴

[doom8199 (～口卡口卡 修～)]

※ 引述《assassin88 (2010)》之銘言：
: For n >= 1, let an be the number of ways to write n as an ordered sum of
: positive integer where each summand is at least 2.
: 請問這一題要怎麼想？
: 完全沒有idea..麻煩指導了~感謝！

---

    假設  x^n 的係數為題目所求

    則考慮以下生成函數:

              ∞
    f(x) =    Σ  (x^2 + x^3 + x^4 + ...)^k
             k=1

              ∞    x^2   k
         =    Σ ( ───)        if ｜x｜<1
             k=1   1 - x

              ∞  2k  ∞             m
         =    Σ x    Σ C(-k,m)*(-x)
             k=1     m=0

              ∞  ∞             m  2k+m
         =    Σ  Σ C(-k,m)*(-1)  x
             k=1 m=0


                     (-k)(-k-1)...(-k-m+1)
    where  C(-k,m)≡ ──────────
                             m!


                                          m
    因此  x^n 的係數 =    Σ   C(-k,m)(-1)
                       n=2k+m

                       [n/2]               n-2k
                     =   Σ  C(-k,n-2k)(-1)
                        k=1

                      即為所求

----


    例如當 n=8

    有以下拆法:
                  8
                  6 + 2
                  2 + 6
                  5 + 3
                  3 + 5
                  4 + 4
                  4 + 2 + 2
                  2 + 4 + 2
                  2 + 2 + 4
                  3 + 3 + 2
                  3 + 2 + 3
                  2 + 3 + 3
                  2 + 2 + 2 + 2
                                        共 13種


    根據前面的推導

    有    C(-1,6) + C(-2,4) + C(-3,2) + C(-4,0)

       =  1 + 5 + 6 + 1

       = 13  種拆法



    希望沒搞錯題意 OTZ

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.64.93.41
※ 編輯: doom8199        來自: 61.64.93.41          (02/07 20:15)
→ assassin88:答案是對的~可是不懂你生成的式子為什麼是這樣列？
→ doom8199:你可以把 x^2、x^3、... 都當成是一個 "物件"
→ doom8199:所以 (x^2 + x^3 + x^4 + ...) ← 這樣寫的意思
→ doom8199:就有點像是從中選取一個物件
→ doom8199:選到 x^2 就代表吾人選取 2當作一個 summand
→ doom8199:k次方的意思，可以解讀成 "把n這個數拆成 k個數字"
推 assassin88:我懂你的意思了~不過第三個等式後面怎麼變出來的= =
→ doom8199:因為可以只拆一個數字，也能拆多個數字
→ assassin88:(1-x)^-n不是等於ΣC(n+r-1 r)x^r 嗎>?
→ doom8199:都對阿，那個是利用泰勒展開得來的
→ doom8199:我只是習慣這種寫法= =a
推 assassin88:我可能等級太低..不知道怎麼從同變數拆出兩個(k,m)ˊˋ
→ doom8199:你那樣寫是把 (-1)^r  併到 C(-n,r) 得來的
→ assassin88:我指的是..他們原本不是都同屬Σk=1~~怎麼拆成兩個的?
→ doom8199:不太懂 = =ll  ,你是指哪一步有問題?
推 assassin88:ㄜ..第三個等號後面Σm..這邊原本不是都k? 該怎麼使用
→ doom8199:就泰勒展開，有時候會把它當成廣義的二項式定理
→ doom8199:接著就是算出 x^n 項的係數
→ doom8199:因此只要把滿足 n=2k+m 的所有 (k,m)都算出來即可
推 EntHeEnd:這是利用生成函數解整數分割問題吧 ?
推 JMD:問一下d大是數學系的嗎?
→ doom8199:不是XD
→ assassin88:我研究不出來= = ... 這是越級打怪嗎XD
→ doom8199:(1-x)^(-k) = Σ C(-k,m)*(-x)^m   這個@@?
→ doom8199:http://en.wikipedia.org/wiki/Binomial_theorem
→ doom8199:往下拉到 Newton's generalized binomial theorem
→ doom8199:型態跟維基百科上的 (x+y)^r 展開式完全一樣
→ doom8199:對應上面的符號，就是 (x,y,r) ←→ (1,-x,-n)
→ doom8199:打錯，是  (x,y,r) ←→ (1,-x,-k)
推 assassin88:我的意思是 變數可以換?原來上一式是k..下面可以轉成m?
→ doom8199:不懂你的問題所在 OTZ