A288972 Number A(n,k) of Dyck paths having exactly k peaks in each of the levels 1,...,n and no other peaks; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 9, 10, 1, 1, 1, 44, 471, 92, 1, 1, 1, 225, 27076, 82899, 1348, 1, 1, 1, 1182, 1713955, 102695344, 36913581, 28808, 1, 1, 1, 6321, 114751470, 147556480375, 1565018426896, 34878248649, 845800, 1

Offset

0,9

Comments

The semilengths of Dyck paths counted by A(n,k) are elements of the integer interval [k*n+n-1, k*n*(n+1)/2] for n,k>0.

Links

Alois P. Heinz, Antidiagonals n = 0..26, flattened

Wikipedia, Counting lattice paths

Example

. A(3,1) = 10:
.
.        /\        /\          /\        /\
.     /\/  \      /  \/\    /\/  \      /  \/\
.  /\/      \  /\/      \  /      \/\  /      \/\
.
.                /\        /\                /\
.           /\  /  \      /  \  /\    /\    /  \
.        /\/  \/    \  /\/    \/  \  /  \/\/    \
.
.              /\        /\            /\
.         /\  /  \      /  \    /\    /  \  /\
.        /  \/    \/\  /    \/\/  \  /    \/  \/\  .
.
Square array A(n,k) begins:
  1,    1,        1,             1,                 1, ...
  1,    1,        1,             1,                 1, ...
  1,    2,        9,            44,               225, ...
  1,   10,      471,         27076,           1713955, ...
  1,   92,    82899,     102695344,      147556480375, ...
  1, 1348, 36913581, 1565018426896, 81072887990665625, ...

Maple

b:= proc(n, k, j, v) option remember; `if`(n=j, `if`(v=1, 1, 0),
      `if`(v<2, 0, add(b(n-j, k, i, v-1)*(binomial(i, k)*
       binomial(j-1, i-1-k)), i=1..min(j+k, n-j))))
    end:
A:= proc(n, k) option remember; `if`(n=0 or k=0, 1,
      add(b(w, k, k, n), w=k*n+n-1..k*n*(n+1)/2))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

b[n_, k_, j_, v_]:=b[n, k, j, v]=If[n==j, If[v==1, 1, 0], If[v<2, 0, Sum[b[n - j, k, i, v - 1] Binomial[i, k] Binomial[j - 1, i - 1 - k], {i, Min[j + k, n - j]}]]]; A[n_, k_]:=A[n, k]=If[n==0 || k==0, 1, Sum[b[w, k, k, n], {w, k*n + n - 1, k*n*(n + 1)/2}]]; Table[A[n, d - n], {d, 0, 10}, {n, 0, d}] // Flatten (* Indranil Ghosh, Jul 06 2017, after Maple code *)

Crossrefs

Columns k=0-2 give: A000012, A289020, A289054.

Rows n=0+1,2,3 give: A000012, A176479, A289030.

Main diagonal gives A288940.

Sequence in context: A061538 A123602 A208896 * A065521 A225700 A156188

Adjacent sequences: A288969 A288970 A288971 * A288973 A288974 A288975

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 20 2017

Status

approved