Mostrar que $n!^{n+1}$ divide $(n^2)!$

Question

Mi intento, hasta ahora, es por inducción. Deje $f(n) = \frac{(n^2)!}{n!^{n+1}}$, voy a tratar de mostrar que $f(n)$ es un entero positivo para todos los $n$.

Tenemos $f(0) = \frac{0!}{0!^{n+1}} = 1$.

Ahora suponga para la inducción, que $f(n) = k$ para algún entero positivo k.

A continuación, voy a examinar $f(n+1) = \frac{((n+1)^2)!}{(n+1)!^{n+2}}$.

Tenga en cuenta que $(n+1)!^{n+2} = [(n+1)(n)!]^{n+2} = (n+1)^{n+2}(n)!^{n+2} = (n+1)^{n+2}(n)!(n)!^{n+1}$.

Y que $(n+1)!^2 = \frac{(n+1)^2!}{n^2!}n^2!$

Por lo $f(n+1) = \frac{\frac{(n+1)^2!}{n^2!}n^2!}{(n+1)^{n+2}(n)!(n)!^{n+1}} = \frac{\frac{(n+1)^2!}{n^2!}}{(n+1)^{n+2}(n)!} \frac{(n^2)!}{n!^{n+1}} = \frac{\frac{(n+1)^2!}{n^2!}}{(n+1)^{n+2}(n)!}k$.

Además, puedo demostrar que $\frac{(n+1)^2!}{n^2!} = \prod_{i=0}^{2n}{(n+1)^2-i}$.

Y aquí es donde yo no se cómo proceder. Algún consejo? Estoy dispuesto a chatarra de todo esto y empezar de cero como esto se siente como un callejón sin salida.

Answer 1

Aquí está una combinatoria de prueba:

Organizar $n^2$ persona $n^2$ sillas en fila, tenemos $n^2!$ maneras.

Alternativamente, se puede recoger $n$ personas para la primera $n$ sillas, a continuación, $n$ personas para sillas de $n+1$$2n$, $n$ personas $2n + 1$$3n$,, etc,, a continuación, organizar cada grupo de $n$ de las personas, tenemos $\left(\prod_{k=0}^{n-1}{n^2-kn \choose n}\right)(n!)^n$ formas

Por lo $$n^2! = \left(\prod_{k=0}^{n-1}{n^2-kn \choose n}\right)(n!)^n$$

Entonces solo tenemos que demostrar $n!$ divide $\prod_{k=0}^{n-1}{n^2-kn \choose n}$.

Denotar por $K$el número de maneras de dividir $n^2$ de las personas en la no-ordenó $n$ grupos, cada uno de los cuales contiene $n$ de las personas , entonces realmente podemos señalar

$$\prod_{k=0}^{n-1}{n^2-kn \choose n} = Kn!$$

debido a $\prod_{k=0}^{n-1}{n^2-kn \choose n}$ es la forma de dividir $n^2$ personas en ordenadas $n$ grupos, cada uno de los cuales contiene $n$ de las personas.

Ahora ya está hecho. En resumen, para organizar $n^2$ persona $n^2$ sillas en fila($n^2$! maneras), podemos dividirlos en no-ordenó $n$ grupos de igual tamaño($K$ formas), hacer una permutación de los grupos($n!$ formas) y, a continuación, hacer permutaciones dentro de cada grupo($(n!)^n$ formas). Así que tenemos $$(n^2)! = K (n!)^{n+1}$$