A373447 Number of ternary strings of length n avoiding the substrings 00, 11, 22, 121, 212, 202.

1, 3, 6, 9, 14, 23, 36, 57, 90, 143, 226, 357, 566, 895, 1416, 2241, 3546, 5611, 8878, 14049, 22230, 35175, 55660, 88073, 139362, 220519, 348938, 552141, 873678, 1382463, 2187536, 3461441, 5477202, 8666835, 13713942, 21700217, 34337278, 54333495, 85974452

Offset: 0

Author

Miquel A. Fiol, Jun 05 2024

Keywords

• nonn
• easy

Examples

			For n=3 the a(3)=9 solutions are 010, 012, 020, 021, 101, 102, 120, 201, 210.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (0,1,2,1,0,-1).

Crossrefs

Cf. A003945.

Programs

Mathematica

LinearRecurrence[{0,1,2,1,0,-1},{1,3,6,9,14,23,36},40] (* Harvey P. Dale, Aug 04 2025 *)

Formula

a(n) = a(n-2) + 2*a(n-3) + a(n-4) - a(n-6).

G.f.: (x+1)*(x^2+x+1)*(x^3-x^2-x-1)/(-x^6+x^4+2*x^3+x^2-1). - Alois P. Heinz, Jun 05 2024