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,2

References

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

Links

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

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

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

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

Crossrefs

Cf. A000079, A028859, A119826.

Sequence in context: A059502 A291006 A289781 * A318773 A331631 A036142

Adjacent sequences: A209236 A209237 A209238 * A209240 A209241 A209242

Keyword

nonn,easy

Author

Geoffrey Critzer, Jan 13 2013

Status

approved