Estimar una cierta fila de Pascal ' triángulo s

Question

Necesito calcular todos los números en una determinada fila del triángulo de Pascal. Obviamente, esto es fácil de hacer con la combinatoria. Sin embargo, ¿qué hacer cuando usted necesita para calcular todos los números en, digamos, la 100000th fila del triángulo de Pascal?

Es allí cualquier manera de estimar el número para que la costosa multiplicaciones y divisiones de binomios se puede evitar? Ya estoy estimación factoriales con la fórmula de Stirling, pero todavía tiene un número de segundos para calcular un número - y necesito unos 100000/2 (ya que una fila es simétrica).

Answer 1

Eres el cómputo de la factoriales y , a continuación, dividir? No hagas eso. Usted puede combinar las estimaciones se obtiene de la fórmula de Stirling en

$${n+m \choose n} \approx \sqrt{ \frac{m+n}{2 \pi mn} } \frac{(m+n)^{m+n}}{m^m n^n}$$

e incluso entonces usted puede optimizar, por ejemplo reescribir el segundo factor como

$$\left( 1 + \frac{n}{m} \right)^m \left( 1 + \frac{m}{n} \right)^n$$

y, dependiendo de los tamaños relativos de $m$$n$, aplicando la aproximación $\left( 1 + \frac{x}{n} \right)^n \approx e^x$. Esto funcionará si uno de $m$ $n$ son grandes en comparación con los otros y en el caso intermedio de las anteriores competencias deben ser fáciles de calcular. Ver también los Ejercicios 1 y 2 en este post del blog de Terence Tao sobre el tema.

Dependiendo de qué tipo de precisión que usted necesita, usted debería considerar la posibilidad de trabajar con los logaritmos y no con los números directamente.

Answer 2

Si desea que todos los números en una fila, cada uno de los últimos con uno puedes multiplicar y un dividir. ${n \choose m}={n \choose m-1}*(n-m+1)/m$

Para los componentes individuales, puede utilizar el hecho de que la distribución es aproximadamente normal con desviación estándar $\sqrt n$ y el coeficiente central es $4^n/\sqrt n\pi$. No estoy seguro de que es todo más rápido que la sugerencia de Qiaochu

Answer 3

Las entradas de la $n$ ésima fila del triángulo de Pascal (para grandes $n$) siga una curva gaussiana bastante cerca, como consecuencia del teorema de límite central. Vea el artículo de Wikipedia sobre la distribución binomial.