A Bijection between Necklaces and Multisets with Divisible Subset Sum
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 Richard Stanley (Enumerative Combinatorics Vol. 1 Chapter 1, Problem 105(b)).