|
%I #41 Jul 18 2018 02:54:02
%S 0,1,2,2,2,5,4,7,10,14,18,31,40,63,94,142,210,329,492,765,1170,1810,
%T 2786,4341,6712,10461,16274,25414,39650,62075,97108,152287,238838,
%U 375166,589526,927555,1459960,2300347,3626242,5721044,9030450,14264309,22542396,35646311,56393862
%N Number of n-bit binary necklaces (unmarked cyclic n-bit binary strings) containing no runs of length > 2.
%C This is the "unmarked" version of sequence A007040. An unmarked cyclic string is a necklace. Notice that we define a(1) = 0 and a(2) = 1 because wrapping around the circle is allowed here (otherwise we would have to let a(1) = 2 and a(2) = 3).
%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 (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 If f3(m,q,n) is the number of q-ary necklaces (= unmarked cyclic strings) 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 If A(x) is the g.f. of the current sequence (a(n): n >= 1), we have A(x) = F3(m=2, q=2, x). Also, a(n) = f3(m=2, q=2, n) = (1/n)*Sum_{d|n} phi(n/d)*f2(m=2, q=2, d). Note that f2(m=2, q=2, n=1) = 0 and f2(m=2, q=2, n) = A007040(n) for n >= 2.
%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 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 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 (1993), no. 1, 2-6.
%F For proofs of the following formulae, see the comments above.
%F a(n) = (1/n)*Sum_{d|n} phi(n/d)*A007040(d)*I(d > 1), where I(condition) = 1 if the condition holds, and 0 otherwise.
%F a(n) = A000358(n) - A011655(n). (This formula is the "unmarked" version of E. W. Weisstein's formula that can be found in the comments for sequence A007040.)
%F a(p) = A007040(p)/p for p prime >= 2.
%F G.f.: A(x) = -x*(1+x)/(1-x^3) - Sum_{s>=1} (phi(s)/s)*log(1 - x^s - x^(2*s)) = (g.f. of A000358) - (g.f. of A011655).
%e For n=1 we have no allowable necklaces (because the strings 0 and 1 can be wrapped around themselves on a circle, and thus they contain runs of length > 2).
%e For n=2, the only allowable necklace is 01 (because 00 and 11 can be wrapped around themselves on a circle, and thus they contain runs of length > 2).
%e For n=3, the allowable necklaces are 011 and 100.
%e For n=4, the allowable necklaces are 0011 and 1010.
%e For n=5, the allowable necklaces are 01010 and 10101.
%e For n=6, the allowable necklaces are 010101, 001001, 110110, 101001, and 010110.
%o (PARI) a(n) = (1/n) * sumdiv(n, d, eulerphi(n/d)*(fibonacci(d-1)+fibonacci(d+1))) - sign(n%3); \\ _Michel Marcus_, Jul 10 2018; using 2nd formula
%Y Cf. A000358, A007040, A011655, A092297, A218034.
%K nonn
%O 1,3
%A _Petros Hadjicostas_, Jul 09 2018
%E More terms from _Michel Marcus_, Jul 10 2018
|
