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,13

Links

Alois P. Heinz, Antidiagonals n = 0..115, flattened

Wikipedia, Counting lattice paths

Formula

Column k is INVERTi transform of row k of A368025.

Example

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, ...

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);

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.

Sequence in context: A108561 A174626 A264909 * A104579 A079531 A182882

Adjacent sequences: A378107 A378109 A378110 * A378113 A378114 A378115

Keyword

nonn,tabl,new

Author

Alois P. Heinz, Nov 16 2024

Status

approved