MHB Is (m²)/(m)² always an integer?

[anemone]

Prove that $\dfrac{m^2!}{(m!)^2}$ is an integer, where $m$ is a positive integer.

 

[Nono713]

Prove that $\dfrac{m^2!}{(m!)^2}$ is an integer, where $m$ is a positive integer.

Spoiler

Suppose a prime power $p^{2k}$ divides $(m!)^2$. It must be of the form $2k$, since $(m!)^2$ is a square. By Euclid's lemma, $p^k$ must divide $m!$, that is, $p$ divides $m!$ $k$ times. This implies that the first $k$ multiples of $p$ appear in the factorial product $m!$, since $p$ is prime. And $p \geq 2$ hence $2p \leq p^2$ and it follows that:
$$k p \leq m ~ ~ ~ \implies ~ ~ ~ 2 k p \leq k^2 p^2 \leq m^2$$
Thus the first $2k$ multiples of $p$ appear in the factorial product $(m^2)!$, and so $p^{2k}$ also divides $(m^2)!$. So the fraction is reducible to an integer in that every prime power in the denominator also appears in the numerator, QED.​

 

[anemone]

Spoiler

Suppose a prime power $p^{2k}$ divides $(m!)^2$. It must be of the form $2k$, since $(m!)^2$ is a square. By Euclid's lemma, $p^k$ must divide $m!$, that is, $p$ divides $m!$ $k$ times. This implies that the first $k$ multiples of $p$ appear in the factorial product $m!$, since $p$ is prime. And $p \geq 2$ hence $2p \leq p^2$ and it follows that:
$$k p \leq m ~ ~ ~ \implies ~ ~ ~ 2 k p \leq k^2 p^2 \leq m^2$$
Thus the first $2k$ multiples of $p$ appear in the factorial product $(m^2)!$, and so $p^{2k}$ also divides $(m^2)!$. So the fraction is reducible to an integer in that every prime power in the denominator also appears in the numerator, QED.​

Good job, Bacterius! And thanks for participating!

I will share with you and MHB the combinatorial proof of other, as in this case, I think the proof of it is pretty good and straightforward. :)

Spoiler

Let there be $m^2$ objects distributed in $m$ groups, each group containing $m$ identical objects. So the number of arrangement of these $m^2$ objects are $\dfrac{m^2!}{(m!)^m}$ and the the number of arrangements has to be an integer.

 

[mathbalarka]

Spoiler

$$\frac{(n^2)!}{(n!)^2} = \frac{(2n)! \cdot (2n + 1) \cdot (2n + 2) \, \cdots \, n^2}{(n!)^2} = \frac{(2n)!}{n! \cdot n!} \cdot k = \binom{2n}{n} \cdot k$$

As $k = (2n + 1)(2n + 2) \, \cdots \, n^2$ is an integer and binomial coefficients are all integers from their combinatorial interpretation, $(n^2)!/n!^2$ is also an integer.

 

[anemone]

Spoiler

$$\frac{(n^2)!}{(n!)^2} = \frac{(2n)! \cdot (2n + 1) \cdot (2n + 2) \, \cdots \, n^2}{(n!)^2} = \frac{(2n)!}{n! \cdot n!} \cdot k = \binom{2n}{n} \cdot k$$

As $k = (2n + 1)(2n + 2) \, \cdots \, n^2$ is an integer and binomial coefficients are all integers from their combinatorial interpretation, $(n^2)!/n!^2$ is also an integer.

Bravo, mathbalarka!(Yes) And thanks for participating!

 

[kaliprasad]

Good job, Bacterius! And thanks for participating!

I will share with you and MHB the combinatorial proof of other, as in this case, I think the proof of it is pretty good and straightforward. :)

Spoiler

Let there be $m^2$ objects distributed in $m$ groups, each group containing $m$ identical objects. So the number of arrangement of these $m^2$ objects are $\dfrac{m^2!}{(m!)^2}$ and the the number of arrangements has to be an integer.

Spoiler

The above is not quite correct.

it should be
So the number of arrangement of these $m^2$ objects are $\dfrac{m^2!}{(m!)^m}$

kindly note that the power is m in denominator and not 2

 

[anemone]

Spoiler

The above is not quite correct.

it should be
So the number of arrangement of these $m^2$ objects are $\dfrac{m^2!}{(m!)^m}$

kindly note that the power is m in denominator and not 2

the power is m in denominator and not 2

Ops...you're absolutely right. The solution I posted refers to the problem where the exponent in the denominator should be $m$. Sorry to MHB and all members and guests who have read this thread...

Thanks to you kaliprasad for pointing this out to me. I have edited my post (#3) to fix it.