Let $q$ be a power of a prime. It's well-known that the function $B(n, q) = \frac{1}{n} \sum\_{d | n} \mu \left( \frac{n}{d} \right) q^d$ counts both the number of irreducible polynomials of degree $n$ over $\mathbb{F}\_q$ and the number of [Lyndon words](http://en.wikipedia.org/wiki/Lyndon_word) of length $n$ over an alphabet of size $q$. Does there exist an explicit bijection between the two sets?



Exhibit an explicit bijection between irreducible polynomials over finite fields and Lyndon words.
In Reutenauer's "Free Lie Algebras", section 7.6.2:


A direct bijection between primitive necklaces of length $n$ over $F$ and the set of irreducible polynomials of degree $n$ in $F[x]$ may be described as follows: let $K$ be the field with $q^n$ elements; it is a vector space of dimension $n$ over $F$, so there exists in $K$ an element $\theta$; such that the set $\{\theta, \theta^q, ..., \theta^{q^{n-1}}\}$ is a linear basis of $K$ over $F$.


With each word $w = a\_0\cdots a\_{n-1}$ of length $n$ on the alphabet $F$, associate the element $\beta$ of $K$ given by $\beta = a\_0\theta + a\_1\theta^q + \cdots + a\_{n-1} \theta^{q^{n-1}}$. It is easily shown that to conjugate words $w, w'$ correspond conjugate elements $\beta, \beta'$ in the field extension $K/F$, and that $w \mapsto \beta$ is a bijection. Hence, to a primitive conjugation class corresponds a conjugation class of cardinality $n$ in $K$; to the latter corresponds a unique irreducible polynomial of degree $n$ in $F[x]$. This gives the desired bijection.


