This site is supported by donations to The OEIS Foundation.

 Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS"). Other ways to donate

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A005588 Number of free binary trees admitting height n. (Formerly M1813) 4
 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..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]; (* Jean-François Alcover, Apr 22 2013, program corrected and improved by Michael Somos *) CROSSREFS Cf. A002658, A006894. Sequence in context: A237195 A275597 A118191 * A106898 A106899 A259530 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified December 11 21:28 EST 2018. Contains 318052 sequences. (Running on oeis4.)