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

Offset

0,3

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.

References

E. Munarini and N. Zagaglia Salvi, Binary strings without zigzags, Séminaire Lotharingien de Combinatoire, vol. 49 (2004), Article B49h (electronic).

Links

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

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

Example

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

Mathematica

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

Prog

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

Crossrefs

Cf. A078678.

Sequence in context: A211277 A114589 A192908 * A025577 A085279 A153133

Adjacent sequences: A078676 A078677 A078678 * A078680 A078681 A078682

Keyword

easy,nonn

Author

Emanuele Munarini, Dec 17 2002

Status

approved