Finding number of functions from a set to itself such that $f(f(x)) = x$ The questions states that $f: A\rightarrow A$ is a function which satisfies $f(f(x)) = x.$
We have to find the number of such functions with $A = \left\{1,2,3,4\right\}$.
The given condition clearly states that the function is the inverse of itself. Since the set $A$ was given to be so small, I first tried to think of some familiar functions that could fit. I came up with $f(x) = x$ and $f(x) = 5-x$. But the answer was nowhere near $2$.
I think there has to be a general method to find the no. of functions that satisfy a given condition instead of hit and trial and counting on fingers. But I'm not able to figure out what it is.
 A: Note that a function does not necessarily have a closed expression which defines it. that is you to not necessarily need to express it $f(x)=5-x$ or $f(x)=x$, but rather we may just state where each element go. So one function is if $f(1)=4, f(4)=1, f(2)=3, f(3)=2$.
Each function satisfying the above condition must be of the form $f(x)=y$ if and only if $f(y)=x$.
We may Choose $f(1)$ in 4 different ways. 


*

*If $f(1)\neq 1$ then we have left to choose where the two elements which are not 1 or $f(1)$ should be mapped, and this we may do in 2 different ways. This if $f(1)\neq 1$ we have 2 choices.

*If $f(1)=1$ we have 3 choices of some other element which needs to also be mapped to it self. Then the rest of the elements may be mapped to them self or each other. This gives us 4 choices in total, 3 where the elements are mapped to each other and 1 where all elements are fixated.


We had 3 ways to get case 1 which induced 2 choices, and we had 1 way to get to case 2 which induced 4 choices. Thus we get $3\cdot 2 + 1\cdot 4 = 10$ such functions.
A: This can me asked as a graph theory problem: how many graphs with vertices $\{a,b,c,d\}$ exist such that each vertex lies in exactly one cycle of length at most $2$? 
Case 1: All cycles are of length 1. This is equivilant to the identity function, which we know is unique. However from a graph theoretic point of view this is equal to $\binom{4}{4}$ because we are choosing 4 vertices to have cycle length one (notice that order does not matter because cycles start and end in the same place, and if two functions have the same cycles regardless of order they are equal). $\binom{4}{4} = 1$, consistent with what we know about the identity. 
Case 2: One cycle is of length 2, and 2 are of length one. We know that the two of length one are chosen by $\binom{4}{2}$ and the reaming two vertices are forces to be in the cycles of length two (or are 'chosen' by $\binom{2}{2}$). 
Case 3: 2 cycles of length 2, which is the same amount of choices as above, since the two remaining ones are forced to be the cycle. We have to divide by the number of ways there are to arrange 2 $2$-cycles, which is $2!$
Summing the amounts of functions from the three cases we get $10$.
A: The number of such functions is the number of ways of dividing our set, in this case $\{1,2,3,4\}$ into $1$ or $2$ element subsets. For given such a subdivision, we can define $f(x)$ to be $x$ if $x$ is a singleton in the subdivision, and by $f(x)=y$, $f(y)=x$ if in the subdivision $x$ and $y$ are a "couple." Conversely, a function $f$ such that $f(f(x))=x$ for all $x$ determines a subdivision of $\{1,2,3,4\}$ into singles and couples. 
Let us tackle the number of ways to divide  an $n$-element set, say $\{1,2,\dots,n\}$, into singles and/or couples. Call this number of ways $a_n$.
Note that $a_{n+1}=a_n+na_{n-1}$. For if we add a new element $n+1$ to $\{1,2,\dots,n\}$, it can be all by itself, in which case there are $a_n$ ways to divide the rest  into groups of $1$ and/or $2$, or it can be paired with one of the earlier elements, in which case the rest can be subdivided into singles and/or couples in $a_{n-1}$ ways. We have obtained the recurrence
$$a_{n+1}=a_n+na_{n-1}.$$
It is clear that $a_1=1$ and $a_2=2$. Thus by the recurrence, we have $a_3=a_2+2a_1=4$, $a_4=a_3+3a_2=10$, $a_5=26$, and so on. 
There is no nice closed form known for $a_n$.
