A287847 Number A(n,k) of Dyck paths of semilength n such that no level has more than k peaks; square array A(n,k), n >= 0, k >= 0, read by descending antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 3, 0, 1, 1, 2, 4, 5, 0, 1, 1, 2, 5, 12, 13, 0, 1, 1, 2, 5, 13, 31, 31, 0, 1, 1, 2, 5, 14, 40, 90, 71, 0, 1, 1, 2, 5, 14, 41, 119, 264, 181, 0, 1, 1, 2, 5, 14, 42, 130, 376, 797, 447, 0, 1, 1, 2, 5, 14, 42, 131, 414, 1202, 2402, 1111, 0

Offset: 0

Author

Alois P. Heinz, Jun 01 2017

Keywords

• nonn
• tabl

Examples

			. A(3,1) = 3:                    /\
.                 /\    /\      /  \
.              /\/  \  /  \/\  /    \   .
.
. A(3,2) = 4:                            /\
.                 /\    /\      /\/\    /  \
.              /\/  \  /  \/\  /    \  /    \   .
.
. A(3,3) = 5:                                    /\
.                         /\    /\      /\/\    /  \
.              /\/\/\  /\/  \  /  \/\  /    \  /    \   .
.
Square array A(n,k) begins:
  1,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   1,   1,   1,   1,   1,   1, ...
  0,  1,   2,   2,   2,   2,   2,   2, ...
  0,  3,   4,   5,   5,   5,   5,   5, ...
  0,  5,  12,  13,  14,  14,  14,  14, ...
  0, 13,  31,  40,  41,  42,  42,  42, ...
  0, 31,  90, 119, 130, 131, 132, 132, ...
  0, 71, 264, 376, 414, 427, 428, 429, ...
		

Links

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

Crossrefs

Columns k=0-10 give: A000007, A281874, A287966, A287967, A287968, A287969, A287970, A287971, A287972, A287973, A287974.

Main diagonal and first two lower diagonals give: A000108, A001453, A120304.

Cf. A287822.

Programs

Maple

b:= proc(n, k, j) option remember; `if`(j=n, 1, add(
      b(n-j, k, i)*add(binomial(i, m)*binomial(j-1, i-1-m),
       m=max(0, i-j)..min(k, i-1)), i=1..min(j+k, n-j)))
    end:
A:= proc(n, k) option remember; `if`(n=0, 1, (m->
      add(b(n, m, j), j=1..m))(min(n, k)))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

b[n_, k_, j_] := b[n, k, j] = If[j == n, 1, Sum[b[n - j, k, i]*Sum[ Binomial[i, m]*Binomial[j - 1, i - 1 - m], {m, Max[0, i - j], Min[k, i - 1]}], {i, 1, Min[j + k, n - j]}]];
A[n_, k_] := A[n, k] = If[n==0, 1, Sum[b[n, #, j], {j, 1, #}]&[Min[n, k]]];
Table[A[n, d - n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, May 25 2018, translated from Maple *)

Python

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def b(n, k, j): return 1 if j==n else sum([b(n - j, k, i)*sum([binomial(i, m)*binomial(j - 1, i - 1 - m) for m in range(max(0, i - j), min(k, i - 1) + 1)]) for i in range(1, min(j + k, n - j) + 1)])
@cacheit
def A(n, k):
    if n==0: return 1
    m=min(n, k)
    return sum([b(n, m , j) for j in range(1, m + 1)])
for d in range(21): print([A(n, d - n) for n in range(d + 1)]) # Indranil Ghosh, Aug 16 2017

Formula

A(n,k) = Sum_{j=0..k} A287822(n,j).