Re: [理工] [離散]用生成函數解遞迴

看板Grad-ProbAsk作者doom8199 (～口卡口卡　修～)時間12年前 (2012/01/07 19:18)推噓3(3推 0噓 0→)

留言3則, 3人參與討論串2/3 (看更多)

※ 引述《dingfun (頂方)》之銘言： : 題目是An- 2An -1 = 6n^2 , A0=1 求An： : ∞ ∞ ∞ : 我是先 ΣAn(X^n) - 2ΣAn-1(X^n) = Σ(6n^2(X^n)) : n=1 n=1 n=1 : 等號左邊照往常，會算出A(x)(1-2x)-1 : 而右邊，我的想法是用生成函數的概念 : ∞ ∞ 6x+6x^2 : Σ(6n^2(X^n))=6Σ(n^2(X^n))=--------- : n=1 n=1 (1-x)^3 ↓ 這裡是 + : 37 -18x^2 - 42x -36 : 所以求得A(x)=------ + -------------------- : 1-2x (1-x)^3 : 後面我就不會算了..... : 答案是An = 37*(2^n) - 36 - 24n -6(n^2) : 因為算出來(2^n)的系數是對的，所以我覺得我的想法應該沒有錯 : 還是，我徹頭徹尾的錯了咧= =" : 感謝耐心看完!!!快考試了大家加油!!! ---- ∞ n 原po想法並沒有錯，您只是缺少背幾個公式: ( 令 GF{A[n]} = Σ A[n]x ) n=0 1 GF{1} = ─── , │x│< 1 1 - x x GF{n} = ──── , │x│< 1 (1-x)^2 x(x+1) GF{n^2} = ──── , │x│< 1 (1-x)^3 1 GF{a^n} = ─── , │x│< 1/│a│ , a≠0 1 - ax GF{A[n-1]} = x*GF{A[n]} + A[-1] -------- 有了上面的公式: A[n] - 2A[n-1] = 6n^2 , A[0]=1 6x(x+1) => G(x) - 2[xG(x) + 1/2] = ──── ( Note that GF{A[n]} := G(x) ) (1-x)^3 6x(x+1) => (1-2x)G(x) = 1 + ──── (1-x)^3 1 6x(x+1) => G(x) = ─── + ─────── (1-2x) (1-2x)(1-x)^3 1 36 -18x^2 + 42x -36 = ─── + ─── + ──────── (1-2x) (1-2x) (1-x)^3 37 -6x(x+1) - 24x(1-x) - 36(1-x)^2 = ─── + ─────────────── (1-2x) (1-x)^3 n 2 => A[n] = 37*2 - 6n - 24n - 36 (n≧-1) ps: 生成函數解遞迴式並不慢慢的是沒有把一系列的公式背下來並熟練這就跟用 Laplace Transform 算 ode 一樣若只從原始定義出發，一定會算很久 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.113.211.139

推

pikachu123

01/07 19:30, , 1^F

01/07 19:30, 1^F

推

justbelieve

01/07 19:58, , 2^F

01/07 19:58, 2^F

令 f(x) = -18x^2 + 42x - 36 = ax(x+1) + bx(1-x) + c(1-x)^2 ┌ f(1) = -18+42-36 = 2a │ f(0) = -36 = c └ f(-1) = -18-42-36 = -2b + 4c 解一下聯立就出來了

推

dingfun

01/07 23:10, , 3^F