[分析] 二元樹問題

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