作者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/cn.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