Exercise 1.3.16 (Number of $m$-cycles in $S_n$)

Proof. Let $ℐ([[1,m]],[[1,n]])$ be the set of injections of $[[1,m]]$ to $[[1,n]]$, and ${𝒞}_m$ be the set of $m$-cycles in $S_n$.

As in the text (p. 29), an injective function $\tau :[[1,m]]\to [[1,n]]$ can send the number $1$ to any of the $n$ elements of $\{1,2,3,...,n\}$; $\tau (2)$ can then be any one of the elements of this set except $\tau (2)$ (so there are $n-1$ choices for $\tau (2)$); $\tau (3)$ can be any element except $\tau (1)$ or $\tau (2)$ (so there are $n-2$ choices for $\tau (3)$), and so on, up to the choice of $\tau (m)$ among $n-m+1$ elements, so there are $n(n-1)(n-2)\cdots (n-m+1)$ such injections.

We write $\left(\begin{array}{cccc}\hfill 1\hfill & \hfill 2\hfill & \hfill \cdots \hfill & \hfill m\hfill \\ \hfill a_1\hfill & \hfill a_2\hfill & \hfill \cdots \hfill & \hfill a_m\hfill \end{array}\right)$ the injection which sends $i\in [[1,m]]$ on $a_i$, where the $a_i$ are distinct.

Consider the map

which sends the injection $\{i\mapsto a_i\}$ on the cycle $(a_1{a}_2\dots a_m)$.

Every permutation $\sigma =(a_1{a}_2\dots a_m)\in {𝒞}_m$ is such that the $a_i$ are distinct, so $\sigma$ is the image by $\phi$ of the injection $\left(\begin{array}{cccc}\hfill 1\hfill & \hfill 2\hfill & \hfill \cdots \hfill & \hfill m\hfill \\ \hfill a_1\hfill & \hfill a_2\hfill & \hfill \cdots \hfill & \hfill a_m\hfill \end{array}\right)$. This shows that $\phi$ is surjective.

Moreover, since

every cycle $(a_1{a}_2\dots a_m)$ has $m$ preimages $\left(\begin{array}{cccc}\hfill 1\hfill & \hfill 2\hfill & \hfill \cdots \hfill & \hfill m\hfill \\ \hfill a_1\hfill & \hfill a_2\hfill & \hfill \cdots \hfill & \hfill a_m\hfill \end{array}\right),\cdots ,\left(\begin{array}{cccc}\hfill 1\hfill & \hfill 2\hfill & \hfill \cdots \hfill & \hfill m\hfill \\ \hfill a_m\hfill & \hfill a_1\hfill & \hfill \cdots \hfill & \hfill a_{m-1}\hfill \end{array}\right)$.

There is no other preimage: if $\tau =(a_1{a}_2\dots a_m)=(b_1{b}_2\dots b_m)$, then $\{a_1,a_2,\dots ,a_m\}=\{b_1,b_2,\dots ,b_m\}$, thus $b_1=a_i$ for some index $i$. Then $b_2=\tau (b_1)=\tau (a_i)=a_{i+1},b_3=\tau (b_2)=\tau (a_{i+1})=a_{i+2},\dots$ (the indices are taken modulo $m$) so $(b_1,b_2,\dots ,b_m)=(a_i,a_{i+1},\dots ,a_{i-1})$.

This shows that each permutation has exactly $m$ preimages: for every cycle $\sigma \in {𝒞}_m$,

By the so called “shepherd principle”, since

we obtain

so

The number of $m$-cycles in $S_n$ is given by

□