login
Number of ternary sequences which contain 000.
5

%I #19 Jul 27 2021 12:57:54

%S 0,0,0,1,5,21,81,295,1037,3555,11961,39667,130049,422403,1361385,

%T 4359115,13880129,43984227,138795849,436367131,1367434577,4272615603,

%U 13315096089,41397076939,128429930465,397665266595,1229127726825,3792875384251,11686625364785

%N Number of ternary sequences which contain 000.

%C Recurrence formula given below, a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)) based on following recursive construction: To a string of length (n-1) containing 000 add any of {0,1,2}. To a string of length (n-4) NOT containing 000, add 1000 or 2000. These two operations result in the two terms of the formula.

%H Harvey P. Dale, <a href="/A231430/b231430.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-4,-4,-6).

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

%F G.f.: x^3/(1 - 5*x + 4*x^2 + 4*x^3 +6*x^4). - _Geoffrey Critzer_, Jan 14 2014

%e For n = 3, the only string is 000.

%e For n = 4, the 5 strings are: 0000,0001,0002,1000,2000.

%e For n = 5, there are: 1 with 5 0's, 12 with 4 0's, and 8 with just 3; total 21.

%t t = {0, 0, 0, 1}; Do[AppendTo[t, 3 t[[-1]] + 2*(3^(n - 4) - t[[-4]])], {n, 4, 30}]; t (* _T. D. Noe_, Nov 11 2013 *)

%t (* or *)

%t nn=28;r=Solve[{s==2x s+2x a+2x b+1,a==x s,b==x a,c==3x c+x b},{s,a,b,c}];CoefficientList[Series[c/.r,{x,0,nn}],x] (* _Geoffrey Critzer_, Jan 14 2014 *)

%t CoefficientList[Series[x^3/(1-5x+4x^2+4x^3+6x^4),{x,0,40}],x] (* or *) LinearRecurrence[{5,-4,-4,-6},{0,0,0,1},40] (* _Harvey P. Dale_, Jul 27 2021 *)

%Y Cf. A119826 (without 000), A119827 (exactly one 000).

%Y Cf. A186244 (with 00).

%K nonn

%O 0,5

%A _Toby Gottfried_, Nov 09 2013