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

Author

Andrew Woods, Jan 12 2015

Keywords

• nonn
• easy

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

Crossrefs

Cf. A001590, A196700.

Programs

Mathematica

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

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

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

Extensions

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