Descomposición del factorial en producto de potencias de números primos

[teclado]

Me gustaría abrir este blog con una reflexión sobre algo que me ha inquietado desde hace mucho tiempo y que no he conseguido resolver hasta hace bien poco.

Hace unos pocos meses, en Twitter, @edusadeci propuso el siguiente problema: Decidir si

$$\dst \frac{5300!}{100!(53!)^{100}}$$

es un número entero o no.

Me llamó la atención porque hacía mucho tiempo que me traía de cabeza una forma de demostrar que los coeficientes binomiales sean todos enteros, ya que siempre me pareció asombroso que lo sean dada la ecuación que los da:

$$\dst {m \choose n}=\frac{m!}{n!(m-n)!}$$

Es evidente que los primeros $n$ factores de $m!$ se cancelan con el $n!$ del denominador, pero en éste siguen quedando los primeros $m-n$ números, de modo que se me hacía raro que el resultado sea un número entero.

Con la idea de resolver este problema pasé algunos viajes en autobús al trabajo intentando averiguar cómo descomponer el factorial en producto de potencias de números primos. De esa forma podría ver cómo se cancelan todos los factores del denominador.

Para ello me pregunté cuántas veces aparece un factor primo multiplicando en el factorial:

Un factor $p$ cualquiera aparece multiplicando en $n!$ un total de $\left \lfloor \frac{n}{p} \right \rfloor$ veces, ya que cada $p$ posiciones se repite. Sin embargo también aparecen todas sus potencias, la segunda potencia aparece $\left \lfloor \frac{n}{p^2} \right \rfloor$ veces, la tercera $\left \lfloor \frac{n}{p^3} \right \rfloor$, etc. Cada aparición de la primera potencia aporta un factor $p$ a la descomposición del factorial y cada una de la segunda, aporta un $p^2$. Sin embargo, como ya se ha contado uno cada vez al contar las apariciones de la primera potencia, sólo añade un factor $p$. Lo mismo ocurre con las apariciones de la tercera potencia y las siguientes, cada una aporta sólo un factor $p$ adicional, ya que en las cuentas anteriores se han obtenido ya todas las apariciones de las potencias menores.

De modo que un factor $p$ aparece multiplicando, en la descomposición de $n!$:

$$\dst N(n,p) = \sum_{i=1}^{\left\lfloor\log_p{n}\right\rfloor}\left\lfloor\frac{n}{p^i}\right\rfloor$$

Como $n!$ tiene como factores todos los números primos menores o iguales a $n$, y se han contado todas sus apariciones, se puede concluir:

$$n! = \prod_{p=2}^np^{\sum_{i=1}^{\left\lfloor\log_p{n}\right\rfloor}\left\lfloor\frac{n}{p^i}\right\rfloor}$$

Ahora bien, con esto, para resolver si ${m \choose n}=\frac{m!}{n!(m-n)!}$ es entero se puede hacer la sustitución, sumando o restando las potencias a las que aparece elevado cada factor. Según los valores de $n$ y $m$, aparecerán tres tipos de términos en dicha suma:

• $\left\lfloor\frac{m}{p^i}\right\rfloor - \left\lfloor\frac{n}{p^i}\right\rfloor$ Estos términos son siempre no negativos, ya que $m\ge n$
• $\left\lfloor\frac{m}{p^i}\right\rfloor - \left\lfloor\frac{m-n}{p^i}\right\rfloor$ Vuelven a ser no negativos, ya que $m\ge m-n$
• $\left\lfloor\frac{m}{p^i}\right\rfloor - \left\lfloor\frac{n}{p^i}\right\rfloor - \left\lfloor\frac{m-n}{p^i}\right\rfloor$ En este caso hay que pensar un poco más:

Sabiendo que $\left\lfloor a - b\right\rfloor$ puede valer $\left\lfloor a\right\rfloor - \left\lfloor b\right\rfloor$ o bien $\left\lfloor a\right\rfloor - \left\lfloor b\right\rfloor - 1$, los términos que responden al último caso quedan como alguno de los siguientes:

• $\left\lfloor\frac{m}{p^i}\right\rfloor - \left\lfloor\frac{n}{p^i}\right\rfloor - \left\lfloor\frac{m}{p^i}\right\rfloor + \left\lfloor\frac{n}{p^i}\right\rfloor = 0$
• $\left\lfloor\frac{m}{p^i}\right\rfloor - \left\lfloor\frac{n}{p^i}\right\rfloor - \left\lfloor\frac{m}{p^i}\right\rfloor + \left\lfloor\frac{n}{p^i}\right\rfloor + 1 = 1$

Quedando siempre sumas de números positivos en las potencias de los factores implicados, los coeficientes binomiales son siempre enteros.

[teclado]

No consigo tampoco modificar el enlace para que dirija al post original en Twitter, pero está aquí:
https://twitter.com/edusadeci/status/1154702602552139776
En él se comenta que son las formas de ordenar 5300 elementos en 100 grupos de tamaño 53, por lo que debería ser entero. Pero no me queda claro cómo llegan a esa conclusión.
También he intentado resolverlo haciendo la misma sustitución que usé aquí para los coeficientes binomiales, pero llego a que me sale una suma en la que los términos tienen la forma:
$(n(m \mod p^i)+n \mod p^i-(mn) \mod p^i - n)/p^i$, así que estoy atascado.

[teclado]

En tu caso te estás olvidando de un 53 adicional en el numerador debido al 2809, que es 53 al cuadrado.

[Richard R Richard]

Hahaha ya veo donde me equivoco


El 53 es un numero primo,el numerador 5300! tiene 101 veces al número 53 como divisor pues entre sus factores está el 53, el 106, el 159 ...5300 o bien $1\cdot 53,2\cdot 53,3\cdot53,.....53\cdot 53,.....,100\cdot 53$y el denominador tiene 100 veces al 53 solo cuando elevas a la 100 el factorial de 53, mas una vez mas en el factorial de 100, luego, puede ser que un numero entero sea ese cociente. ...vere si puedo mejorarlo si tanta teoría de grupos...

si quiero contar la cantidad de grupos con diferentes elementos de un total de 5300 elementos de forma que que haya 100 grupos de 53 elementos cada uno, lo hayas haciendo la formula que expones, luego como esa cantidad es una cuenta, es decir arranca en 1 y termina en ese valor de conjuntos, luego es un número entero....