Dear Uncle Colin,

I need to work out - or at least estimate - the middle value in a row of Pascal’s triangle. Is there a quick way?

Strange Times - I’m Really Lucky I’m Not Guessing

Hi, STIRLING, and thanks for your message!

It turns out there’s a really nice way to get a good estimate using Stirling’s approximation ((Hey! That’s your name!)).

That says that $\ln (n!) \approx n \ln (n) - n + \frac{1}{2}\ln(2n\pi)$.

If we’re looking for $\ln \br{\nCr{2n}{n}}$ as a first step, we need to work out $\ln(2n!) - 2\ln(n!)$.

The first term is $2n \ln(2n) - (2n) + \frac{1}{2}\ln(4n\pi)$

The second term is $2n\ln(n) - (2n) + \frac{2}{2}\ln(2n\pi)$.

A lot of that cancels out! You’re left with $2n\ln (2) - \frac{1}{2}\ln(n\pi)$.

That gives an approximation for $\nCr {2n}{n}$ of $\frac{2^{2n}}{\sqrt{n\pi}}$.

For example, $\nCr{64}{32}$ would have $n=32$, and ought to be $\frac{2^{64}}{\sqrt{32\pi}}$.

(The calculator says: $1.84 \times 10^{18}$, compared to $1.83\times 10^{18}$, an error of 0.4%.)

Whoosh

“Of course, sensei, this has your fingerprints all over it.”

“Pineapple juice. No fingerprints.”

“As you say.”

“Gosper says you can replace $2n\pi$ with $\br{2n+\frac{1}{3}}\pi$ under the square root for a better approximation.”

“And does that help?”

“But of course. If you work through the algebra – which is, of course, left as an exercise - you’ll find that adjusting the estimate down by around $\frac{1}{7n}$ gives you a better approximation.”

“So in this case, seven thirty-twos are 224, so adjusting the answer down by 0.4 or 0.5 percent gives a better answer!”

“The number is right to one part in 1760 or so, and the logarithm is right to one part in 74,000.”

“Thank you sensei. Enjoy the pineapples!”


Hope that helps!

- Uncle Colin