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

1, 2, 3, 3, 4, 4, 6, 6, 9, 11, 16, 20, 32, 42, 65, 95, 144, 212, 330, 494, 767, 1171, 1812, 2788, 4342, 6714, 10463, 16275, 25416, 39652, 62076, 97110, 152289, 238839, 375168, 589528, 927556, 1459962, 2300349, 3626243, 5721046, 9030452, 14264310, 22542398, 35646313, 56393863, 89264836, 141358276, 223959712

Offset: 0

Author

Marko Riedel, Jun 06 2016

Keywords

• nonn

Comments

The pattern in this enumeration must be contiguous (all three values next to each other in one sequence of three letters).

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

Examples

			The following necklace
     1-1
    /   \
   0     0
   |     |
   1     1
    \   /
     0-0
contains one instance of the subsequence starting in the upper left corner. Unlike a bracelet, the necklace is oriented.
a(8) = 9: 00000000, 00000001, 00000101, 00001001, 00010001, 00010101, 00100101, 01010101, 11111111.
a(9) = 11: 000000000, 000000001, 000000101, 000001001, 000010001, 000010101, 000100101, 000101001, 001001001, 001010101, 111111111.
		

Links

• Petros Hadjicostas and L. Zhang, On cyclic strings avoiding a pattern, Discrete Mathematics, 341 (2018), 1662-1674.
• Petros Hadjicostas, Proof of two formulas for a(n).
• Marko Riedel, Maple code for this sequence.
• Math Stackexchange, Marko Riedel et al. Counting circular sequences.

Crossrefs

Cf. A000010, A000031, A000045, A000204, A000358, A001612, A093305, A274018, A274019, A274020.

Formula

From Petros Hadjicostas, Jan 11 2017: (Start)

For all the formulas below, assume n>=1.

a(n) = 1 + A000358(n). (Notice the different offsets.)

a(n) = 1 + (1/n) * Sum_{d|n} totient(n/d)*(Fibonacci(d-1)+Fibonacci(d+1)).

a(n) = (1/n) * Sum_{d divides n} totient(n/d)*A001612(d).

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.)

G.f.: 1 + Sum_{k>=1} (phi(k)/k) * log(1/C(x^k)) where C(x) = (1-x)*(1-B(x)). (End)

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