# Using permutation or otherwise, prove that $\frac{(n^2)!}{(n!)^n}$ is an integer,where $n$ is a positive integer. [duplicate]

This question already has an answer here:

Using permutation or otherwise, prove that $\displaystyle \frac{(n^2)!}{(n!)^n}$ is an integer,where $n$ is a positive integer.

I have no idea how to prove this..!!I am not able to even start this Can u give some hints or the solution.!cheers.!!

## marked as duplicate by user354271, Namaste algebra-precalculus StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Sep 4 '17 at 16:48

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• You can proceed using Legendre's formula. – Samrat Mukhopadhyay Aug 14 '13 at 16:41
• what is that?i have no idea about this/ – maths lover Aug 14 '13 at 16:45
• look at the reference I've given (Click on "Legendre's formula"). – Samrat Mukhopadhyay Aug 14 '13 at 16:46
• without this is it possible? – maths lover Aug 14 '13 at 16:47
• This is the number of partitioning $n^2$ object into $n$ groups each has $n$ elements. – achille hui Aug 14 '13 at 16:51

## 4 Answers

Looking up the sequence on OEIS you notice this is the number of arrangements of $1, 2, 3, \ldots, n^2$ in an $n\times n$ matrix such that each row is increasing and thus is an integer.

You can verify this by using combinatorics to calculate the number of such arrangements. Given an empty $n\times n$ matrix and a bucket with the numbers $1, 2, 3, \ldots, n^2$, to fill each row of the matrix with increasing numbers you have to choose $n$ numbers from the bucket for each row of the matrix. So the number of such arrangements has to be $\binom{n^2}{n} \binom{n(n-1)}{n} \binom{n(n-2)}{n} \cdots \binom{n}{n}$. When you write out the binomial coefficients in terms of factorials you notice that the denominator of each factor contains the nominator of the next factor and the whole product simplifies to $\frac{(n^2)!}{(n!)^n}$.

One can do a little better. We have $n^2$ people, to be divided into $n$ teams, each of which has $n$ people. Let $w$ be the number of ways to do the job.

Do the division into teams this way. Line up the $n^2$ people, put the first $n$ into a team, then the next $n$, and the next, and so on.

Permuting the people in each group of $n$ does not change the division into teams. This permuting can be done in $(n!)^n$ ways. Also, permuting the groups does not change the division into teams. It follows that $$w=\frac{(n^2)!}{(n!)^{n+1}}.$$ So we get the stronger result that $(n!)^{n+1}$ divides $(n^2)!$.

Remark: In the same way, one can show that $n!(m!)^n$ divides $(mn)!$.

Let $H$ be the subgroup of $S_{n^2}$ consisting of all permutations $\sigma$ for which the following holds: if $kn \lt m \le (k+1)n$, then $kn \lt \sigma (m) \le (k+1)n.$ Then $H$ separately permutes the numbers $$1, 2, ..., n; n+1, ..., n+n=2n; 2n+1, ..., 3n; ...; kn+1, kn+2, ..., (k+1)n; ...; n(n-1), ..., n^2,$$ so $H$ is isomorphic to $(S_n)^n$. Hence $|H| = |(S_n)^n| = |S_n|^n = (n!)^n$, but by Lagrange's theorem $|H|$ divides $|S_{n^2}|=(n^2)!$

Remark : For every (prime) number $p$: $$n \cdot \lfloor \dfrac{n}{p^{\alpha}} \rfloor \leq \lfloor \dfrac{n^2}{p^{\alpha}} \rfloor \ .$$ Proof : Let's denote by $m$ and $p$ the integral part and fractional part of $\dfrac{n}{p^{\alpha}}$

$$m=\lfloor \dfrac{n}{p^{\alpha}} \rfloor \ \ \ \ \ \text{and} \ \ \ \ \ p=\lfloor \dfrac{n}{p^{\alpha}} \rfloor \ ;$$ then one can see easilly that : $$\dfrac{n}{p^{\alpha}}=m+p \Longrightarrow \dfrac{n^2}{p^{\alpha}}=n \cdot m + n \cdot p \Longrightarrow \\ n \cdot \lfloor \dfrac{n}{p^{\alpha}} \rfloor = n \cdot m = \lfloor n \cdot m \rfloor \leq \lfloor \dfrac{n^2}{p^{\alpha}} \rfloor \ .$$

Remark (II) : For every prime number $p$: $$n \cdot \sum \lfloor \dfrac{n}{p^{\alpha}} \rfloor \leq \sum \lfloor \dfrac{n^2}{p^{\alpha}} \rfloor \ \ \Longrightarrow \\ \ \ \ \ \ n \cdot v_p(n!) \leq v_p\Big((n^2)!\Big) \Longrightarrow \\ \ \ \ v_p(n! ^n) \leq v_p\Big((n^2)!\Big) \ .$$

Remark (III) : $$n! ^n \mid (n^2)! \ .$$