A329674 Number of meanders of length n with Motzkin-steps avoiding the consecutive steps DD.

1, 2, 5, 13, 34, 90, 240, 643, 1729, 4662, 12597, 34095, 92406, 250719, 680877, 1850457, 5032296, 13692674, 37274438, 101509476, 276535824, 753574253, 2054064713, 5600176231, 15271331416, 41651397245, 113618996429, 309979833301, 845805408448, 2308108658854, 6299205562846

Offset: 0

Author

Valerie Roitner, Nov 26 2019

Keywords

• nonn
• walk

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.

Examples

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

Crossrefs

Cf. A004148 (shifted by 1) which counts excursions avoiding consecutive DD steps.

Cf. A329672 and A329673 which count meanders avoiding consecutive UU or HH respectively.

Formula

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

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