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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..62

Wikipedia, Counting lattice paths

Formula

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

Example

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 /\
            /\         /\     /\/\     /  \
  /\/\/\   /  \/\   /\/  \   /    \   /    \ .

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

Crossrefs

Main diagonal of A378112.

Cf. A000108, A355400.

Sequence in context: A273976 A098633 A015211 * A266992 A079480 A239398

Adjacent sequences: A378109 A378110 A378112 * A378114 A378115 A378117

Keyword

nonn,new

Author

Alois P. Heinz, Nov 16 2024

Status

approved