Using permutation or otherwise, prove that $\frac{(n^2)!}{(n!)^n}$ is an integer,where $n$ is a positive integer. [duplicate]
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.!!
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)!$
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}$.