Approximate size of the image of functions $f:[n]\to[n]$ [closed]

Question

The following is inspired from the most recent riddle of the week of the German news magazine Der Spiegel.

For any positive integer $n\in\mathbb{N}$, let $[n]$ denote the set $\{1,\ldots,n\}$. Let $E_n$ be the expected value of the size of the image of any function $f:[n]\to[n]$, or more explicitly, $$E_n = \frac{1}{n^n}\sum_{f:[n]\to[n]}|\text{im}(f)|.$$

What is the value of $\lim_{n\to\infty}E_n/n$, or, if the limit does not exist, what are the values of $\lim\inf_{n\to\infty}E_n/n$ and $\lim\sup_{n\to\infty}E_n/n$, respectively?

Answer 1

For each $i \in [n]$, the probability that $i$ is in the image of a random function $f: [n] \to [n]$ is $1 - \frac{(n-1)^n}{n^n}$. By linearity of expectation, the expected size of the image of $f$ is $$n-\frac{(n-1)^n}{n^{n-1}}.$$

Thus, $$\lim_{n \to \infty} \frac{E_n}{n}= \lim_{n \to \infty} 1 - \frac{(n-1)^n}{n^n}=1-\frac{1}{e}.$$