A288140 Number of Dyck paths of semilength n such that the number of peaks is weakly decreasing from lower to higher levels.

1, 1, 1, 3, 4, 12, 28, 63, 177, 455, 1233, 3383, 9359, 26809, 77078, 223201, 653982, 1934508, 5783712, 17431660, 52879184, 161386859, 495432345, 1530191918, 4754079840, 14849407892, 46604383972, 146897291083, 464892421363, 1477052536749, 4711124635655

Offset

0,4

Links

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

Wikipedia, Counting lattice paths

Example

. a(5) = 12:
.                       /\         /\         /\
.   /\/\/\/\/\   /\/\/\/  \   /\/\/  \/\   /\/  \/\/\
.
.    /\               /\/\       /\/\       /\/\
.   /  \/\/\/\   /\/\/    \   /\/    \/\   /    \/\/\
.
.         /\         /\           /\         /\
.      /\/  \       /  \/\     /\/  \       /  \/\
.   /\/      \   /\/      \   /      \/\   /      \/\  .

Maple

b:= proc(n, k, j) option remember; `if`(n=j, 1, add(add(
       b(n-j, t, i)*binomial(i, t)*binomial(j-1, i-1-t),
       t=max(k, i-j)..min(n-j, i-1)), i=1..n-j))
    end:
a:= n-> `if`(n=0, 1, add(b(n, k$2), k=1..n)):
seq(a(n), n=0..31);

Mathematica

b[n_, k_, j_] := b[n, k, j] = If[n == j, 1, Sum[Sum[b[n - j, t, i]* Binomial[i, t]*Binomial[j - 1, i - 1 - t], {t, Max[k, i - j], Min[n - j, i - 1]}], {i, 1, n - j}]];
a[n_] := If[n == 0, 1, Sum[b[n, k, k], {k, 1, n}]];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, May 29 2018, from Maple *)

Crossrefs

Cf. A000108, A008930, A048285, A288141, A288146, A288147.

Sequence in context: A002986 A147569 A090660 * A287594 A296271 A000208

Adjacent sequences: A288137 A288138 A288139 * A288141 A288142 A288143

Keyword

nonn

Author

Alois P. Heinz, Jun 05 2017

Status

approved