

A307577


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


1



0, 0, 1, 4, 13, 40, 119, 348, 1011, 2928, 8471, 24516, 71023, 206024, 598513, 1741332, 5073733, 14804160, 43252855, 126526756, 370551287, 1086365336, 3188090101, 9364411252, 27529374201, 80993754352, 238463467529, 702563144252, 2071200546129, 6109619428824
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

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 xaxis.
A peak is an occurrence of the pattern UD.


LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger. Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata, Algorithmica (2019).


FORMULA

G.f.: (sqrt((1+t)*(13*t))/(13*t)  sqrt((1t)*(12*t)*(1+t+2*t^2))/((1t)*(12*t))) / (4*t).


EXAMPLE

For n = 3 the a(3) = 4 paths are UDH, HUD, UDU, UUD.


MAPLE

b:= proc(x, y, t, c) option remember; `if`(y<0, 0, `if`(x=0, c,
b(x1, y1, 0, irem(c+t, 2))+b(x1, y, 0, c)+b(x1, y+1, 1, c)))
end:
a:= n> b(n, 0$3):
seq(a(n), n=0..35); # Alois P. Heinz, Apr 16 2019


MATHEMATICA

b[x_, y_, t_, c_] := b[x, y, t, c] = If[y<0, 0, If[x==0, c, b[x1, y1, 0, Mod[c+t, 2]] + b[x1, y, 0, c] + b[x1, y+1, 1, c]]];
a[n_] := b[n, 0, 0, 0];
Table[a[n], {n, 0, 35}] (* JeanFrançois Alcover, Apr 29 2019, after Alois P. Heinz *)


CROSSREFS

Cf. A001006.
Sequence in context: A272581 A191132 A119915 * A137744 A027130 A027121
Adjacent sequences: A307574 A307575 A307576 * A307578 A307579 A307580


KEYWORD

nonn


AUTHOR

Andrei Asinowski, Apr 15 2019


STATUS

approved



