|
Search: id:A006196
|
|
|
| A006196 |
|
Number of leftist trees with n leaves.
(Formerly M1143)
|
|
+0
3
|
|
| 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; listen)
|
|
|
OFFSET
|
0,5
|
|
|
REFERENCES
|
R. Kemp, A note on the number of leftist trees, Info. Proc. Lett., 25 (1987), 227-232.
R. Kemp, Further results on leftist trees, pp. 103-130 of Random Graphs '87, Ed. M. Karonski et al., Wiley, 1990.
D. E. Knuth, Vol. 3, Sect. 5.2.3 for definition.
P. Nogueira, On the combinatorics of leftist trees, Discrete Appl. Math., 109 (2001) 253-278. MR1818241 (2002f:05090)
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
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
|
|
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;
|
|
PROGRAM
|
(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 */
|
|
CROSSREFS
|
Sequence in context: A084635 A154222 A114199 this_sequence A089796 A112482 A107597
Adjacent sequences: A006193 A006194 A006195 this_sequence A006197 A006198 A006199
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
N. J. A. Sloane (njas(AT)research.att.com).
|
|
EXTENSIONS
|
Corrected Oct 25, 2003
|
|
|
Search completed in 0.002 seconds
|
