A078679 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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.

LINKS

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

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

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