

A316660


Number of nbit binary necklaces (unmarked cyclic nbit binary strings) containing no runs of length > 2.


1



0, 1, 2, 2, 2, 5, 4, 7, 10, 14, 18, 31, 40, 63, 94, 142, 210, 329, 492, 765, 1170, 1810, 2786, 4341, 6712, 10461, 16274, 25414, 39650, 62075, 97108, 152287, 238838, 375166, 589526, 927555, 1459960, 2300347, 3626242, 5721044, 9030450, 14264309, 22542396, 35646311, 56393862
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

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).
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 (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).
If f3(m,q,n) is the number of qary 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_{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)).
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_{dn} 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.


LINKS

Table of n, a(n) for n=1..45.
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.
Petros Hadjicostas and Lingyun Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 16621674.
W. O. J. Moser, Cyclic binary strings without long runs of like (alternating) bits, Fibonacci Quart. 31 (1993), no. 1, 26.


FORMULA

For proofs of the following formulae, see the comments above.
a(n) = (1/n)*Sum_{dn} phi(n/d)*A007040(d)*I(d > 1), where I(condition) = 1 if the condition holds, and 0 otherwise.
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.)
a(p) = A007040(p)/p for p prime >= 2.
G.f.: A(x) = x*(1+x)/(1x^3)  Sum_{s>=1} (phi(s)/s)*log(1  x^s  x^(2*s)) = (g.f. of A000358)  (g.f. of A011655).


EXAMPLE

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).
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).
For n=3, the allowable necklaces are 011 and 100.
For n=4, the allowable necklaces are 0011 and 1010.
For n=5, the allowable necklaces are 01010 and 10101.
For n=6, the allowable necklaces are 010101, 001001, 110110, 101001, and 010110.


PROG

(PARI) a(n) = (1/n) * sumdiv(n, d, eulerphi(n/d)*(fibonacci(d1)+fibonacci(d+1)))  sign(n%3); \\ Michel Marcus, Jul 10 2018; using 2nd formula


CROSSREFS

Cf. A000358, A007040, A011655, A092297, A218034.
Sequence in context: A103286 A285704 A058704 * A098101 A257670 A105960
Adjacent sequences: A316657 A316658 A316659 * A316661 A316662 A316663


KEYWORD

nonn


AUTHOR

Petros Hadjicostas, Jul 09 2018


EXTENSIONS

More terms from Michel Marcus, Jul 10 2018


STATUS

approved



