Prove $(m!)^3(n!)^4|(3m)!(4n)!$ for all positive integers $m,n$

Question

I need to prove that $(3m)!(4n)!$ is divisible by $(m!)^3(n!)^4$ for all $m,n \in \mathbb{N} $

I think to prove that $(m!)^3|(3m)!$ and $(n!)^4|(4n)!$

That would mean that $(m!)^3(n!)^4|(3m)!(4n)!$

I use mathematical induction to prove that $(m!)^3|(3m)!$ and get lost proving $m+1$ step. I got $\frac{(3(m+1))!}{(m+1)!^3}=\frac{3(m+1)(3m)!}{(m+1)^3(m)!^3}=\frac{3(3m)!}{(m+1)^2(m)!^3}$

What should I do next? Maybe it is easier way to prove it?

Answer 1

The number of ways to put $3m$ objects into $3$ distinct bins with $m$ objects in each bin is given by the multinomial coefficient $$\binom{3m}{m,m,m}=\frac{(3m)!}{(m!)^3}$$ Hence the value must be an integer. Similarly we have $$\binom{4n}{n,n,n,n}=\frac{(4n)!}{(n!)^4}$$ ways to place $4n$ objects into $4$ distinct bins with $n$ objects in each bin.

Answer 2

In terms of Binomial Coefficients, $$ \frac{(3m)!}{m!^3}=\binom{3m}{m}\binom{2m}{m} $$ and $$ \frac{(4n)!}{n!^4}=\binom{4n}{n}\binom{3n}{n}\binom{2n}{n} $$

Answer 3

$$(m!)^3(n!)^4|(3m)!(4n)!$$

---

This is nowhere near as elegant as the first two answers, but I always liked the way it reduced the problem to a simpler problem.

Let's use the notation $p^k || N!$ to mean that $p^k \mid N!$ and $p^{k+1} \not \mid N!$.

Theorem. Legendre's Theorem Let $k = \sum_{i=1}^{\infty}\left\lfloor \dfrac{N}{p^i} \right\rfloor$. Then $p^k \| N!$.

Let $a$ be a positive integer. Then

• $p^k \| (N!)^a$ where $k = a\sum_{i=1}^{\infty}\left\lfloor \dfrac{N}{p^i} \right\rfloor$

• $p^K \| (aN)!$ where $K = \sum_{i=1}^{\infty}\left\lfloor \dfrac{aN}{p^i} \right\rfloor$

THEOREM. $(N!)^a \mid (aN)!$

Proof.

To show that $(N!)^a \mid (aN)!$ it will suffice to show that $a\left\lfloor \dfrac{N}{p^i} \right\rfloor \le \left\lfloor \dfrac{aN}{p^i} \right\rfloor$ for all positive integers $i$.

There exists non negative integers $t$ and $r$ such that $N = tp^i + r$ where $0 \le r \lt p^i$. Then

$\left\lfloor \dfrac{aN}{p^i} \right\rfloor = \left\lfloor \dfrac{atp^i + ar}{p^i} \right\rfloor = at + \left\lfloor \dfrac{ar}{p^i} \right\rfloor \ge at = a\left\lfloor \dfrac{N}{p^i} \right\rfloor$