How many functions $f:S \rightarrow S$ satisfy $f(f(x)) = f(x)$ for all $x \in S$? Let $S = \left\{ {1, 2, 3, 4, 5}\right\}$. How many functions $f:S \rightarrow S$ satisfy $f(f(x)) = f(x)$ for all $x \in S$?

More generally let $S$ be a non-empty, finite set with $n$ elements.
That $f(f(x)) = f(x)$ for all $x \in S$ means that the restriction of $f$ to the image $f(S)$ is the identity, i.e. $f|_{f(S)} = \mathrm{id}_{f(S)}$.
We can construct such a function by taking an arbitrary non-empty subset $T \subseteq S$, choose a function $g \colon S \setminus T \to T$ and define $f$ as
$$
 f_{T,g} \colon S \to S,
 x \mapsto
 \begin{cases}
    x  & \text{if $x \in T$}, \\
  g(x) & \text{if $x \notin T$}.
 \end{cases}
$$
On the other hand it directly follows the first observation that every function $f$ satisfying the desired property is of this form with $T = f(S)$ and $g = f|_{S \setminus T}$ unique.
We can now easily count the possible functions: We have $2^5-1$ non-empty subsets $T \subseteq S$, for each of which we have $|T|^{|S \setminus T|} = |T|^{n-|T|}$ many different functions $S \setminus T \to T$. Thus we have
$$
 \sum_{k=1}^n \binom{n}{k} k^{n-k}
$$
many functions. For the special case of $n = 5$ we thus have $196$ possible functions.
