login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007040 Number of (marked) cyclic n-bit binary strings containing no runs of length > 2.
(Formerly M0354)
8
2, 2, 6, 6, 10, 20, 28, 46, 78, 122, 198, 324, 520, 842, 1366, 2206, 3570, 5780, 9348, 15126, 24478, 39602, 64078, 103684, 167760, 271442, 439206, 710646, 1149850, 1860500, 3010348, 4870846, 7881198, 12752042, 20633238, 33385284, 54018520 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

For n >= 3, also the number of maximal independent vertex sets (and minimal vertex covers) in the n-prism graph. - Eric W. Weisstein, Mar 30 and Aug 07 2017

From Petros Hadjicostas, Jul 08 2018: (Start)

Let q and m be positive integers. We denote by f1(m,q,n) the number of (marked) cyclic q-ary strings of length n that contain no runs of lengths > m when no wrapping around is allowed, and by f2(m,q,n) when wrapping around is allowed.

It is clear that f1(m,q,n) = f2(m,q,n) for n > m, but f1(m,q,n) = q^n and f2(m,q,n) = q^n - q when 1 <= n <= m.

Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).

Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).

By generalizing Moser (1991, 1993), Burstein and Wilf (1997) proved that the g.f. of the numbers f1(m,q,n) is F1(m,q,x) = ((1-x^m)/(1-x))*(q*x + (q-1)*x* g(m, q, x)).

Using the above formula by Burstein and Wilf (1997), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f2(m,q,n) is F2(m,q,x) = ((q-1)*x*(1-x^m)/(1-x))*g(m, q, x).

A necklace is an unmarked cyclic string. If f3(m,q,n) is the number of q-ary necklaces of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m,q,d), where phi(.) is Euler's totient function. Using this formula and F2(m,q,x), Hadjicostas and Zhang (2018) proved that the g.f. of the numbers f3(m,q,n) is given by F3(m,q,x) = -(q-1)*x*(1-x^m)/((1-x)*(1-x^(m+1))) - Sum_{s>=1} (phi(s)/s)*log(1 - (q-1)*(x^s - x^(s*(m+1)))/(1-x^s)).

For the current sequence, we have q = 2 and m = 2. We have a(n) = f1(m=2, q=2, n) = f2(m=2, q=2, n) for n >= 3, but for a(1) and a(2) it is unclear what approach the author of the sequence is following. He has a(1) = q^1 = 2, but a(2) = q^2 - q = 2^2 - 2 = 2. (Note that, for q = m = 2, we have f1(m=2, q=2, 1) = 2, f1(m=2, q=2, 2) = 4, f2(m=2, q=2, 1) = 0, and f2(m=2, q=2, 2) = 2.)

If A(x) is the g.f. of the current sequence, we have A(x) = F1(m=2,q=2, x) - 2*x^2 = F2(m=2, q=2, x) + 2*x.

When m = 1 and q = 3, we have f1(m=1, q=3, n) = number of marked cyclic words on three letters with no two consecutive like letters. We have f1(m=1, q=3, n) = A092297(n) for n >= 2. This was first stated in the comments of that sequence by G. Critzer.

When m = 1 and q = 4, we have f1(m=1, q=4, n) = number of marked cyclic words on four letters with no two consecutive like letters. We have f1(m=1, q=4, n) = A218034(n) for n >= 1. This was first stated in the comments of that sequence by J. Arndt.

A generalization of the above formula by Burstein and Wilf (1997) was given by Taylor (2014) in Section 5 of his paper.

(End)

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 = 1..1000

Z. Agur, A. S. Fraenkel, S. T. Klein, The number of fixed points of the majority rule, Discr. Math., 70 (1988), 295-302.

A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240-247.

A. E. Edlin and D. Zeilberger, The Goulden-Jackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228-232.

W. Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809-821.

Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.

Matthew Macauley, Jon McCammond, 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.

Noriaki Sannomiya, Hosho Katsura, Yu Nakayama, Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion, arXiv preprint arXiv:1612.02285 [cond-mat.str-el], 2016. See Table I, line 2.

Jair Taylor, Counting Words with Laguerre Series, Electron. J. Combin., 21 (2014), P2.1.

Eric Weisstein's World of Mathematics, Maximal Independent Vertex Set

Eric Weisstein's World of Mathematics, Minimal Vertex Cover

Eric Weisstein's World of Mathematics, Prism Graph

Index entries for linear recurrences with constant coefficients, signature (0, 1, 2, 1).

FORMULA

a(n) = a(n-2) + 2*a(n-3) + a(n-4), n >= 7. - David W. Wilson

a(n) = n*Sum_{k=1..n} binomial(2*k, n-2*k)/k, n > 1, a(0)=0, a(1)=2. - Vladimir Kruchinin, Oct 12 2011

G.f.: 2*x*(1+x+2*x^2-x^4)/((1-x-x^2)*(1+x+x^2)). - Colin Barker, Mar 15 2012

a(n) = A000032(n) + 2*cos(2*Pi*n/3) for n > 1. - Eric W. Weisstein, Mar 30 2017

a(n) = 2*A100886(n-1), n>1. - R. J. Mathar, Jan 20 2018

a(n) = A000032(n) - A061347(n) for n > 1. - Wojciech Florek, Feb 18 2018

MATHEMATICA

Join[{2}, LinearRecurrence[{0, 1, 2, 1}, {2, 6, 6, 10}, 40]] (* Harvey P. Dale, Nov 09 2011 *)

Join[{2}, Table[n Sum[Binomial[2 k, n - 2 k]/k, {k, n}], {n, 2, 40}]] (* Harvey P. Dale, Nov 09 2011 *)

Table[LucasL[n] + 2 Cos[2 n Pi/3], {n, 20}] (* Eric W. Weisstein, Mar 30 2017 *)

PROG

(PARI) a(n)=if(n<3, 2, ([0, 1, 0, 0; 0, 0, 1, 0; 0, 0, 0, 1; 1, 2, 1, 0]^(n-2)*[2; 6; 6; 10])[1, 1]) \\ Charles R Greathouse IV, Jun 15 2015

CROSSREFS

Cf. A000032, A007039, A316660.

Sequence in context: A032302 A032214 A290261 * A032139 A032043 A200561

Adjacent sequences:  A007037 A007038 A007039 * A007041 A007042 A007043

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Name clarified by Petros Hadjicostas, Jul 08 2018

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 28 11:31 EST 2020. Contains 332323 sequences. (Running on oeis4.)