Conjugacy Classes in matrix groups $\mathrm{GL}_n(k)$ and rings $M_n(k)$ Let $k$ be a finite field of size $q$, let $n\ge1$, and let $\mathrm{GL}_n(k)$ and $M_n(k)$ be the group of invertible matrices and ring of $n\times n$ matrices, respectively.
Now, I have calculated (by grouping by the characteristic polynomial) that the number of conjugacy classes are:

*

*$q-1$ in $\mathrm{GL}_1(k)=k^\times$, $q$ in $M_1(k)=k$;

*$q^2-1$ in $\mathrm{GL}_2(k)$, $q^2+q$ in $M_2(k)$; and

*$q^3-q$ in $\mathrm{GL}_3(k)$, $q^3+q^2+q$ in $M_3(k)$.

I conjecture that the pattern continues on the $M_n(k)$-side, i.e., that there are always $q^n+\dots+q$ conjugacy classes in $M_n(k)$. However, I cannot seem to prove this. How should I proceed?
Also, is there an analogous formula for the number of conjugacy classes in $\mathrm{GL}_n(k)$?
Note: By conjugacy class in $M_n(k)$, I mean the equivalence classes under the relation, for $a,b\in M_n(k)$, of $a\sim b$ iff there exists a $u\in\mathrm{GL}_n(k)$ such that $a=ubu^{-1}$.
 A: I find $$\sum_{n\ge 0} a_n t^n=\prod_{e=1}^\infty \frac1{1-t^e|k|} \qquad \text{and}\qquad\sum_{n\ge 0} b_n t^n=\prod_{e=1}^\infty \frac{1-t^e}{1-t^e|k|}$$ for the generating functions of the number of $GL_n(k)$-conjugacy classes in $M_n(k)$ and $GL_n(k)$ respectively.
The idea is that $$\frac1{1-t|k|}= \sum_{f\in k[x]\text{ monic}} t^{\deg(f)}$$
so each term in the expansion of $\prod_{e=1}^\infty \frac1{1-t^e|k|}$ is of the form $t^{\sum_{e\ge 1}e \deg(f_e)}$ which corresponds to the conjugacy class of matrices $A\in M_n(k), n = \sum_{e\ge 1}e \deg(f_e)$ such that the $k[x]$-module structure on $k^n$ given by $A$ is isomorphic to the $k[x]$-module $$\prod_{e\ge 1} \prod_{h \text{ irreducible},h^m \| f_e} (k[x]/(h^e))^m$$
A: This is based on reuns's idea.
Fix a field $k$ of cardinality $q$.
Lemma 1 There are $\frac1n\sum_{d|n}\mu(\frac nd)q^d$ irreducible monic polynomials of degree $n$ in $k[x]$.
Proof: Let $A_d$ be the set of $\alpha\in\overline k$ such that $k(\alpha)/k$ has degree exactly $d$. Then we have that $\sum_{d|n}A_d=q^n$, so that by Mobius inversion $A_n=\sum_{d|n}\mu(\frac nd)q^d$. Now, the $n$ Galois conjugates of an $\alpha\in\overline k$ with $[k(\alpha):k]=n$ all give rise to the same minimal polynomial, so the number of irreducible polynomial of degree $n$ is $A_n/n$.
Now for every fixed monic irreducible polynomial $f\in k[x]$ of degree $n$ and $e\ge 1$, the $k[x]$-modules of the form $(k[x]/(f^e))^{\oplus k}$ can be encoded in the generating function $\frac1{1-x^{en}}$.
We conclude that the generating function for the conjugacy classes in $M_n(k)$ is:
\begin{align*}
\prod_{f\text{ monic irreducible}}\prod_{e\ge1}\frac1{1-x^{e\deg f}}&=\prod_{n\ge1}\left(\prod_{e\ge1}\frac1{1-x^{en}}\right)^{\frac1n\sum_{d|n}\mu(\frac nd)q^d}.
\end{align*}
I wonder whether this can be simplified.

There is also a very indirect way to simplify the expression.
By Mobius inversion we have $q^n=\sum_{j|n}\mu(j)\sum_{d|\frac nj}q^d=\sum_{dij=n}\mu(j)q^d$, so that
\begin{align*}
\sum_{n\ge1}\frac1n\sum_{d|n}\mu\big(\frac nd\big)q^d\log\left(\frac1{1-x^n}\right)&=\sum_{j\ge1}\frac1{dj}\sum_{d\ge1}\mu(j)q^d\log\left(\frac1{1-x^{dj}}\right)\\
&=\sum_{j\ge1}\frac1{dj}\sum_{d\ge1}\mu(j)q^d\sum_{i\ge1}\frac1ix^{dij}\\
&=\sum_{n\ge1}\frac1n\sum_{dij=n}\mu(j)q^dx^n\\
&=\sum_{n\ge1}\frac1nq^nx^n=\log\big(\frac1{1-qx}\big).
\end{align*}
This shows
$$\prod_{n\ge1}\left(\prod_{e\ge1}\frac1{1-x^{en}}\right)^{\frac1n\sum_{d|n}\mu(\frac nd)q^d}=\prod_{e\ge1}\left(\frac1{1-qx^e}\right).$$

P.S. In particular,
$$\prod_{e\ge1}\left(\frac1{1-qx^e}\right)=1+qx+(q^2+q)x^2+(q^3+q^2+q)x^3+(q^4+q^3+2q^2+q)x^4+(q^5+q^4+2q^3+2q^2+q)x^5+\dots,$$
so my conjecture was wrong.
