# It’s counting time

What is the number of idempotent functions $f:\{1,\dots,n\}\to\{1,\dots,n\}$?

1. It is relatively straightforward to prove that if $X_n$ is the number of such functions, then $X_{n+2} = X_{n+1} + (n+1)X_n$ for $n\geqslant 0$, with $X_1=X_0=1$. If $f$ is the EGF of such sequence of numbers, one obtains after some algebra that $f'(z) = (1+z)f(z)$ with initial condition $f(0)=1$, which gives $f(z) = \exp(z+z^2/2)$, and hence a closed formula for the $X_n$.
2. A low brow solution: an idempotent function $f$ is uniquely determined by its set of fixed points $X$ together with its restriction $f:[n]\setminus X \to X$. Conversely, this set of data uniquely determines an idempotent function.
Therefore, $X_n = \sum_{k=0}^n \binom{n}{k} k^{n-k}$.