Let \(S_{n}\) be the group of permutations on \(n\) objects (under cycle composition). It is well known that finding the total number of subgroups of \(S_{n}\) is difficult and computationally complex; so instead, we outline here an approach to finding the total number of cyclic subgroups of \(S_{n}\), a much easier problem. The general idea is to exploit facts about the cycle structures of the generators of these cyclic subgroups, characterizing them by conjugacy class, and enumerating over said conjugacy classes.
Before demonstrating the main work that drives the result, we must introduce a preliminary first theorem. To do so, we need the following two definitions:
Definition 1. A cycle structure of a permutation \(\sigma \in S_{n}\) is a multiset of lengths \((l_{1}, {l_2}, ..., {l_m})\) of the constituent disjoint cycles in \(\sigma\).
Definition 2. Group elements \(\sigma, \tau \in G\) are conjugate iff there exists \(x \in G\) such that
\[ \tau = x \sigma x^{-1} \]
With these two definitions, we can proceed to the first theorem\(^{[1]}\):
Theorem 1. Permutations \(\sigma, \tau \in S_{n}\) are conjugate iff they share the same cycle structure.
Critically, this does not hold for proper subgroups of \(S_{n}\). We can prove that “if \(\sigma, \tau \in S_{n}\) are conjugate, then they share the same cycle structure” will hold for all proper subgroups of \(S_{n}\), but not the other way around. This is what prevents the upcoming counting formula from being generalizable to dihedral groups or alternating groups. An example of this is \((1 \space 2 \space 3)\) and \((1 \space 3 \space 2)\) in \(A_{3}\); these cycles share the same cycle structure, but they are not conjugate in \(A_{3}\), which can be verified by showing that the above definition of conjugacy does not hold for any \(x \in A_{3}\).
Theorem 1 is necessary for the proof of Theorem 2, the primary portion of the counting argument. The general idea is that conjugacy “splits” the permutations by their inherent structure (the cycle structure). Many permutations are, in essence, just “relabelings” of each other.
Example. Consider \((1 \space 2 \space 3)(4 \space 5), (2 \space 3 \space 5)(4 \space 6) \in S_{6}\). We know that these are conjugate by Theorem 1. And indeed, through \((1 \space 6 \space 5)\), we have
\[ (1 \space 6 \space 5) * (2 \space 3 \space 5)(4 \space 6) * (1 \space 6 \space 5)^{-1} = (1 \space 6 \space 5) * (1 \space 2 \space 3 \space 5 \space 4 \space 6) = (1 \space 2 \space 3)(4 \space 5). \]
The above two permutations are almost identical in nature, each a composition of a 3-cycle and a 2-cycle. The only major difference was the specific numbers in the cycles.
Let \(\langle \sigma \rangle\) be the cyclic subgroup of \(S_{n}\) generated by \(\sigma\).
Theorem 2. Let \(\sigma, \tau \in S_{n}\). If \(\langle \sigma \rangle = \langle \tau \rangle\), then \(\sigma, \tau\) are conjugate.
Proof. Let \(\langle \sigma \rangle = \langle \tau \rangle\). Then there exists \(k \in \mathbb{N}\) such that \(\sigma^{k} = \tau\), with \(k, |\sigma|\) (the order of the cyclic group generated by \(\sigma\)) being relatively prime. Write \(\sigma\) as a product of \(m\) disjoint cycles
\[ \sigma = \prod\limits^{m}_{h = 1}{c_{h}}. \]
If \(L\) is the cycle structure of \(\sigma\), then it is known that \(|\sigma| = \text{lcm}\Big(\Big\{l_{h} | l_{h} \in L\Big\}\Big)\). As \(k, |\sigma|\) are relatively prime, it follows that \(k, l_{h}\) are relatively prime for each \(l_{h} \in L\), as they necessarily share no prime factors. Now, take
\[ \sigma^{k} = \Big(\prod\limits^{m}_{h = 1}{c_{h}}\Big)^{k} = \prod\limits^{m}_{h = 1}{c_{h}^{k}}. \]
For each \(c_{h}^{k}\) in \(\sigma^{k}\), as \(l_{h}, k\) are relatively prime, \(|c_{h}^k| = |c_{h}|\). And so, \(\sigma, \sigma^{k}\) share the same cycle structure; by Theorem 1 we have that \(\sigma, \tau\) are conjugate in \(S_{n}\).
Corollary. All generators of a given cyclic subgroup in \(S_{n}\) are conjugate (belong to the same conjugacy class).
The first part of the corollary above follows immediately from Theorem 2 when comparing any two arbitrary generators of the same cyclic group. It is also well-known that a cyclic group has \(\phi(|\sigma|)\) generators, where \(\phi\) is Euler’s totient function.
The corollary, as well as the totient function, now allow us to count the number of cyclic subgroups of \(S_{n}\) generated by elements in a given conjugacy class of \(S_{n}\), provided that we know how many elements are actually in said conjugacy class.
First, we will identify a fact that is useful for computation.
Note. There exists a one-to-one relationship between conjugacy classes of \(S_{n}\) and integer partitions of \(n\).
This is clearly true since conjugacy classes in \(S_{n}\) are uniquely determined by the cycle structures of the elements in the class (as established earlier); as there are as many distinct cycle structures within \(S_{n}\) as there are ways to partition the \(n\) objects, we have our relationship.
Let \(I\) be an arbitrary integer partition of \(n\). Then, as our counting strategy depends upon the sizes of conjugacy classes of \(S_{n}\), we will use the following known formula\(^{[2]}\) for the size of the conjugacy class \(C\) corresponding to \(I\):
\[ |C| = \large\frac{n!}{\prod_{i \in I}{k_{i}!i^{k_{i}}}} \]
with \(k_{i}\) being the multiplicity of \(i\).
The intuition behind this formula is as follows: List out the “cycle parentheses” without any numbers in them, in descending order of length. Start dropping numbers into the parentheses in any of the \(n!\) unique orderings of the numbers that we have. For each cycle length, we divide out by the length of the cycle (since it doesn’t matter which of the numbers in the cycle we start with). Thus, we are dividing by \(i\) a total of \(k_{i}\) times, once for each cycle of length \(i\). Then we divide out by \(k_{i}!\), the number of orderings of the cycles of a given length \(i\), since this also doesn’t matter (as the cycles are all disjoint).
For each cyclic subgroup \(\langle \sigma \rangle\) of \(S_{n}\), that cyclic subgroup will have \(\phi(|\sigma|)\) generators, all belonging to the same conjugacy class. Thus, the number of unique cyclic subgroups generated by a given conjugacy class will be \(\frac{|C|}{\phi(|\sigma|)}\) for any \(\sigma\) in \(C\).
Now, let \(P(n)\) be the set of integer partitions of \(n\). Summing across integer partitions of \(n\) (and therefore conjugacy classes of \(S_{n}\)), we finally obtain
\[ \text{s}(n) = \large\sum\limits_{\normalsize I \in P(n)}{\large\frac{n!}{\Big(\prod_{i \in I}{k_{i}!i^{k_{i}}}\Big) \phi\Big(\text{lcm}(I)\Big)}} \]
with \(\text{s}(n)\) as the total number of cyclic subgroups of \(S_{n}\).
Consider \(S_{4}\), the permutation group on 4 objects. Direct enumeration yields that there are 17 cyclic subgroups of \(S_{4}\). However, we can also find this result using the found formula. First, we will list out each integer partition of 4:
\[ (4) \] \[ (3, 1) \] \[ (2, 2) \] \[ (2, 1, 1) \] \[ (1, 1, 1, 1) \]
For each integer partition \(I\), calculate
\[ \large\frac{4!}{\Big(\prod_{i \in I}{k_{i}!i^{k_{i}}}\Big)\phi\Big(\text{lcm}(I)\Big)} \]
where \(k_{i}\) is the multiplicity of \(i \in I\). Summing across partitions, we get
\[ \frac{24}{(1!4^1)2} + \frac{24}{(1!3^1)(1!1^1)2} + \frac{24}{(2!2^2)1} + \frac{24}{(1!2^1)(2!1^2)1} + \frac{24}{(4!1^4)1} = 3 + 4 + 3 + 6 + 1 = 17 \]
which verifies the formula for \(S_{4}\). A list of computed values of the formula can be found in Appendix B.
An R program written for computation of the counting formula for \(S_{n}\).
# Disallow scientific notation
options(scipen=999)
# Library for integer partitions, gcd, lcm
library(partitions)
library(numbers)
s <- function(n) {
# Make integer partitions of n
partitions <- parts(n)
# Loop through partitions and find sums
total <- 0
for (t in 1:ncol(partitions)) {
# Current integer partition
I <- partitions[, t]
# Info about partitions
uniqs <- rev(unique(I[I > 0]))
mults <- as.numeric(table(I[I > 0]))
# Total addition
if (length(uniqs) >= 2) {
cont <- factorial(n)/(prod(factorial(mults) * (uniqs ** mults)) * eulersPhi(mLCM(uniqs)))
}
else {
cont <- factorial(n)/(prod(factorial(mults) * (uniqs ** mults)) * eulersPhi(uniqs))
}
total <- total + cont
}
return(total)
}A list of computed values for \(S_{n}\) with \(n \le 40\):
- “Conjugate Permutations Have Same Cycle Type - ProofWiki.” Proofwiki.org, 2025, proofwiki.org/wiki/Conjugate_Permutations_have_Same_Cycle_Type. Accessed 8 May 2026.
- Dummit, David Steve, and Richard M Foote. Abstract Algebra. 3rd ed., Danvers, John Wiley & Sons, 2004.