Find number of functions such that $f(f(x)) = f(x)$, where $f: \{1,2,3,4,5\}\to \{1,2,3,4,5\}$

Question

Consider set $A=\{1,2,3,4,5\}$, and functions $f:A\to A.$ Find the number of functions such that $f\big(f(x)\big) = f(x)$ holds.

I tried using recursion but could not form a recursion relation. I tried counting the cases manually, but it was too exhaustive and impractical. I tried drawing/mapping but that too included counting by making cases. Random variable was another approach I tried but couldn't make a summation.

A general idea for such problems is needed.

Thanks.

Answer 1

If a variable $x$ is in the range of $f(x)$, then $f(x)=x$. This means that we can effectively categorize the potential functions by their range. The number of functions that have a given range is $n^{5-n}$, with $n$ being the number of values in the range. The number of ranges that have $n$ values in them is $\frac{5!}{n!(5-n)!}$. This means that the total number of functions is $$\sum_{n=1}^5\frac{5!}{n!(5-n)!}n^{5-n}$$which comes out to be $196$.