|
%I #63 May 11 2018 01:49:39
%S 1,2,3,3,4,4,6,6,9,11,16,20,32,42,65,95,144,212,330,494,767,1171,1812,
%T 2788,4342,6714,10463,16275,25416,39652,62076,97110,152289,238839,
%U 375168,589528,927556,1459962,2300349,3626243,5721046,9030452,14264310,22542398,35646313,56393863,89264836,141358276,223959712
%N Number of n-bead binary necklaces (no turning over allowed) that avoid the subsequence 110.
%C The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).
%C The proofs of all my formulas below become evident once it is realized that A001612(n) gives the number of cyclic sequences of length n consisting of zeros and ones that avoid the pattern 001 (or equivalently, the pattern 110) provided the positions of zeros and ones on a circle are fixed. Everything else follows from the material that can be found in A001612. - _Petros Hadjicostas_, Jan 11 2017
%H Petros Hadjicostas and L. 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 Petros Hadjicostas, <a href="/A274017/a274017.pdf">Proof of two formulas for a(n).</a>
%H Marko Riedel, <a href="/A274017/a274017.maple.txt">Maple code for this sequence</a>.
%H Math Stackexchange, Marko Riedel et al. <a href="http://math.stackexchange.com/questions/1812920/">Counting circular sequences</a>.
%F From _Petros Hadjicostas_, Jan 11 2017: (Start)
%F For all the formulas below, assume n>=1.
%F a(n) = 1 + A000358(n). (Notice the different offsets.)
%F a(n) = 1 + (1/n) * Sum_{d|n} totient(n/d)*(Fibonacci(d-1)+Fibonacci(d+1)).
%F a(n) = (1/n) * Sum_{d divides n} totient(n/d)*A001612(d).
%F G.f. = x/(1-x) + Sum_(k>=1} phi(k)/k * log(1/(1-B(x^k))) where B(x)=x*(1+x). (This is a modification of a formula due to _Joerg Arndt_.)
%F G.f. = Sum_{k>=1} phi(k)/k * log(1/C(x^k)) where C(x) = (1-x)*(1-B(x)). (End)
%F a(n) = 1 + (1/n) * Sum_{d|n} A000010(n/d)*A000204(d). [After the second formula above given by Hadjicostas]. - _Antti Karttunen_, Jan 12 2017
%e The following necklace
%e . 1-1
%e . / \
%e . 0 0
%e . | |
%e . 1 1
%e . \ /
%e . 0-0
%e contains one instance of the subsequence starting in the upper left corner. Unlike a bracelet, the necklace is oriented.
%e a(8) = 9: 00000000, 00000001, 00000101, 00001001, 00010001, 00010101, 00100101, 01010101, 11111111.
%e a(9) = 11: 000000000, 000000001, 000000101, 000001001, 000010001, 000010101, 000100101, 000101001, 001001001, 001010101, 111111111.
%Y Cf. A000010, A000031, A000045, A000204, A000358, A001612, A093305, A274018, A274019, A274020.
%K nonn
%O 0,2
%A _Marko Riedel_, Jun 06 2016
|
