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

Links

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

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

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

Example

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

Mathematica

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

Crossrefs

Cf. A003945.

Sequence in context: A310173 A310174 A058597 * A362070 A310175 A146562

Adjacent sequences: A373444 A373445 A373446 * A373448 A373449 A373450

Keyword

nonn,easy

Author

Miquel A. Fiol, Jun 05 2024

Status

approved