cp's OEIS Frontend

A005588 Number of free binary trees admitting height n.

%I A005588 M1813 #68 Aug 28 2022 08:22:55
%S A005588 2,7,52,2133,2590407,3374951541062,5695183504479116640376509,
%T A005588 16217557574922386301420514191523784895639577710480,
%U A005588 131504586847961235687181874578063117114329409897550318273792033024340388219235081096658023517076950
%N A005588 Number of free binary trees admitting height n.
%C A005588 a(n) is the number of free 3-trees which have a rooting as a binary tree of height n.
%C A005588 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
%D A005588 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A005588 David Wassermann, <a href="/A005588/b005588.txt">Table of n, a(n) for n = 1..12</a>
%H A005588 Harary, Frank; Palmer, Edgar M.; Robinson, Robert W., <a href="http://cobweb.cs.uga.edu/~rwr/publications/binary.pdf">Counting free binary trees admitting a given height</a>, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175--181. MR1216977 (94c:05039)
%H A005588 Harary, Frank; Palmer, Edgar M.; Robinson, Robert W., <a href="/A005588/a005588.pdf">Counting free binary trees admitting a given height</a>, J. Combin. Inform. System Sci. 17 (1992), no. 1-2, 175-181. (Annotated scanned copy)
%H A005588 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A005588 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A005588 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A005588 Harary et al. give a complicated recurrence.
%e A005588 +---------+
%e A005588 | o   o o | a(1) = 2
%e A005588 | |    \| |
%e A005588 | o     o |
%e A005588 +---------------------------------------------+
%e A005588 | o   o o     o   o o   o o   o o o   o o o o | a(2) = 7
%e A005588 | |    \|     |    \|   | |   |  \|    \| |/  |
%e A005588 | o     o   o o   o o   o o   o   o     o o   |
%e A005588 | |     |    \|    \|    \|    \ /       \|   |
%e A005588 | o     o     o     o     o     o         o   |
%e A005588 +---------------------------------------------+
%e A005588 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
%t A005588 bin2[n_] = Binomial[n, 2];
%t A005588 bin3[n_] = Binomial[n, 3];
%t A005588 p[0] = q[0] = 0;
%t A005588 p[1] = q[1] = 1;
%t A005588 q[h1_] := q[h1] = With[{h = h1-1}, q[h] + p[h]];
%t A005588 p[h1_] := p[h1] = With[{h = h1-1}, bin2[1 + p[h]] + p[h] q[h]];
%t A005588 a[h_] := a[h] = bin3[2 + p[h]] + bin2[1 + p[h]] q[h];
%t A005588 b[h_] := b[h] = bin2[1 + p[h]];
%t A005588 e[h_, i_] := e[h, i] = 1 + Sum[d[j, i], {j, h-1}];
%t A005588 d[h_, h_] := 0; d[h_, i_] := p[h] /; i > h;
%t A005588 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];
%t A005588 e[h_, 1] := e[h, 1] = p[h-1];
%t A005588 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]}];
%t A005588 t2[h_] := Sum[b[h-i+1] - bin2[1 + d[h-i+1, i]], {i, Quotient[h+1, 2]}];
%t A005588 t[h_] := bin2[1 + p[h]] + t1[h] + t2[h];
%t A005588 Table[t[n], {n, 1, 12}] (* _Jean-François Alcover_, Apr 22 2013, program corrected and improved by _Michael Somos_ *)
%Y A005588 Cf. A002658, A006894.
%K A005588 nonn,easy,core,nice
%O A005588 1,1
%A A005588 _N. J. A. Sloane_; entry revised by _N. J. A. Sloane_, Aug 31 2012