# How to prove that $\frac{(5m)!(5n)!}{(m!)(n!)(3m+n)!(3n+m)!}$ is a natural number?

How to prove that $$\frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!}$$ is a natural number $$\forall m,n\in\mathbb N$$ , $$m\geqslant 1$$ and $$n\geqslant 1$$?

If $$p$$ is a prime, then the number of times $$p$$ divides $$N!$$ is $$e_p(N)=\sum_{k=1}^\infty\left\lfloor\frac{N}{p^k}\right\rfloor$$. So I need $$e_p(5m)+e_p(5n)\geq e_p(m)+e_p(n)+e_p(3m+n)+e_p(3n+m).$$ What to do next? Thanks in advance.

Let $p$ be a prime number. You should show that

$$\left\lfloor \frac{5m}{p^k}\right\rfloor+\left\lfloor \frac{5n}{p^k}\right\rfloor \geq \left\lfloor \frac{m}{p^k}\right\rfloor+\left\lfloor \frac{n}{p^k}\right\rfloor+\left\lfloor \frac{3m+n}{p^k}\right\rfloor+\left\lfloor \frac{3n+m}{p^k}\right\rfloor$$

for $k \geq 1.$ By Hermite's identity you will get

$$\left\lfloor \frac{5m}{p^k}\right\rfloor=\left\lfloor \frac{m}{p^k}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{1}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{2}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{3}{5}\right\rfloor+\left\lfloor \frac{m}{p^k}+\frac{4}{5}\right\rfloor$$

Then you should show that

$$\sum_{i=1}^{4} \left\lfloor \frac{m}{p^k}+\frac{i}{5}\right\rfloor+\sum_{j=1}^{4}\left\lfloor \frac{n}{p^k}+\frac{j}{5}\right\rfloor \geq \left\lfloor \frac{3m+n}{p^k}\right\rfloor+\left\lfloor \frac{3n+m}{p^k}\right\rfloor$$

which can be done by considering different cases for the values $\frac{m}{p^k}, \frac{n}{p^k}$ i.e. each can be in the following intervals $(0,\frac15), [\frac15, \frac25), [\frac25, \frac35), [\frac35, \frac45), [\frac45, 1),$ since $\lfloor x+n \rfloor=\lfloor x\rfloor+n,$ for and real number $x$ and an integer $n,$ you can just ignore the case when $\frac{m}{p^k}, \frac{n}{p^k}$ are bigger that $1.$

Earlier thought: The expression can be rewritten as

$$\frac{\binom{5m}{3m}(3m)!\binom{5n}{n}n!}{(3m+n)!} \frac {\binom{4n}{3n}(3n)!\binom{2m}{m}m!}{(3n+m)!}$$

I was hoping to find a combinatorial interpretation for this expression but I haven't found yet!

If $m=n$ this is $\binom{5m}{m} ^ 2$

Assume $m>n$

$$\frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!}$$

$$= \frac{(4m+(m-n)+n)! \cdot (4n-(m-n)+m)!}{m! \cdot n! \cdot (4m-(m-n))! \cdot (4n+(m-n))!}$$

$$= \frac{(4m-(m-n)+n+2(m-n))! \cdot (4n+(m-n)+m-2(m-n))!}{n! \cdot (4m-(m-n))! \cdot m! \cdot (4n+(m-n))!}$$

$$= \binom{4m-(m-n)+n}{n}\cdot\frac{(4m-(m-n)+n+2(m-n))!}{(4m-(m-n)+n)!} \cdot\binom{4n+(m-n)+m}{m}\cdot\frac{(4n+(m-n)+m-2(m-n))!}{(4n+(m-n)+m)!}$$

$$= \binom{3m+2n}{n}\cdot\frac{(5m)!}{(3m+2n)!} \cdot\binom{3n+2m}{m}\cdot\frac{(5n)!}{(3n+2m)!}$$

$$= \binom{3m+2n}{n} \cdot\frac{(5m)!}{(3m+2n)!} \cdot\frac{(5m-(3m+2n))!}{(5m-(3m+2n))!} \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3n+2m)!}$$

$$\cdots 5n<3n+2m$$

$$= \binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot (5m-(3m+2n))! \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3n+2m)!}$$

$$= \binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m} \cdot \frac{(2m-2n)! (5n)!}{(3n+2m)!}$$

$$= \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m}} {\binom{3n+2m}{5n}}$$

Consider the last factor and the denominator: $$\frac{\binom{3n+2m}{m}} {\binom{3n+2m}{5n}}$$ $$= \frac{\frac{(3n+m)\cdots(3n+2m)}{m!}} {\frac{(2m-2n)\cdots(2m+3n)}{(5n)!}}$$ $$= {\frac{(m+3n)\cdots(2m+3n)}{(2m-2n)\cdots(2m+3n)}} \cdot {\frac{(5n)!}{m!}}$$

Cases: ($m\le5n$ or $m>5n$) and ($m+3n<2m-2n$ or $m+3n\ge2m-2n$)
i.e. ($m\le5n$ or $m>5n$) and ($5n<m$ or $5n\ge m$)
i.e. $m\le5n$ or $m>5n$

Case: $m\le5n$ i.e. $2m-2n \le m+3n$
$$= {\frac{(m+1)\cdots(5n)}{(2m-2n)\cdots(m+3n-1)}}$$

Case: $m>5n$ i.e. $2m-2n > m+3n$
$$= {\frac{(m+3n)\cdots(2m-2n-1)}{(5n+1)\cdots(m)}}$$

There's probably a simple final step now that I don't know/see at the moment...

Alternatively:

$$= \binom{3m+2n}{n} \cdot\frac{(5m)!}{(3n+2m)!} \cdot\frac{(5m-(3n+2m))!}{(5m-(3n+2m))!} \cdot\binom{3n+2m}{m} \cdot\frac{(5n)!}{(3m+2n)!}$$

$$\cdots 5n<3m+2n$$

$$= \binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m} \cdot\frac{(3m-3n)! (5n)!}{(3m+2n)!}$$

$$= \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m}} {\binom{3m+2n}{5n}}$$

Another:

$$\frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!}$$

$$= \frac{(5m)!}{m!(4m)!}\cdot(4m)! \cdot \frac{(5n)!}{n!(4n)!}\cdot(4n)! \cdot \frac{1} {(3m+n)! \cdot (3n+m)!}$$

$$= \frac{(5m)!}{m!(4m)!} \cdot \frac{(5n)!}{n!(4n)!} \cdot \frac{(4m)!\cdot(4n)!} {(4m-(m-n))! \cdot (4n+(m-n))!}$$

$$= \frac{(5m)!}{m!(4m)!} \cdot \frac{(5n)!}{n!(4n)!} \cdot \frac{(4m)!} {(4m-(m-n))!(m-n)!} \cdot\frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!}$$

$$= \frac{\binom{5m}{m}\binom{5n}{n}\binom{4m}{m-n}}{\binom{4n+(m-n)}{m-n}}$$

$$\dots \space\text{using} \space\binom{n}{r}\binom{n-r}{k}=\binom{n}{k}\binom{n-k}{r}$$

$$= \frac{\binom{5n}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{4n+(m-n)}{m-n}}$$

$$= \frac{\binom{5n}{n}\binom{4n}{k}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{4n}{k}\binom{4n+(m-n)}{m-n}}$$

$$\dots \space\text{and again for some}\space k : \space 0\leq k\leq 4n$$

$$= \frac{\binom{5n}{k}\binom{5n-k}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{4n+(m-n)-k}{m-n}\binom{4n+(m-n)}{k}}$$

$$\dots \space\text{try}\space k=2n$$

$$= \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{2n+(m-n)}{2n}\binom{4n+(m-n)}{2n}}$$

Just considering $\frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!}$ ($= 1/\binom{4n+(m-n)}{m-n}$):

$$\frac{(m-n)!\cdot(4n)!} {(4n+(m-n))!}$$

$$= \frac{(m-n)!^2(4n-(m-n))!\cdot(4n-(m-n)+(m-n))!} {(4n+(m-n))!(4n-(m-n))!(m-n)!}$$

$$= \frac{(m-n)!^2(5n-m)!} {(3n+m)!} \cdot\binom{4n}{m-n} \dots \text{if } 5n>m$$

and this is clearly an integer if $5n-m>3n+m$ i.e. $n>m$, but we've assumed the opposite :-(

A possibly better "assumption": Assume $m=k+n>n$

$$\frac{(5m)! \cdot (5n)!}{m! \cdot n! \cdot (3m+n)! \cdot (3n+m)!}$$

$$= \frac{(5k+5n)! \cdot (5n)!}{(k+n)! \cdot n! \cdot (3k+4n)! \cdot (4n+k)!}$$

Applied to the above results:

$$= \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3m+2n} \cdot\binom{3n+2m}{m}} {\binom{3n+2m}{5n}}$$

$$= \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{3k+5n} \cdot\binom{5n+2k}{k+n}} {\binom{5n+2k}{5n}}$$

$$= \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{2k} \cdot\binom{5n+2k}{k+n}} {\binom{5n+2k}{2k}}$$

. . .

$$= \frac{\binom{3m+2n}{n} \cdot\binom{5m}{3n+2m} \cdot\binom{3n+2m}{m}} {\binom{3m+2n}{5n}}$$

$$= \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{5n+2k} \cdot\binom{5n+2k}{n+k}} {\binom{3k+5n}{5n}}$$

$$= \frac{\binom{3k+5n}{n} \cdot\binom{5k+5n}{3k} \cdot\binom{5n+2k}{n+k}} {\binom{3k+5n}{3k}}$$

. . .

$$= \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5m}{m-n}\binom{5m-(m-n)}{m}}{\binom{2n+(m-n)}{2n}\binom{4n+(m-n)}{2n}}$$

$$= \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5n+5k}{k}\binom{5n+4k}{n+k}}{\binom{2n+k}{2n}\binom{4n+k}{2n}}$$

$$= \frac{\binom{5n}{2n}\binom{3n}{n}\binom{5n+5k}{k}\binom{5n+4k}{n+k}}{\binom{2n+k}{k}\binom{4n+k}{2n}}$$

This is USAMO'1975 Problem 1. A proof requires the lemma below. However, I would love to see a combinatorial proof.

Lemma. Let $$x,y\geq 0$$. Then, $$\lfloor 5x\rfloor +\lfloor 5y\rfloor \geq \lfloor x\rfloor +\lfloor y\rfloor+\lfloor 3x+y\rfloor +\lfloor x+3y\rfloor$$.

Proof. Without loss of generality, suppose that $$0\leq x,y<1$$. Otherwise, replace $$x$$ and $$y$$ by $$x-\lfloor x\rfloor$$ and $$y-\lfloor y\rfloor$$, respectively. Thus, the claim becomes $$\lfloor 5x\rfloor+\lfloor 5y\rfloor\geq \lfloor 3x+y\rfloor+\lfloor x+3y\rfloor\text{ for }0\leq x,y<1\,.\tag{*}$$

Take $$u:=\lfloor 5x\rfloor$$ and $$v:=\lfloor 5y\rfloor$$, then $$u,v\in\{0,1,2,3,4\}$$, $$\dfrac{u}{5}\leq x < \dfrac{u+1}{5}\,,$$ and $$\dfrac{v}{5}\leq y<\dfrac{v+1}{5}\,.$$ Therefore, $$\frac{3u+v}{5}\leq 3x+y<\frac{3u+v+3}{5}$$ and $$\frac{u+3v}{5}\leq x+3y<\frac{u+3v+3}{5}\,.$$ By symmetry, we may assume further that $$u\leq v$$.

For convenience, write $$a:=\lfloor 3u+v\rfloor$$ and $$b:=\lfloor u+3v\rfloor$$. We need to show that $$u+v\geq a+b$$.

• If $$(u,v)=(0,0)$$, then obviously $$a=b=0$$, whence (*) is an equality.

• If $$(u,v)=(0,1)$$, then $$a=0$$ and $$b\in\{0,1\}$$, so (*) is again true.

• If $$(u,v)=(0,2)$$, then $$a=0$$ and $$b=1$$, so (*) is a strict inequality.

• If $$(u,v)=(0,3)$$, then $$a\in\{0,1\}$$ and $$b\in\{1,2\}$$, so (*) is true.

• If $$(u,v)=(0,4)$$, then $$a\in\{0,1\}$$ and $$b=2$$, so (*) is a strict inequality.

• If $$(u,v)=(1,1)$$, then $$a,b\in\{0,1\}$$, so (*) is true.

• If $$(u,v)=(1,2)$$, then $$a=b=1$$, so (*) is a strict inequality.

• If $$(u,v)=(1,3)$$, then $$a=1$$ and $$b=2$$, so (*) is a strict inequality.

• If $$(u,v)=(1,4)$$, then $$a=1$$ and $$b\in\{2,3\}$$, so (*) is a strict inequality.

• If $$(u,v)=(2,2)$$, then $$a,b\in\{1,2\}$$, so (*) is true.

• If $$(u,v)=(2,3)$$, then $$a,b\in\{1,2\}$$, so (*) is a strict inequality.

• If $$(u,v)=(2,4)$$, then $$a=2$$ and $$b\in\{2,3\}$$, so (*) is a strict inequality.

• If $$(u,v)=(3,3)$$, then $$a=b=2$$, so (*) is a strict inequality.

• If $$(u,v)=(3,4)$$, then $$a\in\{2,3\}$$ and $$b=3$$, so (*) is a strict inequality.

• If $$(u,v)=(4,4)$$, then $$a=b=3$$, so (*) is a strict inequality.

I became aware of this question due to some recent edits. The shorter proofs seem to rely on $$\lfloor5x\rfloor+\lfloor5y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor+\lfloor3x+y\rfloor+\lfloor3y+x\rfloor$$ My answer also uses this inequality. I have tried to provide a complete, yet shorter, proof of it.

Define $$f(x,y)=\lfloor5x\rfloor+\lfloor5y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor-\lfloor3x+y\rfloor-\lfloor3y+x\rfloor\tag1$$ Note that $$f(x+1,y)=f(x,y+1)=f(x,y)$$. Thus, we only need worry about $$x,y\in[0,1)$$.

Let $$x\in\left[\frac j5,\frac{j+1}5\right)$$ and $$y\in\left[\frac k5,\frac{k+1}5\right)$$, where $$j,k\in\{0,1,2,3,4\}$$. Then $$\lfloor x\rfloor=\lfloor y\rfloor=0\tag{2a}$$ $$\lfloor5x\rfloor=j\qquad\text{and}\qquad\lfloor5y\rfloor=k\tag{2b}$$ $$\lfloor3x+y\rfloor\le\left\lfloor\frac{3j+k+3}5\right\rfloor \qquad\text{and}\qquad \lfloor x+3y\rfloor\le\left\lfloor\frac{j+3k+3}5\right\rfloor \tag{2c}$$ Apply $$(2)$$ to $$(1)$$: \begin{align} f(x,y) &=\lfloor5x\rfloor+\lfloor5y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor-\lfloor3x+y\rfloor-\lfloor3y+x\rfloor\\ &\ge j+k-\left\lfloor\frac{3j+k+3}5\right\rfloor-\left\lfloor\frac{j+3k+3}5\right\rfloor\\ &=g(j,k)\tag3 \end{align} Compute the values of $$g(j,k)$$ for $$j,k\in\{0,1,2,3,4\}$$: $$\begin{array}{c|cc} g&0&1&2&3&4\\\hline 0&0&0&0&0&0\\ 1&0&0&0&1&0\\ 2&0&0&0&1&1\\ 3&0&1&1&0&1\\ 4&0&0&1&1&2 \end{array}\tag4$$ Inequality $$(3)$$, table $$(4)$$, and the lattice periodicity of $$f$$, show that $$f(x,y)\ge0$$ for all $$x,y$$. That is, $$\lfloor5x\rfloor+\lfloor5y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor+\lfloor3x+y\rfloor+\lfloor3y+x\rfloor\tag5$$ Inequality $$(5)$$, when combined with Legendre's Formula, yields $$m!\,n!\,(3m+n)!\,(m+3n)!\mid(5m)!\,(5n)!\tag6$$