Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site brl-tgr.ARPA
Path: utzoo!watmath!clyde!burl!ulysses!allegra!mit-eddie!godot!harvard!seismo!brl-tgr!ron
From: ron@brl-tgr.ARPA (Ron Natalie <ron>)
Newsgroups: net.puzzle,net.math
Subject: Re: Questions thrice about binary trees.  (SPOILER)
Message-ID: <5961@brl-tgr.ARPA>
Date: Tue, 20-Nov-84 15:25:14 EST
Article-I.D.: brl-tgr.5961
Posted: Tue Nov 20 15:25:14 1984
Date-Received: Thu, 22-Nov-84 05:53:04 EST
References: <113@talcott.UUCP>
Distribution: net
Organization: Ballistic Research Lab
Lines: 15


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