Combinatorics of necklaces and ``Hermite reciprocity'' (Q1818375)

Let \(G=C_n\) be the cyclic group of order \(n\), \(V=\mathbb{C} G\) the regular module over the complex numbers, \(A:=\text{Sym} (V^*)^G= \bigoplus_{i\geq 0}A_i\) the corresponding graded ring of polynomial invariants and \(a_0(m, n):= \dim A_m\). In an earlier paper the first two authors showed that \(a_0(m,n)\) is equal to the number of solutions \((\lambda_0,\lambda_1, \dots,\lambda_{n-1}) \in\mathbb{N}^n\) of the system \[ \sum^{n-1}_{j=0} j\lambda_j\equiv 0 \text{mod} n;\quad \sum^{n-1}_{j=0} \lambda_j=m \] and derived an explicit formula for \(a_0(m,n)\), which implied a `Hermite reciprocity' \(a_0(m,n)= a_0(n,m)\). In the present paper the authors generalize this result in the following way: Let \(c_n(k)\) be the Ramanujan sum of \(k\)-th powers of all complex primitive \(n\)-th roots of unity and define \(a_k(n,m)\) to be the number of solutions of \[ \sum^{n-1}_{j=0}j \lambda_j \equiv k \text{mod} n;\quad \sum^{n-1}_{j=0} \lambda_j=m, \] where \(k\) is any nonnegative integer. The authors prove that \[ a_k(n,m)={1\over n+m} \sum_{d \mid (n,m)}c_d (k){n/d+m/d \choose n/d}. \] In particular there is again a `Hermite reciprocity': \(a_k(n,m)=a_k(m,n)\). Furthermore the authors give a combinatorial interpretation of this reciprocity, in terms of a set of bicoloured oriented necklaces, acted on by a certain involution. This approach also leads to a combinatorial proof of the above formula for \(a_k(n,m)\).