A bijection between necklaces and multisets with divisible subset sum (Q1732032)

Summary: Consider these two distinct combinatorial objects: (1) the necklaces of length \(n\) with at most \(q\) colors, and (2) the multisets of integers modulo \(n\) with subset sum divisible by \(n\) and with the multiplicity of each element being strictly less than \(q\). We show that these two objects have the same cardinality if \(q\) and \(n\) are mutually coprime. Additionally, when \(q\) is a prime power, we construct a bijection between these two objects by viewing necklaces as cyclic polynomials over the finite field of size \(q\). Specializing to \(q=2\) answers a bijective problem posed by \textit{R. P. Stanley} [Enumerative combinatorics. Vol. 1. Cambridge: Cambridge University Press (2012; Zbl 1247.05003), Chapter 1, Problem 105(b)].