Let $f$ be a uniformly selected random function that maps the set $[n] = \{1,2,...,n\}$ to itself, so $f(1),...,f(n)$ are i.i.d. and uniformly distributed over $[n]$. If $R(f)$ denotes the range of the function $f(·)$. In other words, $R(f) = \{y ∈ [n] : (∃x ∈ [n] : f(x) = y)\}$. Try to compute the probability of $|R(f)|=k$, for $\forall k\leq n$.
For example, for $n=6$, for instance, $f[1,2,3,4,5,6]=[2,2,3,3,3,5]$, then $|R(f)|=3$, since there are three numbers $(2,3,5)$ appears in the range. What is $P(|R(f)|=3)$?
The expectation is given: $E(|R(f)|)=n(1-(1-\frac{1}{n})^n)$. I have tried several expressions of possible probability distributions but nothing is accord with this expectation after check.
Any help would be appreciate!
The probability is \begin{equation} P(|R(f)|=k)=\frac{\binom{n}{k} k!F (n,k)}{n^n}, \end{equation} where \begin{equation} F (n,k)=F(n-1,k-1)+kF(n-1,k),\quad F(n,1)=F(n,n)=1. \end{equation}
Since $f$ is uniformly selected, there are $n^n$ kinds of equiprobable mappings, yields the denominator.
Suppose $|R(f)|=k$. Firstly choosing $k$ images, there are $\binom{n}{k}$ probabilities. Secondly, mapping $n$ different pre-images into these $k$ different images. For the case $n=6, k=3$, see the figure below.
This process is like putting n different balls into k different boxes.
The formula of putting n different balls into k same boxes is $F(n,k)$, thinking it as a recursive process yields $F(n,k)=F(n-1,k-1)+kF(n-1,k),\quad F(n,1)=F(n,n)=1.$Since these boxes are different, we need to time $F(n,k)$ with $k!$.
I have checked for case $n=4$:
$P(|R(f)=1|)=\frac{4}{256}$
$P(|R(f)=2|)=\frac{6*2*7}{256}$
$P(|R(f)=3|)=\frac{4*6*6}{256}$
$P(|R(f)=4|)=\frac{1*24*1}{256}$
Their sum is 1. Besides, the expectation is 2.734375, which is accord to the result given by the expression of expectation.