Conference rusure::math

184.0. "Counting Binary Trees" by HARE::STAN () Mon Nov 19 1984 01:27

Newsgroups: net.puzzle,net.math
Path: decwrl!decvax!genrad!wjh12!talcott!gjk
Subject: Questions thrice about binary trees.
Posted: Sat Nov 17 13:22:33 1984


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.

Newsgroups: net.puzzle,net.math
Path: decwrl!decvax!genrad!mit-eddie!godot!harvard!seismo!brl-tgr!ron
Subject: Re: Questions thrice about binary trees.  (SPOILER)
Posted: Tue Nov 20 12:25:14 1984



> 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))