Show that the number of monic irreducible polynomials of degree $n$ over a finite field of size $q$ is the same as the number of primitive necklaces of size $n$ with $q$ colors. I have the formula
$$M(q,n) = \sum\limits_{d|n} q^d \mu\Big(\frac{n}{d}\Big)$$
which counts primitive necklaces. The goal is to show this counts monic irreducibles over a finite field combinatorially. I can use Mobius inversion. I know this question has been asked before, but the previous answers require a lot of algebra.
I tried a special case when $q = 3$ and $n = 2$. Let the colors of the beads of a necklace be red (R), yellow (Y) and blue (B). Then the primitive necklaces are $RY$, $RB$ and $YB$. I computed the irreducible polynomials of degree $2$ as well, they are: $x^2 + 1, x^2 + x + 2$ and $x^2 + 2x + 2$. It is really unclear how I could map necklaces to these polynomials. If I just consider these as $3$-tuples then we have $(1, 0, 1), (1, 1, 2)$ and $(1, 2, 2)$ so it isn't even clear how to map the colors.