MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have also posted this question at 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, to no avail.

share|cite|improve this question
up vote 10 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|cite|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


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.