A307576 Number of Motzkin excursions of length n with an even number of peaks.

1, 1, 1, 2, 5, 11, 26, 65, 164, 421, 1101, 2912, 7777, 20957, 56891, 155418, 426975, 1178841, 3269023, 9101182, 25428895, 71279177, 200391716, 564899237, 1596399798, 4521769035, 12835037619, 36504130056, 104012102095, 296872273835, 848694416554, 2429884047993

Offset

0,4

Comments

A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0.

A peak is an occurrence of the pattern UD.

Links

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

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

D-finite with recurrence 2*n*(n+2)*(6213*n-138098)*a(n) +(n-1)*(12426*n^2+978417*n+821680)*a(n-1) +2*(-23065*n^3-728759*n^2+2760574*n-410840)*a(n-2) +2*(-292946*n^3 +3649919*n^2 -11479673*n +8929300)*a(n-3) +2*(233455*n^3 -3707982*n^2 +13757984*n -13497400)*a(n-4) +(608874*n^3 -5758645*n^2 +11199163*n +5963900)*a(n-5) +2*(848625*n^3 -11463971*n^2 +51225442*n -77109420)*a(n-6) -16*(n-7)*(2213*n^2 +270746*n -1493325)*a(n-7) -24*(88769*n -321795)*(n-7)*(n-8)*a(n-8)=0. - R. J. Mathar, Jan 25 2023

a(n) + A307578(n) = A001006(n). - R. J. Mathar, Jan 25 2023

Example

For n = 4 the a(4) = 5 paths are HHHH, HUHD, UHDH, UHHD, UDUD.

Maple

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

Mathematica

b[x_, y_, t_, c_] := b[x, y, t, c] = If[y > x || 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];
a /@ Range[0, 35] (* Jean-François Alcover, May 12 2020, after Maple *)

Crossrefs

Cf. A001006.

Sequence in context: A235496 A025245 A300125 * A079223 A095892 A239311

Adjacent sequences: A307573 A307574 A307575 * A307577 A307578 A307579

Keyword

nonn

Author

Andrei Asinowski, Apr 15 2019

Status

approved