這個是Catalan numbers的遞迴~
用 OGF 來看
suppose g(z)=a0+a1*z+a2*z^2+...+an*z^n+...
且因遞迴式,所以觀察一下[g(z)]^2 和 g(z)
可以得到 g(z)=1+z*[g(z)]^2
然後硬算得 g(z)=2/[1+(1-4z)^(1/2)]
有生成函數後取 [z^n] 即可得解~
有錯誤請指教謝謝
※ 引述《timmys (小毛)》之銘言：
: a0 = 1, a1 = 1
: a2 = a0*a1 + a1* a0 = 2
: a3 = a2*a0 + a1*a1 + a0*a2 = 2+1+2 =5
: a4 = a3*a0 + a2*a1 + a1*a2 + a0*a3 = 5+2+2+5 = 14
: an = a_(n-1)*a0 + a_(n-2)*a1 + ... + a_(n-n)*a(n-1)
: n-1
: = Σ ai*a_(n-1-i)
: i=0
: 1 2n
: = ----- * ( )
: n+1 n
: 1 (2n)!
: = ----- * -------
: n+1 n! n!
: 是的，我把答案寫出來了。
: 但是我導不出來Q_Q
: 可以教教我嘛??
: 其實標題我也不知道該怎麼下，
: 因為這是我在讀資料結構的時後
: 遇到的一題計算題
: 我覺得應該算是離散，但是我也不知道是算哪一個範圍的ORZ
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.127.223.144
※ 編輯: BDK 來自: 140.127.223.144 (12/24 16:18)