A263658 - OEIS

%I #18 Sep 11 2017 13:34:56

%S 0,0,1,1,2,3,7,12,27,57,128,285,659,1518,3561,8389,19936,47607,114397,

%T 276018,669035,1627491,3973106,9728991,23892779,58828866,145201423,

%U 359182693,890350290,2211257973,5501701981,13711368630,34225162345,85555609119,214166692430,536810116905

%N Number of (0, 1)-necklaces with n zeros and n ones without zigzags (see reference for precise definition).

%C See page 16 in the reference.

%C 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.

%H Andrew Howroyd, <a href="/A263658/b263658.txt">Table of n, a(n) for n = 0..100</a>

%H E. Munarini and N. Z. Salvi, <a href="http://www.emis.de/journals/INTEGERS/papers/d19/d19.Abstract.html">Circular Binary Strings without Zigzags</a>, Integers: Electronic Journal of Combinatorial Number Theory 3 (2003), #A19.

%F a(n) = (1/n) * Sum_{d | n} totient(n/d) * A263656(d) / 2. - _Andrew Howroyd_, Feb 26 2017

%e For n=2 the necklace is 0011.

%e For n=3 the necklace is 000111.

%e For n=4 the necklaces are 00001111, 00110011.

%e For n=5 the necklaces are 0000011111, 0001110011, 0001100111.

%t (* b = A263656 *)

%t b[n_ /; n < 6] := {0, 0, 4, 6, 12, 30}[[n + 1]];

%t 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]);

%t a[0] = 0;

%t a[n_] := (1/n)*DivisorSum[n, EulerPhi[n/#] * b[#]/2&];

%t Array[a, 36, 0] (* _Jean-François Alcover_, Sep 11 2017, after _Andrew Howroyd_ *)

%Y Main diagonal of A263657.

%Y Cf. A007039, A263655, A263656, A263659.

%K nonn

%O 0,5

%A _Felix Fröhlich_, Oct 23 2015

%E Offset corrected and a(21)-a(35) from _Andrew Howroyd_, Feb 26 2017