This might not be the right forum for this question but here goes: In order to estimate the run-time, I need to compute the cumulative probability of getting all combinations in a certain simulation. The formula for the probability is
$$ P_n(m) = \sum_{k=1}^n (-1)^{n-k} \binom{n}{k} \left( \frac{k}{n} \right)^m = 1+\sum_{k=1}^{n-1} (-1)^k \binom{n}{k} \left( 1 - \frac{k}{n} \right)^m $$
My program is running in Visual Basic using Excel but every time I use a value for n above the order of 1500 (and m up to an order of 10 to 100 times higher) I get overflow. Stirling does not really work (I think) because of the series expression. So is there some other trick that might work (except for manual programming and finding the exponents and putting everything together in strings) or is there some way to get a good approximation to the series expression - maybe like some integral?
For slightly more convenience in the case $m=0$, let your summation start at $k=0$ instead of $1$. Then $$P_n(m) = \frac{n!}{n^m}\left\{ {m \atop n} \right\}$$ where $\left\{ {m \atop n} \right\}$ is a Stirling number of the second kind.
The Stirling numbers can be computed using the recursion
$$ \left\{ {m+1 \atop n} \right\} = n \left\{ {m \atop n} \right\} + \left\{ {m \atop n-1} \right\} $$
which corresponds to this recursion for $P_n(m)$:
$$ P_n(m+1) = P_n(m) + \left(\frac{n-1}{n}\right)^m P_{n-1}(m) $$ with boundary conditions $P_{n}(0) = 1$ for $n \ge 1$, $P_n(m) = 0$ for $n > m$. I don't think this should result in any overflows, and it lets you compute all $P_n(m)$ for $1 \le n \le N$, $1 \le m \le M$ in time and space $\mathcal O(MN)$.