How many inequivalent ways to paint $n$ equally spaced points on a circle with $m$ colors? [duplicate]

Let $C = \{1, ...,X\}^n$ represent the set of colorings of $n$ labeled vertices. The dihedral group $D_n$ acts on $C$ by permuting elements, representing the rigid motions of an $n$-gon. The "distinct colorings" we're looking for are the orbits of this group action.

Burnside's Lemma tells us that the number of orbits is equal to the average number of fixed points of a group element. So for each element $g \in D_n$, we should calculate $|C^g|$, the number of colorings in $C$ that are unchanged by $g$.

$D_n$ consists of $n$ rotations (including the identity element, which we can think of as a rotation by $n$ steps) and $n$ reflections.

If $g$ is a rotation by $k$ steps, then choosing a fixed point of $g$ corresponds to freely choosing the colors of $\gcd(n, k)$ adjacent vertices; the constraint that our coloring is unchanged by $g$ forces us to repeat this color sequence around the polygon, determining the remaining vertices' colors. So $|C^g|=X^{\gcd(n, k)}$.

If $g$ is a reflection, then to build a fixed point we can freely choose the colors of any vertices that lie on the axis of reflection, and the remaining vertices must be colored in pairs so that they match their reflections. If $n$ is odd, each reflection has one vertex on its axis, so $|C^g|=X^{(n+1)/2}$. If $n$ is even, half of the reflections have two vertices on their axis (yielding $|C^g|=X^{n/2+1}$) and the other half have none (yielding $|C^g|=X^{n/2}$).

Putting these things together and taking the average, we find that the number of orbits is $$ \frac 1{2n} \left( \sum_{k=1}^n X^{\gcd(n, k)} + \begin{cases} n X^{(n+1)/2} & \text{$n$ odd} \\ \frac n 2 X^{n/2+1} + \frac n 2 X^{n/2} & \text{$n$ even} \end{cases} \right). $$

There are two possibilities here, rotational symmetry (necklace) or dihedral symmetry (bracelet). For the first one we have the cycle index of the cyclic group:

$$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}.$$

For second one we have the cycle index of the dihedral group

$$Z(D_n) = \frac{1}{2} Z(C_n) + \begin{cases} \frac{1}{2} a_1 a_2^{(n-1)/2} & n \text{ odd} \\ \frac{1}{4} \left( a_1^2 a_2^{n/2-1} + a_2^{n/2} \right) & n \text{ even.} \end{cases}$$

By Burnside we must average the number of colorings fixed by each permutation. We then use that a permutation fixes a coloring if it is constant on the cycles, so we have $X$ choices for each cycle. Therefore we get for necklaces

$$P_n(X) = \frac{1}{n} \sum_{d|n} \varphi(d) X^{n/d}$$

and for bracelets

$$Q_n(X) = \frac{1}{2} P_n(X) + \begin{cases} \frac{1}{2} X^{(n+1)/2} & n \text{ odd} \\ \frac{1}{4} \left( X^{n/2+1} + X^{n/2} \right) & n \text{ even.} \end{cases}$$

This is for the case of using at most $X$ colors from a set of $X.$ On the other hand, if we use exactly $X$ colors we have using Stirling numbers the closed form for necklaces

$$P'_n(X) = \frac{X!}{n} \sum_{d|n} \varphi(d) {n/d\brace X}$$

and for bracelets

$$Q'_n(X) = \frac{1}{2} P'_n(X) + \begin{cases} \frac{X!}{2} {(n+1)/2 \brace X} & n \text{ odd} \\ \frac{X!}{4} \left( {n/2+1 \brace X} + {n/2\brace X} \right) & n \text{ even.} \end{cases}$$

The Stirling number formulae can be derived by inclusion-exclusion. This goes as follows. The nodes $K$ of the poset are all the subsets of the colors $Y$ with $|Y|=X$ and represent colorings using some subset of the set of colors $K.$ The weight attached to the colorings represented at $K$ is $(-1)^{|Y|-|K|}.$ Now clearly colorings using all colors of $Y$ are included only in the top node $K=Y$ where they receive weight one. Colorings using an exact set $L\subset Y$ are represented by all nodes that are supersets of $L$, for a total weight of

$$\sum_{M\subseteq Y\setminus L} (-1)^{|Y|-(|M|+|L|)} = \sum_{m=0}^{|Y|-|L|} {|Y|-|L|\choose m} (-1)^{|Y|-(m+|L|)} \\ = (-1)^{|Y|-|L|} \sum_{m=0}^{|Y|-|L|} {|Y|-|L|\choose m} (-1)^m = 0.$$

This was zero because $L$ is a proper subset of $Y.$ We see that when summing the colorings represented at all nodes of the poset only the ones that use all colors contribute, with a weight of one, so this sum is the queried statistic. On the other hand summing over the nodes first rather than the colorings we obtain

$$\sum_{K\subseteq Y} (-1)^{|Y|-|K|} P_n(|K|) = \sum_{k=0}^X {X\choose k} (-1)^{X-k} P_n(k) \\ = \sum_{k=0}^X {X\choose k} (-1)^{X-k} \frac{1}{n} \sum_{d|n} \varphi(d) k^{n/d} \\ = \frac{1}{n} \sum_{d|n} \varphi(d) \sum_{k=0}^X {X\choose k} (-1)^{X-k} k^{n/d} \\ = \frac{1}{n} \sum_{d|n} \varphi(d) \sum_{k=0}^X {X\choose k} (-1)^{k} (X-k)^{n/d}.$$

We recognize the Stirling number at this point and may conclude. Or if another step is desired we recall that the combinatorial class for set partitions is

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SET}(\mathcal{U} \times \textsc{SET}_{\ge 1}(\mathcal{Z}))$$

giving the EGF

$${n\brace k} = n! [z^n] \frac{(\exp(z)-1)^k}{k!}$$

and note that

$$\sum_{k=0}^X {X\choose k} (-1)^{X-k} k^{n/d} = (n/d)! [z^{n/d}] \sum_{k=0}^X {X\choose k} (-1)^{X-k} \exp(kz) \\ = (n/d)! [z^{n/d}] (\exp(z)-1)^X = X! \times (n/d)! [z^{n/d}] \frac{(\exp(z)-1)^X}{X!}.$$

Remark. We can show that the alternate form by user @Karl is the same as what we obtain from the cycle index. We get

$$\frac{1}{n} \sum_{k=1}^n X^{\gcd(n,k)} = \frac{1}{n} \sum_{d|n} \sum_{k=1, \; \gcd(k,n)=d}^n X^d \\ = \frac{1}{n} \sum_{d|n} X^d \sum_{k=1, \; \gcd(kd,n)=d}^{n/d} 1 = \frac{1}{n} \sum_{d|n} X^d \sum_{k=1, \; \gcd(k,n/d)=1}^{n/d} 1 \\ = \frac{1}{n} \sum_{d|n} \varphi(n/d) X^d.$$