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

Author

Alois P. Heinz, Nov 16 2024

Keywords

• nonn

Examples

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

Links

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

Crossrefs

Column k=3 of A378112.

Cf. A000108, A006149.

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

Formula

INVERTi transform of A006149.