A378112 Number A(n,k) of k-tuples (p_1, p_2, ..., p_k) of Dyck paths of semilength n, such that each p_i is never below p_{i-1} and the upper path p_k only touches the x-axis at its endpoints; square array A(n,k), n>=0, k>=0, read by antidiagonals.
1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 2, 0, 1, 1, 3, 9, 5, 0, 1, 1, 4, 23, 55, 14, 0, 1, 1, 5, 46, 265, 400, 42, 0, 1, 1, 6, 80, 880, 3942, 3266, 132, 0, 1, 1, 7, 127, 2347, 23695, 70395, 28999, 429, 0, 1, 1, 8, 189, 5403, 105554, 824229, 1445700, 274537, 1430, 0
Offset: 0
Examples
A(3,2) = 9:
/\
/\/\ / \ /\ /\/\
(/\/\/\,/ \) (/\/\/\,/ \) (/ \/\,/ \)
.
/\ /\
/\ / \ /\ /\/\ /\ / \
(/ \/\,/ \) (/\/ \,/ \) (/\/ \,/ \)
.
/\ /\ /\
/\/\ /\/\ /\/\ / \ / \ / \
(/ \,/ \) (/ \,/ \) (/ \,/ \)
.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, 6, ...
0, 2, 9, 23, 46, 80, 127, ...
0, 5, 55, 265, 880, 2347, 5403, ...
0, 14, 400, 3942, 23695, 105554, 382508, ...
0, 42, 3266, 70395, 824229, 6601728, 40446551, ...
Links
- Alois P. Heinz, Antidiagonals n = 0..115, flattened
- Wikipedia, Counting lattice paths
Crossrefs
Programs
-
Maple
b:= proc(n, k) option remember; `if`(n=0, 1, 2^k*mul( (2*(n-i)+2*k-3)/(n+2*k-1-i), i=0..k-1)*b(n-1, k)) end: A:= proc(n, k) option remember; b(n, k)-add(A(n-i, k)*b(i, k), i=1..n-1) end: seq(seq(A(n, d-n), n=0..d), d=0..10);
Formula
Column k is INVERTi transform of row k of A368025.