Proving $(n!)^n | (n^2)!$

Question

If we can say n is a natural number, then prove that $(n!)^n \mid (n^2)!$. I want a process involving variables only. Please help me.

Answer 1

If you have an $n\times n$ grid of cells, and you want to fill those cells with $n$ of each number from $1$ to $n$ so that there is one number in each cell, then $$ \frac{(n^2)!}{(n!)^n} $$ is the number of different ways you can do that, and therefore it has to be an integer.

Different example (which is actually the same example of you look closely): You have $n^2$ people, and you need to divide them into teams: a red team, a blue team, a green team, and so on. There are $n$ different teams, and each team must have $n$ people in them. Then there are $\frac{(n^2)!}{(n!)^2}$ different ways to assign people to these teams.

Answer 2

The given value is the multinomial coefficient $\binom{n^2}{n \cdots n}$. It's thus the coefficient of $x_1^n \cdots x_n^n$ in $(x_1 + \cdots + x_n)^{n^2}$, for example, and in particular is an integer.

Answer 3

We can consider $(S_n)^n = S_n \times S_n \times \dots \times S_n$ as a subgroup of $S_{n^2}$ Just let the first copy act on the first $n$ elements in an $n^2$ element set, the second copy on the next $n$ elements etc. This gives a faithful action of $(S_n)^n$ on an $n^2$ element set, hence an embedding $(S_n)^n \hookrightarrow S_{n^2}$.

We get $(n!)^n \mid (n^2)!$ by Lagrange's theorem.

---

Edit: This method can be generalized to show that the multinomial coefficient $\displaystyle \frac{(n_1 + \ldots + n_k)!}{n_1! \cdot \ldots \cdot n_k!}$ mentioned in other answers is an integer.

Consider $S_{n_1} \times S_{n_2} \times \dots \times S_{n_k}$ and let this group act on an $n_1 + n_2 + \dots + n_k$ element set by having the first factor act on the first $n_1$ elements, the second on the next $n_2$ elements, etc. giving an embedding $S_{n_1} \times S_{n_2} \times \dots \times S_{n_k} \hookrightarrow S_{n_1 + \ldots + n_k}$. Then the statement follows again by Lagrange's theorem.

---

Edit 2:

With more careful use of group theory, we can even prove a stronger statement.

Consider the semidirect product $S_n \rtimes (S_n)^n$ where $S_n$ acts on $(S_n)^n$ by permuting the different factors (This is also called a wreath product)

We can define an action of $S_n \rtimes (S_n)^n$ on an $n^2$ set as follows: Partition the $n^2$ set in $n$ subsets of $n$ elements. We let the left factor $S_n$ of $S_n \rtimes (S_n)^n$ act by permuting the $n$ subsets and let each factor of $(S_n)^n$ act on one of the $n$ subsets. These actions interact in the right way to define an action of the semidirect product $S_n \rtimes (S_n)^n$, which is also faithful. We get an embedding $S_n \rtimes (S_n)^n \hookrightarrow S_{n^2}$ and we get $(n!)^{n+1} \mid (n^2)!$ by Lagrange's theorem.