cp's OEIS Frontend

A274017 Number of n-bead binary necklaces (no turning over allowed) that avoid the subsequence 110.

%I A274017 #68 Mar 07 2025 02:54:24
%S A274017 1,2,3,3,4,4,6,6,9,11,16,20,32,42,65,95,144,212,330,494,767,1171,1812,
%T A274017 2788,4342,6714,10463,16275,25416,39652,62076,97110,152289,238839,
%U A274017 375168,589528,927556,1459962,2300349,3626243,5721046,9030452,14264310,22542398,35646313,56393863,89264836,141358276,223959712
%N A274017 Number of n-bead binary necklaces (no turning over allowed) that avoid the subsequence 110.
%C A274017 The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).
%C A274017 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 A274017 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 A274017 Petros Hadjicostas, <a href="/A274017/a274017.pdf">Proof of two formulas for a(n).</a>
%H A274017 Marko Riedel, <a href="/A274017/a274017.maple.txt">Maple code for this sequence</a>.
%H A274017 Math Stackexchange, Marko Riedel et al. <a href="http://math.stackexchange.com/questions/1812920/">Counting circular sequences</a>.
%F A274017 From _Petros Hadjicostas_, Jan 11 2017: (Start)
%F A274017 For all the formulas below, assume n>=1.
%F A274017 a(n) = 1 + A000358(n). (Notice the different offsets.)
%F A274017 a(n) = 1 + (1/n) * Sum_{d|n} totient(n/d)*(Fibonacci(d-1)+Fibonacci(d+1)).
%F A274017 a(n) = (1/n) * Sum_{d divides n} totient(n/d)*A001612(d).
%F A274017 G.f.: 1/(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 A274017 G.f.: 1 + Sum_{k>=1} (phi(k)/k) * log(1/C(x^k)) where C(x) = (1-x)*(1-B(x)). (End)
%F A274017 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 A274017 The following necklace
%e A274017      1-1
%e A274017     /   \
%e A274017    0     0
%e A274017    |     |
%e A274017    1     1
%e A274017     \   /
%e A274017      0-0
%e A274017 contains one instance of the subsequence starting in the upper left corner. Unlike a bracelet, the necklace is oriented.
%e A274017 a(8) = 9: 00000000, 00000001, 00000101, 00001001, 00010001, 00010101, 00100101, 01010101, 11111111.
%e A274017 a(9) = 11: 000000000, 000000001, 000000101, 000001001, 000010001, 000010101, 000100101, 000101001, 001001001, 001010101, 111111111.
%Y A274017 Cf. A000010, A000031, A000045, A000204, A000358, A001612, A093305, A274018, A274019, A274020.
%K A274017 nonn
%O A274017 0,2
%A A274017 _Marko Riedel_, Jun 06 2016