A248959 Number of ternary words of length n in which all digits 0..2 occur in every subword of 4 consecutive digits.

1, 3, 9, 27, 36, 72, 132, 240, 444, 816, 1500, 2760, 5076, 9336, 17172, 31584, 58092, 106848, 196524, 361464, 664836, 1222824, 2249124, 4136784, 7608732, 13994640, 25740156, 47343528, 87078324, 160162008, 294583860, 541824192, 996570060, 1832978112

Offset

0,2

Comments

For n < 4 the constraint is voidly satisfied: each of the n-digit words satisfies the definition since there is no subword of length 4. - M. F. Hasler, Jan 13 2015

Links

Colin Barker, Table of n, a(n) for n = 0..1000 (corrected by Georg Fischer, Jan 20 2019)

Index entries for linear recurrences with constant coefficients, signature (1,1,1).

Formula

G.f.: (1 + 2*x + 5*x^2 + 14*x^3 - 3*x^4 - 3*x^6)/(1 - x - x^2 - x^3). - Corrected by Colin Barker, Jan 12 2015

a(n) = a(n-1) + a(n-2) + a(n-3).

a(n) = A001590(n+1) * 12, for n>=4.

a(n) = A196700(n) * 6, for n>=4. - Alois P. Heinz, Jan 12 2015

Mathematica

Join[{1, 3, 9, 27}, LinearRecurrence[{1, 1, 1}, {36, 72, 132}, 30]] (* Harvey P. Dale, Mar 12 2015 *)

Prog

(PARI) Vec((1+2*x+5*x^2+14*x^3-3*x^4-3*x^6)/(1-x-x^2-x^3) + O(x^100)) \\ Colin Barker, Jan 12 2015; extended to indices 0..3 by M. F. Hasler, Jan 13 2015

Crossrefs

Cf. A001590, A196700.

Sequence in context: A305617 A292390 A211219 * A070362 A027889 A360423

Adjacent sequences: A248956 A248957 A248958 * A248960 A248961 A248962

Keyword

nonn,easy

Author

Andrew Woods, Jan 12 2015

Extensions

a(0)-a(3) from M. F. Hasler, Jan 13 2015

Status

approved