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

看板Grad-ProbAsk作者 (迪西)時間15年前 (2011/02/11 09:51), 編輯推噓5(5推 0噓 12→)
留言17則, 10人參與, 最新討論串1/1
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
推
02/11 09:54, , 1F
證這個很麻煩= =" 先從式子bn=b_n-1*b0+b_n-2*b1+..+bn-1*b0
02/11 09:54, 1F
→
02/11 09:55, , 2F
這個是把一點當root 左子樹有b0~b_n-1 右子樹則是b_n-1~b0
02/11 09:55, 2F
→
02/11 09:57, , 3F
初值令b0=1 然後開始生成函數去處理@@...
02/11 09:57, 3F
→
02/11 09:57, , 4F
..看書比較實在。。
02/11 09:57, 4F
→
02/11 09:59, , 5F
真的= = 其中 bn為n個node的相異二元樹個數
02/11 09:59, 5F
→
02/11 10:08, , 6F
簡而言之這是Catalan Number的證明。
02/11 10:08, 6F
→
02/11 10:29, , 7F
手邊的書沒有看到這個的證明 請問有推薦的網站之類的嗎?
02/11 10:29, 7F
→
02/11 11:06, , 8F
沒時間的話不建議看這個，黃子嘉的書證明這個證了四頁....
02/11 11:06, 8F
→
02/11 11:14, , 9F
某年考古題有出現過,還是看一下比較好 不需要花太多時間
02/11 11:14, 9F
推
02/11 11:15, , 10F
這個證明一頁而已吧@@
02/11 11:15, 10F
→
02/11 11:36, , 11F
ok，只是因為這個東西需要的技巧不少，而且很煩 orz
02/11 11:36, 11F
推
02/11 11:45, , 12F
我有在math版上證過 你可以參考看看 #1D72gftL (Math)
02/11 11:45, 12F
→
02/11 12:03, , 13F
感謝各位的解答^^
02/11 12:03, 13F
→
02/11 12:03, , 14F
這個證明沒看過的話 應該也寫不出來XD
02/11 12:03, 14F
推
02/11 18:46, , 15F
這個證明我來來回回看了不下五次 才稍微記住= =
02/11 18:46, 15F
推
02/08 19:59, , 16F
証這題的時間可以寫5題了
02/08 19:59, 16F
→
09/11 14:14, , 17F
感謝各位的解答^^ https://daxiv.com
09/11 14:14, 17F
‣ 更多 weiyung 的文章
文章代碼(AID): #1DL9O-qH (Grad-ProbAsk)