计算具有 i 个节点的二叉树的数量
令bi 为具有i 节点的二叉树的数量。计算b10。
这是我遇到的一个问题。
到目前为止，我已经能够想出这些：
B0=1
B1=1
B2=2
B3=5
B4=12
随着我变大，它很快就会变得有点太多了。
除了画出树木并数数之外，还有人能想到更好的计算 Bi 的方法吗？
Let bi be the number of binary trees with i nodes. Compute b10.
This is a problem I've come upon.
I've able to come up with these so far:
B0=1
B1=1
B2=2
B3=5
B4=12
It quickly gets a bit too much as I gets bigger.
Can anyone think of a better way to compute Bi than just drawing out the trees and count them?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我将您的答案输入 OEIS，它得出了一些结果。
一个有希望的结果是 A000669——系列减少的具有 n 片叶子的种植树木的数量。提供以下示例：a(4)=5，具有以下系列减少的种植树：(oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ( （哦）（哦））。也就是说，我们的树不一定是种植的。
然而，经过一番工作后，我必须通知您，您的 B4 值不正确 - 正确答案是 14。那么答案就很清楚了： 加泰罗尼亚数字。加泰罗尼亚数字计算了奇怪且多种多样的事物，包括您在此处提出的问题（来自 Wolfram）。值得注意的是这里的加泰罗尼亚数字恒等式 (8) - 定义加泰罗尼亚数字的递归。这个求和可以被认为是决定一个节点左边的节点数量（其余的将在右边）。
概念化这一点的一种更简单的方法是使用戴克词。设 X 表示“左括号”，Y 表示“0”。 （我使用树的列表表示 - 左侧的节点是元素左侧的列表，反之亦然；如果节点没有左侧或右侧列表，则它被视为叶子。）我们将在适当的情况下放入右括号。那么我们 B3 的树如下：
(((0)0)0) => XXXYYY
((0)0(0)) => XXYYXY
(0(0(0))) => XYXYXY
((0(0))0) => XXYXYY
(0((0)0)) => XYXXYY
从维基百科来看，这种形式的五个 2n 长度 Dyck 词是 XXXYYY、XYXXYY、XYXYXY、XXYYXY 和 XXYXYY。最后，闭合形式
I typed your answer into OEIS and it came up with a few results.
A promising result is A000669 - the number of series-reduced planted trees with n leaves. The following example is provided: a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)). That said, our trees are not necessarily planted.
However, after a bit of work, I must inform you that your value for B4 is incorrect - the correct answer is 14. Then the answer is clear: the Catalan numbers. The Catalan numbers count a strange and varied number of things, including the problem you're presented here (via Wolfram). It is worth noting Catalan number identity (8) here - the recurrence that defines the Catalan numbers. This summation can be thought of as deciding the number of nodes that will be to the left of a node (and the rest will be to the right).
An easier way to conceptualize this is using Dyck words. let X mean 'left parenthesis' and Y mean '0'. (I am using a list representation for trees - nodes to the left are lists on the left of an element and visa versa; if a node has no left or right lists it is considered a leaf.) We will put in right parentheses where appropriate. Then our trees for B3 are as follows:
(((0)0)0) => X X X Y Y Y
((0)0(0)) => X X Y Y X Y
(0(0(0))) => X Y X Y X Y
((0(0))0) => X X Y X Y Y
(0((0)0)) => X Y X X Y Y
From Wikipedia, the five 2n-length Dyck words of this form are XXXYYY, XYXXYY, XYXYXY, XXYYXY, and XXYXYY. And finally, the closed form