# You have to estimate $\binom{63}{19}$ in $2$ minutes to save your life.

This is from the lecture notes in this course of discrete mathematics I am following.

The professor is writing about how fast binomial coefficients grow.

So, suppose you had 2 minutes to save your life and had to estimate, up to a factor of $100$, the value of, say, $\binom{63}{19}$. How would you do it? I will leave this (hopefully intriguing!) question hanging and maybe come back to the topic of efficiently estimating binomial coefficients later.

Any ideas/hints on how to do it?

• I'd use this bound, fail to compute it in 120 seconds, and die. Apr 28 '16 at 13:55
• I would use the best tool possible, my CALCULATOR. Apr 28 '16 at 13:56
• What does "up to a factor of $100$" actually mean? $x/100 \le \hat{x} \le 100 x$? Or all digits right except the last two?
– mvw
Apr 28 '16 at 14:28
• I find it funny that none of the answers below gets it wrong! The reason is of course simple - people probably checked the final result before posting (as is a reasonable thing to do) and then tuned their result if it was wrong. Because of this effect I would expect several of the answers below to be biased in their choice of approximations. Apr 28 '16 at 16:07
• @Winther I bet they took more than 2 minutes..... Apr 28 '16 at 20:09

Two minutes is a lot of calculations, I'd write the 19 numbers in the numerator and the 19 numbers in the denominator, and cancel whatever can be cancelled in under a minute.

You get:

$$3^3\times5^2\times7^2\times23\times29\times31\times47\times53\times59\times61$$

We approximate this as:

$$20\times 20 \times 50 \times 20 \times 20 \times 20 \times 50 \times 50\times 50 \times 50=10^{15}$$

The actual value is $6.131164307078475\times 10^{15}$

• It takes more than $2$ minutes for me!
– user217174
Apr 28 '16 at 14:50
• I tried...If you write with 2 hands at the same time, one from the left and one from the right, it can be done. +1 nonetheless!!!! Apr 28 '16 at 15:42
• @imranfat was that a joke or you can actually write with two hands? :P
– Ant
Apr 28 '16 at 19:27
• With numbers I could, but writing words, uhhm....NO. I also tried to write with my feet. No success either....:) Apr 28 '16 at 20:06

In the numerator we have $63!/(63-19)!\approx(63-9)^{19}=54^{19}\approx50^{20}=100^{20}/2^{20}\approx10^{34}$.

In the denominator we have $19!\approx\left(\frac{1+19}2\right)^{19}=10^{19}$.

So the quotient is roughly $10^{15}$.

I'm not sure I could have done that in two minutes under the threat of death, though.

• +1 but I am not following the steps when you approximate the factorial :) Could you explain it better?
– Ant
Apr 28 '16 at 19:28
• @Ant: In the numerator, it's $((63-0)(63-18))((63-1)(63-17))\cdots((63-8)(63-10))(63-9)\approx(63-9)^{19}$; in the denominator it's $((1\cdot19)(2\cdot18)\cdots(9\cdot11)10\approx10^{19}$. Apr 28 '16 at 21:05

Use averages between two equally displaced factors: $\frac {63 \times 62 ... \times 54 ...\times 45}{19 \times 18 \times ... \times 9 ...\times 1} \approx \frac {54^{19}}{9^{19}} = 6^{19}$

Based on formula $(N+n)\times(N-n)= N^2-n^2$, $n^2$ "small" to $N^2$, which is good enough for numerator and not so good for denominator, so because of easier calculation writing 9 instead of 10.

$6^{19} = 6.09359740010496\times 10^{15}$, well it is factor of 10, but almost exact and most important, really achievable within two minutes.

• Except the denominator here should be $10^{19}$. Apr 28 '16 at 14:49
• @Michael Lugo, 9 is better for further calculation and hopefully within factor 100 variability.
– z100
Apr 28 '16 at 14:59
• @z100 It's a case of two wrongs making a right: the ratio of $10^{19}$ to $9^{19}$ is very roughly about $e^2 \approx 7$, while a sharper bound for the denominator is $19 \cdot (18\times17\cdots\times 2) \le 19 \cdot 10^{17}$, so we know that $10^{19}$ overshoots $19!$ by at least a factor of $5$. This makes $9^{19}$ the better approximation anyway. I'd be far more worried about dying by using $10^{19}$! Apr 28 '16 at 15:13

With pen and paper, Stirling's approximation:

\begin{align} {63 \choose 19} &= \frac{63!}{19! 44!} \\ &\doteq \frac{\sqrt{2\pi 63}}{\sqrt{2\pi 19}\sqrt{2\pi 44}} \left( \frac{63}{e}\right)^{63} \left( \frac{e}{19}\right)^{19} \left( \frac{e}{44}\right)^{44} \\ &\doteq \sqrt{\frac{60}{2 \cdot 3 \cdot 20 \cdot 50}} \cdot 20^{63} \cdot 5^{-19} \cdot 15^{-44} \\ &\doteq \frac{1}{10} \cdot 2^{63} \cdot 10^{63} \cdot 2^{19} \cdot 10^{-19} \cdot 3^{-44} \cdot 2^{44} \cdot 10^{-44} \\ &= 10^{-1} \cdot 2^{126} \cdot 3^{-44} \\ &= 10^{-1} \cdot (2^{10})^{12} \cdot 2^6 \cdot (3^2)^{-22} \\ &\doteq 50 \cdot 10^{-1+36-22} \\ &= 5 \cdot 10^{14} \end{align} using various estimates including $2^{10} \doteq 10^3$.

Crude, but if instead you had to estimate ${630 \choose 19}$ then you might not want to do cancelling by writing out integer factors.

• Two minutes are required to type value in calculator if calculators are disallowed then it's not very easy Apr 28 '16 at 14:38
• @ArchisWelankar By calculator, do you mean basic $+ - \cdot /$ or scientific?
– user332714
Apr 28 '16 at 14:43
• @ArchisWelankar If you had a scientific calculator, you could just use the $\log$ form of Stirling's approximation,
– user332714
Apr 28 '16 at 15:03
• If you were estimating $C(630,19)$ then it makes sense to save Stirling's for estimating $19!$, and use $621^{19}$ as an approximant of $630!/611!$. That seems a lot more accurate than having to round to the nearest $5$ inside an exponent like $630$, and much less baggage to carry. Apr 28 '16 at 15:04
• If you have a smartphone and Internet access, you can use Wolfram Alpha anyway.
– z100
Apr 28 '16 at 15:05

So we want to estimate: $$\frac{63!}{19!44!}$$ We do this by doing a geometric average approximation, replacing each factorial by it's geometric average, and the following approximations $9.5^{19} \approx 9^{20}$ and since it's a matter of life and death we expose we know the 10% and 5% interest tables by heart (useful since $22 = 20\cdot 1.10$ and $31.5 = 30\cdot 1.05$ so the exponents will copy over to the "percentage" part): $$\frac{31.5^{63}}{ 9.5^{19} \cdot 22^{44}} = \frac{22\cdot 3^{63}\cdot10^{63}}{66\cdot 2^{44}\cdot10^{44}\cdot 3^{2\cdot 20}} = \frac{1}{3}\frac{3^{23}10^{19}}{2^{44}}$$ then cancelling by using $2^3 \approx 3^2 \approx 10$:

$$\approx \frac{10^{19}}{2^{11}} \approx 2.5\cdot 10^{15}$$

Here you go!

${63\choose19} = 6.13116E+15$

${63\choose19} = \frac{63!}{19!44!}$ $$= \frac{63^{63}}{19^{19}.44^{44}}$$$$\approx \frac{60^{60}}{20^{20}.40^{40}}$$$$\approx \frac{3^{60}}{2^{40}}$$$$\approx 16.3^{32}$$$$\approx 9^{16}$$$$\approx 10^{16}$$

This uses Sterling's approximation for factorial (n)

• $63^{63} \approx 60^{60}$ does not hold to within a factor of $100$.
– user332714
Apr 28 '16 at 14:50
• I rounded off to close numbers both numerator and denominator and I think it is OK. Apr 28 '16 at 14:52
• In fact that ratio is over $4 \cdot 10^6$, so it is only coincidencental overestimates and underestimates that have produced the $10^{16}$. wolframalpha.com/input/?i=63%5E63%2F60%5E60+scientific+form
– user332714
Apr 28 '16 at 15:00
• I certainly believe it is not coincidental. For your information, $\frac{63^{63}}{44^{44}}$ = 1.11311E+41 $\frac{60^{60}}{40^{40}}$ = 4.04274E+42. The ratio is 36.31938782 within a factor of 100. Apr 28 '16 at 15:08
• You're not getting my point. $63^{63}/60^{60} = 4.67 \cdot 10^6$ and $44^{44}/40^{40} = 1.70 \cdot 10^8$.
– user332714
Apr 28 '16 at 15:16