Re: [離散] 生成函數

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

※ 引述《ltc510030 (LTC)》之銘言：
: 題目是
: Find the generating function and the number of integer solution for each equation :
:  x1 + 2*x2 + 3*x3 = 30 , 0<=x1,0<=x2,0<=x3
: 目前算到
: A(x) = ( 1/(1-x)^-1)(1/(1-x^2)^-1)(1/(1-x^3)^-1)中找 x^30 的係數，接下來就不知道怎麼解下去，
: 解答是給
: 1+2+4+5+7+8+10+11+13+14+16=91
: 此行是怎麼來的？可以提示或解惑嗎？謝謝
===

   (為了方便書寫， 以下假設 (x,y,z) = (x1,x2,x3) )

        x + 2y + 3z = 30   ,  0 <= x,y,z

   <=>  2y + 3z <= 30  ,  0 <= y,z


    當 z=10:   y <= 0/2   => y in {0}         (num = 1)
       z=9 :   y <= 3/2   => y in {0,1}       (num = 2)
       z=8 :   y <= 6/2   => y in {0,1,2,3}   (num = 4)
       z=7 :   y <= 9/2   => y in {0,1,..,4}  (num = 5)

        ...

    把 num 全部相加就是你那行 total num




  [Note 1]

     若針對 z 的奇偶性做 partition

     得到的數列會是 一等差數列 (公差 = 3)


     例如 當 z is even:  total num = 1 + 4 + 7 + 10 + 13 + 16
                                   = (1+16)*6/2
                                   = 51

             z is odd :  total num = 2 + 5 + 8 + 11 + 14
                                   = (2+14)*5/2
                                   = 40

     所以 非負整數解個數 = 51 + 40 = 91



   [Note 2]

     x + 2y + 3z = n  的非負整數解個數

     可以用生成函數 導出一個漂亮的公式

     結論是: 只要計算  p = (n+3)^2 / 12

             再取 離 p 最接近的正整數 n， 即為 total num

            ( choose integer n such that  │n - p│< 1/2 )


     例如 當 n=30

        =>  p = 33^2 / 12 = 90.75

        所以 n = 91 即為所求

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.33.166.150
→ kiki86151:這題本來就可用排組想 但題目要求用生函…
→ kiki86151:覺得你多開文講其他方法 有點多餘==
推 ltc510030:謝謝doom大提供另外詳細的解法!
===

    題目只有要求寫出 generating function 吧

    並只說要求解的個數 = ? , 沒有限定甚麼方法



      1      1      1
    ── * ───*─── = (1+x+x^2+..)(1+x^2+x^4+..)(1+x^3+x^6+...)
    1-x    1-x^2  1-x^3

                         = p(x)q(x)r(x)

    z = 10 相當於 r(x) 取 (x^3)^10,  再去求 p(x)q(x) 中 x^0 的係數

    得到  x + 2y + 3*10 = 30 的非負整數解個數



    最後得到  1+2+4+5+7+8+10+11+13+14+16

    這篇跟我一開始打的方法，不都是一樣的東西嗎? (加法原理)




    若 k大 你覺得這方法就稱作 "生成函數解法"

    我倒覺得有用跟沒用是一樣的


    因為 generating function 就是從

      (1+x+x^2+..)(1+x^2+x^4+..)(1+x^3+x^6+...)

    推到  1/[(1-x)(1-x^2)(1-x^3)]


    但是求解個數卻又還原回  (1+x+x^2+..)(1+x^2+x^4+..)(1+x^3+x^6+...)

    那  1/[(1-x)(1-x^2)(1-x^3)]  對本題有何任何幫助 ?




    若真的有用

    一定會推導出  1/[(1-x)(1-x^2)(1-x^3)]  展開後

                   (30+3)^2    2                7     (-1)^30
    x^30 的係數為  ──── + ──*cos(20π) - ── + ────
                      12       9               7 2       8


    而非 1+2+4+5+7+8+10+11+13+14+16  這麼 tedious 的式子

※ 編輯: doom8199        來自: 114.33.166.150       (12/21 20:38)