login
Number of n-bit binary necklaces (unmarked cyclic n-bit binary strings) containing no runs of length > 2.
1

%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