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

%I M1143 #70 Dec 30 2020 02:24:46

%S 0,1,1,1,2,4,8,17,38,87,203,482,1160,2822,6929,17149,42736,107144,

%T 270060,683940,1739511,4441255,11378814,29245927,75386341,194838673,

%U 504802508,1310843123,3411070837,8893590439,23230151744,60780377599,159281030250

%N Number of leftist trees with n leaves.

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

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

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

%H Vaclav Kotesovec, <a href="/A006196/b006196.txt">Table of n, a(n) for n = 0..2000</a> (terms 0..200 from Vincenzo Librandi)

%H Paul Barry, <a href="https://arxiv.org/abs/1807.05794">Riordan Pseudo-Involutions, Continued Fractions and Somos 4 Sequences</a>, arXiv:1807.05794 [math.CO], 2018.

%H Steven R. Finch, <a href="http://arxiv.org/abs/2001.00578">Errata and Addenda to Mathematical Constants</a>, p. 39.

%H R. Kemp, <a href="http://dx.doi.org/10.1016/0020-0190(87)90165-7">A note on the number of leftist trees</a>, Info. Proc. Lett., 25 (1987), 227-232.

%H R. Kemp, <a href="/A006196/a006196_1.pdf">A note on the number of leftist trees</a>, Info. Proc. Lett., 25 (1987), 227-232. (Annotated scanned copy)

%H R. Kemp, <a href="/A006196/a006196.pdf">Further results on leftist trees</a>, Random Graphs (1987), 103-130. (Annotated scanned copy)

%H P. Nogueira, <a href="http://dx.doi.org/10.1016/S0166-218X(00)00250-X">On the combinatorics of leftist trees</a>, Discrete Appl. Math., 109 (2001) 253-278. MR1818241 (2002f:05090)

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Leftist_tree">Leftist tree</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

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

%F Series reversion of g.f. A(x) is -A(-x). - _Michael Somos_, Jul 13 2003

%F 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

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

%p 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;

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

%t 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_ *)

%o (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))}

%o (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 */

%o (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

%Y Cf. A247448, A247449.

%K nonn,nice

%O 0,5

%A _N. J. A. Sloane_

%E Corrected by _N. J. A. Sloane_, Oct 25 2003