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,2

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

Links

Table of n, a(n) for n=0..48.

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.

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

G.f. = 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

Example

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.

Crossrefs

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

Sequence in context: A105677 A230476 A103297 * A267597 A238221 A320052

Adjacent sequences: A274014 A274015 A274016 * A274018 A274019 A274020

Keyword

nonn

Author

Marko Riedel, Jun 06 2016

Status

approved