A231430 Number of ternary sequences which contain 000.

0, 0, 0, 1, 5, 21, 81, 295, 1037, 3555, 11961, 39667, 130049, 422403, 1361385, 4359115, 13880129, 43984227, 138795849, 436367131, 1367434577, 4272615603, 13315096089, 41397076939, 128429930465, 397665266595, 1229127726825, 3792875384251, 11686625364785

Offset

0,5

Comments

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.

Links

Harvey P. Dale, Table of n, a(n) for n = 0..1000

Index entries for linear recurrences with constant coefficients, signature (5,-4,-4,-6).

Formula

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

G.f.: x^3/(1 - 5*x + 4*x^2 + 4*x^3 +6*x^4). - Geoffrey Critzer, Jan 14 2014

Example

For n = 3, the only string is 000.
For n = 4, the 5 strings are: 0000,0001,0002,1000,2000.
For n = 5, there are: 1 with 5 0's, 12 with 4 0's, and 8 with just 3; total 21.

Mathematica

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 *)
(* or *)
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 *)
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 *)

Crossrefs

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

Cf. A186244 (with 00).

Sequence in context: A029870 A269915 A273393 * A269916 A273205 A269917

Adjacent sequences: A231427 A231428 A231429 * A231431 A231432 A231433

Keyword

nonn

Author

Toby Gottfried, Nov 09 2013

Status

approved