login
This site is supported by donations to The OEIS 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

Vincenzo Librandi and Vaclav Kotesovec, Table of n, a(n) for n = 0..1000 (first 200 terms 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.

Steven R. Finch, Errata and Addenda to Mathematical Constants, January 22, 2016. [Cached copy, with permission of the author]

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 *)

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 November 21 04:47 EST 2019. Contains 329350 sequences. (Running on oeis4.)