2
$\begingroup$

How to prove that $$\frac{(n^2)!}{(n!)^n}$$ is always a positive integer when n is also a positive integer. NOTE i want to prove it without induction. I just cancelled $n!$ and split term which are $n^2-(a^2)=(n-a)(n+a)$ where a is a perfect square. nothing more i could do.

$\endgroup$
5
$\begingroup$

There are $n^2$ things of which:

  1. $n$ things are of $1$st kind,
  2. $n$ things are of $2$nd kind,
  3. $n$ things are of $3$rd kind,
  4. $n$ things are of $4$th kind, and so on till
  5. $n$ things are of $n$th kind.

So the number of ways in which you can arrange the $n^2$ things is an $\mathbf{integer}$ and is equal to $\frac{(n^2)!}{(n!)^n}$

$\endgroup$
4
$\begingroup$

In general if $m_1+\cdots+m_k=m$ then the number of ways to split up let's say $m$ persons in $k$ groups having sizes $m_1,\dots,m_k$ equals: $$\frac{m!}{m_1!\times\cdots\times m_k!}$$

Here you are dealing with special case $m=n^2$ and $m_i=n$ for $i=1,\dots,k=n$.

$\endgroup$
  • $\begingroup$ Yes, it's like a permutation of $n^2$ objects with $n$ different objects, each occurring $n$ times. $\endgroup$ – SS_C4 Mar 5 '16 at 15:05
3
$\begingroup$

Here is an answer that is number theoretic as opposed to the combinatorial one from Vera. It is based on two simple facts. For any prime $p$:

  1. For any $m$, $m\times\left\lfloor\frac{m}{p}\right\rfloor\le\left\lfloor\frac{m^2}{p}\right\rfloor$.
  2. For any $m$, the number of times $p$ divides $m!$ is $\sum_{i=1}^\infty\left\lfloor\frac{m}{p^i}\right\rfloor$.

Therefore:

The number of times $p$ divides $(n!)^n$ is $n$ times the number of times it divides $n!$, i.e. $\sum_{i=1}^\infty n\times\left\lfloor\frac{n}{p^i}\right\rfloor$. (S1)

The number of times $p$ divides $(n^2)!$ is $\sum_{i=1}^\infty \left\lfloor\frac{n^2}{p^i}\right\rfloor$. (S2)

By Fact 1, every term in the sum (S2) is at least as large as every term in the sum (S1) which means that every prime divides $(n^2)!$ at least as many times as it divides $(n!)^n$. Therefore $(n^2)!/(n!)^n$ must be an integer.

$\endgroup$
2
$\begingroup$

$S_n \times S_n \times \cdots \times S_n$ is a subgroup of $S_{n^2}$.

The number in question is the index of that subgroup and thus an integer by Lagrange's theorem.

$\endgroup$
2
$\begingroup$

Just notice that we can always "cancel" a denominator factor of $n!$ by the following:

$$\binom{n^2}{n}={(n^2)!\over(n(n-1))!n!}={\prod_{k=n^2-n+1}^{n^2}k_0\over n!}\text{ is an integer}\\ \binom{n(n-1)}{n}={(n(n-1))!\over(n(n-2))!n!}={\prod_{k=n^2-2n+1}^{n(n-1)}k_1\over n!}\text{ is an integer}\\ \vdots\\ \binom{2n}n={(2n)!\over n!n!}\text{ is an integer}$$

The above process occurs $n$ times, producing our quantity $(n^2)!\over (n!)^n$ as an integer by "divisibility chain".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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