|
|
A231430
|
|
Number of ternary sequences which contain 000.
|
|
5
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
a(n) = 3*a(n-1) + 2* (3^(n-4) - a(n-4)).
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|