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
Offset: 0
Keywords
Examples
For n = 3 the a(3) = 9 paths are UUU, UUH, UHU, UHH, UHD, HUU, HUH, HHU, HHH.
Links
- 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, 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]; a /@ Range[0, 35] (* Jean-François Alcover, May 12 2020, after Maple *)
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
Comments