|
%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
|
