Asymptotic behavior of the number of idempotent maps For every $n\ge1$, let us denote by $q_n$ the number of maps $f:\lbrack\!\lbrack1,n\rbrack\!\rbrack\to\lbrack\!\lbrack1,n\rbrack\!\rbrack$ such that $f\circ f=f$.
I have obtained the following closed form :
$$q_n=\sum_{k=0}^n{n\choose k}k^{n-k}$$
Computation of $\displaystyle{\frac{q_n}{n^n}}$ provides numerical evidence that $\displaystyle{\lim_{n\to\infty}\frac{q_n}{n^n}=0}$.
I tried to prove it but didn't succeed ...
A more interesting and probably less simple question would be to compute an equivalent of $q_n$.
 A: Just showing that $\dfrac{q_n}{n^n} \to 0$ isn't very hard once one stops looking for more precise estimates:
\begin{align}
\frac{1}{n^n}\sum_{k = 0}^{n} \binom{n}{k} k^{n-k}
&= \frac{1}{n^n}\sum_{k \leqslant n/2} \binom{n}{k} k^{n-k} + \frac{1}{n^n}\sum_{k > n/2} \binom{n}{k} k^{n-k} \\
&\leqslant \frac{1}{n^n} \sum_{k \leqslant n/2} \binom{n}{k} \biggl(\frac{n}{2}\biggr)^{n-k} + \frac{1}{n^n}\sum_{k > n/2} \binom{n}{k} n^{n/2} \\
&\leqslant \frac{1}{2^n} \sum_{k \leqslant n/2} \binom{n}{k}\biggl(\frac{2}{n}\biggr)^k + \frac{1}{n^{n/2}} \sum_{k > n/2} \binom{n}{k} \\
&\leqslant \frac{1}{2^n}\biggl(1 + \frac{2}{n}\biggr)^n + \frac{2^n}{n^{n/2}} \\
&< \frac{e^2}{2^n} + \biggl(\frac{2}{\sqrt{n}}\biggr)^n.
\end{align}
Finding the asymptotic behaviour of $q_n$ seems difficult. It's not even easy to find the largest term in the sum. Some quick-and-dirty estimates say that the largest terms occur when $k$ is about $n/\log n$, and that would suggest
$$\log q_n = n(\log n - \log \log n - 1) + o(n)$$
if I haven't made a mistake in my scribblings, but I wouldn't bet on it.
A: This is sequence A00358 in OEIS. A detailed analysis of the asymptotic behaviour of $q_n$ can be found in [1].
[1] B. Harris and L. Schoenfeld, The number of idempotent elements in symmetric semigroups, J. Combin. Theory, 3 (1967), 122-135.
