A078679 Number of Grand Motzkin paths of length n with no zigzags, that is with no factors UDU and DUD.

1, 1, 3, 7, 17, 43, 111, 291, 771, 2059, 5533, 14943, 40523, 110271, 300949, 823417, 2257877, 6203239, 17071779, 47054475, 129872499, 358896927, 992907525, 2749737663, 7622185263, 21146597511, 58714466733, 163142652877, 453612137587, 1262048222181, 3513361583965

Offset: 0

Author

Emanuele Munarini, Dec 17 2002

Keywords

• easy
• nonn

Comments

Also number of words on the alphabet {0,1,h} with length n, with an equal number of 1's and 0's and avoiding zigzags that is avoiding the subwords 101 and 010.

Examples

			For n = 3 we have the words hhh, 01h, 0h1, h01, 10h, 1h0, h10.
		

Links

• Emanuele Munarini and N. Z. Salvi, Binary strings without zigzags, Séminaire Lotharingien de Combinatoire, B49h (2004), 15 pp.

Crossrefs

Cf. A078678.

Programs

Mathematica

Table[SeriesCoefficient[Series[Sqrt[ ( 1 - x + x^2 ) / ( 1 - 3 x + x^3 + x^4 )], {x, 0, n}], n], {n, 0, 40}]

Maxima

a(n):=coeff(taylor(sqrt((1-x+x^2)/(1-3*x+x^3+x^4)),x,0,n),x,n);
makelist(a(n),n,0,12); /* Emanuele Munarini, Jul 07 2011 */

Formula

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

Recurrence: 0 = (n+6)*a(n+6) - (4*n+21)*a(n+5) + (4*n+15)*a(n+4) - (2*n+3)*a(n+3) + a(n+2) - a(n+1) + (n+1)*a(n).