Necklaces over a Group with Identity Product

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, \ldots, 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, \ldots, 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, \ldots, a_n\right) = \left(ha_1, ha_2, \ldots, ha_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.

Necklaces over a Group with Identity Product

Darij Grinberg and Peter Mao Department of Mathematics Drexel University Korman Center, Room 291 15 S. 33rd Street Philadelphia PA, 19104 USA

Darij Grinberg and Peter Mao
Department of Mathematics
Drexel University
Korman Center, Room 291
15 S. 33rd Street
Philadelphia PA, 19104
USA