Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #24 Jul 24 2022 12:39:42
%S 1,1,0,1,2,1,2,6,6,7,20,30,34,75,140,182,322,644,972,1554,3024,5091,
%T 8052,14784,26378,43032,75504,136994,232232,399399,720356,1257256,
%U 2161874,3852576,6831552,11858418,20949304,37350768,65554788,115476376,205872448
%N 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.
%C 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.
%C Essentially the same as A025277: a(n) = A025277(n+3).
%C 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.
%H Andrei Asinowski, Cyril Banderier, Valerie Roitner, <a href="https://lipn.univ-paris13.fr/~banderier/Papers/several_patterns.pdf">Generating functions for lattice paths with several forbidden patterns</a>, (2019).
%F 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.
%F G.f.: (1-sqrt(1-4*x^3-4*x^4))/(2*x^3).
%F a(n) = a(0)*a(n-3)+a(1)*a(n-4)+...+a(n-3)*a(0) for n>=3.
%F 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
%Y Cf. A025277.
%Y Cf. A329694 (Motzkin paths with different forbidden consecutive steps but a similar G.f.).
%K nonn,walk
%O 0,5
%A _Emeric Deutsch_, Jan 14 2015