¿Cómo puedo calcular Coeficientes binomiales de eficiente?

Question

Estoy tratando de reproducir [función combinat de Excel] [1] en C#. El número de combinaciones es la siguiente, donde número = n y tamaño = k:

$${n \choose k} = \frac{n!}{k! (n-k)!}.$$

No puedo utilizar esta fórmula porque el factorial desborda la capacidad del ordenador realmente rápido. Int32 sólo puede hacer hasta 12!, Int64 hasta 20! y hasta un 170 friolera! después de estoy por mi cuenta.

¿Cómo obtengo los mismos resultados con una fórmula más suave para el ordenador?

Answer 1

André Nicolas identifica correctamente que deberíamos tal vez de usar: $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$$

But we should also use:

$$\binom{n}{k}=\binom{n}{n-k}$$

And this also seems important:

$$\binom{n}{0} = \frac{n!}{(n-0)!} = \frac{n!}{n!} = 1$$

Great, we have everything we need to implement the function recursively!

---

I like to implement n choose k in a functional language like so:

n `choose` k
  | k > n           = undefined
  | k == 0          = 1
  | k > (n `div` 2) = n `choose` (n-k)
  | otherwise       = n * ((n-1) `choose` (k-1)) `div` k

Or in an imperative language like so:

f(n, k) {
  if(k >  n)
    throw some_exception;
  if(k == 0)
    return 1;
  if(k > n/2)
    return f(n,n-k);
  return n * f(n-1,k-1) / k;
}

It is pretty easy to see that both implementations run in $\mathcal{S}(n)$ tiempo y evita errores de desbordamiento de fijo los números de precisión mucho mejor que el cálculo de n!/(n-k)!.

Answer 2

Tal vez usar %#% $ #%

Answer 3

Supongo que usted está buscando un punto flotante respuesta aquí.

$\prod_{i=0}^{k-1} \frac{n-i}{k-i}$. Calcular la parte de cada plazo $\frac{n-i}{k-i}$ y se multiplican.

Answer 4

Tenga en cuenta que $$\frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)\cdots (n-k+1)}{k!}$$ Al hacer esto a mano, hay mucho de cancelación que se puede hacer. De hecho, desde el $\binom{n}{k}$ es un número entero, se están garantizados para ser capaz de cancelar todos los de $k!$.

Por la forma, ya que $\binom{n}{k} = \binom{n}{n-k}$, siempre podemos configurar la fracción de modo que no hay más de $n/2$ factores en la parte superior y la parte inferior.

Espero que esto ayude!

Answer 5

Usted puede utilizar Stirling aproximación para calcular el logaritmo. $\ln n!\approx n \ln n - n + \frac 12 \ln (2 \pi n)$. Es bastante precisa como $n$ se hace grande (aun $10$)