[net.math] Questions thrice about binary trees.

gjk@talcott.UUCP (Greg J Kuperberg) (11/18/84)

Example:  There are five binary trees that have three nodes.  They are:

 x - x - x - nil   x - x -nil  x -nil      x -nil     x - x - nil
 |   |   |         |   |       |           |          |   |
nil nil nil       nil  x -nil  x - x -nil  x -nil     x  nil
                       |       |   |       |          | \
                      nil     nil nil      x -nil    nil nil
                                           |
                                          nil

Easy question:  How many binary trees are there with four nodes?

Harder question:  How many binary trees are there with fifty nodes? (You are
allowed to use a computer.)

Yet harder question:  If B(n) is the number of binary trees with n nodes,
what is log(B(10,000,000)) to the nearest integer? (Use of a computer is
highly recommended.)

Note:  Consulting a book on combinatorics is considered cheating.

ron@brl-tgr.ARPA (Ron Natalie <ron>) (11/20/84)

> Harder question:  How many binary trees are there with fifty nodes? (You are
> allowed to use a computer.)
> 
> Yet harder question:  If B(n) is the number of binary trees with n nodes,
> what is log(B(10,000,000)) to the nearest integer? (Use of a computer is
> highly recommended.)
> 
> Note:  Consulting a book on combinatorics is considered cheating.

B(50) = 1978261657756160653623774456  I cheated, but Macsyma helps.

If my hasty calculations are correct.

	O(log(B(n)) = O(n*log(n))