This question is motivated by the answers given to my previous [one](https://mathoverflow.net/questions/101464). In combinatorics, the [necklace polynomials](http://en.wikipedia.org/wiki/Necklace_polynomial) are given by
$$M(X,n)=\frac1n\sum\_{d|n}\mu\left(\frac{n}{d}\right)X^d,$$
where $\mu$ is the Möbius function.


It seems that the following formula holds true (at least, I checked it up to $n=6$):
$$\sum\_{k\le n}k\left[\frac{n}{k}\right]M(X,k)=X^n+X^{n-1}+\cdots+X^2+X.$$
Is this classical. Is there any reference. Are there known applications of it ?


To me, here is an application: the *lcm* of all the monic polynomials of degree $n$ over ${\mathbb F}\_p$, which is the simplest polynomial vanishing identically over ${\bf M}\_n({\mathbb F}\_p)$, has degree $p^n+p^{n-1}+\cdots+p^2+p$.



A combinatorial formula involving the necklace polynomial
By plugging in the definition of $M$ and rearranging the terms, your polynomial is
$$\sum\_dx^d\sum\_{m\le n/d}\left\lfloor\frac n{md}\right\rfloor\mu(m).$$
A basic property of Möbius inversion is that
$$\sum\_{m\le x}\left\lfloor\frac xm\right\rfloor\mu(m)=\begin{cases}1,&x\ge1,\\\\0,&x<1.\end{cases}$$


