¿Se puede calcular eficientemente un coeficiente binomial (o multinomial)?

Question

Parecería que una consulta previa sería pertinente, pero no realmente para mí. Una de las respuestas se acerca, pero no está completa tal como está. Dado que la respuesta va a ser un número entero, todos los factores en el denominador se cancelarán. Los factores primos pueden ser eliminados por cualquier factor en el numerador que sea un múltiplo. El problema son los números compuestos; cancelarlos puede implicar múltiples factores en el numerador que comparten primos. Y está el problema auxiliar de determinar los factores primos de los compuestos (es decir ¿qué factor(es) compuesto(s) en el numerador debo cancelar contra un factor compuesto en el denominador).

Estoy pensando en una analogía con el cálculo del máximo común divisor de dos enteros positivos. Podrías determinar el MCD descomponiendo ambos argumentos en sus factorizaciones primas, luego usar el exponente mínimo para cada primo. Pero usar algo como el algoritmo de Euclides es mucho más fácil. Para un coeficiente multinomial, podría ejecutar una Criba de Eratóstenes hasta el factor máximo del numerador, usar esa tabla para obtener todas las factorizaciones primas aplicables, luego hacer un montón de cancelaciones, pero eso parece ser mucho trabajo. ¿Existe un procedimiento similar al del MCD de Euclides que podamos aplicar a los coeficientes binomiales?

Answer 1

Tal vez lo que estás buscando es el teorema de Kummer. Según el artículo de Wikipedia:

El teorema de Kummer establece que para enteros dados $\,n\ge m\ge 0\,$ y un número primo $\,p\,$, la valoración $p$-ádica de $\,\nu_p({n \choose m})\,$ es igual al número de acarreos cuando $\,m\,$ se suma a $\,n-m\,$ en base $\,p.\,$

Todo lo que se necesita ahora para calcular $\,N:={n\choose m}\,$ es la lista de todos los primos $\,p\le n\,$ y así $$ N = \prod_{p\le n} p^{\nu_p(N)}. $$ Es bien sabido (ver teorema multinomial) que cualquier coeficiente multinomial es un producto de coeficientes binomiales y por lo tanto la valoración $p$-ádica de un coeficiente multinomial es la suma de las valoraciones $p$-ádicas de algunos coeficientes binomiales bien definidos.

Por supuesto, hay formas más elementales de calcular coeficientes binomiales sin depender de factorizaciones primas. Simplemente utiliza uno de varios tipos de relaciones de recurrencia. Todo depende de tu caso de uso.

Answer 2

Si quieres hacer esto rápidamente, utiliza la factorización de primos, el teorema de Kummer y una estrategia de multiplicación equilibrada. Consulta por ejemplo https://codegolf.stackexchange.com/q/37270/194

Si prefieres mantenerlo simple, la descomposición $$\binom{n}{k} = \frac{n-k+1}{k} \binom{n}{k-1}$$ y sus variantes ofrecen diversos bucles simples que no requieren llevar un registro de lo que se debe cancelar. Por ejemplo:

resultado = 1
para i = 0 a k-1:
    resultado = resultado * (n-i) / (i+1)