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?

Solution 1:

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}$

Solution 2:

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.

Solution 3:

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.

Solution 4:

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.

Solution 5:

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}$$