¿Cómo es $\frac{n!}{n_1!\cdot n_2!\cdot...\cdot n_k!}$ es siempre un número entero?

Question

Posibles Duplicados:
La división de Factoriales

Para un conjunto de $n$ objetos de los cuales, $n_1$ son iguales y uno de una clase, $n_2$ son iguales y uno de una clase, ... , $n_k$ son iguales y uno de una clase, de tal manera que $n_1+n_2+...+n_k=n$, el número de permutaciones distinguibles es: $$\frac{n!}{n_1!\cdot n_2!\cdot...\cdot n_k!}$$ ¿Cómo es que este es siempre un número entero?

Answer 1

$${(n_1 + \dots + n_k)! \over n_1! \cdots n_k!} = \frac{n_1!}{n_1!} \cdot \frac{(n_1 + n_2)!}{n_1!n_2!} \cdot \frac{(n_1 + n_2 + n_3)!}{(n_1 + n_2)!n_3!} \cdots \frac{(n_1 + \dots + n_k)!}{(n_1 + \dots + n_{k-1})!n_k!} =\\ \binom{n_1}{n_1} \cdot \binom{n_1+n_2}{n_2} \cdot \binom{n_1+n_2+n_3}{n_3} \cdots \binom{n_1 + \dots + n_k}{n_k}$$

Answer 2

Se sigue por el Teorema Fundamental de la Aritmética y la potencia de un primo en un factorial:

Si $p$ es un número primo, el poder de la $p$ en la parte superior es

$$\sum_{m=1}^\infty \lfloor \frac{n_1+n_2+..+n_k}{p^m} \rfloor$$

mientras que el poder de la $p$ en el denominador es

$$\sum_{m=1}^\infty \lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor$$

Ahora, $\lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor$ es un número entero y

$$\lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor \leq \frac{n_1+n_2+..+n_k}{p^m}$$

así

$$\lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor \leq \lfloor \frac{n_1+n_2+..+n_k}{p^m} \rfloor$$

y por lo tanto

$$\sum_{m=1}^\infty \lfloor \frac{n_1}{p^m} \rfloor+ \lfloor \frac{n_2}{p^m} \rfloor+...+\lfloor \frac{n_k}{p^m} \rfloor \leq \sum_{m=1}^\infty \lfloor \frac{n_1+n_2+..+n_k}{p^m} \rfloor$$

Ahora, ya que todos los números primos aparecen en un mayor poder en el numerador, el TLC garantiza que este número es un entero.

Answer 3

Se puede demostrar que los $S_{n_1} \times S_{n_2} \times \ldots \times S_{n_k}$ es un subgrupo de $S_n$, la instrucción que sigue a continuación, a partir del teorema de Lagrange.