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
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Jun 01 2017
STATUS
approved