推 sansia :T_2=2 吧? 樹根+左子 或 樹根+右子 08/17 20:02
不對
補充這些小樹的長相 ●=internal ■=external
T_0 = 0, T_1 = 1, T_2 = 1,
不存在 ■ ●
/ \
■ ■
T_3 = 2,(這才是sansia說的 樹根+左子 或 樹根+右子)
● ●
/ \ / \
● ■ ■ ●
/ \ / \
■ ■ ■ ■
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.25.198
※ 引述《weeeeeeeeell (等雨停)》之銘言：
※ 引述《biglongtoday (大長今)》之銘言：
: 看到上面的文章突然想到的
: 2n
: n個節點 可以組合出( ) 不同的二元數
: n
: --------
: n+1
: 以前只是記下來 不知道怎推理的
: 麻煩各位一下 謝謝
1. google "catalan number" "rooted binary tree"
2. 先定義T_n為n個外部節點的二元有根樹個數
T_n := # of binary trees with N external nodes.
一些小樹
T_0 = 0, T_1 = 1, T_2 = 1, ...
遞迴式
T_N = Σ T_k*T_(N-k), ...
生成函數式
Τ(z) = z + (Τ(z))^2, ...
解出生成函數
Τ(z) = (1/2)*(1±√(1-4z)), ... 負不合
取出第n+1項係數 因為 n internal nodes <=> n+1 external nodes
[z^(n+1)]Τ(z) = [z^(n+1)](1/2)*(1-√(1-4z))
= (-1/2)[z^(n+1)]Σ(1/2choose k)(-4z)^k
= (-1/2)(1/2 choose n+1)(-4)^(n+1)
= (4^n)(1/((n+1)!)(1-1/2)...(n-1/2)
= (2^n)(1/((n+1)!)(2-1)...(2n-1)
= (2^n)(2n-1)!!(2n)!!/(n+1)!(2n)!!
= (2^n)(2n)!/(n+1)!(2n)!!
= (2n)!/(n+1)!n!
= (1/(n+1))(2n choose n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.25.198