On the number of solutions of certain linear Diophantine equations (Q2641306)

It is well-known that the n-th exponent M(q,n) of the so-called cyclotomic identity \[ \frac{1}{1- qt}=\prod^{\infty}_{n=1}(\frac{1}{1-t^ n})^{M(q,n)} \] may be interpreted as \(\bullet\) the number of irreducible polynomials of degree n over the finite field \({\mathbb{F}}_ q\) with q elements (C. F. Gauss \(\sim\) 1800) \(\bullet\) the number of primitive or aperiodic necklaces with n beads which are coloured with q colours (M. C. Moreau 1872) \(\bullet\) the dimension of the submodule of homogeneous elements of degree n in the free Lie algebra with q generators (E. Witt 1937). In every case there is an evident combinatorial interpretation of the right hand side of the identity and of the logarithmic derivative of its left hand side. Hence a formal proof of the cyclotomic identity results by taking its logarithmic derivative and using Möbius inversion. Recently N. Metropolis and G.-C. Rota provided bijections in the context of necklaces which led to a direct combinatorial proof of the cyclotomic identity. In this note a refinement of Metropolis' and Rota's result is proved. It is used to compute the exact number of solutions of certain linear diophantine equations and allows to analyze the relationship between the various contributions towards a combinatorial interpretation of the cyclotomic identity.