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

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

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

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

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

Cf. A000032, A007040, A057079, A111734.

Sequence in context: A237614 A257255 A248765 * A025248 A213170 A321741

Adjacent sequences: A007036 A007037 A007038 * A007040 A007041 A007042

Keyword

nonn,easy,eigen

Author

N. J. A. Sloane

Status

approved