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

Links

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

Wikipedia, Counting lattice paths

Formula

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

Example

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

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

Prog

(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

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.

Sequence in context: A096799 A370292 A243081 * A377666 A336201 A271369

Adjacent sequences: A287844 A287845 A287846 * A287848 A287849 A287850

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 01 2017

Status

approved