A006196 Number of leftist trees with n leaves. (Formerly M1143)

0, 1, 1, 1, 2, 4, 8, 17, 38, 87, 203, 482, 1160, 2822, 6929, 17149, 42736, 107144, 270060, 683940, 1739511, 4441255, 11378814, 29245927, 75386341, 194838673, 504802508, 1310843123, 3411070837, 8893590439, 23230151744, 60780377599, 159281030250

Offset

0,5

References

S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 310.

D. E. Knuth, Vol. 3, Sect. 5.2.3 for definition.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Vaclav Kotesovec, Table of n, a(n) for n = 0..2000 (terms 0..200 from Vincenzo Librandi)

Paul Barry, Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences, arXiv:1807.05794 [math.CO], 2018.

Steven R. Finch, Errata and Addenda to Mathematical Constants, p. 39.

R. Kemp, A note on the number of leftist trees, Info. Proc. Lett., 25 (1987), 227-232.

R. Kemp, A note on the number of leftist trees, Info. Proc. Lett., 25 (1987), 227-232. (Annotated scanned copy)

R. Kemp, Further results on leftist trees, Random Graphs (1987), 103-130. (Annotated scanned copy)

P. Nogueira, On the combinatorics of leftist trees, Discrete Appl. Math., 109 (2001) 253-278. MR1818241 (2002f:05090)

Wikipedia, Leftist tree

Index entries for sequences related to trees

Formula

G.f. satisfies A(x) = x+A(x*A(x)). - P. Nogueira, Oct 24 2003

Series reversion of g.f. A(x) is -A(-x). - Michael Somos, Jul 13 2003

a(n)=T(n,1),a(0)=0, T(n,m)=sum(j=0..m-1, binomial(m,j)* sum(k=0..floor((n+j)/2)-m, T(n-k-m,k+m-j)*T(k+m-j,m-j))), n>m, T(n,n)=1. - Vladimir Kruchinin, May 04 2012

a(n) ~ c * d^n / n^(3/2), where c = A247449 = 0.2503634293925235068... and d = A247448 = 2.7494879027499877498588... - Vaclav Kotesovec, Mar 10 2014

Maple

A := x; for w from 2 to 42 do t1 := series( x+subs(x=x*A, A), x, w+2); t := coeff( t1, x, w); A := series(A+t*x^w, x, w+2); od: A;

Mathematica

t[n_, n_] = 1; t[n_, m_] := t[n, m] = Sum[ Binomial[m, j] * Sum[ t[n-k-m, k+m-j] * t[k+m-j, m-j], {k, 0, (n+j)/2 - m}], {j, 0, m-1}]; a[n_] := t[n, 1]; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Sep 05 2012, after Vladimir Kruchinin's formula *)
nmax = 40; p = x; m = 1; While[m < nmax, m = 2*m; p1 = (p/.x -> -4*x^2); p2 = (p/.x -> 4*x^2); p = Sqrt[p1^2/4 + p2/4] + p1/2;  p = Simplify[Normal[Series[p, {x, 0, nmax}]], x > 0]; ]; coefs = CoefficientList[-Series[p/.x -> -Normal[ InverseSeries[ Series[p, {x, 0, nmax}]]], {x, 0, nmax}], x]; Table[coefs[[k]]/4^(k-2), {k, 1, Length[coefs]}] (* Vaclav Kotesovec, Dec 27 2020, after Michael Somos *)

Prog

(PARI) {a(n)=local(A); if(n<1, 0, A=O(x); for(i=1, n, A=x+subst(A, x, x*A)); polcoeff(A, n))}
(PARI) {a(n)=local(A, m); if(n<1, 0, A=x+O(x^2); m=1; while(m<n, m*=2; A=sqrt(subst(A, x, -4*x^2)^2/4+subst(A, x, 4*x^2)/4)+subst(A, x, -4*x^2)/2); polcoeff(-subst(A, x, -serreverse(A)), n)/4^(n-1))} /* Michael Somos, Sep 20 2006 */
(Maxima) T(n, m):=if n=m then 1 else sum(binomial(m, j)*sum(T(n-k-m, k+m-j)*T(k+m-j, m-j), k, 0, floor((n+j)/2)-m), j, 0, m-1); makelist(T(n, 1), n, 1, 15); /* Vladimir Kruchinin, May 04 2012 */

Crossrefs

Cf. A247448, A247449.

Sequence in context: A294529 A154222 A114199 * A089796 A112482 A193050

Adjacent sequences: A006193 A006194 A006195 * A006197 A006198 A006199

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

Corrected by N. J. A. Sloane, Oct 25 2003

Status

approved