login
A101308
Number of ordered trees with n edges and having no branches of length 2.
1
1, 1, 1, 3, 7, 18, 47, 129, 362, 1038, 3022, 8917, 26600, 80098, 243132, 743180, 2285597, 7067271, 21957947, 68517606, 214633572, 674712991, 2127790260, 6729876378, 21342679122, 67851885121, 216204228642, 690371596017
OFFSET
0,4
COMMENTS
Column 0 of the triangle A101307.
LINKS
Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees and branch lengths, Discrete Math., 282, 2004, 89-94.
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214-222.
FORMULA
G.f.: [1-z^2+z^3-sqrt[(1-z^2+z^3)(1-4z+3z^2-3z^3)]]/[2z(1-z+z^2)].
D-finite with recurrence (n+2)*a(n) +(-5*n-4)*a(n-1) +(7*n+2)*a(n-2) +(-4*n-5)*a(n-3) +(-7*n+31)*a(n-4) +3*(5*n-22)*a(n-5) +2*(-8*n+41)*a(n-6) +9*(n-6)*a(n-7) +3*(-n+7)*a(n-8)=0. - R. J. Mathar, May 31 2014
EXAMPLE
a(3)=3 because we have:(i) a path of length tree hanging from the root, (ii) an edge hanging from the root, from the end of which two edges are hanging and (iii) three edges hanging from the root.
MAPLE
G:=(1-z^2+z^3-sqrt((1-z^2+z^3)*(1-4*z+3*z^2-3*z^3)))/2/z/(1-z+z^2): Gser:=series(G, z=0, 34): 1, seq(coeff(Gser, z^n), n=1..32);
CROSSREFS
Cf. A101307.
Sequence in context: A211276 A018028 A045994 * A279482 A018029 A099483
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 22 2004
STATUS
approved