If $n\ge m$, then the number of $m$-cycles in $S_n$ is given by $\frac{n(n-1)(n-2)\cdots(n-m+1)}{m}$.

Question

Show that if $n\ge m$, then the number of $m$-cycles in $S_n$ is given by

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

My doubt

Suppose I wish to count the number of $m$-cycles. Then I will get $\binom n m$ ways of choosing such cycles. And the cycles which have the same representation must be divided so I will get $$\frac{\binom n m}{m}.$$

What am I doing wrong? Kindly help me.

Answer 1

Suppose we want to count the number of $3$-cycles in $S_5$. We start by choosing any $3$-element subset of $\{1,2,3,4,5\}$, say $\{1,3,4\}$. This doesn't uniquely determine a cycle though, since we could have:

• $(1,3,4) = (3,4,1) = (4,1,3)$
• $(1,4,3) = (4,3,1) = (3,1,4)$

---

To prevent overcounting due to cyclic permutations, we make the convention that the smallest number of the $m$-element subset of $\{1,2,\ldots,n\}$ must come first in the cycle. This leaves us with $m - 1$ elements that can be permuted in any order, each of which will produce a distinct cycle. So we obtain: \begin{align*} \binom{n}{m} \cdot (m - 1)! &= \frac{n!}{m!(n - m)!} \cdot (m - 1)! \\ &= \frac{n(n - 1)\cdots(n - m + 1)(n - m)!}{(n - m)!} \cdot \frac{(m - 1)!}{m(m - 1)!} \\ &= \frac{n(n - 1)\cdots(n - m + 1)}{m} \\ \end{align*}

Answer 2

Hint: There are more than $\binom{n}{m}$ ways of choosing such cycles. Using $\binom{n}{m}$ implies that order is unimportant in choosing the elements of a cycle, which is not the case. Instead, you want to count the number of cycles by saying: there are $n$ possibilities for the first element, $n-1$ for the second, and so forth. Then you can divide by $m$ to remove the multiple representations for a given cycle.

Answer 3

If we use permutation notation, we have $\frac{P(n,m)}{m}$ for the number of $m$-cycles in $S_n$. Also, I think the formula is valid for $n=m$, so the question should be edited to "if $n\ge m $".