Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.!!

share|improve this 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
6  
This is the number of partitioning $n^2$ object into $n$ groups each has $n$ elements. –  achille hui Aug 14 '13 at 16:51

3 Answers 3

up vote 2 down vote accepted

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}$.

share|improve this answer

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)!$

share|improve this answer

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)!$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.