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$?
 A: 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.
A: Functions like that are often called retractions. 
Let $f$ be a retraction
on $S$ and let $A\subseteq S$ be its image. 
Then on $A$ the function
$f$ is determined: we have $a\mapsto a$ for each $a\in A$. 
This because $a=f\left(b\right)$ for some $b\in S$ so that $f\left(a\right)=f\left(f\left(b\right)\right)=f\left(b\right)=a$.
Let
$k$ be the cardinality of $A$. 
Then $5-k$ elements of $S$ are
not in $A$. 
They are all sent by $f$ to an element in $A$ wich
is the only condition on them. 
That gives $k^{5-k}$ possibilities.
Shown is now that there are $k^{5-k}$ retractions on $S$ that satisfy
the extra condition $\text{im}f=A$.
The number of subsets of $S$ having a cardinality $k$ is $\binom{5}{k}$ so $\binom{5}{k}k^{5-k}$ is the number of retractions on $S$ that have an image with cardinality $k$.

We conclude that the number of retractions on $S$ is: $\sum_{k=1}^{5}\binom{5}{k}k^{5-k}$.

A: The general (finite) case, with an $n$-element set, is tabulated at the Online Encyclopedia of Integer Sequences. No closed form is given, but there are generating functions, recursions, references to the literature, and the asymptotic formula, $$r^{-n}n!e^{(n+1)/(r+1)}\sqrt{{r+1\over2\pi(n+1)(r^2+3r+1)}}$$ where $r$ is the root of the equation $r(r+1)e^r=n+1$. 
