login
A178520
Number of ordered trees with n edges and with no vertex of outdegree 2 that have two leaves as their two children.
2
1, 1, 1, 4, 11, 32, 98, 309, 998, 3285, 10981, 37178, 127227, 439369, 1529280, 5359314, 18894435, 66967086, 238473876, 852825314, 3061529014, 11028596473, 39853923390, 144435373636, 524837483375, 1911763716717, 6979451843306
OFFSET
0,4
COMMENTS
Empirical: for n >= 3, a(n) is the number of Dyck n-paths avoiding UUUDDD. E.g., of the 5 Dyck 3-paths UUUDDD is avoided so a(3)=4. - David Scambler, Mar 24 2011
LINKS
FORMULA
a(n) = A178519(n,0).
G.f.: G=G(z) satisfies (G+z^2)*(1-z*G)=1.
a(n) ~ sqrt((1+r)*(1-r+r^2)*(1-5*r^3)) / (4*sqrt(Pi)*n^(3/2)*r^(n+1)), where r = 0.2587353940253970315668... is the root of the equation (1+r^3)^2 = 4*r. - Vaclav Kotesovec, Mar 21 2014
Conjecture D-finite with recurrence: (n+1)*a(n) +(n+2)*a(n-1) +(n+9)*a(n-2) +(-82*n+203)*a(n-3) +5*(2*n-9)*a(n-4) +21*(2*n-11)*a(n-5) +(n-8)*a(n-6) +5*(n-9)*a(n-7) +21*(n-10)*a(n-8)=0. - R. J. Mathar, Jan 28 2020
EXAMPLE
a(3)=4 because among the 5 ordered trees with 3 edges only -< has a forbidden vertex (the root).
MAPLE
eq := z*G^2-(1-z^3)*G+1-z^2; G := RootOf(eq, G): Gser := series(G, z = 0, 30): seq(coeff(Gser, z, n), n = 0 .. 27);
MATHEMATICA
CoefficientList[Series[(1-x^3-Sqrt[1-4*x+2*x^3+x^6])/(2*x), {x, 0, 20}], x] (* Vaclav Kotesovec, Mar 21 2014 *)
PROG
(PARI) x='x+O('x^50); Vec((1-x^3-sqrt(1-4*x+2*x^3+x^6))/(2*x)) \\ G. C. Greubel, Mar 24 2017
CROSSREFS
Cf. A178519.
Sequence in context: A289246 A199109 A025268 * A306419 A376071 A149232
KEYWORD
nonn
AUTHOR
Emeric Deutsch, May 31 2010
STATUS
approved