Re: [離散] 生成函數
※ 引述《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
→
12/21 15:03, , 1F
12/21 15:03, 1F
→
12/21 15:03, , 2F
12/21 15:03, 2F
推
12/21 18:55, , 3F
12/21 18:55, 3F
===
題目只有要求寫出 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)
討論串 (同標題文章)