|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,13
|
|
LINKS
|
|
|
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.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|