A287776 Number of Dyck paths of semilength n such that every peak at level y > 1 is preceded by (at least) one peak at level y-1 and is followed by (at least) one peak at level y-1.

1, 1, 1, 1, 2, 4, 8, 17, 39, 95, 241, 629, 1679, 4572, 12684, 35812, 102774, 299371, 883848, 2641121, 7978262, 24337821, 74908008, 232451921, 726831776, 2288799963, 7255401745, 23143158678, 74256591422, 239582207959, 777047305709, 2532730030266, 8293970682858

Offset

0,5

Links

Alois P. Heinz, Table of n, a(n) for n = 0..430

Axel Bacher, Progressive and rushed Dyck paths, arXiv:2403.08120 [math.CO], 2024. See p. 7.

Alois P. Heinz, Animation of a(9) = 95 paths

Wikipedia, Counting lattice paths

Example

 a(4) = 2:                 /\
            /\/\/\/\    /\/  \/\  .
 a(5) = 4:                   /\        /\          /\/\
            /\/\/\/\/\  /\/\/  \/\  /\/  \/\/\  /\/    \/\  .

Maple

b:= proc(x, y, k, h, t) option remember; `if`(x=0, `if`(h<2, 1, 0),
      `if`(y<=k and y<x-1, b(x-1, y+1, k, h, 1), 0) +`if`(y>0,
       b(x-1, y-1, max(y, k), `if`(t=1 and h<=y+1, y, h), 0), 0))
    end:
a:= n-> b(2*n, 0$4):
seq(a(n), n=0..35);

Mathematica

b[x_, y_, k_, h_, t_] := b[x, y, k, h, t] = If[x == 0, If[h < 2, 1, 0], If[y <= k && y < x - 1, b[x - 1, y + 1, k, h, 1], 0] + If[y > 0, b[x - 1, y - 1, Max[y, k], If[t == 1 && h <= y + 1, y, h], 0], 0]];
a[n_] := b[2n, 0, 0, 0, 0];
Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Jun 01 2018, from Maple *)

Crossrefs

Cf. A000108, A287709.

Sequence in context: A371726 A054199 A054197 * A137856 A373353 A304970

Adjacent sequences: A287773 A287774 A287775 * A287777 A287778 A287779

Keyword

nonn

Author

Alois P. Heinz, May 31 2017

Status

approved