作者Ifault (Not my fault)
看板Math
標題[分析] 二元樹問題
時間Sat Aug 22 01:47:37 2020
我不知道該選啥分類
N個節點的二元樹 可以組成多少
不同的二元樹
答案是c 2n取n n+1
想問一下推導過程
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.129.29 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1598032059.A.699.html
1F：推 expiate : 你的二元樹是有限制在 complete還是節點數只要是 N 08/22 05:15
2F：→ expiate : 都算？ 08/22 05:15
3F：→ Ifault : 不用完整 傾斜也可以 08/22 05:34
4F：→ Ifault : 不平衡也可以 08/22 05:34
5F：推 hwanger : 如果不區別這個n個節點 令f(n)為有n個節點的二元樹 08/22 09:04
6F：→ hwanger : 則有下列遞歸式 f(0)=f(1)=1 08/22 09:06
7F：→ hwanger : f(n)={sum over k from 0 to n-1}f(k)*f(n-1-k) 08/22 09:07
8F：推 hwanger : 上面是"令f(n)為有n個節點的二元樹的個數" 08/22 09:11
9F：→ hwanger : 會有這個遞歸式 是因為二元樹是有分左右的 然後用 08/22 09:13
10F：→ hwanger : 二元樹的遞迴定義得到的 08/22 09:14
11F：→ hwanger : 同樣地 如果這個n個節點皆相異 08/22 09:14
12F：→ hwanger : 令g(n)為有n個相異節點的二元樹的個數 則 08/22 09:17
13F：→ hwanger : g(0)=g(1)=1 08/22 09:18
14F：→ hwanger : g(n)=n*(ΣC(n-1,k)f(k)*f(n-1-k)) where k runs 08/22 09:20
15F：→ hwanger : over 1,2,...,n-1 08/22 09:21
16F：推 hwanger : 我看不太懂"答案是c 2n取n ? n+1" 這一行 不過你已 08/22 09:23
17F：→ hwanger : 經有答案的話 用數學歸納法就可以做了 08/22 09:25
18F：→ Ifault : 感謝你 我在想想 08/22 09:34
19F：推 hwanger : 上面g(n)打錯 應該是 08/22 09:34
20F：→ hwanger : g(n)=n*(ΣC(n-1,k)g(k)*g(n-1-k)) 不過也不用這麼 08/22 09:35
21F：→ hwanger : 麻煩 就是g(n)=n!*f(n) 08/22 09:35
22F：推 hwanger : 分類應該是"離散" 不過好像沒有這個選項 XDDD 08/22 09:47
23F：推 hwanger : Ok 離散離我太久遠了 f(n)就是Catalan number 08/22 10:08
24F：→ hwanger : 所以可以用generating function去證 08/22 10:09
25F：→ hwanger : f(n)=C(2n,n)/(n+1) 冏 08/22 10:11
26F：→ Ifault : 哈 謝謝你 沒發現/打成? 08/22 12:26