7
$\begingroup$

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

  • 0
    Depending on the accuracy you need, this bound might help: $\left(\frac{n}{k}\right)^k \leq \binom{n}{k} \leq \left(\frac{ne}{k}\right)^k.$2011-08-31

3 Answers 3

7

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.

  • 0
    A nit-shouldn't the 2*pi be in the denominator? There are two factorials there2010-10-14
7

If you want all the numbers in one particular row, you can get each from the last with one multiply and one divide. ${n \choose m}={n \choose m-1}*(n-m+1)/m$

For individual components, you can use the fact that the distribution is approximately normal with standard deviation $\sqrt n$ and the central coefficient is about $\frac {4^n}{\sqrt n\pi}$. I'm not sure that is any faster than Qiaochu's suggestion

  • 0
    See my comment to @Hans Lundmark's response concerning the use of the normal distribution.2010-10-14
-1

The entries in the $n$th row of Pascal's triangle (for large $n$) follow a Gaussian curve quite closely, as a consequence of the central limit theorem. See the Wikipedia article about the binomial distribution.

  • 0
    @whuber: I stand corrected. Thank you!2010-10-15