A248100 Number of ordered trees with n edges such that non-leaf vertices at even levels have outdegree 1 and those at odd levels have outdegree 2.

1, 1, 0, 1, 2, 1, 2, 6, 6, 7, 20, 30, 34, 75, 140, 182, 322, 644, 972, 1554, 3024, 5091, 8052, 14784, 26378, 43032, 75504, 136994, 232232, 399399, 720356, 1257256, 2161874, 3852576, 6831552, 11858418, 20949304, 37350768, 65554788, 115476376, 205872448

Offset

0,5

Comments

a(n) (n>=1) is the number of ordered trees with n-1 edges such that non-leaf vertices at even levels have outdegree 2 and those at odd levels have outdegree 1. Indeed, these trees can be obtained by deleting the root-edge from the trees described in the definition.

Essentially the same as A025277: a(n) = A025277(n+3).

a(n) is also the number of excursions of length n with Motzkin-steps avoiding the consecutive steps without UU, UD and HH. The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). An excursion is a path starting at (0,0), ending at (n,0) and never crossing the x-axis, i.e., staying at nonnegative altitude.

Links

Table of n, a(n) for n=0..40.

Andrei Asinowski, Cyril Banderier, Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, (2019).

Formula

G.f.: g(x) satisfies g = 1 + x + x^3*g^2. Sketch of proof (the symbolic method): the set S of ordered trees such that non-leaf vertices at even levels have outdegree 1 and those at odd levels have outdegree 2 consists of the one-point tree, the tree | , and the trees obtained from the tree Y (root at bottom) by attaching at each of the two leaves a tree from the set S (not necessarily the same). For the g.f. g(x) of S, x marking edges, this "decomposition picture" of S translates at once into the given equation.

G.f.: (1-sqrt(1-4*x^3-4*x^4))/(2*x^3).

a(n) = a(0)*a(n-3)+a(1)*a(n-4)+...+a(n-3)*a(0) for n>=3.

D-finite with recurrence 5*(n+3)*a(n) +4*(-n-2)*a(n-1) +4*(-n-1)*a(n-2) +10*(-2*n+3)*a(n-3) +4*(-n+5)*a(n-4) +8*(4*n-15)*a(n-5) +16*(n-5)*a(n-6)=0. - R. J. Mathar, Oct 07 2016

Crossrefs

Cf. A025277.

Cf. A329694 (Motzkin paths with different forbidden consecutive steps but a similar G.f.).

Sequence in context: A351317 A094965 A025277 * A153896 A074727 A059587

Adjacent sequences: A248097 A248098 A248099 * A248101 A248102 A248103

Keyword

nonn,walk

Author

Emeric Deutsch, Jan 14 2015

Status

approved