Let $A = \{1,2,3,4\}$. Number of functions $f :A \to A$, such that $f(f(x))=x~\forall x \in A$ , is. Let $A = \{1,2,3,4\}$. Number of functions $f :A \to A$, such that $f(f(x))=x,  \forall x \in A$ , is.


For this , what I thought was 2 cases are possible. Either an element maps to itself or 2 elements map to each other.

Eg either $1 \to 1$ or $1 \to 2$ and $2 \to 1.$

So for this I can group the elements in groups of 2 in $^4C_2 $ways. Then say I group $(a,b)$ and$ (c,d)$ . Then $ a$ can either map to $a$ or $b$. The other element from that group will automatically be defined. Similarly for $(c,d)$

So the answer should be $^4C_2× 2×2 = 24$ . But the answer is


  $13$


Please help.
Case 1: There are 4 fixed points. The only such involution is the identity.

Case 2: There are 2 fixed points. In this case, once 2 elements are fixed, the remaining 2 elements must map to each other. Hence, the number of involutions with 2 fixed points is $\binom{4}{2} = 6$.

Case 3: The involution is a derangement (fixed-point-free). In this case, the number 1 must map to 2, 3, or 4, and whatever 1 maps to must be mapped to 1. Then, the remaining 2 elements must map to each other. Hence, the number of involutions without any fixed points is 3.

In total, there are 10 involutions on a 4-element set like $A = \{1, 2, 3, 4\}$.
There are 3 cases:


each element is mapped onto itself $x\to x$
The pair $(a,b)$ is mapped onto $(b,a)$ and the pair $(c,d)$ is mapped on $(d,c)$. There are 6 ways you can choose $(a,b)$
The pair $(a,b)$ is mapped onto $(b,a)$ and $c\to c$ and $d\to d$. There are 6 ways you can choose $(a,b)$


Total 13 cases