A007039 Number of cyclic binary n-bit strings with no alternating substring of length > 2.

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

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• eigen

Comments

John W. Layman observes that the second differences give the sequence shifted to the right.

Examples

			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 + ...
		

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 1000
• 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.
• Index entries for linear recurrences with constant coefficients, signature (2,-1,0,1).

Crossrefs

Cf. A000032, A007040, A057079, A111734.

Programs

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

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

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