Probability distribution of $P(|R(f)|=k)$ 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!
 A: 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.

