A329673 Number of meanders of length n with Motzkin-steps avoiding the consecutive steps HH.

1, 2, 4, 10, 24, 60, 152, 388, 1000, 2592, 6752, 17664, 46368, 122080, 322240, 852464, 2259552, 5999552, 15954560, 42486592, 113282048, 302386304, 807999744, 2161077120, 5785032448, 15498450944, 41551965184, 111478804480, 299274439680, 803905119232, 2160632498176, 5810087371520

Offset

0,2

Comments

The Motzkin step set is U=(1,1), H=(1,0) and D=(1,-1). A meander is a path starting at (0,0) and never crossing the x-axis, i.e., staying at nonnegative altitude.

Links

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

Formula

G.f.: -(1-2*t-2*t^2-sqrt(1-4*t^2-8*t^3-4*t^4))/(2*t*(1-2*t-2*t^2)).

D-finite with recurrence (n+1)*a(n) -2*a(n-1) -4*n*a(n-2) +8*(-n+2)*a(n-3) +4*(-n+3)*a(n-4)=0. - R. J. Mathar, Jan 25 2023

Example

a(2)=4 since we have 4 meanders of length 2 avoiding HH, namely UU, UH, UD and HU.

Crossrefs

Cf. A104545 which counts excursions avoiding consecutive HH steps. Cf. A329672 and A329674 which count meanders avoiding consecutive UU and DD respectively.

Sequence in context: A100087 A291419 A088354 * A055919 A006575 A377256

Adjacent sequences: A329670 A329671 A329672 * A329674 A329675 A329676

Keyword

nonn,walk

Author

Valerie Roitner, Nov 26 2019

Status

approved