-3

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?

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
spider
  • 53
  • 5
  • 1
    possible duplicate of [With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?](http://stackoverflow.com/questions/3042412/with-n-no-of-nodes-how-many-different-binary-and-binary-search-trees-possib) and [The possible number of binary search trees that can be created with N keys is given by the Nth catalan number. Why?](http://stackoverflow.com/questions/1352776/the-possible-number-of-binary-search-trees-that-can-be-created-with-n-keys-is-gi) – Raymond Chen Dec 31 '11 at 14:18

1 Answers1

1

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

  Bn = (1 / (n + 1)) * (2n choose n) = (2n!)/((n+1)!(n!))
kaosjester
  • 121
  • 4