A307564 Number of Motzkin excursions of length n with an even number of humps.

1, 1, 1, 1, 2, 6, 19, 57, 162, 442, 1176, 3092, 8119, 21451, 57275, 154771, 422970, 1166762, 3241282, 9049682, 25356109, 71229481, 200520398, 565594404, 1598436567, 4526347791, 12843234665, 36514629469, 104015020498, 296835850798, 848542194283, 2429468192825

Offset

0,5

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 ends at the altitude 0.

A hump is an occurrence of the pattern UHH...HD (the number of Hs in the pattern is not fixed, and can be 0).

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

D-finite with recurrence: n*(n+2)*(n-17)*a(n) +(n^3+93*n^2+14*n-60)*a(n-1) +(-37*n^3-96*n^2+376*n-60)*a(n-2) +(107*n^3-273*n^2-527*n+876)*a(n-3) +3*(-29*n^3+120*n^2+117*n-540)*a(n-4) +(-31*n^3+339*n^2-1178*n+1212)*a(n-5) +(37*n^3-60*n^2-1234*n+2844)*a(n-6) +(-107*n^3+981*n^2-1039*n-5628)*a(n-7) +(n-7)*(86*n^2-187*n-1068)*a(n-8) +30*(n-3)*(n-7)*(n-8)*a(n-9)=0. - R. J. Mathar, Jan 27 2020

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

Example

For n = 5 the a(5) = 6 paths are HHHHH, UDUHD, UHDUD, UDUDH, UDHUD, HUDUD.

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, t, 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, t, c] + b[x-1, y+1, 1, c]]];
a[n_] := b[n, 0, 0, 0];
a /@ Range[0, 35] (* Jean-François Alcover, May 11 2020, after Maple *)

Crossrefs

Cf. A001006.

Sequence in context: A121483 A077834 A325918 * A308240 A328658 A067675

Adjacent sequences: A307561 A307562 A307563 * A307565 A307566 A307567

Keyword

nonn

Author

Andrei Asinowski, Apr 15 2019

Status

approved