|
%I M0354 #139 Jul 13 2020 06:35:29
%S 2,2,6,6,10,20,28,46,78,122,198,324,520,842,1366,2206,3570,5780,9348,
%T 15126,24478,39602,64078,103684,167760,271442,439206,710646,1149850,
%U 1860500,3010348,4870846,7881198,12752042,20633238,33385284,54018520
%N Number of (marked) cyclic n-bit binary strings containing no runs of length > 2.
%C 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
%C From _Petros Hadjicostas_, Jul 08 2018: (Start)
%C 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.
%C 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.
%C Burstein and Wilf (1997) and Edlin and Zeilberger (2000) considered f1(m,q,n) while Hadjicostas and Zhang considered f2(m,q,n).
%C Let g(m, q, x) = (m+1-m*q*x)/(1-q*x+(q-1)*x^(m+1)) - (m+1)/(1-x^(m+1)).
%C 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)).
%C 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).
%C 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)).
%C 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.)
%C 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.
%C 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.
%C 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.
%C A generalization of the above formula by Burstein and Wilf (1997) was given by Taylor (2014) in Section 5 of his paper. (End)
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Vincenzo Librandi, <a href="/A007040/b007040.txt">Table of n, a(n) for n = 1..1000</a>
%H Z. Agur, A. S. Fraenkel, and S. T. Klein, <a href="http://dx.doi.org/10.1016/0012-365X(88)90005-2">The number of fixed points of the majority rule</a>, Discr. Math., 70 (1988), 295-302.
%H A. Burstein and H. S. Wilf, <a href="https://www.fq.math.ca/Scanned/35-3/burstein.pdf">On cyclic strings without long constant blocks</a>, Fibonacci Quarterly, 35 (1997), 240-247.
%H A. E. Edlin and D. Zeilberger, <a href="https://doi.org/10.1006/aama.2000.0696">The Goulden-Jackson cluster method for cyclic words</a>, Adv. Appl. Math., 25 (2000), 228-232.
%H W. Florek, <a href="http://doi.org/10.1016/j.amc.2018.06.014">A class of generalized Tribonacci sequences applied to counting problems</a>, Appl. Math. Comput., 338 (2018), 809-821.
%H Petros Hadjicostas and Lingyun Zhang, <a href="https://doi.org/10.1016/j.disc.2018.03.007">On cyclic strings avoiding a pattern</a>, Discrete Mathematics, 341 (2018), 1662-1674.
%H Matthew Macauley, Jon McCammond, and Henning S. Mortveit, <a href="http://www.emis.de/journals/JACO/Volume33_1/hgv665924j44t770.html">Dynamics groups of asynchronous cellular automata</a>, Journal of Algebraic Combinatorics, 33(1) (2011), 11-35.
%H A. McLeod and W. O. J. Moser, <a href="http://www.jstor.org/stable/27642988">Counting cyclic binary strings</a>, Math. Mag., 80(1) (2007), 29-37.
%H W. O. J. Moser, <a href="/A007040/a007040.pdf">On cyclic binary n-bit strings</a>, Report from the Department of Mathematics and Statistics, McGill University, 1991. (Annotated scanned copy)
%H W. O. J. Moser, <a href="http://www.fq.math.ca/Scanned/31-1/moser.pdf">Cyclic binary strings without long runs of like (alternating) bits</a>, Fibonacci Quart. 31(1) (1993), 2-6.
%H Noriaki Sannomiya, Hosho Katsura, and Yu Nakayama, <a href="http://arxiv.org/abs/1612.02285">Supersymmetry breaking and Nambu-Goldstone fermions with cubic dispersion</a>, arXiv:1612.02285 [cond-mat.str-el], 2016. See Table I, line 2.
%H Jair Taylor, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p1">Counting Words with Laguerre Series</a>, Electron. J. Combin., 21 (2014), P2.1.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MaximalIndependentVertexSet.html">Maximal Independent Vertex Set</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/MinimalVertexCover.html">Minimal Vertex Cover</a>.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrismGraph.html">Prism Graph</a>.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,1,2,1).
%F a(n) = a(n-2) + 2*a(n-3) + a(n-4), n >= 7. - _David W. Wilson_
%F a(n) = n*Sum_{k=1..n} binomial(2*k, n-2*k)/k for n > 1 with a(0) = 0 and a(1) = 2. - _Vladimir Kruchinin_, Oct 12 2011
%F G.f.: 2*x*(1 + x + 2*x^2 - x^4)/((1 - x - x^2)*(1 + x + x^2)). - _Colin Barker_, Mar 15 2012
%F a(n) = A000032(n) + 2*cos(2*Pi*n/3) for n > 1. - _Eric W. Weisstein_, Mar 30 2017
%F a(n) = 2*A100886(n-1), n > 1. - _R. J. Mathar_, Jan 20 2018
%F a(n) = A000032(n) - A061347(n) for n > 1. - _Wojciech Florek_, Feb 18 2018
%t Join[{2}, LinearRecurrence[{0, 1, 2, 1}, {2, 6, 6, 10}, 40]] (* _Harvey P. Dale_, Nov 09 2011 *)
%t Join[{2}, Table[n Sum[Binomial[2 k, n - 2 k]/k, {k, n}], {n, 2, 40}]] (* _Harvey P. Dale_, Nov 09 2011 *)
%t Table[LucasL[n] + 2 Cos[2 n Pi/3], {n, 20}] (* _Eric W. Weisstein_, Mar 30 2017 *)
%o (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
%Y Cf. A000032, A007039, A316660.
%K nonn,nice,easy
%O 1,1
%A _N. J. A. Sloane_
%E Name clarified by _Petros Hadjicostas_, Jul 08 2018
|
