login
A263658
Number of (0, 1)-necklaces with n zeros and n ones without zigzags (see reference for precise definition).
5
0, 0, 1, 1, 2, 3, 7, 12, 27, 57, 128, 285, 659, 1518, 3561, 8389, 19936, 47607, 114397, 276018, 669035, 1627491, 3973106, 9728991, 23892779, 58828866, 145201423, 359182693, 890350290, 2211257973, 5501701981, 13711368630, 34225162345, 85555609119, 214166692430, 536810116905
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
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
Main diagonal of A263657.
Sequence in context: A099163 A000676 A283823 * A296517 A182692 A203837
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