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