# A combinatorial formula involving the necklace polynomial

This question is motivated by the answers given to my previous one. In combinatorics, the necklace polynomials 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$.

-
Replacing $\mathbf{F}_p[X]$ with $\mathbf{Z}$, the analogue of this number is $\operatorname{lcm}(1,\ldots,n)$, whose asymptotic behaviour is somewhat similar : $\log \operatorname{lcm}(1,\ldots,n) \sim n$ by the prime number theorem, see e.g. mathworld.wolfram.com/LeastCommonMultiple.html –  François Brunault Jul 6 '12 at 14:05

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}$$
The LHS of your formula can be rewritten as $$\sum_{k\ge 1, d\mid k}\left[\frac{n}{k}\right]\mu(k/d)X^d,$$ which after rearranging terms becomes $$\sum_{d\ge 1}X^d\sum_{s\ge 1}\mu(s)\left[\frac{n}{ds}\right].$$ Let us denote $l:=\frac{n}{d}$, then the coefficient of $X^d$ in this sum is $$\sum_{s\ge 1}\mu(s)\left[\frac{l}{s}\right].$$ Applying the M\"obius inversion in the form (see Concrete Mathematics (4.61)) $$g(x)=\sum_{d\ge 1}f(x/d) \quad \text{ iff } \quad f(x)=\sum_{d\ge 1}\mu(d)g(x/d)$$ to the functions $$f(x)=[x\ge 1]$$ and $$g(x)=[x],$$ we conclude that $$\sum_{s\ge 1}\mu(s)\left[\frac{n}{ds}\right]$$ is equal to $0$ for $1>\frac{n}{d}$ and is equal to $1$ for $1\le\frac{n}{d}$, which is precisely what your conjectured RHS says.
You probably shouldn't use $[\ast]$ both for the floor function and the Iverson bracket... –  Dan Petersen Jul 6 '12 at 14:03