login
This site is supported by donations to The OEIS Foundation.

 

Logo


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)

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: 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified April 22 00:45 EDT 2018. Contains 302877 sequences. (Running on oeis4.)