Number of conjugates of an $m$-cycle $\sigma$ in $S_n$

Question

I am currently reading the following from Dummit and Foote can someone explain to me why the number of conjugates of $\sigma$ is:

$$\frac{n(n\ -\ 1)...(n\ -\ m\ + \ 1)}{m}\ ?$$

Answer 1

Denote $$ \sigma=(a_{1}a_{2}\ldots a_{m}) $$ There is a theorem that states that for every $\tau\in S_{n}$ $$ \tau^{-1}\sigma\tau=(\tau(a_{1}),\tau(a_{2}),\ldots,\tau(a_{m})) $$

thus, given any $m$ elements of $\{1,...,n\}$ there is some $\tau$ s.t $\tau^{-1}\sigma\tau$ will result in a cycle of those exactly $m$ elements.

For the above formula recall two things:

1. $\binom{n}{m}$ is the number of ways choosing $m$ elements from a set of $n$ elements

2. Any cyclic shift of the $m$ elements results in the same cycle e.g $(123)=(231)=(312)$ so to cancel those repetitions we need to divide by $m$ which is the number of such cyclic shifts

Answer 2

A permutation is conjugate if it has the same cycle structure. In this case you want to find the no. conjugates of a m cycle, so your question boils down to find the no. of m cycles in Sn. Which can be done by n(n-1)(n-2)...(n-m+1)/m ways as for first entry you have n options, for next entry you have (n-1) options and finally you divide n(n-1)...(n-m+1) by m as each m cycle can be represented in m ways.

Answer 3

Two permutations in $S_{n}$ are conjugate if and only if they have the same cycle type, so really the question is how many $m$-cycles there are in $S_{n}$. Well, choose your $m$ elements from $n$ in $n\choose{m}$ ways. But we can rearrange those $m$ elements in $m!$ ways. Finally, each of our cycles has been represented $m$ times by a cyclic rearrangement, so we divide by $m$. So our final count is $$\frac{n!}{(n-m)!m}$$ as required.