login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006196 Number of leftist trees with n leaves.
(Formerly M1143)
6
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 (list; graph; refs; listen; history; text; internal format)
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

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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 10:03 EST 2021. Contains 340385 sequences. (Running on oeis4.)