

A007040


Number of (marked) cyclic nbit 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 nprism 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 qary 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+1m*q*x)/(1q*x+(q1)*x^(m+1))  (m+1)/(1x^(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) = ((1x^m)/(1x))*(q*x + (q1)*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) = ((q1)*x*(1x^m)/(1x))*g(m, q, x).
A necklace is an unmarked cyclic string. If f3(m,q,n) is the number of qary necklaces of length n with no runs of length > m (and wrapping around is allowed), then f3(m,q,n) = (1/n)*Sum_{dn} 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) = (q1)*x*(1x^m)/((1x)*(1x^(m+1)))  Sum_{s>=1} (phi(s)/s)*log(1  (q1)*(x^s  x^(s*(m+1)))/(1x^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), 295302.
A. Burstein and H. S. Wilf, On cyclic strings without long constant blocks, Fibonacci Quarterly, 35 (1997), 240247.
A. E. Edlin and D. Zeilberger, The GouldenJackson cluster method for cyclic words, Adv. Appl. Math., 25 (2000), 228232.
W. Florek, A class of generalized Tribonacci sequences applied to counting problems, Appl. Math. Comput., 338 (2018), 809821.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 16621674.
Matthew Macauley, Jon McCammond, Henning S. Mortveit, Dynamics groups of asynchronous cellular automata, Journal of Algebraic Combinatorics, Vol 33, No 1 (2011), pp. 1135.
A. McLeod and W. O. J. Moser, Counting cyclic binary strings, Math. Mag., 80 (No. 1, 2007), 2937.
W. O. J. Moser, On cyclic binary nbit 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, 26.
Noriaki Sannomiya, Hosho Katsura, Yu Nakayama, Supersymmetry breaking and NambuGoldstone fermions with cubic dispersion, arXiv preprint arXiv:1612.02285 [condmat.strel], 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(n2) + 2*a(n3) + a(n4), n >= 7.  David W. Wilson
a(n) = n*Sum_{k=1..n} binomial(2*k, n2*k)/k, n > 1, a(0)=0, a(1)=2.  Vladimir Kruchinin, Oct 12 2011
G.f.: 2*x*(1+x+2*x^2x^4)/((1xx^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(n1), 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]^(n2)*[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



