# Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

Prove that $\dfrac{(n^2)!}{(n!)^n}$ is an integer for every $n \in \mathbb{N}$

I know that there are tools in Number theory to proves the required but I want to use the tool that says that if you can prove that an expression solves a combinatorial problem then it represents an integer for every $n \in \mathbb{N}$

My solution is, assume we are given $n^2$ beads, $n$ beads in every color of $n$ colors, and we want to place them in a row ($(n^2)!$) now since we have $n$ groups of colors and every group has $n$ beads in it, we need to cancel the inner sort of each of the groups, which gives us $(n!)^n$ for all the possible inner sorts of the beads.

Will that proof work? What are its flaws?

• Your argument is correct. In slightly more generality, the multinomial coefficient $$\displaystyle \binom{n_1+n_2+\cdots n_k}{n_1,n_2, \cdots, n_k} = \frac{(n_1+n_2+\cdots n_k)!}{n_1!n_2!\cdots n_k!}$$ counts the number of permutations of a multiset with $k$ different elements occurring with multiplicities $n_i, 1 \leq i \leq k$, and your problem is the special case when $k = n$ and all the $n_i$ equal $n$. This is exactly what the accepted answer is saying but without using the name multinomial coefficient which is sometimes useful to know. Commented Jun 22, 2013 at 3:21
• This is quite an improvement on the fact we usually see, $\frac {(n^2)!}{2^nn!}$ is an integer. Commented Jun 22, 2013 at 3:29

Note that $\dfrac{(a+b)!}{a! b!}$ is an integer. In general, $$\dfrac{\left(\displaystyle \sum_{k=1}^m a_k \right)!}{\displaystyle \prod_{k=1}^m a_k!}$$ is an integer. The above can be shown to be an integer by a combinatorial argument. Consider $\displaystyle\sum_{k=1}^m a_k$ balls, where $a_l$ balls are of color '$l$'. Then the number of possible arrangements of these balls in a straight line is given by $\dfrac{\left(\displaystyle \sum_{k=1}^m a_k \right)!}{\displaystyle \prod_{k=1}^m a_k!}$, which is an integer.

In your case, take $m=n$ and $a_k = n$, $\forall k \in \{1,2,\ldots,n\}$.

• Which means in other words that my combinatorial proof is O.K, right? :) Commented Jun 21, 2013 at 20:22
• @Georgey Yes. ${}{}$
– user17762
Commented Jun 21, 2013 at 20:23

The argument can be continued to give an additional $n!$ of divisibility.

After removing the redundancy of the inner ordering within the groups, the groups can be sorted relative to each other (by least element, or in any other way that gives a unique order).

Hence $\frac{(n^2)!}{(n!)^{n+1}}$ is an integer, equal to the number of partitions of $n^2$ different objects into $n$ sets of $n$.

• And you can't increase that $n+1$ to $n+2$ because that fails for $n=2$. Commented Jun 22, 2013 at 4:24
• Or any prime $n$. But when $n$ is square or a perfect power I think there may be additional factors. @martycohen
– zyx
Commented Jun 22, 2013 at 4:57

To add a little formalism, you can prove that $n$ copies of the symmetric group $S_n$ is a subgroup of $S_{n^2}$ by considering $n$ disjoint supports of size $n$. Then Lagrange's theorem concludes the proof. Essentially, this is the same proof as yours.
The product of $n$ consecutive integers is divisible by $n!$, therefore, the product of $kn$ consecutive integers (in particular when $k=n$) is divisible by $(n!)^k$. In particular:
$\dfrac{(n^2)!}{(n!)^n}=\dbinom n n\dbinom{2n}n\dbinom{3n}n\dots\dbinom{n^2}n=\dbinom{n^2}{n,n,n,\dots,n}$.