login
A078679
Number of Grand Motzkin paths of length n with no zigzags, that is with no factors UDU and DUD.
2
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).
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
KEYWORD
easy,nonn
AUTHOR
Emanuele Munarini, Dec 17 2002
STATUS
approved