Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have also posted this question at http://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.

share|improve this question

1 Answer 1

up vote 9 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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