División de Factoriales [los coeficientes binomiales son enteros]

Question

Tengo una partición de un entero positivo $(p)$ . ¿Cómo puedo demostrar que el factorial de $p$ siempre se puede dividir por el producto de los factoriales de las partes?

Como ejemplo rápido $\frac{9!}{(2!3!4!)} = 1260$ (sin resto), donde $9=2+3+4$ .

Puedo casi verlo mirando los factores, pero no veo la forma de garantizarlo.

Answer 1

A continuación se presenta un esbozo de un puramente aritmético prueba de que los coeficientes binomiales son integrales. He construido la prueba a propósito para que sea comprensible para un profano en la materia. La prueba da un algoritmo para reescribir un coeficiente binomial como un producto de fracciones cuyos denominadores son coprimos de cualquier primo dado. El método de demostración se comprende mejor aplicando el algoritmo a un ejemplo concreto.
[ Nota: Puede resultar útil leer primero este ejemplo más sencillo antes de pasar a la exposición siguiente].

Por ejemplo, considere $\ \ \binom{39}{17}\: =\: \frac{39!}{22! \; 17!}\: =\: \frac{23 \cdot 24 \cdots\; 39}{1 \cdot 2 \cdots\; 17}.\, $ Cuando esta fracción se reduce a los términos más bajos $\rm\:a/b,\, $ no prime $\rm\ p > 17\ $ puede dividir su denominador $\rm\: b,\: $ desde $\rm\ b\:|\:17\:!\ \:$ Por lo tanto, para demostrar que $\rm\ a/b\ $ es un número entero, basta con demostrar que ningún primo $\rm\ p \le 17\ $ divide su denominador $\rm\: b$ .

Por ejemplo, demostramos que $2$ no divide $\rm b$ . El mayor poder de $2$ en los términos del denominador es $16 < 17$ . Alinear los numeradores y denominadores $\rm (mod\ 16)$ desplazando el primer término del numerador para que quede por encima de su valor $\!\bmod 16,\,$ a saber $\,\color{#c00}{23 \equiv 7} \pmod{\!16}$ por lo que hay que desplazar a la derecha los términos del numerador hasta $23\:$ se encuentra por encima de $7$

$$\color{#0a0}{\frac{}{1}\frac{}{2}\frac{}{3}\frac{}{4}\frac{}{5}\frac{}{6}}\color{#c00}{\frac{23}{7}}\frac{24}{8}\frac{25}{9}\frac{26}{10}\frac{27}{11}\frac{28}{12}\frac{29}{13}\frac{30}{14}\frac{31}{15}\frac{32}{16}\frac{33}{17}\color{#0a0}{\frac{34}{}\frac{35}{}\frac{36}{}\frac{37}{}\frac{38}{}\frac{39}{}}$$

Afirmamos que $2$ no divide el denominador reducido de cada fracción alineada. En efecto, $\ 24/8 = 3$ , $\: 26/10 = 13/5 $ , $\:\ 28/12 = 7/3 $ , $\:\ 30/14 = 15/7 $ , $\:\ 32/16 = 2$ . Esto es así porque estas fracciones $\rm\; c/d \;$ satisfacer $\,\rm c \equiv d\ (mod\ 16)\:$ es decir $\rm c = d + 16\: n \;$ así que $\,\rm 2|d \Rightarrow 2|c$ , $\rm\; 4|d \Rightarrow 4|c$ , $\:\cdots $ , $\rm\; 16|d \Rightarrow 16|c$ , es decir, cualquier potencia de $2\:$ debajo de $16$ que divide $\rm d$ también debe dividir $\rm c$ por lo que se anula al reducirse.

Por lo tanto, para demostrar que $2$ no divide el denominador reducido de $\binom{39}{17}$ basta con demostrar lo mismo para la fracción "sobrante" $\,\color{#0a0}{(34 \cdots 39)/(1 \cdots 6) = \binom{39}{6}}\,$ compuesto de los términos no alineados anteriores. Siendo un $\rm\binom{n}{k}$ con más pequeños $\rm k = 6 < 17,\,$ esto se deduce por inducción.

Como la misma prueba funciona para cualquier primo $\rm p$ concluimos que ningún primo divide el denominador reducido de $\binom{39}{17}$ Por lo tanto, es un número entero. $\quad$ QED

Informalmente, la razón por la que esto funciona es porque la secuencia del denominador comienza en $1$ que es coprima de todos los primos $\rm p$ . Esto asegura que es la secuencia contigua de enteros más "verde" posible, en el sentido de que su producto contiene la menor potencia de $\rm\:p\:$ en comparación con otras secuencias contiguas de igual longitud.

El algoritmo se extiende a los multinomios utilizando la simple reducción de los multinomios a productos de binomios mencionada en mi anterior post aquí.

Answer 2

La forma de "alto nivel" de ver esto es recordar que siempre que un grupo finito $G$ tiene un subgrupo $H$ sabemos que $|H|$ divide $|G|$ . A continuación, observe que $S_n$ contiene claramente $S_{n_1} \times ... \times S_{n_k}$ como subgrupo para cualquier partición $n_1 + ... + n_k = n$ . (En realidad, esto es lo mismo que la interpretación combinatoria en la respuesta de Robin Chapman, ya que lo que estamos contando es el número de cosets $G/H$ y estos cosets son precisamente lo que cuenta el teorema multinomial).

Este lema básico es sorprendentemente útil. Por ejemplo, no es difícil utilizarlo para demostrar que $m! (n!)^m$ divide $(mn)!$ .

Answer 3

Estos cocientes son enteros ya que resuelven problemas de conteo. Por ejemplo, ¿cuántas palabras de nueve letras hay con 2 A, 3 B y 4 C?

Para ver la historia completa, consulte el teorema del multinomio .

Answer 4

Si crees (:-) en el caso de Newton de dos partes, entonces el resto se obtiene fácilmente por inducción. Por ejemplo (para motivarte a escribir una prueba completa):

$$\frac{9!}{2! \cdot 3! \cdot 4!}\ =\ \frac{9!}{5!\cdot 4!}\cdot \frac{5!}{2!\cdot 3!}$$

Answer 5

Además de las interpretaciones combinatorias obvias, también se tiene la siguiente reducción de coeficiente multinomial a productos de coeficientes binomiales. A saber, para $n = i+j+k+\cdots + m $

$$ \frac{n!}{i!j!k!\cdots m!} = \binom{n}{i} \frac{(n-i)!}{j!k!\cdots m!} = \binom{n}{i}\binom{n-i}{j} \frac{(n-i-j)!}{k!\cdots m!} = \;\cdots$$