[理工] [離散] 95清大資工

[weiyung (迪西)]

10.Show that the number of binary trees

   with n internal nodes is 1/(n+1)*C(2n,n)




請問一下這題要怎麼證明呢？毫無頭緒，感謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 180.176.168.15
推 dy957:證這個很麻煩= =" 先從式子bn=b_n-1*b0+b_n-2*b1+..+bn-1*b0
→ dy957:這個是把一點當root 左子樹有b0~b_n-1 右子樹則是b_n-1~b0
→ dy957:初值令b0=1 然後開始生成函數去處理@@...
→ aoqq12:..看書比較實在。。
→ dy957:真的= = 其中 bn為n個node的相異二元樹個數
→ ybite:簡而言之這是Catalan Number的證明。
→ weiyung:手邊的書沒有看到這個的證明 請問有推薦的網站之類的嗎?
→ ybite:沒時間的話不建議看這個，黃子嘉的書證明這個證了四頁....
→ ai305428d:某年考古題有出現過,還是看一下比較好 不需要花太多時間
推 boy5548:這個證明一頁而已吧@@
→ ybite:ok，只是因為這個東西需要的技巧不少，而且很煩 orz
推 jameschou:我有在math版上證過 你可以參考看看 #1D72gftL (Math)
→ weiyung:感謝各位的解答^^
→ boy5548:這個證明沒看過的話 應該也寫不出來XD
推 christianSK:這個證明我來來回回看了不下五次 才稍微記住= =
推 zensword:証這題的時間可以寫5題了
→ sneak: 感謝各位的解答^^ https://daxiv.com