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

Author

Alois P. Heinz, Nov 16 2024

Keywords

• nonn
• tabl

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

Columns k=0-3 give: A019590(n+1), A120588, A355281, A378114.

Rows n=0+1,2,3 give: A000012, A001477, A101986.

Main diagonal gives A378113.

Cf. A000108, A078920, A123352, A368025.

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.