help needed counting rooted trees

N. J. A. Sloane njas at research.att.com
Wed Aug 31 00:08:54 CEST 2005


Take the standard rooted binary tree of depth n, with
2^(n+1) - 1 labeled nodes.  Here is a poor picture of
the tree of depth 3.  

       o
     /   \ 
    /     \
   o       o
  / \     / \
 o   o   o   o
/ \ / \ / \ / \
o o o o o o o  o

My question is, how many rooted subtrees are there?
(All rooted at the original root, of course.)

For n = 1 the 4 subtrees are:
o   o   o      o
   /     \    / \
  o       o  o   o

I get:

n: 0  1  2
#: 1  4  25

Is this A007830?

NJAS





More information about the SeqFan mailing list