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