I stumbled upon entry [OEIS-A208535](https://oeis.org/A208535) on the enumeration of certain kinds of colored necklaces and noticed that the integers for the odd prime rows of the table there seem to be given by the [Moreau necklace polynomials](http://en.wikipedia.org/wiki/Necklace_polynomial) 


$$a(p,n)=\frac{n^p-n}{p}.$$


(This is reminiscent of the cyclotomic polynomials, $\Phi\_p(x)=\frac{x^p-1}{x-1}$ for the prime indices, and indeed they are related.)


The primes and colored necklaces are both well plumbed but vast waters, so maybe formulas for the non-prime rows are well-known to number theorists / combinatorialists, but it's hard to track them down. Familiar to anyone? Any references? 



A number array related to colored necklaces and the primes
By Burnside's lemma applied to the cyclic group of order $m$, the number of $m$-bead necklaces colored in $n$ colors in which adjacent bead have different colors, which is what [A208535](https://oeis.org/A208535) counts, is
$$\frac{1}{m}\sum \_{d|m} P\_d(n) \phi(m/d),$$
where $\phi$ is Euler's totient function and $P\_d(n)=(n-1)^d +(-1)^d (n-1)\ \ $ is the chromatic polynomial of a $d$-cycle for $d\ge2$, where for $d=2\ $ we interpret a 2-cycle as the connected graph on two vertices, and $P\_1(n)=0$.


If $m$ is an odd prime, this is 
$$\frac{1}{m} P\_m(n) = \frac{1}m\left((n-1)^m - (n-1)\right).$$


Since $\sum\_{d|m} \phi(m/d)=m\ $ and $\sum\_{d|m}(-1)^d \phi(m/d) = 0\ $ for $m$ even, the sum can be simplified to 
$$\frac{1}{m}\sum \_{d|m} (n-1)^d \phi(m/d)\tag{$\*$}$$ for $m\ $ even
and 
$$\frac{1}{m}\sum \_{d|m} (n-1)^d \phi(m/d) -(n-1)$$ for $m\ $ odd.


Note that $(\*)$ is the number of $m$-bead necklaces colored in $n-1$ colors (with no restrictions on adjacent beads).


