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

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.

Links

Table of n, a(n) for n=0..65.

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

Example

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.

Prog

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

Crossrefs

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

Sequence in context: A026758 A130523 A034363 * A368735 A026769 A257365

Adjacent sequences: A378806 A378807 A378808 * A378810 A378811 A378812

Keyword

nonn,easy,tabl

Author

John Tyler Rascoe, Dec 08 2024

Status

approved