What are the elements of order $2$ of the symmetric group $S_n$?
I've tried listing some of the sets for small $n$ to get a better understanding but I'm really not sure:
$S_1$ has only one element and that's order $1$. $S_2$ has elements $\begin{pmatrix}1&2\\1&2\end{pmatrix}$ and $\begin{pmatrix}1&2\\2&1\end{pmatrix}$ ; the first of these is order $1$ and the second is order $2$.
I don't know how to proceed though.
On
The elements of $S_n$ of order $2$ are those permutations $\varphi$ such that $\varphi(\varphi(x)) = x$ for all $x$.
One way for this to happen is to have $\varphi(x) = x$, however if we have $\varphi(x) = y$ with $y\neq x$ then we must have $\varphi(y)=x$.
What this means is that our function $\varphi$ will split the numbers $\{1,2,\dots,n\}$ into two different numbers. We first have the set $F$ of numbers that are fixed by $\varphi$. We also have the set of numbers $M$ that are moved by $\varphi$, and these numbers get split into pairs of numbers, such that for each pair $\{a,b\}$ we have $\varphi(a)=b$ and $\varphi(b)=a$.
The problem is that this description is a bit confusing haha, and especially when looking at your way of representing permutations it can be a bit confusing.
However if you look at the "disjoint cycle representation" you just need all the cycles to have size $2$.
Also, permutations of order $2$ are called involutions, so perhaps you can find more stuff by searching that.
Hint: any permutation is a a product of disjoint cycles. If $\sigma_1, \sigma_2, \ldots, \sigma_k$ are disjoint cycles, the order of $\sigma= \sigma_1\sigma_2\cdots\sigma_k$ is the least common multiple of the orders of the $\sigma_i$. So what can you say about the orders of the $\sigma_i$ if the order of $\sigma$ is $2$?