OFFSET
1,1
COMMENTS
a(n) is the number of free 3-trees which have a rooting as a binary tree of height n.
a(n) <= A002658(n+1) [Harary, et al.] "This is because any tree with a binary rooting of height h corresponds to a planted 3-tree of height h+1. [...] In general there are trees with more than one binary rooting of height h, so equality does not hold". - Michael Somos, Sep 02 2012
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
David Wassermann, Table of n, a(n) for n = 1..12
Harary, Frank; Palmer, Edgar M.; Robinson, Robert W., Counting free binary trees admitting a given height, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175--181. MR1216977 (94c:05039)
Harary, Frank; Palmer, Edgar M.; Robinson, Robert W., Counting free binary trees admitting a given height, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175-181. (Annotated scanned copy)
FORMULA
Harary et al. give a complicated recurrence.
EXAMPLE
+---------+
| o o o | a(1) = 2
| | \| |
| o o |
+---------------------------------------------+
| o o o o o o o o o o o o o o o | a(2) = 7
| | \| | \| | | | \| \| |/ |
| o o o o o o o o o o o o |
| | | \| \| \| \ / \| |
| o o o o o o o |
+---------------------------------------------+
a(3) = 52 while A002658(4) = 56 because there are 56 - 52 = 4 free binary trees admitting height 3 which have two rootings, while the rest have only one rooting. The four trees have degree sequences 32111, 322111, 3222111, 3321111. - Michael Somos, Sep 02 2012
MATHEMATICA
bin2[n_] = Binomial[n, 2];
bin3[n_] = Binomial[n, 3];
p[0] = q[0] = 0;
p[1] = q[1] = 1;
q[h1_] := q[h1] = With[{h = h1-1}, q[h] + p[h]];
p[h1_] := p[h1] = With[{h = h1-1}, bin2[1 + p[h]] + p[h] q[h]];
a[h_] := a[h] = bin3[2 + p[h]] + bin2[1 + p[h]] q[h];
b[h_] := b[h] = bin2[1 + p[h]];
e[h_, i_] := e[h, i] = 1 + Sum[d[j, i], {j, h-1}];
d[h_, h_] := 0; d[h_, i_] := p[h] /; i > h;
d[h1_, i1_] := d[h1, i1] = With[{h = h1-1, i = i1-1}, bin2[1 + d[h, i]] + d[h, i] e[h, i]]; d[h_, 1] := d[h, 1] = p[h] - p[h-1];
e[h_, 1] := e[h, 1] = p[h-1];
t1[h_] := Sum[a[h-i] - bin3[2 + d[h-i, i]] - bin2[1 + d[h-i, i]] e[h-i, i], {i, Quotient[h, 2]}];
t2[h_] := Sum[b[h-i+1] - bin2[1 + d[h-i+1, i]], {i, Quotient[h+1, 2]}];
t[h_] := bin2[1 + p[h]] + t1[h] + t2[h];
Table[t[n], {n, 1, 12}] (* Jean-François Alcover, Apr 22 2013, program corrected and improved by Michael Somos *)
CROSSREFS
KEYWORD
nonn,easy,core,nice
AUTHOR
N. J. A. Sloane; entry revised by N. J. A. Sloane, Aug 31 2012
STATUS
approved