Skip to main content
2 of 2
edited tags
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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

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?