OFFSET
0,1
COMMENTS
Tribonacci numbers 4*A001590(n+2) (i.e., tribonacci numbers t(n) = t(n-1) + t(n-2) + t(n-3) with t(0) = 0, t(1) = 4, t(2) = 8) for n > 2 are numbers of ternary sequences (q(1),q(2),...,q(n)), q(i) = 0,1,2, of length n such that all triples (q(i),q(i+1),q(i+2)) contain digits 0 and 1 at least once. In the other words {0,1} is a subset of each {q(i),q(i+1),q(i+2)}. Similarly, A075092(n), for n > 2, presents a number of ternary cyclic sequences with this property. Hence, a(n), for n > 2, gives a number of (ordinary) sequences which do not lead to cyclic sequences with triples (q(n-1),q(n),q(1)) and (q(n),q(1),q(2)) satisfying the above formulated condition. The special cases, n = 1,2, can be included in a way proposed in A001644.
The recurrence formula is the same as this for A075092, with different initial conditions.
LINKS
Wojciech Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809-821.
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31(1) (1993), 2-6.
Index entries for linear recurrences with constant coefficients, signature (0,1,4,1,0,-1).
FORMULA
a(n) = a(n-2) + 4*a(n-3) + a(n-4) - a(n-6), a(0) = -6, a(1) = 4, a(2) = 6, a(3) = 0, a(4) = 18, a(5) = 24.
G.f.: (4*x^5-2*x^4-20*x^3-12*x^2-4*x+6)/(-x^6+x^4+4*x^3+x^2-1).
EXAMPLE
If n = 4, then there are 24 finite sequences: 0010, 0011, 0012, 0100, 0101, 0102, 0110, 0120, 0210, nine analogous starting with 1, 2010, 2011, 2012, 2100, 2101, and 2102. Only six of them, namely 0011, 0101, 0110, 1001, 1010, 1100, yield cyclic sequences satisfying the restriction imposed. Therefore, a(4) = 24 - 6 = 18.
MATHEMATICA
nterms=50; LinearRecurrence[{0, 1, 4, 1, 0, -1}, {-6, 4, 6, 0, 18, 24}, nterms] (* Paolo Xausa, Nov 26 2021 *)
CROSSREFS
KEYWORD
sign,easy
AUTHOR
Wojciech Florek, Nov 25 2021
STATUS
approved