Tienes que estimar $\binom{63}{19}$ $2$ minutos para salvarle la vida.

Question

Esto es a partir de las notas de la conferencia en este curso de matemáticas discretas, que estoy siguiendo.

El profesor está escribiendo sobre lo rápido que los coeficientes binomiales crecer.

"Así que, supongamos que tienes 2 minutos para salvar su vida y tuvo que estimar, hasta un factor de $100$, el valor de, digamos, $\binom{63}{19}$. Cómo lo harías? Voy a dejar esto (ojalá intrigante!) la pregunta que cuelga y vuelve al tema de manera eficiente la estimación de los coeficientes binomiales más tarde."

Todas las ideas/sugerencias sobre cómo hacerlo?

Answer 1

Dos minutos es un montón de cálculos, me escribe el 19 número en el numerador y el 19 número en el denominador y cancelar todo lo que pueden ser canceladas en menos de un minuto.

Se obtiene:

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

Aproximamos a esto como:

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

El valor real es $6.131164307078475\times 10^{15}$

Answer 2

En el numerador tenemos $63!/(63-19)!\approx(63-9)^{19}=54^{19}\approx50^{20}=100^{20}/2^{20}\approx10^{34}$.

En el denominador tenemos $19!\approx\left(\frac{1+19}2\right)^{19}=10^{19}$.

Así, el cociente es aproximadamente $10^{15}$.

No estoy seguro de que podría haber hecho en dos minutos bajo la amenaza de muerte, sin embargo.

Answer 3

Utilizar las medias entre dos factores igualmente desplazados: $\frac {63 \times 62 ... \times 54 ...\times 45}{19 \times 18 \times ... \times 9 ...\times 1} \approx \frac {54^{19}}{9^{19}} = 6^{19}$

Basado en el fórmula $(N+n)\times(N-n)= N^2-n^2$, $n^2$ "pequeño" $N^2$, que es lo suficientemente bueno para el numerador y no tan buenos para el denominador, así que por el cálculo más fácil escribir 9 en lugar de 10.

$6^{19} = 6.09359740010496\times 10^{15}$, también es factor de 10, pero casi exacto y más importante, realmente alcanzables dentro de dos minutos.

Answer 4

Con lápiz y papel, a Stirling aproximación:

$$ \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} $$ utilizando diversas estimaciones incluidas $2^{10} \doteq 10^3$.

Crudo, pero si en su lugar había para estimar el ${630 \choose 19}$, entonces usted podría no querer hacer la cancelación por escrito entero factores.

Answer 5

Aquí tienes!

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

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

Este utiliza la libra Esterlina aproximación factorial (n)