Orbits of Hamiltonian Paths and Cycles in Complete Graphs

Samuel Herman and Eirini Poimenidou Division of Natural Sciences New College of Florida Sarasota, FL 34243 USA

                samuel.herman18@ncf.edu
                  poimenidou@ncf.edu

Abstract

We enumerate certain geometric equivalence classes of subgraphs induced by Hamiltonian paths and cycles in complete graphs. These classes are orbits under the action of certain direct products of dihedral and cyclic groups on sets of strings representing subgraphs. The orbits are enumerated using Burnside’s lemma. The technique used also provides an alternative proof of the formulae found by Golomb and Welch, which give the number of distinct n-gons on fixed, regularly spaced vertices up to rotation and optionally reflection.

1 Introduction

All graphs are considered as their geometric realizations, which are defined as follows: if a graph G has n vertices, its geometric realization is the figure obtained by first associating its vertices with n regularly spaced points on a circle, then representing its edges as line segments between said points. For example, the geometric realizations associated with the complete graphs K_{n} for 3 ≤ n ≤ 6 are

Recall that a Hamiltonian path is a path in a graph which visits every vertex exactly once, and a Hamiltonian cycle is a Hamiltonian path which is a cycle. Any Hamiltonian path or cycle in a graph induces a subgraph whose vertex set is the same as the original graph, but whose edges consist of those traversed in the path or cycle; e.g.:

Our investigation begins with a natural observation regarding the shapes of subgraphs induced by Hamiltonian paths in complete graphs. Consider the set of subgraphs of K_{4} induced by Hamiltonian paths which have an endpoint at the top left vertex:

Notice that these subgraphs form one of just three distinct shapes—that is, any subgraph of K_{4} induced by a Hamiltonian path is obtainable as a rotation or reflection of one of the following three graphs:

The analogous observation in the case of K_{5} yields eight of these shapes:

Furthermore, the analogous observations regarding subgraphs induced by Hamiltonian cycles in K_{4} and K_{5} yield two and four of these shapes, respectively:

The natural inclination at this point is to ask whether there are formulae for enumerating these distinct shapes. Answering this question in the affirmative is the focus of this paper, and we begin by making its statement precise.

From now on, n denotes a natural number greater than or equal to 3.

Definition 1. Let P_{n} and C_{n} denote the sets of subgraphs of the complete graph K_{n} which are induced by Hamiltonian paths or cycles, respectively. Define two equivalence relations on P_{n} and C_{n} as follows.

1. Two subgraphs G_{1}, G_{2} are said to be equivalent, denoted by G_{1} ≡_{E} G_{2}, if they are obtainable from one another by a rotation.

2. Two subgraphs G_{1}, G_{2} are said to be similar, denoted by G_{1} ≡_{S} G_{2}, if they are obtainable from one another by a rotation or reflection.

Example 2.

.

This allows us to state our problem as one of enumerating the equivalence classes of either P_{n} or C_{n} under either ≡_{S} or ≡_{E}. That is, we seek the sizes of the sets

P_{n}/ ≡_{S}, P_{n}/ ≡_{E}, C_{n}/ ≡_{S}, and C_{n}/ ≡_{E} .

These are shown to be given by the formulae

|P_{n}/ ≡_{S} | = \frac{1}{4} ((n − 1)! + \begin{cases}(\frac{n}{2} + 1)(n − 2)!!, & if n is even; \\ (n − 1)!!, & if n is odd. \end{cases}) ,

|P_{n}/ ≡_{E} | = \frac{1}{2} ((n − 1)! + \begin{cases}(n − 2)!!, & if n is even; \\ 0, & if n is odd. \end{cases}) ,

|C_{n}/ ≡_{S} | = \frac{1}{4n^{2}} (∑_{d|n} ((φ (\frac{n}{d}))^{2} (\frac{n}{d})^{d} d!) + \begin{cases}n!!\frac{n(n+6)}{4}, & if n is even; \\ n^{2}(n − 1)!!, & if n is odd. \end{cases}) ,

|C_{n}/ ≡_{E} | = \frac{1}{2n^{2}} (∑_{d|n} ((φ (\frac{n}{d}))^{2} (\frac{n}{d})^{d} d!) + \begin{cases}\frac{n}{2}n!!, & if n is even; \\ 0, & if n is odd. \end{cases}) ,

in Theorems 7, 8, 9, and 10, respectively, where n!! denotes the product of n with every natural number less than n of the same parity as n, i.e.,

n!! = \begin{cases}n(n − 2) ⋯ (2), & if n is even; \\ n(n − 2) ⋯ (3)(1), & if n is odd. \end{cases}

Illustrations of P_{n}/ ≡_{S} and C_{n}/ ≡_{S} for 3 ≤ n ≤ 6 may be found in Figures 4 and 5, respectively; and Table 1 gives the size of each of these sets for 3 ≤ n ≤ 10.

\begin{matrix}n & |P_{n}/ ≡_{S} | & |P_{n}/ ≡_{E} | & |C_{n}/ ≡_{S} | & |C_{n}/ ≡_{E} | \\ 3 & 1 & 1 & 1 & 1 \\ 4 & 3 & 4 & 2 & 2 \\ 5 & 8 & 12 & 4 & 4 \\ 6 & 38 & 64 & 12 & 14 \\ 7 & 192 & 360 & 39 & 54 \\ 8 & 1320 & 2544 & 202 & 332 \\ 9 & 10176 & 20160 & 1219 & 2246 \\ 10 & 91296 & 181632 & 9468 & 18264 \end{matrix}

Table 1: Table of values for 3 ≤ n ≤ 10.

2 Setup

We obtain these answers by converting the original problem into one of enumerating the orbits of a specific group action. These orbits are enumerated by way of Burnside’s lemma, which is a standard tool in the theory of finite group actions.

Lemma 3 (Burnside’s lemma). Consider a group G acting on a set A. For each g ∈ G, let fix(g) denote the set of elements of A which are fixed by g, i.e.,

fix(g) = {a ∈ A | g · a = a }.

Let A/G denote the set of orbits of this action. The number of orbits under the action of G on A is given by

|A/G| = \frac{1}{|G|} ∑_{g∈G} |fix(g)|.

Definition 4. Fix a labelling of the vertices of K_{n} with the set n̄ = {0, 1, …, n − 1}, and let X_{n} denote the set of n-length strings which are permutations of the elements of n̄, i.e.,

X_{n} = {x_{0}x_{1} ⋯ x_{n−1} | x_{i} ∈ n̄ and i ≠ j ⇒ x_{i} ≠ x_{j}} .

Note that X_{n} has n! elements.

Each string in X_{n} is associated with an interpretation as a graph in either P_{n} or C_{n} as follows.

1. (X_{n} ⟶ P_{n}) Associate each string (x_{0}x_{1} ⋯ x_{n−1}) ∈ X_{n} with the subgraph of K_{n} induced by the Hamiltonian path which traverses the vertices of K_{n} in the order indicated by the string, i.e., the association is of the form

(x_{0}x_{1} ⋯ x_{n−1}) ⟼ ⟨x_{0} → x_{1} → ⋯ → x_{n−1}⟩.

Notice that both a string and its reversal are mapped to the same subgraph in P_{n}.

Figure 1: Interpretations of strings in X_{n} as graphs in P_{n}.

Figure 2: Interpretations of strings in X_{n} as graphs in C_{n}.

2. (X_{n} ⟶ C_{n}) Associate each string (x_{0}x_{1} ⋯ x_{n−1}) ∈ X_{n} with the subgraph of K_{n} induced by the Hamiltonian cycle which traverses the vertices of K_{n} in the order indicated by the string, i.e., the association is of the form

(x_{0}x_{1} ⋯ x_{n−1}) ⟼ ⟨x_{0} → x_{1} → ⋯ → x_{n−1} → x_{0}⟩.

Notice that all cyclic permutations of a string as well as each of their reversals are mapped to the same subgraph in C_{n}.

For each choice of P_{n} or C_{n} and ≡_{S} or ≡_{E} we define a group to act on X_{n} such that the orbits of this action coincide with the desired equivalence classes. This group is a direct product where the first coordinate acts purely on strings (i.e., an action of the first coordinate may only send strings to strings which have the same interpretation), while the second coordinate acts on a string’s interpretation as a graph.

Definition 5.

1. Define the following two groups which correspond to considering either P_{n} or C_{n}:

S(P, n) = ⟨v | v^{2} = 1⟩

and

S(C, n) = ⟨v, c | c^{n} = v^{2} = 1, vcv = c^{−1}⟩.

Note that S(P, n) is isomorphic to the cyclic group of order 2, and S(C, n) is isomorphic to the dihedral group of order 2n.

Figure 3: Geometric interpretation of the action of G(S, n) on strings in X_{n}.

2. Define the following two groups which correspond to considering either ≡_{S} or ≡_{E}:

G(≡_{S}, n) = ⟨r, s | r^{n} = s^{2} = 1, srs = r^{−1}⟩

and

G(≡_{E}, n) = ⟨r | r^{n} = 1⟩.

Note that G(S, n) is isomorphic to the dihedral group of order 2n, and G(E, n) is isomorphic to the cyclic group of order n.

3. Finally, given a choice of α = P_{n}, C_{n} and a choice of β =≡_{S}, ≡_{E}, the acting group with respect to these choices is given by

Γ(n, α, β) = S(α, n) × G(β, n).

For example, the acting group for P_{n} under ≡_{S} is

Γ(n, P, ≡_{S}) = S(P, n) × G(≡_{S}, n).

Definition 6. The elements of Γ(n, α, β) act on strings in X_{n} as follows:

(c, 1) · (x_{0}x_{1} ⋯ x_{n−1}) = (x_{1} ⋯ x_{n−1}x_{0}),
(v, 1) · (x_{0}x_{1} ⋯ x_{n−1}) = (x_{n−1} ⋯ x_{1}x_{0}),

and

(1, r) · (x_{0}x_{1} ⋯ x_{n−1}) = \overline{(x_{0} + 1)} \overline{(x_{1} + 1)} ⋯ \overline{(x_{n−1} + 1)},
(1, s) · (x_{0}x_{1} ⋯ x_{n−1}) = (−x_{0})(−x_{1}) ⋯ (−x_{n−1}),

where \overline{(x_{i} + 1)} denotes the sum (x_{i} + 1) taken modulo n, and (−x_{i}) denotes the (additive) inverse of x_{i} modulo n. The correct geometric interpretations of the actions of the second component are illustrated in Figure 3.

This action has the following important properties:

1. Two strings in X_{n} have the same interpretation as graphs in P_{n} or C_{n} if and only if they are contained in the same orbit under the action of S(P, n) or S(C, n) on X_{n}, respectively.

2. If two strings in X_{n} are contained in the same orbit under the action of G(≡_{S}, n) or G(≡_{E}, n), then their interpretations as graphs are similar or equivalent, respectively.

Considering these properties in the context of Burnside’s lemma yields the observation that the equivalence classes of P_{n} or C_{n} under ≡_{S} or ≡_{E} correspond bijectively to the orbits of X_{n} under the appropriate acting group. In particular, we have the following:

|P_{n}/ ≡_{S} | = |X_{n}/Γ(n, P, ≡_{S})| = \frac{1}{4n} ∑_{g∈Γ(n,P,≡_{S})} |fix(g)|,

|P_{n}/ ≡_{E} | = |X_{n}/Γ(n, P, ≡_{E})| = \frac{1}{2n} ∑_{g∈Γ(n,P,≡_{E})} |fix(g)|,

|C_{n}/ ≡_{S} | = |X_{n}/Γ(n, C, ≡_{S})| = \frac{1}{4n^{2}} ∑_{g∈Γ(n,C,≡_{S})} |fix(g)|,

|C_{n}/ ≡_{E} | = |X_{n}/Γ(n, C, ≡_{E})| = \frac{1}{2n^{2}} ∑_{g∈Γ(n,C,≡_{E})} |fix(g)|.

3 The path cases

We begin by considering the cases involving P_{n}. We first enumerate the equivalence classes of P_{n} under ≡_{S}, and the size of P_{n}/ ≡_{E} follows as corollary.

Theorem 7. Let n ≥ 3. The number of equivalence classes of P_{n} under ≡_{S} is given by

|P_{n}/ ≡_{S} | = \frac{1}{4} ((n − 1)! + \begin{cases}(\frac{n}{2} + 1)(n − 2)!!, & if n is even; \\ (n − 1)!!, & if n is odd. \end{cases})

Proof. Notice that each element of Γ(n, P, ≡_{S}) may be expressed in exactly one of the forms

(1, r^{k}), (1, sr^{k}), (v, r^{k}), (v, sr^{k})

for some integer 0 ≤ k ≤ n − 1. Considering this fact in the context of Burnside’s lemma yields the observation that

|X_{n}/Γ(n, P, ≡_{S})| = \frac{1}{4n}(A_{1} + A_{2} + A_{3} + A_{4}),

where

A_{1} = ∑_{k=0}^{n−1} |fix(1, r^{k})|, A_{2} = ∑_{k=0}^{n−1} |fix(1, sr^{k})|, A_{3} = ∑_{k=0}^{n−1} |fix(v, r^{k})|, A_{4} = ∑_{k=0}^{n−1} |fix(v, sr^{k})|.

1. Clearly (1, r^{k}) fixes (x_{0}x_{1} ⋯ x_{n−1}) only when k = 0. Hence A_{1} = |fix(1, 1)| = n!.

2. For each 0 ≤ k ≤ n − 1, if the action of (1, sr^{k}) fixes the string (x_{0}x_{1} ⋯ x_{n−1}), then we must have x_{i} ≡ −x_{i} − k (mod n) for all 0 ≤ i ≤ n − 1, and so 2x_{i} + k ≡ 0 (mod n). But since there is some x_{j} such that x_{j} = 0, it follows that k = 0 and so sr^{k} = s, which clearly fixes no strings. Thus A_{2} = 0.

3. Notice that (v, r^{k}) fixes (x_{0}x_{2} ⋯ x_{n−1}) if and only if x_{i} ≡ x_{−(i+1)} + k (mod n) and x_{−(i+1)} ≡ x_{i} + k (mod n) for all 0 ≤ i ≤ n − 1. This implies that x_{i} ≡ x_{i} + 2k (mod n) and thus that 2k ≡ 0 (mod n). Hence n must be even and, since (v, 1) clearly fixes no strings, we have k = n/2. Now, x_{i} ≡ x_{−(i+1)} + n/2 (mod n) implies that x_{i} − x_{−(i+1)} ≡ n/2 (mod n). Hence, for each of the (n/2)! bijections between the sets of compatible pairs of indices {i, −(i + 1)} and compatible pairs of labels {x_{i}, x_{−(i+1)}}:

P_{ind} = \{\{0, n − 1\} , \{1, n − 2\} , …, \{\frac{n}{2} − 1, \frac{n}{2}\}\}
↕
P_{lab} = \{\{0, \frac{n}{2}\} , \{1, \frac{n}{2} + 1\} , …, \{\frac{n}{2} − 1, n − 1\}\};

we obtain 2^{n/2} strings, for 2^{n/2} · (n/2)! = n!! fixed strings in total; that is, we have

A_{3} = \begin{cases}n!!, & if n is even; \\ 0, & if n is odd. \end{cases}

4. Notice that (v, sr^{k}) fixes (x_{0}x_{1} ⋯ x_{n−1}) if and only if x_{i} ≡ −(x_{−(i+1)} + k) (mod n) for all 0 ≤ i ≤ n − 1. First note that if k is even, then there is some entry x_{j} such that x_{j} ≡ −k/2 (mod n). Hence

x_{j} ≡ −k/2 ≡ −x_{−(j+1)} − k (mod n),

which implies that x_{j} ≡ x_{−(j+1)} (mod n), and thus that n must be odd. We must consider the following cases.

(a) If n is even and k is odd, then for each of n/2 possible values of k and each of the (n/2)! bijections between the sets of pairs of compatible indices and pairs of compatible labels:

P_{ind} = \{\{0, n − 1\} , \{1, n − 2\} , …, \{\frac{n}{2} − 1, \frac{n}{2}\}\}
↕
P_{lab}^{(k)} = \{\{n − \frac{k − 1}{2}, n − \frac{k + 1}{2}\} , …, \{n − 1, n − k + 1\}\};

we have 2^{n/2} fixed strings, for a total of (n/2)n!! fixed strings for this case.

(b) If n is odd and k is even, we have 2x_{\frac{n−1}{2}} ≡ −k (mod n), and thus x_{\frac{n−1}{2}} = n − \frac{k}{2}. Hence our set of pairs of compatible indices is a pairing of the set n̄ − \{\frac{n−1}{2}\}, and our set of pairs of compatible labels is a pairing of the set n̄ − \{n − \frac{k}{2}\}. So for each even value of k and each of the (\frac{n−1}{2})! bijections between

P_{ind} = \{\{0, n − 1\} , \{1, n − 2\} , …, \{\frac{n − 3}{2}, \frac{n + 1}{2}\}\}
↕
P_{lab}^{(k)} = \{ \{0, n − k\} , …, \{\frac{n − k − 1}{2}, \frac{n − k + 1}{2}\} , \{n − k + 1, n − 1\} ,

…, \{n − 1 − \frac{k}{2}, n + 1 − \frac{k}{2}\} \},

we have 2^{\frac{n−1}{2}} fixed strings, yielding (n − 1)!! fixed strings in total for this case.

(c) If n and k are both odd, as above we have 2x_{\frac{n−1}{2}} ≡ −k (mod n), and thus x_{\frac{n−1}{2}} = \frac{n−k}{2}. Hence our set of pairs of compatible indices is again a pairing of the set n̄ − \{\frac{n−1}{2}\}, and our set of pairs of compatible labels is a pairing of the set n̄ − \{\frac{n−k}{2}\}. So, as above, for each odd value of k and each of the (\frac{n−1}{2})! bijections between

P_{ind} = \{\{0, n − 1\} , \{1, n − 2\} , …, \{\frac{n − 3}{2}, \frac{n + 1}{2}\}\}
↕
P_{lab}^{(k)} = \{ \{0, n − k\} , …, \{\frac{n − k}{2} − 1, \frac{n − k}{2} + 1\} , \{n − k + 1, n − 1\} ,

…, \{n − \frac{k − 1}{2}, n − \frac{k + 1}{2}\} \},

we have 2^{\frac{n−1}{2}} fixed strings, again yielding (n − 1)!! fixed strings in total for this case. Hence over all n possible values of k we have a total of n(n − 1)!! fixed odd-length strings.

Thus we obtain

A_{4} = \begin{cases}(\frac{n}{2})n!!, & if n is even; \\ n(n − 1)!!, & if n is odd. \end{cases}

Having evaluated each of these sums, the desired theorem now follows.

Since Γ(n, P, ≡_{E}) is a subgroup of Γ(n, P, ≡_{S}), the number of equivalence classes of P_{n} under ≡_{E} follows as an easy corollary.

Theorem 8. Let n ≥ 3. The number of equivalence classes of P_{n} under ≡_{E} is given by

|P_{n}/ ≡_{E} | = \frac{1}{2} ((n − 1)! + \begin{cases}(n − 2)!!, & if n is even; \\ 0, & if n is odd. \end{cases})

4 The cycle cases

As before, we begin by enumerating C_{n}/ ≡_{S}, and the enumeration of C_{n}/ ≡_{E} follows as corollary.

Theorem 9. Let n ≥ 3. The number of equivalence classes of C_{n} under ≡_{S} is given by

|C_{n}/ ≡_{S} | = \frac{1}{4n^{2}} (∑_{d|n} ((φ (\frac{n}{d}))^{2} (\frac{n}{d})^{d} d!) + \begin{cases}n!!\frac{n(n+6)}{4}, & if n is even; \\ n^{2}(n − 1)!!, & if n is odd. \end{cases})

Proof. Notice that each element of Γ(n, C, ≡_{S}) may be expressed in exactly one of the forms

(c^{m}, r^{k}), (c^{m}, sr^{k}), (c^{m}v, r^{k}), (c^{m}v, sr^{k})

for some integers 0 ≤ k, m ≤ n − 1. Considering this fact in the context of Burnside’s lemma yields the observation that

|X_{n}/Γ(n, C, ≡_{S})| = \frac{1}{4n^{2}} (B_{1} + B_{2} + B_{3} + B_{4}),

where

B_{1} = ∑_{k,m=0}^{n−1} |fix(c^{m}, r^{k})|,  B_{2} = ∑_{k,m=0}^{n−1} |fix(c^{m}, sr^{k})|,

B_{3} = ∑_{k,m=0}^{n−1} |fix(c^{m}v, r^{k})|,  B_{4} = ∑_{k,m=0}^{n−1} |fix(c^{m}v, sr^{k})|.

As before, we proceed to evaluate each of these sums.

1. Notice that (c^{m}, r^{k}) fixes (x_{0}x_{1} … x_{n−1}) if and only if x_{i} ≡ x_{i+m} + k (mod n) for all 0 ≤ i ≤ n − 1, and so x_{i} ≡ x_{i+ℓm} + ℓk (mod n) for all 0 ≤ i ≤ n − 1 and all ℓ ≥ 0.

In particular, for ℓ = \frac{n}{gcd(n,m)}, we must have that n | ℓm and so x_{i} = x_{i+ℓm}. Hence x_{i} ≡ x_{i} + ℓk (mod n) and ℓk ≡ 0 (mod n); that is, n | ℓk and thus gcd(n, m) | k. Consequently, we have gcd(n, m) | gcd(n, k). Similarly, for ℓ = \frac{n}{gcd(n,k)}, we have n | ℓm, implying that gcd(n, k) | m and hence gcd(n, k) | gcd(n, m).

Figure 4: Representatives from each class of P_{n}/ ≡_{S} for 3 ≤ n ≤ 6. 11

Figure 5: Representatives from each class of C_{n}/ ≡_{S} for 3 ≤ n ≤ 6.

We conclude that gcd(n, k) = gcd(n, m) = d for some divisor d of n, and therefore

∑_{0≤k,m<n} |fix(c^{m}, r^{k})| = ∑_{d|n} ∑_{\begin{matrix}gcd(k,n)=d \\ gcd(m,n)=d \end{matrix}} |fix(c^{m}, r^{k})|.  (1)

Now, fix some particular k, m, d with d = gcd(n, k) = gcd(n, m). We seek to determine the size of fix(c^{m}, r^{k}). Both of r^{k} and c^{m} have order n/d, and hence, if (c^{m}, r^{k}) fixes (x_{0}x_{1} … x_{n−1}), then

x_{i} ≡ x_{i+ℓm} + ℓk (mod n) for all 0 ≤ i ≤ n − 1 and 0 ≤ ℓ ≤ \frac{n}{d} − 1.

Hence, each choice of label x_{i} determines the labels of all positions of the form x_{i+ℓm} for 0 ≤ ℓ ≤ \frac{n}{d} − 1. Note that, for t ∈ {0, 1, …, n − 1} with gcd(t, n) = d and α ∈ {0, …, d − 1}, the elements of the set

F_{α}^{(t)} = \{α + ℓt | 0 ≤ ℓ ≤ \frac{n}{d} − 1\}

are all congruent to α modulo d yet are all distinct modulo n [3]. Setting t = k, m, we see that the set {0, 1, …, n − 1} may be partitioned in two different ways via Π_{m} and Π_{k}, where

Π_{m} = \{\{0, m, …, (\frac{n}{d} − 1) m\} , …, \{d − 1, d − 1 + m, …, 1 + d − (\frac{n}{d} − 1) m\}\} ,

and

Π_{k} = \{\{0, k, …, (\frac{n}{d} − 1) k\} , …, \{d − 1, d − 1 + k, …, 1 + d − (\frac{n}{d} − 1) k\}\} .

Consequently, the label of x_{i} determines all labels with indices in the set F_{i}^{(m)} such that all such labels are contained within a unique F_{α}^{(k)}. In fact, we see that the labels of the initial substring (x_{0}x_{1} … x_{d−1}) completely determine the labelling of the rest of the string. Hence, for each of the d! bijections between Π_{m} and Π_{k}, each of the (n/d)^{d} possible sets of choices of labelling i ↦ x_{i} ∈ F_{i}^{(k)} determines a unique fixed string. That is, for each particular valid k, m, d, we have

|fix(c^{m}, r^{k})| = (\frac{n}{d})^{d} d!.

Combining this with (1), we obtain

B_{1} = ∑_{k,m=1}^{n−1}|fix(c^{m}, r^{k})| = ∑_{d|n} ∑_{\begin{matrix}gcd(k,n)=d \\ gcd(m,n)=d \end{matrix}} |fix(c^{m}, r^{k}),

= ∑_{d|n} (\frac{n}{d})^{d} d! ∑_{gcd(k,n)=d} ∑_{gcd(m,n)=d} 1,

= ∑_{d|n} (φ (\frac{n}{d}) · φ (\frac{n}{d}) · (\frac{n}{d})^{d} · d!) ,

where φ denotes Euler’s totient function.

2. Notice that (c^{m}, sr^{k}) fixes (x_{0}x_{1} … x_{n−1}) if and only if −x_{i+m} − k ≡ x_{i} (mod n) for all 0 ≤ i ≤ n − 1. Thus we have x_{i+m} + x_{i} ≡ −k (mod n), and so x_{i+2m} + x_{i+m} ≡ −k (mod n), which implies that x_{i} ≡ x_{i+m} (mod n) for all 0 ≤ i ≤ n − 1, and hence m = 0 or m = n/2. But if m = 0, then from the evaluation of A_{2} above, no strings are fixed, and so we must have m = n/2 and n must be even. Hence we have that x_{i} + x_{i+ \frac{n}{2}} ≡ −k (mod n). Note that k cannot be even, since, as n is even, −k would also be even, and so we would have x_{i} = −k/2 = x_{i+ \frac{n}{2}} , which cannot be the case since c^{\frac{n}{2}} fixes no points. Thus k must be odd, and so for all n/2 odd choices of k we have (n/2)! bijections

P_{ind} = \{\{0, \frac{n}{2}\} , \{1, \frac{n}{2} + 1\} , …, \{\frac{n}{2} − 2, n − 2\} , \{\frac{n}{2} − 1, n − 1\}\}
↕
P_{lab}^{(k)} = \{\{0, −k\} , \{1, −(k + 1)\} , …, \{\frac{k − 1}{2}, \frac{k + 1}{2}\}\} ,

each of which affords 2^{(n/2)} fixed strings. Therefore we obtain

B_{2} = \begin{cases}\frac{n}{2}n!!, & if n is even; \\ 0, & if n is odd. \end{cases}

3. Notice that (c^{m}v, r^{k}) fixes (x_{0}x_{1} … x_{n−1}) if and only if x_{−(i+1)+m} + k ≡ x_{i} (mod n) for all 0 ≤ i ≤ n − 1, which is the case if and only if x_{−(i+1)} + k ≡ x_{i−m} (mod n) for all x_{i}. There are three cases.

(a) If n is odd, then for all values of m there exists a unique 0 ≤ a ≤ n − 1 such that −(a + 1) ≡ a − m (mod n), and hence x_{−(a+1)} = x_{a−m} and consequently k = 0. But, since all other entries of the string are moved, it follows that no odd-length strings are fixed by (c^{m}v, r^{k}).

(b) If n is even and m is odd, then there exist exactly two indices 0 ≤ a, b ≤ n − 1 such that −(a + 1) ≡ a − m (mod n) and −(b + 1) ≡ b − m (mod n), and hence x_{−(a+1)} = x_{a−m} and x_{−(b+1)} = x_{b−m}. Then, just as above, we have k = 0 and thus no strings are fixed.

(c) If both n and m are even, then, since there must be some x_{i} = 0, each of n/2 choices of m fully determines the value of k. Hence, in the same manner as before, for each m we consider the (n/2)! bijections between

P_{ind}^{(m)} = \{\{0, n − 1 + m\} , \{1, n − 2 + m\} , …, \{\frac{n}{2} − 1, \frac{n}{2} + m\}\}
↕
P_{lab}^{(m)} = \{\{0, −k\} , \{1, 1 − k\} , …, \{\frac{n}{2} − 1, \frac{n}{2} − 1 − k\}\};

each of which, as before, yields 2^{\frac{n}{2}} fixed strings, for a total of n!! fixed strings for each value of m.

Hence we obtain

B_{3} = \begin{cases}\frac{n}{2}n!!, & if n is even; \\ 0, & if n is odd. \end{cases}

4. Notice that (c^{m}v, sr^{k}) fixes (x_{0}x_{1} … x_{n−1}) if and only if −(x_{−(i+1)+m} +k) ≡ x_{i} (mod n) for all 0 ≤ i ≤ n − 1. There are three cases.

(a) If n is odd, then it is tedious but not difficult to see that an analogous argument to the evaluation of A_{4} in the proof of Theorem 7 applies for all n values of m, yielding a total of n^{2}(n − 1)!! fixed strings.

(b) If n, m are both even, then it is again not difficult to see that an analogous argument to the evaluation of A_{4} in the proof of Theorem 7 applies for all n/2 even values of m. That is, each even choice of m allows for n/2 odd values of k, each of which affords n!! fixed strings.

(c) If n is even and m is odd, then there are exactly two indices 0 ≤ a, b ≤ n − 1 such that 2a ≡ 2b ≡ m + 1 (mod n). It follows that m − a − 1 ≡ a (mod n) and m − b − 1 ≡ b (mod n), and so −x_{a} − k ≡ x_{a} (mod n) and −x_{b} − k ≡ x_{b} (mod n). Hence 2x_{a} ≡ 2x_{b} ≡ −k (mod n), and so k must be even. Now, for particular values of m, a, b, there are n/2 possible even values of k. Each choice of k fixes the values of {x_{a}, x_{b}}, which may be ordered in two ways; and, by the same methods as before, both choices of ordering afford (n−2)!! fixed strings. Hence, in this case we have (n/2) · (n/2) · 2 · (n − 2)!! = (n/2)n!! fixed strings in total.

Thus we obtain

B_{4} = \begin{cases}(\frac{n}{2} + 1)\frac{n}{2}n!!, & if n is even; \\ n^{2}(n − 1)!!, & if n is odd. \end{cases}

Having evaluated each of these sums, the desired theorem now follows.

As before, since Γ(n, C, ≡_{E}) is a subgroup of Γ(n, C, ≡_{S}), the number of equivalence classes of C_{n} under ≡_{E} follows as an easy corollary.

Theorem 10. Let n ≥ 3. The number of equivalence classes of C_{n} under ≡_{E} is given by

|C_{n}/ ≡_{E} | = \frac{1}{2n^{2}} (∑_{d|n} ((φ (\frac{n}{d}))^{2} (\frac{n}{d})^{d} d!) + \begin{cases}\frac{n}{2}n!!, & if n is even; \\ 0, & if n is odd. \end{cases})

Finally, it is worth noting a small corollary to the above theorems. Since φ(p) = (p − 1) for any prime p, we have the following.

Corollary 11. Let p be an odd prime. Then

|C_{p}/ ≡_{S} | = \frac{1}{4p} ((p − 1)^{2} + p(p − 1)!! + (p − 1)!) ,

and

|C_{p}/ ≡_{E} | = \frac{1}{2p} ((p − 1)^{2} + (p − 1)!) .

5 Further remarks

Here we note some interesting connections which the authors noticed over the course of writing this paper. After completing the enumeration of P_{n}/ ≡_{S}, we discovered that there are exactly as many of them as there are tone rows in n-tone music—the enumeration of which may be found in a paper of Reiner [2]. The corresponding sequence in the On-Line Encylopedia of Integer Sequences (OEIS) is \underline{A099030}—which, as has been noted, is identical to the sequence \underline{A089066}. The number of equivalence classes of P_{n} under ≡_{E} is the given by the sequence \underline{A275527}.

Further, for reasons which should be clear, there are exactly as many classes in C_{n}/ ≡_{S} as there are classes of similar n-gons (that is, classes of n-gons which are equivalent up to rotations and reflections). These classes—as well as the analogous case of n-gons equivalent up to rotations only—were enumerated in a 1960 paper of Golomb and Welch [1]. As such, this paper provides an alternative proof of their result. The corresponding OEIS sequences are \underline{A000940} and \underline{A000939}, respectively. It should also be noted that the evaluation of B_{1} in the proof of Theorem 9 is in large part an adaptation of an argument of Moser [3]. In particular, the sum of Euler φ terms which makes an appearance in this paper as well as in the paper of Golomb and Welch [1] is the same as that which appears in the case of a = 1 in Moser’s paper [3]. This connection is (as far as the authors are aware) not yet noted anywhere.

6 Acknowledgments

The authors would like to thank Chris Kottke for providing valuable feedback on several early versions this paper. We would also like to thank the anonymous reviewer for his or her constructive suggestions, many of which were incorporated into this final version. Finally, the first author would like to thank Nika Sigua for his role in the initial discovery of the problems discussed in this paper.

References

[1] S. W. Golomb and L. R. Welch, On the enumeration of polygons, Amer. Math. Monthly 67 (1960), 349–353.

[2] D. L. Reiner, Enumeration in music theory, Amer. Math. Monthly 92 (1985), 51–54.

[3] W. O. J. Moser, A (modest) generalization of the theorems of Wilson and Fermat, Canad. Math. Bull. 33 (1990), 253–256.

2010 Mathematics Subject Classification: Primary 05C30; Secondary 05E18. Keywords: Hamiltonian path, group action, Burnside’s lemma.

(Concerned with sequences \underline{A000939}, \underline{A000940}, \underline{A089066}, \underline{A099030}, and \underline{A275527}.)

Received May 17 2019; revised versions received January 8 2020; March 28 2020. Published in Journal of Integer Sequences, June 27 2020.

Return to Journal of Integer Sequences home page.