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

Author

Alois P. Heinz, Jun 20 2017

Keywords

• nonn
• tabl

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.

Examples

			. 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, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..26, flattened
• Wikipedia, Counting lattice paths

Crossrefs

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

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

Main diagonal gives A288940.

Programs

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 *)