42
$\begingroup$

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?

$\endgroup$
  • 10
    $\begingroup$ I'd use this bound, fail to compute it in 120 seconds, and die. $\endgroup$ – Clement C. Apr 28 '16 at 13:55
  • 6
    $\begingroup$ I would use the best tool possible, my CALCULATOR. $\endgroup$ – SchrodingersCat Apr 28 '16 at 13:56
  • 7
    $\begingroup$ For crying out loud...where is this professor from, North Korea? +1 though (but not for NK) $\endgroup$ – imranfat Apr 28 '16 at 14:22
  • 2
    $\begingroup$ 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? $\endgroup$ – mvw Apr 28 '16 at 14:28
  • 7
    $\begingroup$ 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. $\endgroup$ – Winther Apr 28 '16 at 16:07
45
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ It takes more than $2$ minutes for me! $\endgroup$ – user217174 Apr 28 '16 at 14:50
  • 1
    $\begingroup$ 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!!!! $\endgroup$ – imranfat Apr 28 '16 at 15:42
  • $\begingroup$ @imranfat was that a joke or you can actually write with two hands? :P $\endgroup$ – Ant Apr 28 '16 at 19:27
  • 1
    $\begingroup$ With numbers I could, but writing words, uhhm....NO. I also tried to write with my feet. No success either....:) $\endgroup$ – imranfat Apr 28 '16 at 20:06
14
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ +1 but I am not following the steps when you approximate the factorial :) Could you explain it better? $\endgroup$ – Ant Apr 28 '16 at 19:28
  • $\begingroup$ @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}$. $\endgroup$ – joriki Apr 28 '16 at 21:05
5
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Except the denominator here should be $10^{19}$. $\endgroup$ – Michael Lugo Apr 28 '16 at 14:49
  • 2
    $\begingroup$ @Michael Lugo, 9 is better for further calculation and hopefully within factor 100 variability. $\endgroup$ – z100 Apr 28 '16 at 14:59
  • 2
    $\begingroup$ @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}$! $\endgroup$ – Erick Wong Apr 28 '16 at 15:13
2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Two minutes are required to type value in calculator if calculators are disallowed then it's not very easy $\endgroup$ – Archis Welankar Apr 28 '16 at 14:38
  • $\begingroup$ @ArchisWelankar By calculator, do you mean basic $+ - \cdot /$ or scientific? $\endgroup$ – lastresort Apr 28 '16 at 14:43
  • $\begingroup$ @ArchisWelankar If you had a scientific calculator, you could just use the $\log$ form of Stirling's approximation, $\endgroup$ – lastresort Apr 28 '16 at 15:03
  • $\begingroup$ 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. $\endgroup$ – Erick Wong Apr 28 '16 at 15:04
  • $\begingroup$ If you have a smartphone and Internet access, you can use Wolfram Alpha anyway. $\endgroup$ – z100 Apr 28 '16 at 15:05
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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)

$\endgroup$
  • 1
    $\begingroup$ $63^{63} \approx 60^{60}$ does not hold to within a factor of $100$. $\endgroup$ – lastresort Apr 28 '16 at 14:50
  • $\begingroup$ I rounded off to close numbers both numerator and denominator and I think it is OK. $\endgroup$ – Satish Ramanathan Apr 28 '16 at 14:52
  • $\begingroup$ 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 $\endgroup$ – lastresort Apr 28 '16 at 15:00
  • $\begingroup$ 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. $\endgroup$ – Satish Ramanathan Apr 28 '16 at 15:08
  • 1
    $\begingroup$ 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$. $\endgroup$ – lastresort Apr 28 '16 at 15:16

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.