OFFSET
0,5
COMMENTS
See page 16 in the reference.
A zigzag is a substring which is either 010 or 101. The necklaces 01 and 10 are considered to be with a zigzag. Necklaces do not allow turnover.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..100
E. Munarini and N. Z. Salvi, Circular Binary Strings without Zigzags, Integers: Electronic Journal of Combinatorial Number Theory 3 (2003), #A19.
FORMULA
a(n) = (1/n) * Sum_{d | n} totient(n/d) * A263656(d) / 2. - Andrew Howroyd, Feb 26 2017
EXAMPLE
For n=2 the necklace is 0011.
For n=3 the necklace is 000111.
For n=4 the necklaces are 00001111, 00110011.
For n=5 the necklaces are 0000011111, 0001110011, 0001100111.
MATHEMATICA
(* b = A263656 *)
b[n_ /; n < 6] := {0, 0, 4, 6, 12, 30}[[n + 1]];
b[n_] := b[n] = (1/n)*(3*(n - 1)*b[n - 1] - 4*(n - 4)*b[n - 2] + (7*n - 27)*b[n - 3] - 6*b[n - 4] + (7*n - 37)*b[n - 5] - 3*(n - 6)*b[n - 6]);
a[0] = 0;
a[n_] := (1/n)*DivisorSum[n, EulerPhi[n/#] * b[#]/2&];
Array[a, 36, 0] (* Jean-François Alcover, Sep 11 2017, after Andrew Howroyd *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Felix Fröhlich, Oct 23 2015
EXTENSIONS
Offset corrected and a(21)-a(35) from Andrew Howroyd, Feb 26 2017
STATUS
approved