proving that $\frac{(n^2)!}{(n!)^n}$ is an integer 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. 
 A: There are $n^2$ things of which:

  
*
  
*$n$ things are of $1$st kind, 
  
*$n$ things are of $2$nd kind,
  
*$n$ things are of $3$rd kind,
  
*$n$ things are of $4$th kind, and so on till
  
*$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}$
A: 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$.
A: 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$:


*

*For any $m$, $m\times\left\lfloor\frac{m}{p}\right\rfloor\le\left\lfloor\frac{m^2}{p}\right\rfloor$.

*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.
A: 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".
A: $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.
