A378113 Number of n-tuples (p_1, p_2, ..., p_n) of Dyck paths of semilength n, such that each p_i is never below p_{i-1} and the upper path p_n only touches the x-axis at its endpoints.

1, 1, 2, 23, 880, 105554, 40446551, 50637232553, 209584899607676, 2881189188022646406, 131778113962930341491415, 20065327661524165382215337625, 10173706896856510992170168595911888, 17178054578218938036671513200907244799852, 96590987238453485101729361602126273065518820938

Offset: 0

Author

Alois P. Heinz, Nov 16 2024

Keywords

• nonn

Examples

			a(2) = 2:
          /\       /\   /\
   (/\/\,/  \)   (/  \,/  \) .
The a(3) = 23 3-tuples can be encoded as 114, 115, 124, 125, 134, 135, 144, 145, 155, 224, 225, 244, 245, 255, 334, 335, 344, 345, 355, 444, 445, 455, 555, where the digits represent the following Dyck paths:
  1        2        3        4        5 /\
            /\         /\     /\/\     /  \
  /\/\/\   /  \/\   /\/  \   /    \   /    \ .
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..62
• Wikipedia, Counting lattice paths

Crossrefs

Main diagonal of A378112.

Cf. A000108, A355400.

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:
a:= n-> A(n$2):
seq(a(n), n=0..15);

Formula

a(n) = A378112(n,n).