|
%I #16 Apr 29 2019 13:00:10
%S 0,0,1,4,13,40,119,348,1011,2928,8471,24516,71023,206024,598513,
%T 1741332,5073733,14804160,43252855,126526756,370551287,1086365336,
%U 3188090101,9364411252,27529374201,80993754352,238463467529,702563144252,2071200546129,6109619428824
%N Number of Motzkin meanders of length n with an odd number of peaks.
%C 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 A peak is an occurrence of the pattern UD.
%H Alois P. Heinz, <a href="/A307577/b307577.txt">Table of n, a(n) for n = 0..1000</a>
%H 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 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 For n = 3 the a(3) = 4 paths are UDH, HUD, UDU, UUD.
%p b:= proc(x, y, t, c) option remember; `if`(y<0, 0, `if`(x=0, c,
%p b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, 0, c)+b(x-1, y+1, 1, c)))
%p end:
%p a:= n-> b(n, 0$3):
%p seq(a(n), n=0..35); # _Alois P. Heinz_, Apr 16 2019
%t 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 a[n_] := b[n, 0, 0, 0];
%t Table[a[n], {n, 0, 35}] (* _Jean-François Alcover_, Apr 29 2019, after _Alois P. Heinz_ *)
%Y Cf. A001006.
%K nonn
%O 0,4
%A _Andrei Asinowski_, Apr 15 2019
|
