Re: [理工] [離散]-生成函數

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

※ 引述《assassin88 (Ace)》之銘言：
: Let x,y,z,w >= 0, and w is odd integer.
: w + 2x + 2y + 5z = 30
: What is thenumber of solution to find by generating-function.
: 有點奇怪的解..麻煩指導了~感謝
---

    考慮
                                         2
    f(x) = (x+x^3+x^5+...)(1+x^2+x^4+...) (1+x^5+x^10+...)

             x          1          1
         = ─── * ───── * ───   for  |x|<1
           1-x^2    (1-x^2)^2    1-x^5

             x           1
         = ─── * ─────
           1-x^5    (1-x^2)^3

               ∞  5k      ∞   r+2   2r
         = x * Σ x     *  Σ  C     x
              k=0         r=0   2


    滿足   1+5k+2r = 30 的非負整數解有

    (k,r) = (1,12) 、 (3,7)  、  (5,2)


    因此根據加法原理

     x^30 的係數  =  C(14,2) + C(9,2) + C(4,2)    即為所求




--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.141.151
推 wassili:應該不用乘-1那項吧..還是我哪裡疏忽了@@?
→ EntHeEnd:後密那邊為什麼有(-1)^r @@ ?
→ EntHeEnd:我算出來是那三個組合數相加
    三個相加沒錯

    因為我係數都是記  C(-3,r) (-x^2)^r

    C(-3,r) = C(r+2,2)*(-1)^r

    忘了把  (-1)^2r 拿掉了QQ
※ 編輯: doom8199        來自: 140.113.141.151      (02/24 15:28)
→ doubleday:我算也是三個組合數相加    是190嗎？
→ crazyjoe:133?
※ 編輯: doom8199        來自: 140.113.141.151      (02/24 15:28)
→ EntHeEnd:XD 剛剛我第三個組合數算錯了
→ EntHeEnd:mm 133
推 assassin88:這方法我懂了~想請問一下 如果在最後解可能性的式子很
→ assassin88:大時，比如1+6x+7y+11z~~  有什麼其他方法嗎？還是只能
→ assassin88:近似暴力法求可能解？
推 polomoss:跳過這題