Find number of functions such that $f(f(a))=a$ Let X ={1, 2, 3, 4}. Find the number of functions $f : X \rightarrow X$ satisfying $f(f(a)) = a$ for all $1 \le a \le 4$.
I took the $f(x) =x$ and, then there are 1 possibilities. But answer is given as 10. How is it 10?
 A: Here are a couple more possibilities.  See if you can figure out the remaining.
$1\to 2, 2\to 1, 3\to 3, 4\to 4$
and
$1\to 2, 2\to 1, 3\to 4, 4\to 3$
A: HINT: If $f(x)=x$, then of course we’ll have $f(f(x))=x$ as well, but there’s another possibility: if $f(x)=y$ and $f(y)=x$, then $f(f(x))=f(y)=x$ and $f(f(y))=f(x)=y$, so both $x$ and $y$ behave correctly. These are the only possibilities, however. Let’s give each such function a code describing which elements of $X$ it leaves fixed and which elements it swaps: if $f(x)=x$, we’ll write $(x)$, and if $f(x)=y\ne x$ and $f(y)=x$, we’ll write $(xy)$. The code for the identity function is therefore $(1)(2)(3)(4)$. The code for the function that sends $1$ to itself, $2$ to $3$, $3$ to $2$ and $4$ to itself is $(1)(23)(4)$.
Now the question becomes: How many such codes are there?


*

*We can have $0$ swaps; that’s $(1)(2)(3)(4)$, the identity function.  

*We can have $1$ swap and two fixed points, like $(1)(23)(4)$; how many of those are there?  

*We can have $2$ swaps, like $(13)(24)$; how many of those are there?

