

A263659


Number of (0, 1)necklaces of length n without zigzags (see reference for precise definition).


5



0, 2, 2, 2, 3, 4, 5, 6, 8, 10, 15, 20, 31, 42, 64, 94, 143, 212, 329, 494, 766, 1170, 1811, 2788, 4341, 6714, 10462, 16274, 25415, 39652, 62075, 97110, 152288, 238838, 375167, 589528, 927555, 1459962, 2300348, 3626242, 5721045
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


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..200
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) * A007039(d).  Andrew Howroyd, Feb 26 2017


EXAMPLE

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


MATHEMATICA

(* b = A007039 *) b[n_ /; n<4] = 2; b[4] = 6; b[n_] := b[n] = 2*b[n1]  b[n2] + b[n4];
a[0] = 0; a[n_] := (1/n) * DivisorSum[n, EulerPhi[n/#] * b[#]&];
Table[a[n], {n, 0, 40}] (* JeanFrançois Alcover, Oct 08 2017, after Andrew Howroyd *)


CROSSREFS

Antidiagonal sums of A263657.
Cf. A007039, A263655, A263656, A263658.
Sequence in context: A026837 A005855 A096748 * A022866 A350701 A099388
Adjacent sequences: A263656 A263657 A263658 * A263660 A263661 A263662


KEYWORD

nonn


AUTHOR

Felix Fröhlich, Oct 23 2015


EXTENSIONS

a(25)a(40) from Andrew Howroyd, Feb 26 2017


STATUS

approved



