Skip to main content
added 107 characters in body
Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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}.$$

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}}.$$

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}.$$

Source Link
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

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}}.$$