A378809 Triangle read by rows: T(n,k) is the number of peak and valleyless Motzkin meanders of length n with k horizontal steps.

1, 1, 1, 1, 2, 1, 1, 4, 3, 1, 1, 5, 9, 4, 1, 1, 7, 15, 16, 5, 1, 1, 8, 27, 34, 25, 6, 1, 1, 10, 37, 76, 65, 36, 7, 1, 1, 11, 55, 124, 175, 111, 49, 8, 1, 1, 13, 69, 216, 335, 351, 175, 64, 9, 1, 1, 14, 93, 309, 675, 776, 637, 260, 81, 10, 1

Offset: 0

Author

John Tyler Rascoe, Dec 08 2024

Keywords

• nonn
• easy
• tabl

Comments

Motzkin meanders are lattice paths starting at (0,0) with steps Up (0,1), Horizontal (1,0), and Down (0,-1) that stay weakly above the x-axis. Peak and valleyless Motzkin meanders avoid UD and DU.

Examples

			The triangle begins
   k=0   1   2   3   4   5   6   7
 n=0 1;
 n=1 1,  1;
 n=2 1,  2,  1;
 n=3 1,  4,  3,  1;
 n=4 1,  5,  9,  4,  1;
 n=5 1,  7, 15, 16,  5,  1;
 n=6 1,  8, 27, 34, 25,  6,  1;
 n=7 1, 10, 37, 76, 65, 36,  7,  1;
 ...
T(3,0) = 1: UUU.
T(3,1) = 4: UUH, UHU, UHD, HUU.
T(3,2) = 3: UHH, HHU, HUH.
T(3,3) = 1: HHH.
		

Crossrefs

Cf. column k=1 A001651, A005773, A088855, column k=2 A247643, row sums A308435, A378810.

Programs

PARI

A088855(n,k) = {binomial(floor((n-1)/2), floor((k-1)/2))*binomial(ceil((n-1)/2),ceil((k-1)/2))}
A_xy(N) = {my(x='x+O('x^N), h = sum(n=0,N, (1/(1-y*x)^(n+1)) * (if(n<1,1,0) + sum(k=1,n, A088855(n,k)*x^(n+k-1)*(y^(k-1)) )) )); for(n=0,N-1,print(Vecrev(polcoeff(h,n))))}
A_xy(10)

Formula

G.f.: Sum_{n>=0} 1/(1-y*x)^(n+1) * ([n=0] + Sum_{k=1..n} A088855(n,k)*x^(n+k-1)*y^(k-1)).