A307575 - OEIS

A307575

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

1, 2, 4, 9, 22, 56, 148, 402, 1112, 3118, 8832, 25205, 72342, 208560, 603404, 1750785, 5092046, 14839710, 43321976, 126661355, 370813762, 1086877792, 3189091724, 9366371000, 27533212140, 81001276874, 238478223648, 702592110803, 2071257446234, 6109731270056

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

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.

LINKS

Table of n, a(n) for n=0..29.

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)*(1-3*t))/(1-3*t) + sqrt((1-t)*(1-2*t)*(1+t+2*t^2))/((1-t)*(1-2*t)) -2) / (4*t).

D-finite with recurrence -3*(n+1)*(n-2)*a(n) +4*(4*n^2-7*n-3)*a(n-1) +3*(-7*n^2+17*n-2)*a(n-2) +4*n*(n-3)*a(n-3) -(n-3)*(25*n-82)*a(n-4) +4*(n-3)*(6*n-19)*a(n-5) +(61*n^2-575*n+1302)*a(n-6) -4*(11*n-37)*(n-6)*a(n-7) -12*(n-6)*(n-7)*a(n-8)=0. - R. J. Mathar, Mar 06 2022

a(n) + A307577(n) = A005773(n+1). - R. J. Mathar, Jan 25 2023

EXAMPLE

For n = 3 the a(3) = 9 paths are UUU, UUH, UHU, UHH, UHD, HUU, HUH, HHU, HHH.

MAPLE

b:= proc(x, y, t, c) option remember; `if`(y<0, 0, `if`(x=0, 1-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, 1-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];