cp's OEIS Frontend

A307577 Number of Motzkin meanders of length n with an odd number of peaks.

%I A307577 #16 Apr 29 2019 13:00:10
%S A307577 0,0,1,4,13,40,119,348,1011,2928,8471,24516,71023,206024,598513,
%T A307577 1741332,5073733,14804160,43252855,126526756,370551287,1086365336,
%U A307577 3188090101,9364411252,27529374201,80993754352,238463467529,702563144252,2071200546129,6109619428824
%N A307577 Number of Motzkin meanders of length n with an odd number of peaks.
%C A307577 A Motzkin meander is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), and never goes below the x-axis.
%C A307577 A peak is an occurrence of the pattern UD.
%H A307577 Alois P. Heinz, <a href="/A307577/b307577.txt">Table of n, a(n) for n = 0..1000</a>
%H A307577 Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger. <a href="https://lipn.univ-paris13.fr/~banderier/Papers/patterns2019.pdf">Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata</a>, Algorithmica (2019).
%F A307577 G.f.: (sqrt((1+t)*(1-3*t))/(1-3*t) - sqrt((1-t)*(1-2*t)*(1+t+2*t^2))/((1-t)*(1-2*t))) / (4*t).
%e A307577 For n = 3 the a(3) = 4 paths are UDH, HUD, UDU, UUD.
%p A307577 b:= proc(x, y, t, c) option remember; `if`(y<0, 0, `if`(x=0, c,
%p A307577       b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, 0, c)+b(x-1, y+1, 1, c)))
%p A307577     end:
%p A307577 a:= n-> b(n, 0$3):
%p A307577 seq(a(n), n=0..35);  # _Alois P. Heinz_, Apr 16 2019
%t A307577 b[x_, y_, t_, c_] := b[x, y, t, c] = If[y<0, 0, If[x==0, c, b[x-1, y-1, 0, Mod[c+t, 2]] + b[x-1, y, 0, c] + b[x-1, y+1, 1, c]]];
%t A307577 a[n_] := b[n, 0, 0, 0];
%t A307577 Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Apr 29 2019, after _Alois P. Heinz_ *)
%Y A307577 Cf. A001006.
%K A307577 nonn
%O A307577 0,4
%A A307577 _Andrei Asinowski_, Apr 15 2019