# Simple approximation to a sum involving Stirling numbers?

I have also posted this question at https://math.stackexchange.com/questions/486917/simple-approximation-to-a-sum-involving-stirling-numbers. I have an exact answer to a problem, which is the function:

$f(x,y)=\frac{1}{y^x}\sum_{i=1}^{x-1}{[i\binom{y}{x-i}(x-i)!S(x,x-i)]}$ where $S(x,x-i)$ is Stirling number of the second kind. Equivalently, $f(x,y)=\frac{1}{y^x}\sum_{i=1}^{x-1}{\{i\binom{y}{x-i}\sum_{j=0}^{x-i}{[(-1)^{x-i-j}\binom{x-i}{j}j^x]}\}}$. Equivalently, $f(x,y)=\frac{y!}{y^x}\sum_{i=1}^{x-1}{\{\frac{i}{(y-(x-i))!}\sum_{j=0}^{x-i}{[\frac{(-1)^{x-i-j}j^x}{j!(x-i-j)!}]}\}}$.

I have noticed that the percent difference between $f(x,y)$ and $g(x,y)$ goes to $0$ for larger values of $x$ and $y$, where $g(x,y)$ is the far more elegant $x-y(1-e^{-\frac{x}{y}})$. How can $f(x,y)$ be approximated by $g(x,y)$? What approximations should be used to make this connection?

I have tried approximations for $S(n,m)$ listed at http://dlmf.nist.gov/26.8#vii, to no avail.

Consider all functions from an $x$ element set to a $y$ element set. Then your $f(x,y)$ gives the expected value of $x$ minus the size of the image of the function. So all you need is to find the expected value of the image. This is easy since the probability that an element is not in the image is just $((y-1)/y)^x$. In other words $f(x,y)$ equals $x-y(1-((y-1)/y)^x)$.
• Thank you. Your answer is correct. To finish it off, define $n=xy$. Taking $\lim_{n\rightarrow\infty}{(\frac{y-1}{y})^x}=e^{-\frac{x}{y}}$. – user1748601 Sep 8 '13 at 8:07