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

Author

Emeric Deutsch, Jan 14 2015

Keywords

• nonn
• walk

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

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

Crossrefs

Cf. A025277.

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

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