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

  • $\begingroup$ "Number of seconds"? With Stirling's formula you can estimate one Binomial coefficient with less then 20 arithmetic operations (some logs, multiplications, additions, and a final exponentiation). Your computer ought to be able to handle up to several million of these a second! Ahh... you're using logarithms, right? $\endgroup$ – whuber Oct 14 '10 at 14:58
  • $\begingroup$ A very rough estimate: every entry in the $n$th row will be less than $2^n$. $\endgroup$ – Rasmus Oct 14 '10 at 15:01
  • $\begingroup$ Well, considering that the answer to Stirling's formula is several 100-1000s digits long, it takes a few milliseconds to calculate. That's not the bottleneck though, it is the multiplication and division of such large numbers that are taking really long. Maybe there's some way to speed that up in the code? $\endgroup$ – Herman Oct 14 '10 at 15:06
  • $\begingroup$ @Rasmus: That is indeed very rough. Since we know the row adds up to $2^n$, can we make a better estimate for every number at position $i$ from knowing what percentage (approximately) that number should be making of the total? $\endgroup$ – Herman Oct 14 '10 at 15:08
  • 2
    $\begingroup$ Stirling's formula is not going to approximate the values to hundreds or thousands of digits. Do all your multiplications and divisions with logarithms. They reduce the multiplication of two 1000-digit numbers to the addition of two values around 1000. Carry this out in double precision. $\endgroup$ – whuber Oct 14 '10 at 18:43

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.

  • $\begingroup$ A nit-shouldn't the 2*pi be in the denominator? There are two factorials there $\endgroup$ – Ross Millikan Oct 14 '10 at 15:36

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

  • $\begingroup$ See my comment to @Hans Lundmark's response concerning the use of the normal distribution. $\endgroup$ – whuber Oct 14 '10 at 18:59

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.

  • 4
    $\begingroup$ This is true in a narrow sense but it doesn't apply to the question. The cumulative sums of the binomial coefficients (suitably normalized) follow the cdf of a Gaussian. On a relative basis, estimates of the binomial coefficients obtained from the Gaussian are pretty good between n/2 - 2*Sqrt(n) and n/2 + 2*Sqrt(n) but become horrible outside that range, where the Gaussian grossly overestimates the binomial coefficients. The error actually gets worse as n gets large. $\endgroup$ – whuber Oct 14 '10 at 18:57
  • $\begingroup$ @whuber: I stand corrected. Thank you! $\endgroup$ – Hans Lundmark Oct 15 '10 at 6:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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