Limit of sum of stirling numbers computing the average image of a random function $f:[n]\to[n]$

Question

I tried to compute the average size of the image of a random function $f:[n]\to[n]$. Using properties of Stirling numbers of the second kind, here denoted by $S(n,k)$, I arrived at the expression $$\left(n^{-n}\sum_{k=1}^n\binom{n}{k} \cdot S(n,k) \cdot k!\cdot k\right),$$ which I believe is correct. I noticed that when one expresses this as a percentage, this number converges for large values of $n$ to some real number around $0.6322$: $$\lim_{n\to\infty} \left(n^{-(n+1)}\sum_{k=1}^n\binom{n}{k} \cdot S(n,k) \cdot k!\cdot k\right)\approx 0.6322$$ I'd like to know why this converges and if we can simplify the limit in question.

Answer 1

Combinatorially for the image to have size $k$ we must first choose the $k$ values and then partition $[n]$ into $k$ non-empty sets, one for each value of $k$, so the sets form an ordered sequence. This yields for the total sizes of all images

$$\sum_{k=1}^n {n\choose k} \times {n\brace k} k! \times k \\ = n \sum_{k=1}^n {n-1\choose k-1} \times {n\brace k} k!.$$

This is

$$n\times n! [z^n] \sum_{k=1}^n {n-1\choose k-1} (\exp(z)-1)^k \\ = n\times n! [z^n] (\exp(z)-1) \sum_{k=1}^n {n-1\choose k-1} (\exp(z)-1)^{k-1} \\ = n\times n! [z^n] (\exp(z)-1) \exp((n-1)z).$$

We thus get for the average size the value

$$n^{-n} \times n\times n! [z^n] (\exp(nz)-\exp((n-1)z)) \\ = n^{-n} \times n\times (n^n - (n-1)^n) \\ = n\times \left(1-\left(1-\frac{1}{n}\right)^n\right).$$

This becomes

$$\bbox[5px,border:2px solid #00A000]{ n \times (1-\exp(-1)) \approx n \times 0.6321205588}$$

in the limit.