proving that $\frac{(n^2)!}{(n!)^n}$ is an integer

Question

How to prove that $$\frac{(n^2)!}{(n!)^n}$$ is always a positive integer when n is also a positive integer. NOTE i want to prove it without induction. I just cancelled $n!$ and split term which are $n^2-(a^2)=(n-a)(n+a)$ where a is a perfect square. nothing more i could do.

Answer 1

There are $n^2$ things of which:

1. $n$ things are of $1$st kind,
2. $n$ things are of $2$nd kind,
3. $n$ things are of $3$rd kind,
4. $n$ things are of $4$th kind, and so on till
5. $n$ things are of $n$th kind.

So the number of ways in which you can arrange the $n^2$ things is an $\mathbf{integer}$ and is equal to $\frac{(n^2)!}{(n!)^n}$

Answer 2

In general if $m_1+\cdots+m_k=m$ then the number of ways to split up let's say $m$ persons in $k$ groups having sizes $m_1,\dots,m_k$ equals: $$\frac{m!}{m_1!\times\cdots\times m_k!}$$

Here you are dealing with special case $m=n^2$ and $m_i=n$ for $i=1,\dots,k=n$.

Answer 3

Here is an answer that is number theoretic as opposed to the combinatorial one from Vera. It is based on two simple facts. For any prime $p$:

1. For any $m$, $m\times\left\lfloor\frac{m}{p}\right\rfloor\le\left\lfloor\frac{m^2}{p}\right\rfloor$.
2. For any $m$, the number of times $p$ divides $m!$ is $\sum_{i=1}^\infty\left\lfloor\frac{m}{p^i}\right\rfloor$.

Therefore:

The number of times $p$ divides $(n!)^n$ is $n$ times the number of times it divides $n!$, i.e. $\sum_{i=1}^\infty n\times\left\lfloor\frac{n}{p^i}\right\rfloor$. (S1)

The number of times $p$ divides $(n^2)!$ is $\sum_{i=1}^\infty \left\lfloor\frac{n^2}{p^i}\right\rfloor$. (S2)

By Fact 1, every term in the sum (S2) is at least as large as every term in the sum (S1) which means that every prime divides $(n^2)!$ at least as many times as it divides $(n!)^n$. Therefore $(n^2)!/(n!)^n$ must be an integer.

Answer 4

$S_n \times S_n \times \cdots \times S_n$ is a subgroup of $S_{n^2}$.

The number in question is the index of that subgroup and thus an integer by Lagrange's theorem.

Answer 5

Just notice that we can always "cancel" a denominator factor of $n!$ by the following:

$$\binom{n^2}{n}={(n^2)!\over(n(n-1))!n!}={\prod_{k=n^2-n+1}^{n^2}k_0\over n!}\text{ is an integer}\\ \binom{n(n-1)}{n}={(n(n-1))!\over(n(n-2))!n!}={\prod_{k=n^2-2n+1}^{n(n-1)}k_1\over n!}\text{ is an integer}\\ \vdots\\ \binom{2n}n={(2n)!\over n!n!}\text{ is an integer}$$

The above process occurs $n$ times, producing our quantity $(n^2)!\over (n!)^n$ as an integer by "divisibility chain".