A263659 - OEIS

%I #21 Oct 08 2017 12:27:54

%S 0,2,2,2,3,4,5,6,8,10,15,20,31,42,64,94,143,212,329,494,766,1170,1811,

%T 2788,4341,6714,10462,16274,25415,39652,62075,97110,152288,238838,

%U 375167,589528,927555,1459962,2300348,3626242,5721045

%N Number of (0, 1)-necklaces of length n 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="/A263659/b263659.txt">Table of n, a(n) for n = 0..200</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) * A007039(d). - _Andrew Howroyd_, Feb 26 2017

%e For n=5 the necklaces are 00000, 11111, 00011, 00111 so a(5)=4.

%t (* b = A007039 *) b[n_ /; n<4] = 2; b[4] = 6; b[n_] := b[n] = 2*b[n-1] - b[n-2] + b[n-4];

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

%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Oct 08 2017, after _Andrew Howroyd_ *)

%Y Antidiagonal sums of A263657.

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

%K nonn

%O 0,2

%A _Felix Fröhlich_, Oct 23 2015

%E a(25)-a(40) from _Andrew Howroyd_, Feb 26 2017