# Necklace polynomial recurrence relation

Let the number of monic, irreducible polynomials of degree $n$ over $F_q$ be $f(n)$, then $f(1)=q$, and to calculate $f(n)$, I would count the number of monic, reducible polynomials of degree $n$ this way:

Given monic, reducible, degree $n$, $g(x)\in F_q[x]$, then there are these possibilities of decomposing $g(x)$ into irreducible monic polynomials:

$g(x)=g_1(x)g_2(x)$, where $g_1$ has degree 1, $g_2$ degree $n-1$,

$g(x)=g_1(x)g_2(x)$, where $g_1$ has degree 2, $g_2$ degree $n-2$,

...

$g(x)=g_1(x)g_2(x)g_3(x)$, where $g_1$ has degree 1, $g_2$ degree $1$, $g_3$ degree $n-2$,

...

One for each partition of $n$ (except the $n=n$ partition).

Then, consider the case of $g_1$ has degree 1, $g_2$ degree $1$, $g_3$ degree $n-2$, $g_3$ has $f(n-2)$ choices, and $g_1$, $g_2$ together has ${f(1)+2-1}\choose{2}$ choices (by the combination with repetitions formula). So together there are $${{f(n-2)+1-1}\choose{1}} \cdot {{f(1)+2-1}\choose{2}}$$

Sum all of them up, there are this many monic, reducible, degree $n$ polynomials: $$\sum_{N=a_1d_1+\dots + a_md_m} \prod_{i=1}^m {{f(d_i)+a_i-1}\choose{a_i}}$$ where $N=a_1d_1+\dots + a_md_m$ is a partition of $N$ with $m>1$, $a_i \geq 1$, $1\leq d_1 < d_2 < \dots < d_m$

So we get $$f(n) = q^n - \sum_{N=a_1d_1+\dots + a_md_m} \prod_{i=1}^m {{f(d_i)+a_i-1}\choose{a_i}}$$

Also, the number of monic irreducible polynomials of degree $n$ over $F_q$ is the necklace polynomial. $$f(n)=\frac{1}{n}\sum_{d|n}\mu (d)q^{n/d}$$ So in this way we obtain a recurrence relation for the necklace polynomial.

Is there a way to derive this relation directly using necklaces, without taking such a detour in polynomials?

• Every argument for how polynomials over finite fields factor into irreducibles can be converted into an argument about how words factor into what are called Lyndon words: en.wikipedia.org/wiki/Lyndon_word – Qiaochu Yuan Mar 5 '17 at 6:26