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

                darijgrinberg@gmail.com
                   pm929@drexel.edu

Abstract

We address two variants of the classical necklace counting problem from enumerative combinatorics. In both cases, we fix a finite group G and a positive integer n. In the first variant, we count the “identity-product n-necklaces”—that is, the orbits of n-tuples (a_{1}, a_{2}, …, a_{n}) ∈ G^{n} that satisfy a_{1}a_{2} ⋯ a_{n} = 1 under cyclic rotation. In the second, we count the orbits of all n-tuples (a_{1}, a_{2}, …, a_{n}) ∈ G^{n} under cyclic rotation and left multiplication (i.e., the operation of G on G^{n} given by h · (a_{1}, a_{2}, …, a_{n}) = (ha_{1}, ha_{2}, …, ha_{n})). 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 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.

1 Introduction

Necklaces are combinatorial objects situated on the spectrum between ordered selections (tuples) and unordered selections (multisets) of elements from a set. Formally, they are defined as orbits (i.e., equivalence classes) of n-tuples under cyclic rotation. They can be visualized as labellings (or colorings) of a circular necklace, where we understand that the necklace can be rotated at will (but not turned over) without changing the object.

Counting necklaces is a classical problem in enumerative combinatorics (see, e.g., [3, §3, Example 3 (b)], [15, Chapter 7], [10, §5.5]). A well-known formula due to Moreau [17] says that the number of n-necklaces (i.e., rotation classes of n-tuples) over a size-q set A is

\frac{1}{n} ∑_{d|n} ϕ (d) q^{n/d},  (1)

where the sum runs over all positive divisors d of n, and where ϕ denotes the Euler totient function (see Definition 4 below). This surprisingly simple formula is a starting point for several deeper developments, including the theory of necklace polynomials [12, §17.3]. The fact that (1) is an integer (obvious from its combinatorial meaning) itself has some uses in number theory (yielding, e.g., Fermat’s Little Theorem when n is prime). The expression (1) also counts irreducible monic polynomials of degree dividing n over the finite field 𝔽_{q} when q is a prime power, and this can be proved using a bijection between necklaces and irreducible polynomials [20, §7.6.2]. There is also a bijection between words and multisets of necklaces [8, §3] with far-reaching applications to symmetric functions, free Lie algebras and permutation enumeration. Further afield, the Burrows–Wheeler transform (transforming words into necklaces) is used for data compression in software such as bzip2 [1, §2.3].

In this paper, we count what we call identity-product necklaces, i.e., necklaces where instead of colored beads we have elements of a finite group G which multiply to the identity. This is an orbit-counting problem for a certain action of the cyclic group C_{n}, which (by a well-known technique) can be reduced to counting identity-product tuples which are fixed under different cyclic rotations. We thus obtain a “sum over divisors” formula similar to (1) but involving the sizes of the group and of its torsion subgroups (Theorem 5). Once again, the integrality of the result is not evident from the formula, and thus gives rise to nontrivial congruences between sizes of torsion subgroups modulo the length of the necklaces being counted.

After proving our main formula, we count the aperiodic identity-product necklaces (i.e., the ones that have no nontrivial rotational symmetries) as well (Theorem 16). As expected from classical necklace-counting, the sum is the same but for the replacement of the Euler totient function ϕ by the Möbius function μ.

The number of identity-product n-necklaces over a group G furthermore equals the number of “homogeneous n-necklaces” over G, that is, orbits of n-tuples of elements of G under the action of the direct product C_{n} × G (where C_{n} acts by cyclic rotation and G acts by left multiplication on each entry). We prove this bijectively (Theorem 19), thus obtaining a formula for the latter number as well.

In Section 8, we extend some of our enumerative results to the more general notion of K-product necklaces, in which the product of the entries is required to belong to a given conjugacy-invariant subset K of the group.

Just like Moreau’s original necklaces, our identity-product necklaces can be connected to irreducible polynomials over finite fields. In Section 9, we take up this connection and prove some enumerative results about conjugacy classes in finite field extensions and irreducible polynomials.

In Section 10, we relate our enumerations to three integer sequences from the Online Encyclopedia of Integer Sequences. In the short final Section 11, we suggest two venues for further research.

2 Definitions

Fix a finite group G with binary operation · and identity element 1.

Definition 1. For any nonnegative integer n, we let G_{1}^{n} be the set of all identity-product n-tuples, defined by

G_{1}^{n} := {a = (a_{1}, a_{2}, …, a_{n}) ∈ G^{n} : a_{1}a_{2}a_{3} ⋯ a_{n} = 1} .

Definition 2. For any integer n, let us define the number [G ÷ n] to be

[G ÷ n] := |{a ∈ G : a^{n} = 1}| .

This is the number of elements in G whose order divides n.

Definition 3. Let n be a positive integer. Then the n-element cyclic group

C_{n} = {1, g, g^{2}, …, g^{n−1}}

acts on G^{n} by cyclic rotation:

g (a_{1}, a_{2}, …, a_{n}) = (a_{n}, a_{1}, a_{2}, …, a_{n−1}) .

To see that the subset G_{1}^{n} of G^{n} is preserved by this action, we observe that the equation

a_{1}a_{2}a_{3} ⋯ a_{n−1}a_{n} = 1

implies that a_{n} is the inverse of a_{1}a_{2}a_{3} ⋯ a_{n−1}, and thus

a_{n}a_{1}a_{2}a_{3} ⋯ a_{n−1} = 1.

Therefore, if a = (a_{1}, a_{2}, a_{3}, …, a_{n}) was an identity-product n-tuple, then ga will be also. Hence G_{1}^{n} is preserved by the action of C_{n} and thus itself becomes a C_{n}-set. The orbits of this action of C_{n} on G_{1}^{n} (that is, the elements of the quotient G_{1}^{n}/C_{n}) are called the identity-product n-necklaces.

Definition 4. Let n be a positive integer. We define the Euler totient ϕ(n) to be the number of integers i ∈ {1, 2, …, n} that are coprime to n.

3 Main theorem I: Identity-product n-necklaces

Our first main result is a formula for the number of identity-product n-necklaces for any finite group G:

Theorem 5. Let n be a positive integer. The number |G_{1}^{n}/C_{n}| of identity-product n-necklaces is

|G_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) [G ÷ \frac{n}{d}] |G|^{d−1} .

Here, as usual, the summation sign means a sum over all positive divisors d of n.

We can make this more explicit if G is abelian. Recall the cyclic groups C_{k} of order k, defined for all positive integers k. The structure theorem for finite abelian groups says that each abelian group is isomorphic to a direct product of such cyclic groups. If G is an abelian group written in such a form, then the above formula reduces to the following:

Corollary 6. Assume that

G = ∏_{i=1}^{m} C_{k_{i}}  (a direct product of cyclic groups)

for some positive integers k_{1}, k_{2}, …, k_{m}. Then the number |G_{1}^{n}/C_{n}| of identity-product nnecklaces is

|G_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) ∏_{i=1}^{m} (gcd (k_{i}, \frac{n}{d}) k_{i}^{d−1}) .

4 Lemmas

Our proofs of the above claims are based on a common set of lemmas. We use the orbitcounting lemma (by historic accident also known as the Burnside lemma; see [24] or [11, Theorem 6.2.5] for a proof):

Lemma 7. Let G be a finite group acting on a finite set X. Then the number |X/G| of orbits is

|X/G| = \frac{1}{|G|} ∑_{g∈G} |\{x ∈ X : g · x = x\}| .

We also need a basic theorem due to Gauss [21, Theorem 2.40]:

Lemma 8. For any positive integer n, we have

∑_{d|n} ϕ(d) = n.

A useful consequence thereof is the following:

Lemma 9. Let f and g be two functions from {1, 2, 3, …} to ℚ. Assume that

g(k) = ∑_{d|k} f(d)  for each k ≥ 1.  (2)

Then

∑_{d|k} \frac{k}{d}f(d) = ∑_{d|k} ϕ (\frac{k}{d}) g (d)  for each k ≥ 1.  (3)

We shall prove this lemma using the following classical notion:

Definition 10. Let f and g be two functions from {1, 2, 3, …} to ℚ. We define the Dirichlet convolution f ∗ g to be the function from {1, 2, 3, …} to ℚ given by

(f ∗ g) (k) = ∑_{d|k} f (d) g (\frac{k}{d}) .

The Dirichlet convolution operation ∗ is known to be commutative and associative (see, e.g., [21, §2.9]). Furthermore, Lemma 8 can be restated as

ϕ ∗ \underline{1} = id,  (4)

where \underline{1} denotes the constant function that sends all positive integers to 1 (because every integer n > 0 satisfies (ϕ ∗ \underline{1})(n) = ∑_{d|n} ϕ(d)\underline{1}(\frac{n}{d}) = ∑_{d|n} ϕ(d) and id(n) = n).

Proof of Lemma 9. We note that the assumption (2) is the written out form of the statement

g = f ∗ \underline{1}  (5)

where \underline{1} is the constant function which maps all positive integers to 1. We can also rewrite the conclusion (3) as

∑_{d|k} f(d)\frac{k}{d} = ∑_{d|k} g (d) ϕ (\frac{k}{d}) ,  (6)

or, equivalently,

(f ∗ id)(k) = (g ∗ ϕ)(k).  (7)

To prove this, we observe that

g ∗ ϕ = (f ∗ \underline{1}) ∗ ϕ  (by (5))
= f ∗ (\underline{1} ∗ ϕ)  (by associativity of the Dirichlet convolution)
= f ∗ (ϕ ∗ \underline{1})  (by commutativity of the Dirichlet convolution)
= f ∗ id  (by (4))

and therefore f ∗ id = g ∗ ϕ.

The following lemma is a classical property of greatest common divisors:

Lemma 11. Let a, b and c be three integers, where a and b are not both 0. Then a | bc holds if and only if \frac{a}{gcd (a, b)} | c.

Proof. The “if” part is easy (since multiplying the divisibility \frac{a}{gcd (a, b)} | c with the obvious

divisibility gcd (a, b) | b yields a | bc). It remains to prove the “only if” part. So let us assume that a | bc, and try to prove that \frac{a}{gcd (a, b)} | c.

Let g = gcd (a, b). Thus, we can write a and b as a = ga′ and b = gb′ for two coprime integers a′ and b′. Consider these a′ and b′. Thus, a | bc rewrites as ga′ | gb′c. Cancelling g (which is nonzero, since a and b are not both 0), we thus obtain a′ | b′c. Since a′ is coprime to b′, we can cancel b′ from this divisibility (by [21, Theorem 1.9]), and obtain a′ | c. In other words, \frac{a}{gcd (a, b)} | c (since a′ = \frac{a}{g} = \frac{a}{gcd (a, b)}), which completes our proof.

Lemma 12. Let a and b be two positive integers. Then [C_{a} ÷ b] = gcd (a, b).

Proof. Set g = gcd (a, b) and a′ = a/g, so that a = ga′. We write \overline{c} for the residue class of an integer c modulo a. This remainder belongs to the finite ring ℤ/aℤ.

Now, by the definition of [C_{a} ÷ b], we have

[C_{a} ÷ b] = |{h ∈ C_{a} : h^{b} = 1}|
= |\{x ∈ ℤ/aℤ : bx = \overline{0}\}|

(since C_{a} is the additive abelian group ℤ/aℤ, rewritten multiplicatively). Hence,

[C_{a} ÷ b] = |\{x ∈ ℤ/aℤ : bx = \overline{0}\}|
= |\{c ∈ \{0, 1, …, a − 1\} : b\overline{c} = \overline{0}\}|  (8)

(since the elements of ℤ/aℤ are precisely the elements \overline{c} with c ∈ \{0, 1, …, a − 1\}). However, for any c ∈ {0, 1, …, a − 1}, we have the chain of equivalences

(b\overline{c} = \overline{0}) ⟺ (bc ≡ 0 mod a) ⟺ (a | bc)

⟺ (\frac{a}{gcd (a, b)} | c) (by Lemma 11)

⟺ (\frac{ga′}{g} | c) (since a = ga′ and gcd (a, b) = g)

⟺ (a′ | c) .

Thus, we can rewrite (8) as

[C_{a} ÷ b] = |{c ∈ {0, 1, …, a − 1} : a′ | c}|

= |{c ∈ {0, 1, …, ga′ − 1} : a′ | c}| (since a = ga′)

= |{the multiples of a′ between 0 (inclusive) and ga′ (exclusive)}| = |{0a′, 1a′, 2a′, …, (g − 1) a′}| = g = gcd (a, b) .

5 Proofs

We now come to the proofs of Theorem 5 and Corollary 6.

Proof of Theorem 5. A period of an n-tuple a = (α_{1}, α_{2}, …, α_{n}) means a positive integer k ∈ {1, 2, 3, …} such that g^{k} · a = a. Clearly, n is a period of each n-tuple. Thus, each n-tuple a has a smallest period. This smallest period must furthermore divide n (because if it does not, then the remainder of n upon division by this smallest period will be an even smaller period of a, which is a contradiction).

Next, we define P_{k} to be the set of all identity-product tuples in G_{1}^{n} which have smallest period k:

P_{k} := {a ∈ G_{1}^{n} : g^{k} · a = a, but g^{l} · a ≠ a for all 0 < l < k} .  (9)

Finally, we define A_{k} to be the set of all identity-product tuples with period k:

A_{k} := {a ∈ G_{1}^{n} : g^{k} · a = a} .  (10)

Lemma 13. For any k | n, we have

|A_{k}| = [G ÷ \frac{n}{k}] |G|^{k−1} .  (11)

Proof of Lemma 13. By definition, A_{k} is the set of identity-product tuples fixed by g^{k}. This implies that if we denote the first k entries of a ∈ A_{k} by α_{1}, α_{2}, …, α_{k}, then

a = (α_{1}, α_{2}, …, α_{k}, \underbrace{∗, …, ∗}_{(n−k) entries})

= g^{k}(α_{1}, α_{2}, …, α_{k}, \underbrace{∗, …, ∗}_{(n−k) entries})

= (\underbrace{∗, …, ∗}_{k entries}, α_{1}, α_{2}, …, α_{k}, \underbrace{∗, …, ∗}_{(n−2k) entries})

= g^{k}(\underbrace{∗, …, ∗}_{k entries}, α_{1}, α_{2}, …, α_{k}, \underbrace{∗, …, ∗}_{(n−2k) entries})

⋮

= ( \underbrace{∗, …, ∗}_{(n−k) entries}, α_{1}, α_{2}, …, α_{k}).

Comparing every other line entrywise, we conclude that

a = (α_{1}, α_{2}, …, α_{k}, α_{1}, α_{2}, …, α_{k}, …, α_{1}, α_{2}, …, α_{k}).

This means that the whole identity-product tuple a ∈ A_{k} is determined by α_{1}, α_{2}, …, α_{k}. Moreover, these k elements α_{1}, α_{2}, …, α_{k} must satisfy

(α_{1} · α_{2} · . . . · α_{k})^{n/k} = 1

(in order for the product of the entries of a to be 1). We can thus construct such a tuple a by first choosing the k − 1 entries α_{1}, α_{2}, …, α_{k−1} arbitrarily (there are |G|^{k−1} many options for this), and then choosing the product α_{1} ·α_{2} ·. . .·α_{k} to be any element a ∈ G that satisfies a^{n/k} = 1 (there are [G ÷ \frac{n}{k}] many such elements); this uniquely determines α_{k} and therefore the entire tuple a. So the total number of such n-tuples a ∈ A_{k} is |G|^{k−1} · [G ÷ \frac{n}{k}]. This proves Lemma 13.

Lemma 14. For any positive integer k, we have

|A_{k}| = ∑_{d|k} |P_{d}| .  (12)

Proof of Lemma 14. Each a ∈ A_{k} has some smallest period d, and this d must divide k (since otherwise, the remainder of k upon division by d would be an even smaller period of a). In other words, each a ∈ A_{k} belongs to P_{d} for some d | k, and this d is obviously unique. Thus,

A_{k} ⊆ ⨆_{d|k} P_{d}.  (13)

Conversely, if p ∈ P_{d} for some d | k, then the tuple p has smallest period d and thus has period k (since k is a multiple of d), so that p belongs to A_{k}. Thus,

⨆_{d|k} P_{d} ⊆ A_{k}.

Combined with (13), this leads to

A_{k} = ⨆_{d|k} P_{d}.  (14)

Hence,

|A_{k}| = |⨆_{d|k} P_{d}| = ∑_{d|k} |P_{d}| .

This proves Lemma 14.

Now Lemma 7 (applied to G = C_{n} and X = G_{1}^{n}) yields

|G_{1}^{n}/C_{n}| = \frac{1}{|C_{n}|} ∑_{h∈C_{n}} |\{a ∈ G_{1}^{n} : h · a = a\}|

= \frac{1}{n} ∑_{k=1}^{n} |\{a ∈ G_{1}^{n} : g^{k} · a = a\}|

(since C_{n} consists of the n elements g^{1}, g^{2}, …, g^{n}). Since each k ∈ {1, 2, …, n} satisfies

|{a ∈ G_{1}^{n} : g^{k} · a = a}| = |A_{k}| = ∑_{d|k} |P_{d}|  (by Lemma 14) ,

we can rewrite this as

|G_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{k=1}^{n} ∑_{d|k} |P_{d}| .

Since the smallest period of an n-tuple must divide n, we have |P_{d}| = 0 whenever d ∤ n. This gives us

\frac{1}{n} ∑_{k=1}^{n} ∑_{d|k} |P_{d}| = \frac{1}{n} ∑_{k=1}^{n} ∑_{\begin{matrix}d|k; \\ d|n \end{matrix}} |P_{d}| .

Now we switch the order of the summations:

\frac{1}{n} ∑_{k=1}^{n} ∑_{\begin{matrix}d|k; \\ d|n \end{matrix}} |P_{d}| = \frac{1}{n} ∑_{d|n} ∑_{\begin{matrix}k∈[1,n]; \\ d|k \end{matrix}} |P_{d}| .

Then we note that there are \frac{n}{d} equal terms in the inner sum since d | k is equivalent to k being a multiple of d, so

\frac{1}{n} ∑_{d|n} ∑_{\begin{matrix}k∈[1,n]; \\ d|k \end{matrix}} |P_{d}| = \frac{1}{n} ∑_{d|n} \frac{n}{d} |P_{d}| = ∑_{d|n} \frac{|P_{d}|}{d}.

Combining the previous five equalities, we obtain

|G_{1}^{n}/C_{n}| = ∑_{d|n} \frac{|P_{d}|}{d}.  (15)

Let us define two functions f and g from {1, 2, 3, …} to ℤ by

f(k) = |P_{k}|;  (16)
g(k) = |A_{k}| .  (17)

Then the assumption of Lemma 9 is satisfied because of Lemma 14. Hence, the former lemma yields

∑_{d|n} \frac{n}{d}f(d) = ∑_{d|n} ϕ (\frac{n}{d}) g(d).

In view of our definitions of f and g and dividing both sides by n, we can rewrite this as

∑_{d|n} \frac{|P_{d}|}{d} = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) |A_{d}| .

Using (15) for the left hand side and Lemma 13 for the right hand side, we can further rewrite this as

|G_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) [G ÷ \frac{n}{d}] |G|^{d−1} .

This proves Theorem 5.

Proof of Corollary 6. To begin with, since

G = ∏_{i=1}^{m} C_{k_{i}},  (18)

we can compute the size

|G| = |∏_{i=1}^{m} C_{k_{i}} | = ∏_{i=1}^{m} |C_{k_{i}}| = ∏_{i=1}^{m} k_{i}.  (19)

Now we need to compute [G ÷ \frac{n}{d}] for each d | n. Any finite groups H_{1}, H_{2}, …, H_{m} and any integer k satisfy

[∏_{i=1}^{m} H_{i} ÷ k] = ∏_{i=1}^{m} [H_{i} ÷ k] ,

since k-th powers in a direct product are taken entrywise. Thus, from (18), we obtain

[G ÷ \frac{n}{d}] = ∏_{i=1}^{m} [C_{k_{i}} ÷ \frac{n}{d}] = ∏_{i=1}^{m} gcd (k_{i}, \frac{n}{d})  (20)

(where we used Lemma 12 in the last step). The claim of Theorem 5 thus becomes

|G_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) [G ÷ \frac{n}{d}] |G|^{d−1}

= \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) (∏_{i=1}^{m} gcd (k_{i}, \frac{n}{d})) (∏_{i=1}^{m} k_{i})^{d−1}  (by (19) and (20))

= \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) ∏_{i=1}^{m} (gcd (k_{i}, \frac{n}{d}) k_{i}^{d−1}) .

6 Main theorem II: Aperiodic necklaces

After having computed the total number of identity-product n-necklaces for a given finite group G, we can further restrict ourselves to just those necklaces which are aperiodic.

We declare an identity-product n-necklace N to be aperiodic if it contains n distinct n-tuples. In other words, a necklace N = {a, g · a, g^{2} · a, …, g^{n−1} · a} ⊆ G_{1}^{n} is aperiodic if and only if no two of the tuples a, g · a, g^{2} · a, …, g^{n−1} · a are equal. This latter condition is equivalent to a ∈ P_{n}, where we use the notation P_{k} introduced in (9) (since g^{n} · a = a holds automatically). Thus, each aperiodic necklace in G_{1}^{n} contains n distinct tuples in P_{n}, and each tuple in P_{n} is contained in a unique aperiodic necklace in G_{1}^{n}. Hence, the number of

aperiodic necklaces in G_{1}^{n} is \frac{|P_{n}|}{n}.

Therefore, it suffices to compute |P_{n}|. To compute it, we need another number-theoretic function instead of the Euler totient function:

Definition 15. We define the Möbius function μ : {1, 2, 3, …} → ℤ by

μ(n) = \begin{cases}(−1)^{m}, & if n is a product of m distinct primes; \\ 0, & otherwise. \end{cases}

Theorem 16. Let n be a positive integer. The number \frac{|P_{n}|}{n} of aperiodic identity-product n-necklaces is

\frac{|P_{n}|}{n} = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) [G ÷ \frac{n}{d}] |G|^{d−1} .

Our proof of this theorem relies on the Möbius inversion formula, a classical result in elementary number theory (see, e.g., [21, Theorem 2.39 and the paragraph that follows]):

Lemma 17. Let f and g be two functions from {1, 2, 3, …} to ℚ. Assume that

g(k) = ∑_{d|k} f(d)  for each k ≥ 1.

Then

f(k) = ∑_{d|k} μ(d)g (\frac{k}{d})  for each k ≥ 1.

Proof of Theorem 16. Let us define two functions f and g from {1, 2, 3, …} to ℤ by

f(k) = |P_{k}| ,  (21)
g(k) = |A_{k}| .  (22)

Then the assumption of Lemma 17 is satisfied because of Lemma 14. Hence, Lemma 17 yields

|P_{k}| = ∑_{d|k} μ(d) |A_{\frac{k}{d}} |  (23)

for all k ≥ 1. Dividing both sides by n and setting k = n, this becomes

\frac{|P_{n}|}{n} = \frac{1}{n} ∑_{d|n} μ(d) |A\frac{n}{d} | .

We can substitute d for \frac{n}{d} in the sum on the right, since the map d ↦ \frac{n}{d} is a bijection from the set of positive divisors of n to itself. This yields

\frac{|P_{n}|}{n} = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) |A_{d}| .  (24)

Finally, we use Lemma 13 to rewrite this as

\frac{|P_{n}|}{n} = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) [G ÷ \frac{n}{d}] |G|^{d−1}  (25)

which concludes the proof.

On top of the special case of aperiodic necklaces, let us consider the case of identityproduct n-necklaces with smallest period k. Here we declare an n-necklace N to have smallest period k when |N| = k. Equivalently, an n-necklace N = {a, g · a, g^{2} · a, …, g^{n−1} · a} ⊆ G_{1}^{n} has smallest period k if and only if the n-tuple a has smallest period k. This is because if k is the smallest period of an n-tuple a, then the first k of the n-tuples a, g ·a, g^{2} ·a, …, g^{n−1} ·a are distinct, while all following tuples are repetitions of them. Thus, each identity-product n-necklace with smallest period k contains k distinct tuples in P_{k}. Hence, the number of these necklaces is \frac{|P_{k}|}{k}.

Corollary 18. Let n and k be positive integers with k | n. The number \frac{|P_{k}|}{k} of identityproduct n-necklaces with smallest period k is

\frac{|P_{k}|}{k} = \frac{1}{k} ∑_{d|k} μ (\frac{k}{d}) [G ÷ \frac{n}{d}] |G|^{d−1} .

Proof. Recall that in the proof of Theorem 16, we proved the general equation (23). That is,

|P_{k}| = ∑_{d|k} μ(d) |A_{\frac{k}{d}} | .

By bijective substitution of d with \frac{k}{d} on the positive divisors of k to themselves, this can be turned into

|P_{k}| = ∑_{d|k} μ (\frac{k}{d}) |A_{d}| .

We can rewrite the right hand side using Lemma 13, applied to d instead of k (since d | k | n). The above equality thus takes the form

|P_{k}| = ∑_{d|k} μ (\frac{k}{d}) [G ÷ \frac{n}{d}] |G|^{d−1} .  (26)

Now, dividing both sides by k, we obtain

\frac{|P_{k}|}{k} = \frac{1}{k} ∑_{d|k} μ (\frac{k}{d}) [G ÷ \frac{n}{d}] |G|^{d−1} .  (27)

7 Main theorem III: Homogeneous necklaces

An interesting variant of necklaces was proposed by Gilbert and Riordan [9]. They count ntuples of elements of the cyclic group C_{q} (which they write additively, as ℤ/q), but identifying each n-tuple not only with its cyclic rotations, but also with all the other n-tuples that can be obtained by multiplying all its entries by the same element of C_{q}. For instance, for q = 3 and n = 3, each n-tuple (a, b, c) ∈ C_{q}^{n} = C_{3}^{3} thus ends up in a single equivalence class with (b, c, a), (c, a, b), (ga, gb, gc), (gb, gc, ga), (gc, ga, gb), (g^{2}a, g^{2}b, g^{2}c), (g^{2}b, g^{2}c, g^{2}a) and (g^{2}c, g^{2}a, g^{2}b). Such equivalence classes can be called “homogeneous necklaces”. They were first considered for q = 2 by Fine [6], motivated by psychometric experiments.

The “homogeneous necklaces” can also be generalized to an arbitrary finite group G instead of C_{q}. Rather than introduce custom terminology for them, we shall define them as the orbits of a group action:

As before, G is a finite group. We also fix a positive integer n. Consider the cyclic group C_{n} = {g^{0}, g^{1}, …, g^{n−1}} with generator g.

We recall that the cyclic group C_{n} acts (from the left) on G^{n} by rotating n-tuples: If i ∈ ℤ, then the element g^{i} ∈ C_{n} acts on an n-tuple by rotating this n-tuple i steps to the right.

The group G also acts from the left on G^{n}, by the rule

h · (a_{1}, a_{2}, …, a_{n}) = (ha_{1}, ha_{2}, …, ha_{n})
for all h ∈ G and (a_{1}, a_{2}, …, a_{n}) ∈ G^{n}.

Thus, an element h ∈ G acts on an n-tuple a ∈ G^{n} by multiplying all entries of a by h from the left.

The two actions (of C_{n} and of G) on G^{n} commute, meaning that

g^{i} · (h · a) = h · (g^{i} · a) for all g^{i} ∈ C_{n} and h ∈ G and a ∈ G^{n}.

(This is intuitively obvious: Multiplying all entries of a by h can be done either before or after a cyclic rotation; the outcome will be the same.)

This commutativity allows us to combine the actions of C_{n} and of G into a single action of the direct product C_{n} × G on G^{n}. Explicitly, the group C_{n} × G acts from the left on G^{n} by the rule

(g^{i}, h) · a = g^{i} · (h · a) = h · (g^{i} · a)
for all g^{i} ∈ C_{n} and h ∈ G and a ∈ G^{n}.

Thus, a pair (g^{i}, h) acts on an n-tuple a ∈ G^{n} by rotating the n-tuple i steps to the right and multiplying each entry by h from the left. The orbits of this action can be called the “homogeneous n-necklaces”, though we shall just refer to them as orbits. Now, we claim the following:

Theorem 19. The number |G^{n}/ (C_{n} × G)| of all orbits of the action of C_{n} × G on G^{n} equals the number |G_{1}^{n}/C_{n}| of all identity-product n-necklaces. Thus,

|G^{n}/ (C_{n} × G)| = |G_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) [G ÷ \frac{n}{d}] |G|^{d−1} .

This is implicitly claimed in the OEIS (On-Line Encyclopedia of Integer Sequences) entry for sequence \underline{A000013} for the case G = C_{2} (see also https://math.stackexchange. com/questions/3249602 ), but the general case appears new. We prove the general case bijectively:

Proof of Theorem 19. If i is any integer, then the residue class of i modulo n will be denoted by \overline{i}. For instance, \overline{n} = \overline{0}.

If a ∈ G^{n} is an n-tuple, then the i-th entry of a (for any given i ∈ {1, 2, …, n}) will be denoted by a\overline{i} (so that a = (a\overline{1}, a\overline{2}, …, a\overline{n}) and a\overline{0} = a\overline{n} and a\overline{n+1} = a\overline{1}). Thus, the entries of our n-tuples are now indexed by elements of ℤ/n. If a ∈ G^{n} is an n-tuple, then a_{r} is hence defined for any residue class r ∈ ℤ/n.

Note that the action of C_{n} on G^{n} can thus be described by the equality

(g^{i} · a)\overline{j} = a\overline{j−i}  (28)

for all g^{i} ∈ C_{n} (that is, all i ∈ ℤ), all a ∈ G^{n} and all j ∈ ℤ.

Likewise, the action of G on G^{n} can be described by the equality

(h · a)\overline{j} = ha\overline{j}  (29)

for all h ∈ G, all a ∈ G^{n} and all j ∈ ℤ.

Hence, for all g^{i} ∈ C_{n}, all h ∈ G, all a ∈ G^{n} and all j ∈ ℤ, we have

((g^{i}, h) · a)\overline{j} = (g^{i} · (h · a))\overline{j}  (since (g^{i}, h) · a = g^{i} · (h · a))
= (h · a)\overline{j−i} (by (28), applied to h · a instead of a)
= ha\overline{j−i}  (30)

(by (30), applied to j − i instead of j).

If a ∈ G^{n} is any n-tuple, then

(a−1 ; \overline{0}a\overline{1}, a−1 ; \overline{1}a\overline{2}, a−1 ; \overline{2}a\overline{3}, …, a−1 ; \overline{n−1}a\overline{n}) ∈ G_{1}^{n},

since

a−1 ; \overline{0}a\overline{1} · a−1 ; \overline{1}a\overline{2} · a−1 ; \overline{2}a\overline{3} · · · · · a−1 ; \overline{n−1}a\overline{n} = a−1 ; \overline{0}a\overline{n}  (by the telescope principle)
= 1 (since a\overline{n} = a\overline{0} (since \overline{n} = \overline{0})) .

Thus, we can define a map

Δ : G^{n} → G_{1}^{n},
a ↦ (a−1 ; \overline{0}a\overline{1}, a−1 ; \overline{1}a\overline{2}, a−1 ; \overline{2}a\overline{3}, …, a−1 ; \overline{n−1}a\overline{n}) .

This map Δ satisfies the equality

(Δ (a))\overline{j} = a−1 ; \overline{j−1}a\overline{j}  (31)

for all a ∈ G^{n} and j ∈ ℤ.

Proof of (31). Let a ∈ G^{n}. The definition of Δ shows that

Δ (a) = (a−1 ; \overline{0}a\overline{1}, a−1 ; \overline{1}a\overline{2}, a−1 ; \overline{2}a\overline{3}, …, a−1 ; \overline{n−1}a\overline{n}) .

Hence, the equality (Δ (a))\overline{j} = a−1 ; \overline{j−1}a\overline{j} holds for each j ∈ \{1, 2, …, n\}. But both sides of this equality—considered as functions of j—are periodic with a period of n (since \overline{j} and \overline{j − 1} are periodic with a period of n). Therefore, having shown that this equality holds for all j ∈ {1, 2, …, n}, we automatically conclude that it must hold for all j ∈ ℤ. This proves (31).

Next we claim the following property of Δ:

Claim 1: If two n-tuples a ∈ G^{n} and b ∈ G^{n} belong to the same C_{n} × G-orbit, then their images Δ (a) and Δ (b) belong to the same C_{n}-orbit.

Proof of Claim 1. Let a ∈ G^{n} and b ∈ G^{n} belong to the same C_{n}×G-orbit. Thus, b = (g^{i}, h)·a for some g^{i} ∈ C_{n} and h ∈ G. Consider these g^{i} and h. Thus, for each j ∈ ℤ, we have

b\overline{j} = ((g^{i}, h) · a)\overline{j} = ha\overline{j−i} (by (30))

and

b\overline{j−1} = ha\overline{j−1−i} (similarly)

and

(Δ (b))\overline{j} = b−1 ; \overline{j−1}b\overline{j}  (by (31), applied to b instead of a)
= (ha\overline{j−1−i})^{−1} (ha\overline{j−i}) (since b\overline{j} = ha\overline{j−i} and b\overline{j−1} = ha\overline{j−1−i})
= \underbrace{a−1 ; \overline{j−1−i}}_{=a−1 ; \overline{j−i−1}} \underbrace{h^{−1}h}_{=1} a\overline{j−i} = a−1 ; \overline{j−i−1}a\overline{j−i}.  (32)

However, for each j ∈ ℤ, we have

(g^{i} · Δ (a))\overline{j} = (Δ (a))\overline{j−i}  (by (28), applied to Δ (a) instead of a)
= a−1 ; \overline{j−i−1}a\overline{j−i} (by (31), applied to j − i instead of j) .

Comparing this with (32), we obtain

(Δ (b))\overline{j} = (g^{i} · Δ (a))\overline{j} for each j ∈ ℤ.

In other words, each entry of Δ (b) equals the corresponding entry of g^{i} · Δ (a). Hence, Δ (b) = g^{i} · Δ (a). This shows that Δ (a) and Δ (b) belong to the same C_{n}-orbit. Claim 1 is thus proved.

Next, we define a map

Γ : G_{1}^{n} → G^{n},
a ↦ (a\overline{1}, a\overline{1}a\overline{2}, a\overline{1}a\overline{2}a\overline{3}, …, a\overline{1}a\overline{2} ⋯ a\overline{n}) .

Thus, this map Γ is given by the rule

(Γ (a))\overline{j} = a\overline{1}a\overline{2} ⋯ a\overline{j}  (33)

for all a ∈ G^{n} and j ∈ {1, 2, …, n}. When a is an identity-product n-tuple, we can extend this rule a bit further: For any a ∈ G_{1}^{n}, we have

(Γ (a))\overline{j} = a\overline{1}a\overline{2} ⋯ a\overline{j}  for all j ∈ \{0, 1, …, n\} .  (34)

Proof of (34). Let a ∈ G_{1}^{n}. Let j ∈ {0, 1, …, n}. We must prove (34). If j ≠ 0, then j ∈ {1, 2, …, n}, and thus (34) follows directly from (33) in this case. Thus, it remains to prove (34) for j = 0. In other words, it remains to prove that (Γ (a))\overline{0} = a\overline{1}a\overline{2} ⋯ a\overline{0}. Since the empty product a\overline{1}a\overline{2} ⋯ a\overline{0} is 1 by definition, this means proving that (Γ (a))\overline{0} = 1. But this is easy: We have \overline{0} = \overline{n}, so that (Γ (a))\overline{0} = (Γ (a))\overline{n} = a\overline{1}a\overline{2} ⋯ a\overline{n} (by (33)). But (a\overline{1}, a\overline{2}, …, a\overline{n}) = a ∈ G_{1}^{n}, and thus a\overline{1}a\overline{2} ⋯ a\overline{n} = 1 (by the definition of G_{1}^{n}). Hence, (Γ (a))\overline{0} = a\overline{1}a\overline{2} ⋯ a\overline{n} = 1, just as we desired to prove. Thus the proof of (34) is complete.

Next, let us prove an analogue of Claim 1 for the map Γ:

Claim 2: If two n-tuples a ∈ G_{1}^{n} and b ∈ G_{1}^{n} belong to the same C_{n}-orbit, then their images Γ (a) and Γ (b) belong to the same C_{n} × G-orbit.

Proof of Claim 2. We define a binary relation ∼ on the set G^{n} by

(u ∼ v) ⟺ (u and v belong to the same C_{n} × G-orbit) .

Clearly, this relation ∼ is an equivalence relation.

Now let us show that every a ∈ G_{1}^{n} satisfies

Γ (a) ∼ Γ (g · a) .  (35)

Indeed, fix a ∈ G_{1}^{n}. We shall show that Γ (g · a) = (g^{1}, a\overline{n})·Γ (a) (where the pair (g^{1}, a\overline{n}) ∈ C_{n} × G acts on Γ (a) via the C_{n} × G-action on G^{n} defined above).

First we observe that g · a = (a\overline{n}, a\overline{1}, a\overline{2}, …, a\overline{n−1}) by the definition of the C_{n}-action on G^{n}. Thus, (g · a)\overline{1} = a\overline{n} and

(g · a)\overline{i} = a\overline{i−1} for each i ∈ ℤ.  (36)

Now, let k ∈ {1, 2, …, n}. Then (33) (applied to g · a and k instead of a and j) shows that

(Γ (g · a))\overline{k} = (g · a)\overline{1} (g · a)\overline{2} ⋯ (g · a)\overline{k}

= \underbrace{(g · a)\overline{1}}_{=a\overline{n}} · \underbrace{(g · a)\overline{2}}_{\begin{matrix}=a\overline{1} \\ (by (36)) \end{matrix}} \underbrace{(g · a)\overline{3}}_{\begin{matrix}=a\overline{2} \\ (by (36)) \end{matrix}} ⋯ \underbrace{(g · a)\overline{k}}_{\begin{matrix}=a\overline{k−1} \\ (by (36)) \end{matrix}}

= a\overline{n} · a\overline{1}a\overline{2} ⋯ a\overline{k−1}.  (37)

On the other hand, from k ∈ {1, 2, …, n}, we obtain k − 1 ∈ {0, 1, …, n}. Hence, (34) (applied to j = k − 1) yields (Γ (a))\overline{k−1} = a\overline{1}a\overline{2} ⋯ a\overline{k−1}. But (30) (applied to 1, a\overline{n}, Γ (a) and k instead of i, h, a and j) yields

((g^{1}, a\overline{n}) · Γ (a))\overline{k} = a\overline{n} · \underbrace{(Γ (a))\overline{k−1}}_{=a\overline{1}a\overline{2}···a\overline{k−1}} = a\overline{n} · a\overline{1}a\overline{2} ⋯ a\overline{k−1}.

Comparing this with (37), we see that

(Γ (g · a))\overline{k} = ((g^{1}, a\overline{n}) · Γ (a))\overline{k} .

Forget that we fixed k. We thus have shown that (Γ (g · a))\overline{k} = ((g^{1}, a\overline{n}) · Γ (a))\overline{k} for each k ∈ {1, 2, …, n}. In other words, each entry of the n-tuple Γ (g · a) equals the corresponding entry of (g^{1}, a\overline{n}) · Γ (a). Hence,

Γ (g · a) = (g^{1}, a\overline{n}) · Γ (a) .

Thus, the two n-tuples Γ (a) and Γ (g · a) belong to the same C_{n} × G-orbit. By the definition of the relation ∼, this means that Γ (a) ∼ Γ (g · a). Thus, (35) is proved.

Now, let a ∈ G_{1}^{n} and b ∈ G_{1}^{n} be two n-tuples that belong to the same C_{n}-orbit. We must prove that their images Γ (a) and Γ (b) belong to the same C_{n} × G-orbit. In other words, we must prove that Γ (a) ∼ Γ (b).

We have assumed that a and b belong to the same C_{n}-orbit. In other words, a = γ · b for some γ ∈ C_{n}. Consider this γ. Thus, γ ∈ C_{n} = {g^{0}, g^{1}, …, g^{n−1}}. In other words, γ = g^{i} for some i ∈ {0, 1, …, n − 1}. Consider this i. Now, for each k ∈ ℕ, we have

Γ (g^{k} · b) ∼ Γ (g^{k+1} · b)  (38)

(since (35) (applied to g^{k} · b instead of a) yields Γ (g^{k} · b) ∼ Γ (\underbrace{g · g^{k}}_{=g^{k+1}} · b) = Γ (g^{k+1} · b)).

Hence, we obtain a chain of relations

Γ (g^{0} · b) ∼ Γ (g^{1} · b) ∼ Γ (g^{2} · b) ∼ · · · .

Since ∼ is an equivalence relation, this yields Γ (g^{i} · b) ∼ Γ (g^{0} · b) in particular. In view of g^{i} = γ and g^{0} = 1, we can rewrite this as Γ (γ · b) ∼ Γ (1 · b). In other words, Γ (a) ∼ Γ (b) (since a = γ · b and b = 1 · b). Hence, Claim 2 is proved.

Now, the map

\overline{Δ} : G^{n}/ (C_{n} × G) → G_{1}^{n}/C_{n},
(C_{n} × G-orbit of a) ↦ (C_{n}-orbit of Δ (a))

is well-defined (by Claim 1), and so is the map

\overline{Γ} : G_{1}^{n}/C_{n} → G^{n}/ (C_{n} × G) ,
(C_{n}-orbit of a) ↦ (C_{n} × G-orbit of Γ (a))

(by Claim 2). We shall now prove that these two maps \overline{Δ} and \overline{Γ} are mutually inverse. We do this through two claims:

Claim 3: We have \overline{Γ} ∘ \overline{Δ} = id.

Proof of Claim 3. Let x ∈ G^{n}/ (C_{n} × G) be arbitrary. Thus, x is the C_{n} × G-orbit of some a ∈ G^{n}. Consider this a. Thus, the definition of \overline{Δ} shows that \overline{Δ} (x) is the C_{n}-orbit of Δ (a). Hence, the definition of \overline{Γ} shows that \overline{Γ} (\overline{Δ} (x)) is the C_{n} × G-orbit of Γ (Δ (a)). We shall now show that Γ (Δ (a)) and a belong to the same C_{n} × G-orbit. More specifically, we shall show that Γ (Δ (a)) = (g^{0}, a−1 ; \overline{0}) · a, where the pair (g^{0}, a−1 ; \overline{0}) ∈ C_{n} × G acts on a via the C_{n} × G-action on G^{n}.

For each k ∈ {1, 2, …, n}, we have

(Γ (Δ (a)))\overline{k} = \underbrace{(Δ (a))\overline{1}}_{\begin{matrix}=a−1 ; \overline{0}a\overline{1} \\ (by (31)) \end{matrix}} · \underbrace{(Δ (a))\overline{2}}_{\begin{matrix}=a−1 ; \overline{1}a\overline{2} \\ (by (31)) \end{matrix}} · · · · · \underbrace{(Δ (a))\overline{k}}_{\begin{matrix}=a−1 ; \overline{k−1}a\overline{k} \\ (by (31)) \end{matrix}}

(by (33), applied to Δ (a) and k instead of a and j)

= a−1 ; \overline{0}a\overline{1} · a−1 ; \overline{1}a\overline{2} · · · · · a−1 ; \overline{k−1}a\overline{k}

= a−1 ; \overline{0}a\overline{k} (by the telescope principle)

and

((g^{0}, a−1 ; \overline{0}) · a)\overline{k} = a−1 ; \overline{0}a\overline{k−0}  (by (30), applied to i = 0 and h = a−1 ; \overline{0} and j = k)

= a−1 ; \overline{0}a\overline{k} (since k − 0 = k) .

Comparing these two equalities, we see that

(Γ (Δ (a)))\overline{k} = ((g^{0}, a−1 ; \overline{0}) · a)\overline{k} for each k ∈ \{1, 2, …, n\} .

In other words, each entry of the n-tuple Γ (Δ (a)) equals the corresponding entry of (g^{0}, a−1 ; \overline{0})· a. Hence, Γ (Δ (a)) = (g^{0}, a−1 ; \overline{0}) · a. Therefore, Γ (Δ (a)) and a belong to the same C_{n} × Gorbit. In other words, the C_{n} × G-orbit of Γ (Δ (a)) is precisely the C_{n} × G-orbit of a. In other words, \overline{Γ} (\overline{Δ} (x)) = x (since \overline{Γ} (\overline{Δ} (x)) is the C_{n} × G-orbit of Γ (Δ (a)), whereas x is the C_{n} × G-orbit of a).

Forget that we fixed x. We thus have shown that \overline{Γ} (\overline{Δ} (x)) = x for each x ∈ G^{n}/ (C_{n} × G). In other words, \overline{Γ} ∘ \overline{Δ} = id. This proves Claim 3.

Claim 4: We have \overline{Δ} ∘ \overline{Γ} = id.

Proof of Claim 4. Let x ∈ G_{1}^{n}/C_{n} be arbitrary. Thus, x is the C_{n}-orbit of some a ∈ G_{1}^{n}. Consider this a. Hence, the definition of \overline{Γ} shows that \overline{Γ} (x) is the C_{n} × G-orbit of Γ (a). Therefore, the definition of \overline{Δ} shows that \overline{Δ} (\overline{Γ} (x)) is the C_{n}-orbit of Δ (Γ (a)). We shall now show that Δ (Γ (a)) = a.

Let k ∈ {1, 2, …, n}. Then (31) (applied to Γ (a) and k instead of a and j) yields

(Δ (Γ (a)))\overline{k} = (Γ (a))−1 ; \overline{k−1} · (Γ (a))\overline{k}
= (a\overline{1}a\overline{2} ⋯ a\overline{k−1})^{−1} · (a\overline{1}a\overline{2} ⋯ a\overline{k})

(since (34) shows that (Γ (a))\overline{k} = a\overline{1}a\overline{2} ⋯ a\overline{k} and (Γ (a))\overline{k−1} = a\overline{1}a\overline{2} ⋯ a\overline{k−1} (because k − 1 ∈ {0, 1, …, n})). Thus,

(Δ (Γ (a)))\overline{k} = (a\overline{1}a\overline{2} ⋯ a\overline{k−1})^{−1} · (a\overline{1}a\overline{2} ⋯ a\overline{k})
= a\overline{k} (since a\overline{1}a\overline{2} ⋯ a\overline{k} = (a\overline{1}a\overline{2} ⋯ a\overline{k−1}) · a\overline{k}) .

Forget that we fixed k. We have thus shown that (Δ (Γ (a)))\overline{k} = a\overline{k} for each k ∈ {1, 2, …, n}. In other words, each entry of the n-tuple Δ (Γ (a)) equals the corresponding entry of a. Hence, Δ (Γ (a)) = a. Therefore, \overline{Δ} (\overline{Γ} (x)) = x (since \overline{Δ} (\overline{Γ} (x)) is the C_{n}-orbit of Δ (Γ (a)), whereas x is the C_{n}-orbit of a).

Forget that we fixed x. We thus have shown that \overline{Δ} (\overline{Γ} (x)) = x for each x ∈ G_{1}^{n}/C_{n}. In other words, \overline{Δ} ∘ \overline{Γ} = id. This proves Claim 4.

Combining Claim 3 with Claim 4, we see that the maps \overline{Δ} and \overline{Γ} are mutually inverse. In particular, \overline{Δ} : G^{n}/ (C_{n} × G) → G_{1}^{n}/C_{n} is an invertible map, i.e., a bijection. Hence, by the bijection principle, we have

|G^{n}/ (C_{n} × G)| = |G_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) [G ÷ \frac{n}{d}] |G|^{d−1}

(by Theorem 5). This proves Theorem 19.

8 K-product necklaces

We can extend the definition we gave earlier for identity-product necklaces to be more general than dealing with only the case of the identity.

For this entire section, we fix a subset K of G that is closed under conjugation (i.e., satisfies gkg^{−1} ∈ K for all g ∈ G and k ∈ K). Equivalently, K shall be a union of conjugacy classes of G. Examples of such subsets K are single conjugacy classes, normal subgroups, complements of normal subgroups, singleton subsets {h} where h lies in the center of G, and the whole group G.

Definition 20. For any nonnegative integer n, we let G_{K}^{n} be the set of all K-product n-tuples, defined by

G_{K}^{n} := {a = (a_{1}, a_{2}, …, a_{n}) ∈ G^{n} : a_{1}a_{2}a_{3} ⋯ a_{n} ∈ K} .

The cyclic group C_{n} acts on G^{n} by cyclic rotation, as we know. We claim that the subset G_{K}^{n} is preserved under this action also. That is, for any K-product n-tuple (a_{1}, a_{2}, …, a_{n}), its cyclic rotation (a_{n}, a_{1}, a_{2}, …, a_{n−1}) is again a K-product n-tuple, since its product

a_{n}a_{1}a_{2} ⋯ a_{n−1} = a_{n} \underbrace{a_{1}a_{2} ⋯ a_{n−1}a_{n}}_{∈K} a_{n}^{−1} ∈ a_{n}Ka_{n}^{−1} ⊆ K

(since K is closed under conjugation). Thus G_{K}^{n} is a C_{n}-set. In a similar fashion as with identity-product necklaces, orbits of this action of C_{n} on G_{K}^{n} will be called K-product nnecklaces.

Definition 21. For any integer n, let us define the number [G ÷ K ÷ n] to be

[G ÷ K ÷ n] := |{a ∈ G : a^{n} ∈ K}| .

This generalizes [G ÷ n], since [G ÷ n] = [G ÷ {1} ÷ n].

With this generalization to K-product n-necklaces, we get an analogue to Theorem 5:

Theorem 22. Let n be a positive integer. The number |G_{K}^{n}/C_{n}| of K-product n-necklaces is

|G_{K}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) [G ÷ K ÷ n] |G|^{d−1} .

The proof of this analogue of Theorem 5 is the same except for the following changes: replace all G_{1} by G_{K} and replace all [G ÷ n] by [G ÷ K ÷ n].

For example, the analogous versions of the definitions of P_{k} and A_{k} as well as Lemma 13 are, respectively

P_{k} := {a ∈ G_{K}^{n} : g^{k} · a = a, but g^{l} · a ≠ a for all 0 < l < k} .  (39)
A_{k} := {a ∈ G_{K}^{n} : g^{k} · a = a} .  (40)

Lemma 23. For any k | n, we have

|A_{k}| = [G ÷ K ÷ \frac{n}{k}] |G|^{k−1} .  (41)

This generalization also subsumes the classical formula (1). Indeed, if we take G = C_{q} and K = G, then Theorem 22 recovers the count of n-necklaces over a size-q set.

With the same replacement of all mentions of G_{1} and [G ÷ n] with their K-product analogues, we can also obtain an analogous K-product version of Theorem 16 which counts the number of aperiodic K-product n-necklaces:

Theorem 24. Let n be a positive integer. The number \frac{|P_{n}|}{n} of aperiodic K-product nnecklaces is

\frac{|P_{n}|}{n} = \frac{1}{n} ∑_{d|n} μ (\frac{n}{d}) [G ÷ K ÷ \frac{n}{d}] |G|^{d−1} .

We leave it as an open question as to whether or not the bijection between identityproduct necklaces and homogeneous necklaces has some analogue in the K-product setting as well.

9 Irreducible polynomials

As we briefly mentioned in the introduction, aperiodic necklaces over a size-q set are related to irreducible degree-n polynomials over the finite field 𝔽_{q} when q is a prime power. This relation can be restricted to aperiodic identity-product n-necklaces (over the additive group of 𝔽_{q}, so the identity is actually 0) on the one hand, and to the irreducible degree-n polynomials with second-highest coefficient 0 on the other. We shall now elaborate on this.

9.1 Reminders on finite fields and their Galois groups

Let q be a prime power. Let K/F be a degree-n field extension, where F is the finite field with q elements. Thus, K is a finite field with q^{n} elements. Note that K/F is a Galois extension (like any extension of finite fields).

It is well-known that the map

F : K → K,
x ↦ x^{q}

is an F -algebra automorphism of K. This is called the Frobenius automorphism over 𝔽_{q}, and generates the Galois group of the field extension K/F. Its k-th power F^{k} sends each x ∈ K to x^{q^{k}}. In particular, its n-th power F^{n} is the identity map, since each x ∈ K satisfies x^{q^{n}} = x^{|K|} = x. Thus, the Galois group Gal(K/F) consists of the n distinct automorphisms F^{0}, F^{1}, …, F^{n−1}.

A significant role in Galois theory is played by the trace:

Definition 25. The trace map is the linear map tr : K → K defined by

tr := F^{0} + F^{1} + ⋯ + F^{n−1}.  (42)

The trace of an element x ∈ K is defined to be the image tr(x) of x under this map. Explicitly,

tr(x) = x + Fx + F^{2}x + ⋯ + F^{n−1}x  (43)
= x + x^{q} + x^{q^{2}} + ⋯ + x^{q^{n−1}}.  (44)

Notably, tr ∘ F = tr, since right-multiplication by F merely cyclically permutes the addends on the right hand side of (42) (since F^{n} = id = F^{0}) but does not affect the sum as a whole. Similarly, F ∘ tr = tr. The latter equality shows that each x ∈ K satisfies F (tr (x)) = tr (x), and thus tr (x) is fixed by the Galois group Gal(K/F) (since all elements of Gal(K/F) are powers of F). Since K/F is a Galois extension, this shows that

tr(x) ∈ F  for all x ∈ K.  (45)

Definition 26. We say that two elements of K are conjugate if they have the same minimal polynomial over F. Equivalently, two elements x, y ∈ K are conjugate if x = A (y) for some A ∈ Gal(K/F).

If x and y are two conjugate elements of K, then their traces are equal: tr(x) = tr(y). Indeed, from tr ∘ F = tr, we obtain

tr ∘ F^{k} = tr  for all k ∈ ℤ.  (46)

But this means that tr ∘ A = tr for each A ∈ Gal(K/F) (since all elements of Gal(K/F) are powers of F). Hence, if x = A (y) for some A ∈ Gal(K/F), then tr (x) = tr (A (y)) = (tr ∘ A) (y) = tr (y).

Hence, we define the trace of an entire conjugacy class to be the trace of any of its elements.

9.2 Normal bases and the bijection Φ

A normal basis of K (over F) means a basis of K as an F -vector space that has the form (θ^{q^{0}}, θ^{q^{1}}, …, θ^{q^{n−1}}), where θ ∈ K. A classical fact (the normal basis theorem for finite fields) says:

Theorem 27. There exists a normal basis of K over F.

Proofs of this theorem can be found in [14, Theorem 2.35], [18, Appendix B], [13, Theorem 1.15], [7, Corollary 2.4.6] and various other texts on finite fields. It is in fact a particular case of the normal basis theorem for arbitrary Galois extensions, which appears (e.g.) in [16, Theorem 5.18], [4] etc.

Henceforth, we fix a normal basis (θ^{q^{0}}, θ^{q^{1}}, …, θ^{q^{n−1}}) of K over F.

Following [20, Section 7.6.2], we introduce the map

Φ : F^{n} → K,
(a_{0}, a_{1}, …, a_{n−1}) ↦ a_{0}θ^{q^{0}} + a_{1}θ^{q^{1}} + ⋯ + a_{n−1}θ^{q^{n−1}}.

This is a bijection, since (θ^{q^{0}}, θ^{q^{1}}, …, θ^{q^{n−1}}) is a basis of K over F. Note that F^{n} (θ) = θ, since F^{n} = id.

Recall that the cyclic group C_{n} acts on the set F^{n} by cyclically rotating n-tuples. We also let C_{n} act on the set K by having the generator g act as the Frobenius automorphism F. This is a well-defined group action, since F^{n} = id. Now we claim the following:

Lemma 28. The bijection Φ is an isomorphism of C_{n}-sets.

Proof. We must prove that Φ is C_{n}-equivariant (since we already know Φ to be a bijection). Thus, need to show that Φ (h · a) = h · Φ (a) for any a ∈ F^{n} and any h ∈ C_{n}. Since the group C_{n} is generated by g, it suffices to show this for h = g. So we must prove that Φ (g · a) = g · Φ (a) for any a ∈ F^{n}.

Consider the standard basis (e_{0}, e_{1}, …, e_{n−1}) of the F -vector space F^{n}, where e_{i} is the n-tuple (0, 0, …, 0, 1, 0, 0, …, 0) with i many 0’s preceding the entry 1. We also set e_{n} := e_{0}. The C_{n}-action on F^{n} then satisfies g · e_{i} = e_{i+1} for each i ∈ {0, 1, …, n − 1}.

We must prove that Φ (g · a) = g · Φ (a) for any a ∈ F^{n}. Since Φ is F -linear, it suffices to prove this for all basis vectors a = e_{i} with i ∈ {0, 1, …, n − 1}. That is, we must show that Φ (g · e_{i}) = g · Φ (e_{i}) for all i ∈ {0, 1, …, n − 1}.

Fix i ∈ {0, 1, …, n − 1}. Then g · e_{i} = e_{i+1} as we saw above. Hence, Φ (g · e_{i}) = Φ (e_{i+1}). But the definition of Φ yields Φ (e_{i}) = θ^{q^{i}} = F^{i} (θ), so that

g · Φ (e_{i}) = g · F^{i} (θ) = F (F^{i} (θ)) = F^{i+1} (θ) .  (47)

Moreover, we claim that Φ (e_{i+1}) = F^{i+1} (θ). Indeed, if i + 1 < n, then this follows from the definition of Φ (similarly to Φ (e_{i}) = F^{i} (θ)), whereas in the case i + 1 = n, it follows from Φ (e_{n}) = Φ (e_{0}) = θ^{q^{0}} = θ = F^{n} (θ). Thus, Φ (g · e_{i}) = Φ (e_{i+1}) = F^{i+1} (θ). Comparing this with (47), we obtain Φ (g · e_{i}) = g · Φ (e_{i}) as desired.

Corollary 29. Two n-tuples in F^{n} lie in the same C_{n}-orbit if and only if their images under Φ are conjugate elements.

Proof. Let x and y be two n-tuples in F^{n}. By Lemma 28, these tuples x and y lie in the same C_{n}-orbit if and only if their images Φ (x) and Φ (y) lie in the same C_{n}-orbit. But the C_{n}-orbits on K are just the orbits of the Galois group Gal(K/F), since C_{n} acts on K by having g act as the generator F of Gal(K/F). So x and y lie in the same C_{n}-orbit if and only if their images Φ (x) and Φ (y) lie in the same orbit of Gal(K/F), that is, are conjugate.

Thus, Φ gives rise to a bijection from F^{n}/C_{n} (that is, n-necklaces over F) to the set of conjugacy classes of elements of K over F. We denote this bijection by Φ̂.

9.3 Zero-sum necklaces and zero-trace conjugacy classes

We say that an n-tuple a = (a_{1}, a_{2}, …, a_{n}) ∈ F^{n} is zero-sum if a_{1} + a_{2} + ⋯ + a_{n} = 0 in F. The zero-sum n-tuples are just the identity-product n-tuples for the abelian group (F, +, 0). We denote the set of those zero-sum n-tuples as F_{0}^{n}.

We say that a given n-necklace a ∈ F^{n}/C_{n} is zero-sum if its representatives a = (a_{1}, a_{2}, …, a_{n}) ∈ a are zero-sum n-tuples (i.e., satisfy a_{1} + a_{2} + ⋯ + a_{n} = 0 in F). This condition clearly does not depend on the choice of the representative, since cyclic rotation of an n-tuple does not change the sum of its entries. The zero-sum n-necklaces are just the n-identity-product necklaces for the abelian group (F, +, 0). Therefore, their set is F_{0}^{n}/C_{n}.

Theorem 30. A necklace a ∈ F^{n}/C_{n} is zero-sum if and only if the corresponding conjugacy class Φ̂ (a) has trace 0.

Proof of Theorem 30. Let us first note that (44) yields tr(θ) = θ + θ^{q} + θ^{q^{2}} + ⋯ + θ^{q^{n−1}} ≠ 0, since (θ, θ^{q}, θ^{q^{2}}, …, θ^{q^{n−1}}) = (θ^{q^{0}}, θ^{q^{1}}, …, θ^{q^{n−1}}) is a basis of K over F.

Fix a necklace a, and let a = (a_{0}, a_{1}, …, a_{n−1}) be a representative (i.e., one of the tuples in a). Thus, Φ̂ (a) is the conjugacy class of

Φ (a) = Φ (a_{0}, a_{1}, …, a_{n−1}) = a_{0}θ^{q^{0}} + a_{1}θ^{q^{1}} + ⋯ + a_{n−1}θ^{q^{n−1}}

= ∑_{k=0}^{n−1} a_{k}θ^{q^{k}} = ∑_{k=0}^{n−1} a_{k}F^{k} (θ) .

Hence, we can compute the trace of Φ̂ (a) as follows:

tr(Φ̂ (a)) = tr (∑_{k=0}^{n−1} a_{k}F^{k} (θ))

= ∑_{k=0}^{n−1} a_{k} tr (F^{k}(θ)) (since tr is F -linear)

= ∑_{k=0}^{n−1} a_{k} (tr ∘ F^{k}) (θ)

= ∑_{k=0}^{n−1} a_{k} tr(θ) (by (46))

= (a_{0} + a_{1} + ⋯ + a_{n−1}) tr(θ).

Thus, tr(Φ̂ (a)) = 0 if and only if a_{0} + a_{1} + ⋯ + a_{n−1} = 0 (since tr(θ) ≠ 0). In other words, Φ̂ (a) has trace 0 if and only if a is a zero-sum necklace.

Corollary 31. The number of conjugacy classes of elements of K over F with trace 0 is equal to |F_{0}^{n}/C_{n}|.

Proof. Theorem 30 shows that the bijection Φ̂ restricts to a bijection from the set F_{0}^{n}/C_{n} of zero-sum n-necklaces to the set of conjugacy classes of elements of K over F with trace 0. Thus, the two sets are equinumerous.

Thus, we can use Theorem 5 to count the conjugacy classes with trace 0.

We shall next restrict ourselves to zero-sum n-tuples and n-necklaces with certain periodicity properties. We recall the notions of “aperiodic” and “smallest period” we introduced in Section 6. We define P_{n} to be the set of all zero-sum n-tuples in F_{0}^{n} whose smallest period is n. This is a particular case of the definition of P_{k} in (9), applied to the group (F, +, 0) as G.

Proposition 32. The number of size-n conjugacy classes of elements of K with trace 0 is equal to the number of aperiodic zero-sum n-necklaces.

Proof. Since Φ : F^{n} → K is a bijection, it preserves the size of any subset of F^{n}. Thus, the size of an n-necklace a as a set must be equal to the size of the conjugacy class Φ̂(a). In particular, the n-necklaces with size n as sets are bijectively mapped by Φ̂ to the size-n conjugacy classes. But the former necklaces are precisely the aperiodic n-necklaces. Thus, by restricting Φ̂ to these necklaces, we obtain a bijection from the aperiodic n-necklaces to the size-n conjugacy classes.

Restricting this bijection further to the zero-sum aperiodic n-necklaces, we obtain precisely the size-n conjugacy classes with trace 0 as their images because of Theorem 30.

By Theorem 16, the number of aperiodic zero-sum n-necklaces is \frac{|P_{n}|}{n}.

Corollary 33. There are |P_{n}| elements in K that belong to size-n conjugacy classes.

Proof. By Proposition 32, the number of size-n conjugacy classes in K is the number of aperiodic zero-sum n-necklaces; but this number is \frac{|P_{n}|}{n} by Theorem 16. Since these classes are disjoint and have size n each, they contain a total of \frac{|P_{n}|}{n} · n = |P_{n}| many elements.

9.4 The viewpoint of irreducible polynomials

Proposition 32 leads to an enumerative result about irreducible polynomials over F. To obtain it, we need a lemma that connects the trace of an element of K with its minimal polynomial:

Lemma 34. Let z ∈ K be an element whose minimal polynomial over F has degree n. Then the second-highest coefficient of this polynomial is − tr(z).

This is a special case where the minimal polynomial is degree n of [16, Corollary 5.45] or of [5, Section 14.2, Exercise 18 (d)].

Corollary 35. The number of monic irreducible polynomials of degree n over F with secondhighest coefficient equal to 0 is equal to the number of aperiodic zero-sum n-necklaces over F.

Proof. Starting from Proposition 32, we know that the number of aperiodic zero-sum nnecklaces over F is equal to the number of size-n conjugacy classes with trace 0.

Each monic irreducible polynomial f of degree n over F has n distinct zeroes in K (since F is a perfect field and K is its only degree-n extension up to isomorphism). These n zeroes form a conjugacy class, and f is their minimal polynomial.

Thus, we can define a map

σ : {monic irreducible polynomials of degree n over F }

→ {size-n conjugacy classes on K} that sends a polynomial to the conjugacy class consisting of its n zeroes in K. The inverse σ^{−1} of this map sends

{z_{1}, z_{2}, …, z_{n}} ↦ (x − z_{1})(x − z_{2}) ⋯ (x − z_{n}).

Thus σ is a bijection.

Via σ^{−1}, each size-n conjugacy class with trace 0 corresponds to a monic irreducible degree-n polynomial over F, and by Lemma 34 that polynomial must have second-highest coefficient 0. Thus the number of monic irreducible polynomials of degree n over F with second-highest coefficient equal to 0 is equal to the number of size-n conjugacy classes on K; but the latter number is in turn equal to the number of aperiodic zero-sum n-necklaces over F.

Combining Corollary 35 with the explicit formula in Theorem 16 for the number of aperiodic zero-sum n-necklaces over F, we obtain a formula for the number of monic irreducible polynomials of degree n over F with second-highest coefficient equal to 0; this recovers [25, Corollary 2.8].

10 Sequences

The numbers |G_{1}^{n}/C_{n}| computed in Theorem 5 give rise to several integer sequences, some of which are present in the OEIS (Online Encyclopedia of Integer Sequences, [19]). The simplest way to obtain a sequence is to fix the group G and to vary n.

Setting the group G to be the cyclic group C_{2}, and varying the length n of the necklaces being counted, we obtain the OEIS sequence \underline{A000013}, which counts the equivalence classes of n-bead binary necklaces with beads of 2 colors with respect to swapping all colors (the equivalence follows from Theorem 19):

|(C_{2})_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) gcd (2, \frac{n}{d}) 2^{d−1}.

See Table 1 for the first few values.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ |(C_{2})_{1}^{n}/C_{n}| & 1 & 2 & 2 & 4 & 4 & 8 & 10 & 20 & 30 \end{matrix}

Table 1: The numbers |(C_{2})_{1}^{n}/C_{n}| for n ≤ 9.

These numbers |(C_{2})_{1}^{n}/C_{n}| appear under the name of S (n − 1) in [22].

We can also vary n and G in lockstep. For instance, we can let G be the cyclic group C_{n} and count identity-product n-necklaces. This gives us the OEIS sequence \underline{A130293}, which counts the number of necklaces of n colors up to cyclic permutation (again by Theorem 19):

|(C_{n})_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) gcd (n, \frac{n}{d}) n^{d−1}

= \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) (\frac{n}{d}) n^{d−1} (since gcd (n, \frac{n}{d}) = \frac{n}{d})

= ∑_{d|n} ϕ (\frac{n}{d}) \frac{n^{d−1}}{d} .

See Table 2.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ |(C_{n})_{1}^{n}/C_{n}| & 1 & 2 & 5 & 20 & 129 & 1316 & 16813 & 262284 & 4783029 \end{matrix}

Table 2: The numbers |(C_{n})_{1}^{n}/C_{n}| for n ≤ 9.

Alternatively, letting G be the cyclic group C_{n+1} and again counting identity-product n-necklaces, we obtain the integer sequence \underline{A121774}. This counts the number of n-bead necklaces with n + 1 colors divided by n + 1:

|(C_{n+1})_{1}^{n}/C_{n}| = \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) \underbrace{gcd (n + 1, \frac{n}{d})}_{=1 (since n+1 is coprime to n)}(n + 1)^{d−1}

= \frac{1}{n} ∑_{d|n} ϕ (\frac{n}{d}) (n + 1)^{d−1}.

See Table 3.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ |(C_{n+1})_{1}^{n}/C_{n}| & 1 & 2 & 6 & 33 & 260 & 2812 & 37450 & 597965 & 11111134 \end{matrix}

Table 3: The numbers |(C_{n+1})_{1}^{n}/C_{n}| for n ≤ 9.

A similar simplified formula can be obtained for |G_{1}^{n}/C_{n}| whenever the size |G| of G is coprime to n; but the result (which equals the number of n-bead necklaces with |G| colors divided by |G|) can also be proved by a simple direct bijection, which we invite the reader to find.

11 Further directions

A variation on the set-up of the problem is to change the group acting on G_{1}^{n}. A natural candidate for this is the dihedral group D_{n}, since G_{1}^{n} is already closed under the reflection r defined by

r · (a_{1}, …, a_{n}) := (a_{n}^{−1}, …, a_{1}^{−1}).

Here, again, we can ask for the number of orbits, noticing that the analogous necklaces on non-group alphabets are known as bracelets and have been counted long ago [26]. When G is abelian, we can also have the symmetric group S_{n} (or a subgroup thereof) act on G_{1}^{n} by permuting the entries.^{1}

Generalizing in a different direction but in a similar vein, we can consider n-tuples of matrices whose product has a given trace:

Definition 36. Let R be a commutative ring. Consider n-tuples of m × m-matrices over R. We define the set of h-trace-product n-tuples ^{h}M_{m}^{n} to be

hM_{m}^{n} := {A = (A_{1}, A_{2}, …, A_{n}) : tr(A_{1}A_{2} ⋯ A_{n}) = h} .

Since tr(AB) = tr(BA), this set ^{h}M_{m}^{n} is a C_{n}-set and therefore we can attempt to count the number of orbits |^{h}M_{m}^{n}/C_{n}| when R is finite.

References

[1] Donald Adjeroh, Tim Bell, and Amar Mukherjee, The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching, Springer, 2008. https://

    doi.org/10.1007/978-0-387-78909-5.

[2] Daniel M. Baczkowski and Dursun A. Bulutoglu, Decimation classes of nonnegative integer vectors using multisets. Arxiv preprint, arXiv:2310.00403 [math.CO], 2023. Avail-

    able at https://arxiv.org/abs/2310.00403.

[3] E. A. Bender and J. R. Goldman, On the applications of Möbius inversion in combinatorial analysis, Amer. Math. Monthly 82 (1975), 789–803.

[4] Dieter Blessenohl, On the normal basis theorem, Note Mat. 27 (2007), 5–10.

[5] D. S. Dummit and R. M. Foote, Abstract Algebra, John Wiley and Sons, Inc., 3rd edition, 2003.

[6] N. J. Fine, Classes of periodic sequences, Illinois J. Math. 2 (1958), 285–302.

1Cf. also the notion of decimation classes considered in [23] and [2].

[7] Shuhong Gao, Normal Bases over Finite Fields, PhD thesis, University of Waterloo,

1993. Available at https://www.math.clemson.edu/~sgao/papers/thesis.pdf.

[8] Ira M. Gessel and Christophe Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory Ser. A 64 (1993), 189–215.

[9] E. N. Gilbert and John Riordan, Symmetry types of periodic sequences, Illinois J. Math. 5 (1961), 657–665.

[10] Solomon W. Golomb and Andy Liu, Solomon Golomb’s Course on Undergraduate Combinatorics, Springer, 2021.

[11] David Guichard, An introduction to combinatorics and graph theory, 2025-01-04. Avail-

able at https://www.whitman.edu/mathematics/cgt_online/cgt.pdf.

[12] Michiel Hazewinkel, Witt vectors. I. In Handbook of Algebra, Vol. 6, pp. 319–472.

Elsevier/North-Holland, 2009. https://doi.org/10.1016/S1570-7954(08)00207-6.

[13] Xiang-dong Hou, Lectures on Finite Fields, Vol. 190 of Graduate Studies in Mathematics, American Mathematical Society, 2018.

[14] Rudolf Lidl and Harald Niederreiter, Finite Fields, Vol. 20 of Encyclopedia of Mathematics and its Applications, Cambridge University Press, second edition, 1997.

[15] Nicholas A. Loehr, Combinatorics, Discrete Mathematics and its Applications, Chap-

man and Hall/CRC, second edition, 2017. https://doi.org/10.1201/9781315153360.

[16] J. S. Milne, Fields and Galois Theory, Kea Books, 2022. Version 5.10 available at

https://www.jmilne.org/math/CourseNotes/ft.html.

[17] C. Moreau, Sur les permutations circulaires distinctes, Nouv. Ann. 11 (1872), 309–314.

[18] Timothy Murphy, Finite fields, 2007. Available at https://www.maths.tcd.ie/pub/

Maths/Courseware/FiniteFields/GF.pdf.

[19] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2024. Published electronically at https://oeis.org.

[20] Christophe Reutenauer, Free Lie Algebras, Vol. 7 of London Mathematical Society Monographs, New Series, Oxford Science Publications, 1993.

[21] Victor Shoup, A Computational Introduction to Number Theory and Algebra, Cambridge University Press, 2005.

[22] N. J. A. Sloane, On single-deletion-correcting codes. In Codes and Designs, Vol. 10 of Ohio State Univ. Math. Res. Inst. Publ., pp. 273–291. De Gruyter, 2002. Newer version

at http://neilsloane.com/doc/dijen.pdf.

[23] Jonathan S. Turner, Dursun A. Bulutoglu, Daniel Baczkowski, and Andrew J. Geyer, Counting the decimation classes of binary vectors with relatively prime length and density, J. Algebraic Combin. 55 (2022), 61–87.

[24] Vince Vatter, A probabilistic proof of a lemma that is not Burnside’s, Amer. Math. Monthly 127 (2020), 63.

[25] Joseph L. Yucas, Irreducible polynomials over finite fields with prescribed trace/prescribed constant term, Finite Fields Appl. 12 (2006), 211–221.

[26] Yevhen Zelenyuk and Yuliya Zelenyuk, Counting symmetric bracelets, Bull. Aust. Math. Soc. 89 (2014), 431–436.

2020 Mathematics Subject Classification: Primary 05E18; Secondary 05A15, 11T06. Keywords: Finite group, necklace, enumerative combinatorics, counting, Euler totient function, Möbius function, orbit, group action, Pólya enumeration, Burnside lemma, finite field, irreducible polynomial, Galois field, Galois theory.

(Concerned with sequences \underline{A000013}, \underline{A081720}, \underline{A121774}, and \underline{A130293}.)

Received May 28 2024; revised version received December 23 2025. Published in Journal of Integer Sequences, August 3 2026.

Return to Journal of Integer Sequences home page.