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

  • $\begingroup$ 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}}$. $\endgroup$ – user1748601 Sep 8 '13 at 8:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.