¿$\forall m,n\in\mathbb Z$, $m\ge1$ $n\ge1$ cómo probar que $$\frac{(mn)!}{m!(n!)^m}$ $ es un número entero?
Gracias de antemano.
Respuestas
¿Demasiados anuncios?
Oli
Puntos
89
Contamos con un grupo de $mn$ de la gente, y queremos dividir en $m$ equipos de $n$ personas cada uno. Su expresión es precisamente el número de maneras de hacerlo. Puesto que la expresión de los recuentos de algo, debe ceder siempre un número entero.
Para contar el número de maneras de dividir el grupo en $m$ de los equipos, lo primero que contar el número de maneras de dividir en equipos que se vestirán de colores uniformes $C_1,C_2,\dots,C_m$.
La línea de la gente. Hay $(mn)!$ maneras de hacer esto. Tome el primer grupo de $n$, asignar los uniformes $C_1$, y así sucesivamente. Este overcounts el número de maneras de dividir a los uniformados en los equipos, ya que cualquier permutación de la primera $n$ de la gente, seguido por cualquier permutación de la próxima $n$, y así sucesivamente, se obtiene la misma subdivisión de uniformados equipos. De ello se desprende que hay $\dfrac{(mn)!}{(n!)^m}$ divisiones en uniformado equipos.
Cualquier permutación de los colores uniformes de los rendimientos de la misma división en uniformless equipos. Por lo que el número de maneras de dividir el grupo en equipos es $\dfrac{1}{m!}\dfrac{(mn)!}{(n!)^m}$
Geoff Robinson
Puntos
17610
OK, ya que se han dado soluciones explícitas, voy a dar el enfoque del grupo teórico explícitamente. El grupo simétrico $S_{nm}$ tiene un subgrupo $S_{n} \wr S_{m}.$ este es un producto semidirecto de una base de grupo $B$ con el grupo simétrico $S_{m}.$ el grupo base $B$ es un producto directo de ejemplares de $m$de % de $S_{n},$ y estos factores son permutada alrededor por el $S_{m}$ que actúa en $B.$ el grupo $S_{n} \wr S_{m}$ por lo tanto tiene orden $m!(n!)^{m},$ que se divide el $(mn)!$ por el teorema de Lagrange.
Abhra Abir Kundu
Puntos
6773
Dividir la expresión $(mn)!$ en m grupos de cada grupo que consiste de la nos. $\{(kn+1)(kn+2).....((k+1)n)\}$, aquí k se ejecuta de $0$ $m-1$
Así tenemos ,$\displaystyle (mn)!=\prod_{k=0}^{m-1}(kn+1)(kn+2).....((k+1)n)$
En cada grupo de la primera $n-1$ nos es divisible por $(n-1)!$ como m grupos para que el total del producto es divisible por $((n-1)!)^m$ (Utilizando el hecho de que el producto de $k$ consecutivo nos es divisible por $k!$)
Producto de los últimos a nos. el grupo es $\displaystyle \prod_{k=0}^{m-1}(k+1)n=m!.n^m$
Así que todo el producto es divisible por $((n-1)!)^m.m!.n^m=m!(n!)^m$
Por lo tanto demostrando el hecho de que $\displaystyle \frac{(mn)!}{m!(n!)^m}$ es un número entero.
Math Gems
Puntos
14842
Utilice telescopy: $\rm\:f(0),\ f(k+1)/f(k)\in \Bbb Z\ \Rightarrow\: f(m)\in \Bbb Z\ $ desde
$$\rm f(0)\ \ \prod_{k\:=\:0}^{m-1}\ \frac{f(k+1)}{f(k)}\ \ = \ \ \ \color{red}{\rlap{--}f(0)}\frac{\color{green}{\rlap{--}f(1)}}{\color{red}{\rlap{--}f(0)}}\frac{\color{royalblue}{\rlap{--}f(2)}}{\color{green}{\rlap{--}f(1)}}\frac{\phantom{\rlap{--}f(3)}}{\color{royalblue}{\rlap{--}f(2)}}\ \ \cdots\ \ \frac{\color{brown}{\rlap{----}f(m-1)}}{\phantom{\rlap{--}f(m-2)}}\frac{f(m)}{\color{brown}{\rlap{----}f(m-1)}}\ =\ \ f(m) $$
De hecho, uno verifica rápidamente $\displaystyle\rm\,\ f(m) \,=\, \dfrac{(mn)!}{m!\,(n!)^{\,m}}\ \Rightarrow\ \dfrac{f(m\!+\!1)}{f(m)} \,=\, {mn\!+\!n\!-\!1\choose n\!-\!1}\in \Bbb Z\ \quad {\bf QED}$
Nota $\ $ Nota telescopy multiplicative reduce la prueba a un trivial cálculo mecánico. Absolutamente ningún ingenio se requiere. Sistemas de álgebra computacional pueden construir fácilmente tales pruebas.
Si escribimos el producto obtenido de la telescopy obtenemos
$$\rm \dfrac{(mn)!}{m!\,(n!)^{\,m}}\ =\ {n\!-\!1\choose n\!-\!1}{2n\!-\!1\choose n\!-\!1} {3n\!-\!1\choose n\!-\!1}\cdots {(m\!+\!1)n\!-\!1\choose n\!-\!1}$$
Esto es equivalente al producto que L.F. declaró desde
$$\rm \frac{1}k {kn\choose n}\, =\, \frac{(kn)!}{k\, n!\, (kn\!-\!n)!} \,=\, \frac{kn (kn\!-\!1)!}{kn \,(n\!-\!1)!\, (kn\!-\!n)!} \,=\, {kn-1\choose n-1}$$
