A208533 Number of n-bead necklaces of n colors not allowing reversal, with no adjacent beads having the same color.

1, 1, 2, 24, 204, 2635, 39990, 720916, 14913192, 348684381, 9090909090, 261535848376, 8230246567620, 281241174889207, 10371206370593250, 410525522392242720, 17361641481138401520, 781282469565908953017, 37275544492386193492506, 1879498672877604463254424

Offset

1,3

Links

Andrew Howroyd, Table of n, a(n) for n = 1..80

Formula

a(n) = (1/n) * Sum_{d | n} totient(n/d) * ((n-1)*(-1)^d + (n-1)^d) for n > 1. - Andrew Howroyd, Mar 12 2017

Example

All solutions for n=4:
..2....1....1....1....1....1....2....1....1....3....1....1....1....2....1....1
..3....2....4....4....4....3....4....4....3....4....3....4....2....3....2....2
..2....4....2....3....2....2....3....1....1....3....4....3....1....4....3....1
..4....2....4....2....3....3....4....4....3....4....2....4....4....3....2....2
..
..1....1....2....1....2....1....1....1
..2....3....3....3....4....2....2....3
..1....4....2....1....2....4....3....2
..3....3....3....4....4....3....4....4

Mathematica

a[1] = 1; a[n_] = (1/n)*DivisorSum[n, EulerPhi[n/#]*((n-1)*(-1)^# + (n-1)^#)& ]; Array[a, 20] (* Jean-François Alcover, Nov 01 2017, after Andrew Howroyd *)

Prog

(PARI) a(n) = if (n==1, 1, (1/n) * sumdiv(n, d, eulerphi(n/d) * ((n-1)*(-1)^d + (n-1)^d))); \\ Michel Marcus, Nov 01 2017

Crossrefs

Diagonal of A208535.

Sequence in context: A052780 A245019 A189769 * A174668 A302444 A121213

Adjacent sequences: A208530 A208531 A208532 * A208534 A208535 A208536

Keyword

nonn

Author

R. H. Hardin, Feb 27 2012

Extensions

a(14)-a(20) from Andrew Howroyd, Mar 12 2017

Status

approved