[商管] [資結]-中央97-資管(丙組)

[iamhebe ( bbb)]

題目：Let B(n) be the number of distinct binary trees
      constructed from n nodes.
      For examples,B(0)=1,B(1)=1,B(2)=2,B(3)=5.

      Please write a recursive formula to define B(n)
      based on a combination of B(i) where 0<=i<n.

雖然#19myFflD這篇文章有版友問過一樣的問題
推文有給答案
但我自己是覺得推文給錯的答案
因為B(4)=14,代入推文的公式是算不出來的
而且代那個公式應該跟recursive沒關係吧

畢竟我記得公式長這樣B(n)=  1   ╭2n╮
                         ───│  │
                         n + 1 ╰ n╯

解很久想不出 recursive formula
不知道有沒有人想出來或有答案的
感謝:)

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.248.224.250
推 rnbjacky:http://tinyurl.com/5wxy8nv
→ rnbjacky:這是資工的重要遞迴 要是沒看過 造的出來那功力要很高...
→ rnbjacky:如果n+1不習慣 把他降一階 n+1變n n變n-1 就可以變Cn
→ rnbjacky:仍然是  for n>= 0  想法是 當固定root後 剩n-1個點
→ rnbjacky:左子樹可能含0個點的 b.t 右子樹含 n-1個點的b.t
→ rnbjacky:相成得到第一種可能遞迴 再來左1 右n-2 相乘 得第二種
→ rnbjacky:一此類推 .....左n-1  右0  得到最後一種可能
→ rnbjacky:最後定義0個點的可能是 1  i.e.C0 = 1
※ 編輯: iamhebe         來自: 111.248.204.168      (02/26 09:26)
推 fgets:我想問解那個遞迴的方法
→ privatewind:請用生成函數
→ fgets:謝謝  但不太好解 不知會不會考..
→ jameschou:用生成函數 可參考數學版#1D72gftL (Math)
→ privatewind:台大有考
推 rnbjacky:耍呆了....  for n>= 1
→ sneak: 請用生成函數 https://daxiv.com