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 when $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.

arXiv comment14 pages; v2 has additional details for the proof of Lemma 4.11 and other stylistic changes suggested by the referee

References in corpus (1)

• A New Approach to Enumerating Statistics Modulo $n$

Cited by in corpus (1)

• A new sieve for restricted multiset counting