I need to calculate all the numbers in a certain row of Pascal's triangle. Obviously, this is easy to do with combinatorics. However, what do you do when you need to estimate all the numbers in, say, the 100000th row of Pascal's triangle?
Is there any way to estimate the number so that the costly multiplications and divisions of binomials can be avoided? I'm already estimating factorials with Stirling's formula, but it still takes a number of seconds to calculate only one number – and I need about 100000/2 (since a row is symmetric).
Best Answer
Are you computing the factorials and then dividing? Don't do that. You can combine the estimates you get from Stirling's formula into
$${n+m \choose n} \approx \sqrt{ \frac{m+n}{2 \pi mn} } \frac{(m+n)^{m+n}}{m^m n^n}$$
and even then you can optimize, for example rewriting the second factor as
$$\left( 1 + \frac{n}{m} \right)^m \left( 1 + \frac{m}{n} \right)^n$$
and, depending on the relative sizes of $m$ and $n$, applying the approximation $\left( 1 + \frac{x}{n} \right)^n \approx e^x$. This will work if one of $m$ and $n$ are large compared to the other and in the intermediate case the above powers should be straightforward to compute. See also Exercises 1 and 2 at this blog post by Terence Tao on the subject.
Depending on what kind of precision you need you should consider just working with the logarithms and not with the numbers directly.