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

[pikachu123 (pika)]

                     2
        1          6x+6x
     _______ + _____________
A(x)=  1-2x    (1-2x)(1-x)^3   解到這可以用部分分式去做


令右邊那個為f(x)=      a         b       c        d
                     ______ + _______+_______ +_______
                     1-2x     (1-x)^3 (1-x)^2   (1-x)


通分一下     a(1-x)^3+b(1-2x)+c(1-2x)(1-x)+d(1-2x)(1-x)^2      6x^2+6x
            ______________________________________________ =______________
                        (1-2x)(1-x)^3                        (1-2x)(1-x)^3

                x=1/2帶入 解得a=36
                x=1帶入   解得b=-12
                x=0帶入  ==>a+b+c+d=6
                x=2帶入  ==>-a-3b+3c-3d=36


                把a,b帶入解c,d 得c=-6,d=-18

                    1        36      -12       -6         -18
                  ______ + ______ + _______ + _______ + ________
        所以A(x)= (1-2x)   (1-2x)   (1-x)^3   (1-x)^2    (1-x)

        剩下的就代公式去算

        GF解遞迴比較麻煩通常都是部分分式
        不然其實也是蠻快的


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 1.162.155.113
※ 編輯: pikachu123      來自: 1.162.155.113        (01/07 20:23)
推 justbelieve:感謝,了解了,我本來以為是拆成一次一次的,原來是觀念
→ justbelieve:錯誤!
→ pikachu123:你要拆成分子都是常數 有x的你不會做的
→ pikachu123:我有背的公式只有等比XD 分子是好幾項相乘
→ pikachu123:就全部拆掉
→ pikachu123:                        母打錯