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

%I #15 Jun 07 2024 16:42:13

%S 1,3,6,9,14,23,36,57,90,143,226,357,566,895,1416,2241,3546,5611,8878,

%T 14049,22230,35175,55660,88073,139362,220519,348938,552141,873678,

%U 1382463,2187536,3461441,5477202,8666835,13713942,21700217,34337278,54333495,85974452

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

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,2,1,0,-1).

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

%F 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

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

%Y Cf. A003945.

%K nonn,easy

%O 0,2

%A _Miquel A. Fiol_, Jun 05 2024