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

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

Offset: 0

Author

Andrei Asinowski, Apr 15 2019

Keywords

• nonn

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 x-axis.

A peak is an occurrence of the pattern UD.

Examples

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

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).

Crossrefs

Cf. A001006.

Programs

Maple

b:= proc(x, y, t, c) option remember; `if`(y<0, 0, `if`(x=0, c,
      b(x-1, y-1, 0, irem(c+t, 2))+b(x-1, y, 0, c)+b(x-1, 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[x-1, y-1, 0, Mod[c+t, 2]] + b[x-1, y, 0, c] + b[x-1, y+1, 1, c]]];
a[n_] := b[n, 0, 0, 0];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Apr 29 2019, after Alois P. Heinz *)

Formula

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).