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
KEYWORD
easy,nonn
AUTHOR
Emanuele Munarini, Dec 17 2002
STATUS
approved