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

Author

R. H. Hardin, Feb 27 2012

Keywords

• nonn

Examples

			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
		

Links

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

Crossrefs

Diagonal of A208535.

Programs

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 *)

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

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

Extensions

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