Necklaces over a group with identity product

Abstract

We address two variants of the classical necklace counting problem from enumerative combinatorics. In both cases, we fix a finite group $\mathcal{G}$ and a positive integer $n$. In the first variant, we count the ``identity-product $n$-necklaces'' -- that is, the orbits of $n$-tuples $\left(a_1,a_2,\dots ,a_n\right)\in {\mathcal{G}}^n$ that satisfy $a_1{a}_2\cdots a_n=1$ under cyclic rotation. In the second, we count the orbits of all $n$-tuples $\left(a_1,a_2,\dots ,a_n\right)\in {\mathcal{G}}^n$ under cyclic rotation and left multiplication (i.e., the operation of $\mathcal{G}$ on ${\mathcal{G}}^n$ given by $h\cdot \left(a_1,a_2,\dots ,a_n\right)=\left(h{a}_1,h{a}_2,\dots ,h{a}_n\right)$). We prove bijectively that both answers are the same, and express them as a sum over divisors of $n$. Consequently, we generalize the first problem to $n$-necklaces whose product of entries lies in a given subset of $\mathcal{G}$ (closed under conjugation), and we connect a particular case to the enumeration of irreducible polynomials over a finite field with given degree and second-highest coefficient $0$.

35 pages. v4 corrects various typos. Comments are welcome!