[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

184.0. "Counting Binary Trees" by HARE::STAN () Sun Nov 18 1984 22: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.
T.RTitleUserPersonal
Name		DateLines
184.1HARE::STANFri Nov 23 1984 11:5621
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))
184.2old oneHERON::BUCHANANThe was not found.Mon Mar 15 1993 11:0831
> How many binary trees are there on 4 nodes?

F(4) = umm, 1*5 + 1*2 + 2*1 + 5*1 = 14

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

$ maple
define(F, forall(integer(n),F(n)=sum(F(k)*F(n-1-k),k=0..n-1)), F(0)=1);
F(50);
			1978261657756160653623774456
define(G, forall(integer(n),G(n)=(2*n)!/(n!*(n+1)!)));
F(50)-G(50);
			0

See Note 1662.* for proof that F=G.
 
> Yet harder question:  If F(n) is the number of binary trees with n nodes,
> what is log(F(10,000,000)) to the nearest integer? (Use of a computer is
> highly recommended.)

Stirling says:
	n! ~ _/(2pi*n)(n/e)^n
So:
	log(n!) ~ �log(2pi*n) + n*log(n) - n
	log(F(n)) ~ 2n*log2 - (3/2)log(n) - �log(pi)

I forget how accurate Stirling is.   But assuming we could neglect other terms
in the approximation, log(F(10^7)) = 13862919, to the nearest integer.

Andrew.