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

1, 1, 3, 23, 265, 3942, 70395, 1445700, 33188889, 834702890, 22656163450, 656075013591, 20085981787831, 645418018740113, 21637970282382744, 753157297564682541, 27105935164769925549, 1005184072184843625837, 38295251586474334236780, 1495061191885030011433707

Offset

0,3

Links

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

Wikipedia, Counting lattice paths

Formula

INVERTi transform of A006149.

Example

a(2) = 3:
               /\            /\   /\       /\   /\   /\
   (/\/\,/\/\,/  \)   (/\/\,/  \,/  \)   (/  \,/  \,/  \)  .
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, 3):
seq(a(n), n=0..20);

Crossrefs

Column k=3 of A378112.

Cf. A000108, A006149.

Sequence in context: A159017 A385413 A004700 * A199544 A302117 A343772

Adjacent sequences: A378111 A378112 A378113 * A378115 A378116 A378117

Keyword

nonn

Author

Alois P. Heinz, Nov 16 2024

Status

approved