login
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.
13
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
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
Main diagonal and first two lower diagonals give: A000108, A001453, A120304.
Cf. A287822.
Sequence in context: A096799 A370292 A243081 * A336201 A271369 A308322
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jun 01 2017
STATUS
approved