Demostrar que $(mn)!$ es divisible por $(n!)\cdot(m!)^n$

Question

Demostrar que

$$(n!)\cdot(m!)^n|(mn)!$$

Puedo demostrar que el uso de Legendre de la Fórmula, pero tengo que usar el lema que

$$ \dfrac{\displaystyle\left(\sum_{i=1}^na_i\right)!}{\displaystyle\prod_{i=1}^na_i!} \in \mathbb{N} $$

Creo que se puede probar usando el lema, ya que en esta respuesta de Qiaochu Yuan se ha mencionado, de modo que al final de su respuesta.

Cualquier ayuda será apreciada.
Gracias.

Answer 1

Tener en cuenta que han $mn$ bolas con $n$ diferentes colores y $m$ bolas de cada color. El número de posibles arreglos se $$(mn)!\over (m!)^n$$.

Sin embargo, cada arreglo ha $n!$ "simétrica disposiciones", es decir, si cambiamos de color entre grupos enteros obtenemos una disposición simétrica. I. E. por ejemplo, si tenemos tres de color R,G,B, a continuación, $RGRBGB$ $GRGBRB$ son simétricas acuerdo mediante el intercambio de colores $R$$G$.

Por lo tanto $(mn)!\over (m!)^n$ es un múltiplo de a $n!$.

Answer 2

Deje $a,b$ ser enteros no negativos. Desde ${b+a\choose a}=\frac{(b+a)!}{a!\;b!}$ es un número entero, sabemos que $$a!\;|\;(b+1)\cdot\ldots\cdot(b+a)={b+a\choose a}\;/\;b! \tag{*}$$

Ahora vamos a utilizar la inducción en $n$ a resolver el problema original.

Para $n=0$, la instrucción es trivialmente cierto. Supongamos que tiene de $n-1$ donde $n \ge 1$. Entonces tenemos

$$\begin{align} n! \cdot (m!)^n &= n\cdot m!\cdot\left((n-1)!\cdot(m!)^{n-1}\right)\\ &\stackrel{hyp.}|n\cdot m! * (mn - m)!\\ &=n\cdot m!\cdot(mn)!\;/\;\left((mn-m+1)\ldots(mn)\right)\\ &=(m-1)!\cdot(mn)!\;/\;\left((mn-m+1)\ldots(mn-1)\right)\\ &\stackrel{(*)}|(mn)! \end{align}$$

Answer 3

De hecho esto se deduce a partir del Teorema de Lagrange: la corona de producto $S_m\wr S_n$ es un subgrupo del grupo simétrico $S_{mn}$. Uno puede ver $S_m\wr S_n$ como el conjunto de permutaciones que preservar la partición del conjunto de $\{\{1,\cdots,m\},\{m+1,\cdots,2m\},\cdots,\{(n-1)m+1,\cdots,nm\}\}$. Si llamamos a las partes de esta partición $X_1,\cdots,X_n$, entonces la elección de un elemento de la estabilizador de cantidades para la elección de una permutación $\sigma:\{1,\cdots,n\}\to\{1,\cdots,n\}$ y, a continuación, para cada una de las $1\le i\le n$ elegir un bijection $X_i\to X_{\sigma(i)}$, por lo que hay $n! m!^n$ elementos en el estabilizador.

Answer 4

Es fácil utilizar el coeficiente multinomial \begin{align*} \frac{\left(\sum_{j=0}^na_j\right)!}{\prod_{j=0}^na_j!}=\binom{a_1+a_2+\cdots+a_n}{a_1,a_2,\ldots,a_n} \in\mathbb{N} \end{align*} para mostrar que \begin{align*} (m!)^n=\prod_{j=1}^nm!\left|\left(\sum_{j=1}^nm\right)!\right.=(mn)! \end{align*}

Esto lamentablemente es demasiado menos sofisticados, ya que también tenemos que respetar el factor de $n!$ y queremos mostrar que \begin{align*} n!(m!)^n\left|(mn)!\right. \end{align*}

Otra idea:

Al considerar $(mn)!$ organizamos el $m\cdot n$ factores $n$ bloques de tamaño $m$ \begin{align*} ((j-1)&m+1)((j-1)m+2)\cdots((j-1)m+m)\tag{1}\\ &=((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\qquad 1\leq j \leq n \\ \end{align*}

Ya para $0\leq m \leq k$ \begin{align*} \binom{k}{m}&=\frac{k!}{m!(k-m)!}\\ &=\frac{(k-m+1)\cdot(k-m+2)\cdots(k-1)\cdot k}{m!}\in\mathbb{N} \end{align*} vemos que el producto de $m$ enteros consecutivos, $\geq 1$ se divide por $m!$. A partir de (1) podemos concluir que para $1\leq j\leq n$ \begin{align*} j( m!)\left|((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\right.\tag{2} \end{align*} observando que en el $jm!=(jm)(m-1)!$ $(m-1)!$ divide el producto \begin{align*} \prod_{k=1}^{n-1}(((j-1)m+k)\qquad\qquad 1\leq j \leq n \end{align*} de la $m-1$ números consecutivos $(j-1)m+k, (k=1,\ldots,m-1)$.

$$ $$

Llegamos a la conclusión de:

\begin{align*} n!(m!)^n&=\left(\prod_{j=1}^nj\right)\left(\prod_{j=1}^nm!\right)\\ &=\prod_{j=1}^n(m-1)!(mj)\\ &\left|\ \prod_{j=1}^n((j-1)m+1)((j-1)m+2)\cdots(jm-1)(jm)\right.\tag{3}\\ &=(nm)!\\ \end{align*}

Comentario:

• En (3) se utiliza la divisibilidad de la propiedad (2)