|
| |
|
|
A005588
|
|
Number of free binary trees admitting height n.
(Formerly M1813)
|
|
3
|
|
|
|
2, 7, 52, 2133, 2590407, 3374951541062, 5695183504479116640376509, 16217557574922386301420514191523784895639577710480, 131504586847961235687181874578063117114329409897550318273792033024340388219235081096658023517076950
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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..21
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)
Index entries for sequences related to rooted trees
Index entries for sequences related to trees
Index entries for "core" sequences
|
|
|
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]; (* Jean-François Alcover, Apr 22 2013, program corrected and improved by Michael Somos *)
|
|
|
CROSSREFS
|
Cf. A002658, A006894.
Sequence in context: A210856 A046662 A118191 * A106898 A106899 A119772
Adjacent sequences: A005585 A005586 A005587 * A005589 A005590 A005591
|
|
|
KEYWORD
|
nonn,easy,core,nice
|
|
|
AUTHOR
|
N. J. A. Sloane. Entry revised by N. J. A. Sloane, Aug 31 2012
|
|
|
STATUS
|
approved
|
| |
|
|
