推 rainyuhtree:謝謝 06/10 20:21
※ 引述《rainyuhtree (ianyu)》之銘言：
: n個字母 的括號數 個數
: 我知道是公式解
: 跟n個node 產生的二元樹個數
: 是同一種公式解
: 但我想問一下
: 針對n個字母來解說
: 公式的緣由
: 或者可以提供相關網頁給我看
: 謝謝
用遞迴推導 :
令 a_n 為 n項 的括號方法數
a_n = a_r * a_n-r
= 先對前r項括號數 * 再對後n-r項括號數
其中 1 ≦ r ≦ n-1
因此可寫成
a_n = a_1*a_n-1 + a_2*a_n-2 + ... + a_n-2*a_2 + a_n-1*a_1
且 a_0 = 0 , a_1 = 1
接著用生成涵數
令 G(x) = Σ(a_n * x^n)
= Σ((a_1*a_n-1 + a_2*a_n-2 + ... + a_n-1*a_1) * x^n)
....過程就不贅述....
解得 G(x) = Σ(1/n)*C(2n-2,n-1)*x^n
故 a_n = (1/n)*C(2n-2,n-1)
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.133.199.28
※ 編輯: svanavs 來自: 220.133.199.28 (06/09 19:14)