A209239 Number of length n words on {0,1,2} with no four consecutive 0's.

1, 3, 9, 27, 80, 238, 708, 2106, 6264, 18632, 55420, 164844, 490320, 1458432, 4338032, 12903256, 38380080, 114159600, 339561936, 1010009744, 3004222720, 8935908000, 26579404800, 79059090528, 235157252096, 699463310848

Offset: 0

Author

Geoffrey Critzer, Jan 13 2013

Keywords

• nonn
• easy

References

• R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, page 377.

Links

• D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 7.
• Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, J. Int. Seq. 18 (2015) # 15.4.7.
• Index entries for linear recurrences with constant coefficients, signature (2,2,2,2).

Crossrefs

Cf. A000079, A028859, A119826.

Programs

Mathematica

nn=25; CoefficientList[Series[(1-x^4)/(1-3x+2x^5), {x,0,nn}], x]
LinearRecurrence[{2,2,2,2},{1,3,9,27},40] (* Harvey P. Dale, Sep 13 2018 *)

Formula

O.g.f.: (1 - x^4)/(1 - 3*x+ 2*x^5) = (1+x)*(1+x^2)/(1-2*x-2*x^2-2*x^3-2*x^4).

a(n) = A160175(n) + A160175(n-1) + A160175(n-2) + A160175(n-3). - R. J. Mathar, Aug 04 2019

a(n) = 2*(a(n-1) + a(n-2) + a(n-3) + a(n-4)) for n>=4, with a(0) = 1, a(1) = 3, a(2) = 9, a(3) = 27. - Taras Goy, Aug 04 2019