A Bijection between Necklaces and Multisets with Divisible Subset Sum

Abstract

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)).