-3

让是具有节点bi的二叉树的数量。i计算b10。

这是我遇到的一个问题。

到目前为止，我已经能够提出这些： 

B0=1
B1=1
B2=2
B3=5
B4=12

随着我变大，它很快变得有点太多了。

谁能想到比仅仅画出树并计算它们更好的方法来计算 Bi？

4

1 回答 1

1

我在 OEIS 中输入了您的答案，它得出了一些结果。

一个有希望的结果是 A000669 - 具有 n 片叶子的系列减少种植树木的数量。提供了以下示例：a(4)=5，具有以下系列减少的种植树：(oooo)、(oo(oo))、(o(ooo))、(o(o(oo)))、( (oo)(oo))。也就是说，我们的树不一定是种的。

但是，经过一番努力，我必须通知您，您对 B4 的值不正确——正确答案是 14。那么答案就很清楚了：加泰罗尼亚数字。加泰罗尼亚数字计算了许多奇怪的事物，包括您在此处提出的问题（通过Wolfram）。这里值得注意的是加泰罗尼亚数字恒等式 (8) - 定义加泰罗尼亚数字的循环。这个总和可以被认为是决定节点左侧的节点数量（其余的将在右侧）。

一个更简单的概念化方法是使用 Dyck 词。让 X 表示“左括号”，Y 表示“0”。（我使用树的列表表示 - 左侧的节点是元素左侧的列表，反之亦然；如果节点没有左列表或右列表，则它被视为叶子。）我们将在适当的地方放入右括号. 那么我们的 B3 树如下：

(((0)0)0) => XXXYYY

((0)0(0)) => XXYYXY

(0(0(0))) => XYXYXY

((0(0))0) => XXYXYY

(0((0)0)) => XXXXYY

来自维基百科，这种形式的五个 2n 长度的 Dyck 词是 XXXYYY、XYXXYY、XYXYXY、XXYYXY 和 XXYYYY。最后，封闭形式

  Bn = (1 / (n + 1)) * (2n choose n) = (2n!)/((n+1)!(n!))
于 2011-12-31T02:25:00.790 回答