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
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
KEYWORD
nonn
AUTHOR
Marko Riedel, Jun 06 2016
STATUS
approved