Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/3/84; site talcott.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!genrad!wjh12!talcott!gjk
From: gjk@talcott.UUCP (Greg J Kuperberg)
Newsgroups: net.puzzle,net.math
Subject: Questions thrice about binary trees.
Message-ID: <113@talcott.UUCP>
Date: Sat, 17-Nov-84 16:22:33 EST
Article-I.D.: talcott.113
Posted: Sat Nov 17 16:22:33 1984
Date-Received: Sun, 18-Nov-84 05:33:01 EST
Distribution: net
Organization: Harvard
Lines: 20
Xref: genrad net.puzzle:500 net.math:1650

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.