¿Cómo se puede probar esta propiedad factorial aparentemente fundamental que resulta de permutaciones básicas?

Answer 1

A veces, la visualización puede ayudar a comprender más que el rigor …
Aquí hay una prueba que enfatiza los pasos que se pueden visualizar.
Podría ser un poco vago en el rigor.

Reescribe x! / (A_1! *… A_n!) Como un producto de n fracciones, donde la fracción i-ésima tiene a_i como su denominador, y los siguientes términos i de la expansión de x! en su numerador

Por ejemplo, si x = 12 y a_1 = 3, a_2 = 4, a_3 = 5, n = 3, reescriba como …

(1 * 2 * 3) / (1 * 2 * 3) * (4 * 5 * 6 * 7) / (1 * 2 * 3 * 4) * (8 * 9 * 10 * 11 * 12) / (1 * 2 * 3 * 4 * 5)

Ahora, si podemos demostrar que cada fracción en el producto es un número entero, entonces se deduce que el producto también es un número entero.

Entonces todo lo que tenemos que demostrar es que

u * (u + 1) * (u + 2) *… * (u + k-1) / k !, es un número entero.

¡Esto es tan simple como probar que si un primo p divide a k! m veces, luego divide cualquier producto de k enteros positivos consecutivos al menos m veces.

Mira k! como una ventana de longitud k en los enteros. ¡Podemos deslizar la ventana hacia la derecha un espacio para obtener (k + 1)! / 1 !, o 2 espacios para obtener (k + 2)! / 2 !,
o n espacios para obtener (k + n)! / n !. Con cada turno, la longitud de la ventana es k.

Si k es lo suficientemente grande como para que la ventana original que comienza en 1 (¡con el producto k!) Contenga múltiples términos divisibles por un primo p, entonces podemos ver lo que sucede cuando deslizamos nuestra ventana hacia la derecha …

Para cualquier m, si p ^ m está en la ventana original, entonces tenemos que deslizar la ventana p ^ m espacios hacia la derecha antes de eliminar p ^ m de la ventana, pero el otro extremo de la ventana también mueve p ^ m espacios a la derecha, para una ventana de longitud k, la nueva ventana será el intervalo cerrado
[p ^ m + 1 … p ^ m + k]

… Pero como k> = p ^ m, podemos expresar k como p ^ m + d para algún número entero no negativo d.

Entonces el intervalo se puede expresar como
[p ^ m + 1 … 2 * p ^ m + d]

Por lo tanto, 2 * p ^ m está en el intervalo.

Entonces, a medida que perdemos poderes de p en el lado izquierdo de la ventana, ganamos al menos los mismos poderes de p en el lado derecho de la ventana.

Por lo tanto p ^ m | k! => p ^ m | x * (x + 1) *… * (x + k-1)

Por lo tanto, u * (u + 1) *… * (u + k-1) / k! es un entero

Por lo tanto, x! / (A_1! *… A_n!) Es un entero si sum (a_i) <= x

Answer 2

Primero suponga que [math] \ sum_ {i = 1} ^ n a_i = x [/ math]. Como señaló, podemos usar un argumento combinatorio para mostrar que este es un número entero, ya que cuenta la cantidad de formas de organizar x objetos de n tipos diferentes, en los que hay objetos de tipo [math] a_i [/ ​​math] yo.

Esta es en realidad una prueba perfectamente rigurosa. Tales pruebas son muy comunes en combinatoria. De hecho, a menudo se prefieren a las pruebas algebraicas, porque proporcionan más información sobre la estructura del problema.

Si la suma de nuestras [matemáticas] a_i [/ ​​matemáticas] es menor que x, entonces podemos aumentar [matemáticas] a_1 [/ matemáticas] hasta obtener una igualdad, es decir, [matemáticas] a’_1 = x – \ sum_ {i = 2} ^ n a_i [/ ​​math]. La fracción resultante será un número entero, según la prueba anterior.

Entonces podemos obtener la fracción original multiplicando por [math] \ frac {a’_1!} {A_1!} [/ Math], que será un número entero porque [math] a’_1> a_1 [/ math]. Entonces la fracción dada es un número entero.