VOOZH about

URL: https://oeis.org/A007039

⇱ A007039 - OEIS

login
A007039
Number of cyclic binary n-bit strings with no alternating substring of length > 2.
9
2, 2, 2, 6, 12, 20, 30, 46, 74, 122, 200, 324, 522, 842, 1362, 2206, 3572, 5780, 9350, 15126, 24474, 39602, 64080, 103684, 167762, 271442, 439202, 710646, 1149852, 1860500, 3010350, 4870846, 7881194, 12752042, 20633240, 33385284, 54018522, 87403802, 141422322
OFFSET
1,1
COMMENTS
John W. Layman observes that the second differences give the sequence shifted to the right.
REFERENCES
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
LINKS
Z. Agur, A. S. Fraenkel, and S. T. Klein, The number of fixed points of the majority rule, Discr. Math., 70 (1988), 295-302.
Matthew Macauley, Jon McCammond, and Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 11-35.
A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80 (No. 1, 2007), 29-37.
W. O. J. Moser, On cyclic binary n-bit strings, Report from the Department of Mathematics and Statistics, McGill University, 1991. (Annotated scanned copy)
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 2-6.
E. Munarini and N. Z. Salvi, Circular Binary Strings without Zigzags, Integers: Electronic Journal of Combinatorial Number Theory 3 (2003), #A19. See relation (8) on page 5.
FORMULA
For n >= 5, a(n) = 2a(n-1) - a(n-2) + a(n-4). - David W. Wilson
G.f.: 2*x*(1+x)*(1-2*x+2*x^2)/((1-x+x^2)*(1-x-x^2)). - Colin Barker, Mar 28 2012
a(n) = A000032(n) + A057079(n + 1). - John M. Campbell, Dec 29 2016
a(n) = abs(A111734(n)). - Alois P. Heinz, Oct 08 2017
E.g.f.: 2*exp(x/2)*(cos(sqrt(3)*x/2) + cosh(sqrt(5)*x/2)) - 4. - Stefano Spezia, Mar 09 2025
EXAMPLE
G.f. = 2*x + 2*x^2 + 2*x^3 + 6*x^4 + 12*x^5 + 20*x^6 + 30*x^7 + 46*x^8 + ...
MATHEMATICA
CoefficientList[Series[2*(1+x)*(1-2*x+2*x^2)/((1-x+x^2)*(1-x-x^2)), {x, 0, 40}], x] (* Vincenzo Librandi, Apr 16 2012 *)
a[n_ /; n<4] = 2; a[4] = 6; a[n_] := a[n] = 2*a[n-1] - a[n-2] + a[n-4]; Array[a, 39] (* Jean-François Alcover, Oct 08 2017 *)
PROG
(PARI) Vec(2*x*(1-x+2*x^3)/((1-x-x^2)*(1-x+x^2))+O(x^66)) \\ Joerg Arndt, Oct 27 2015
CROSSREFS
KEYWORD
nonn,easy,eigen
STATUS
approved