<s>[INST] Show that $n!^{n+1}$ divides $(n^2)!$ My attempt so far is by induction. Let $f(n) = \frac{(n^2)!}{n!^{n+1}}$, I will try showing that $f(n)$ is a positive integer for all $n$.
We have $f(0) = \frac{0!}{0!^{n+1}} = 1$.
Now assume for induction, that $f(n) = k$ for some positive integer k.
Next, I'll examine $f(n+1) = \frac{((n+1)^2)!}{(n+1)!^{n+2}}$. 
Note that $(n+1)!^{n+2} = [(n+1)(n)!]^{n+2} = (n+1)^{n+2}(n)!^{n+2} = (n+1)^{n+2}(n)!(n)!^{n+1}$.
And that $(n+1)!^2 = \frac{(n+1)^2!}{n^2!}n^2!$
So $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$.
Additionally, I can show that $\frac{(n+1)^2!}{n^2!} = \prod_{i=0}^{2n}{(n+1)^2-i}$.
And this is where I don't how to proceed. Any tips? I'm willing to scrap all this and start from scratch as this feels like a dead end.
 [/INST] Here is a combinatorial proof:
Arrange $n^2$ person in $n^2$ chairs in a row, we have $n^2!$ ways.
Alternatively, we can pick $n$ persons for the first $n$ chairs, then $n$ persons for chairs $n+1$ to $2n$, then $n$ persons for $2n + 1$ to $3n$, etc, then arrange each group of $n$ persons, we have $\left(\prod_{k=0}^{n-1}{n^2-kn \choose n}\right)(n!)^n$ ways
So $$n^2! = \left(\prod_{k=0}^{n-1}{n^2-kn \choose n}\right)(n!)^n$$
Then we only need to prove $n!$ divides $\prod_{k=0}^{n-1}{n^2-kn \choose n}$. 
Denote by $K$the number of ways of dividing $n^2$ persons into non-ordered $n$ groups, each of which contains $n$ persons , then actually we can note 
$$\prod_{k=0}^{n-1}{n^2-kn \choose n} = Kn!$$
because $\prod_{k=0}^{n-1}{n^2-kn \choose n}$ is the way of dividing $n^2$ persons into ordered $n$ groups, each of which contains $n$ persons.
Now it's done. In summary, to arrange $n^2$ person in $n^2$ chairs in a row($n^2$! ways), we can divided them into non-ordered $n$ groups of equal size($K$ ways), make a permutation for those groups($n!$ ways), and then make permutations inside each group($(n!)^n$ ways). So we have $$(n^2)! = K (n!)^{n+1}$$
</s>