# Prove by combinatorial method that $\frac{(2m)! \cdot (2n)!}{(m)! \cdot (n)! \cdot (m+n)!}$ is an integer [duplicate]

Prove that

$$\dfrac{(2m)! \cdot (2n)!}{(m)! \cdot (n)! \cdot (m+n)!}$$

is a positive integer, where $(m,n) \in \mathbb{Z^{+}}$

I have already solved it using Legendre's Formula which states that $$e_{p}(n)=\sum_{i=1}^{\infty} \bigg\lfloor \dfrac{n}{p^{i}} \bigg\rfloor$$

where $e_{p}(n)$ is the exponent of a prime $p$ in $n!$. For the problem it was sufficient to show that

$$e_{p}(2m) + e_{p}(2n) \ge e_{p}(m) + e_{p}(n) + e_{p}(m+n)$$

which I can show using the properties of floor function.

However, I'm seeking a combinatorial approach to this problem. For example, using basic combinatorics, I can show that the number of ways to divide $A$ objects into $k$ persons such that the $i^{th}$ person receives $a_{i}$ objects is

$$\dfrac{A!}{\displaystyle\prod_{i=1}^{k}{(a_{i})!}} = \dfrac{\left(\displaystyle\sum_{i=1}^k (a_{i})\right)!}{\displaystyle\prod_{i=1}^{k}{(a_{i})!}}$$

here, the set $\{a_{i}\}_{i=1}^k$ is exhaustive, i.e,

$A = \displaystyle\sum_{i=1}^k a_{i}$.

Using this, I can show the following numbers to be integer

• $\dfrac{(2m)! \cdot (2n)!}{[(m)!]^{2} \cdot [(n)!]^{2} }$

• $\dfrac{(2m)! \cdot (2n)!}{(m-n)! \cdot [(n)!]^2 \cdot (m+n)!}$ ; if $m \geq n$

• $\dfrac{(2m)! \cdot (2n)!}{(n-m)! \cdot [(m)!]^2 \cdot (m+n)!}$ ; if $n \geq m$

However, I can't seem to find a way to tackle this problem using my approach.

Edit: I'm specifically asking for an answer using my combinatorics approach as I've already solved it using the answer given in the other question.

Any help will be appreciated.
Thanks.

## marked as duplicate by Empy2, Cheerful Parsnip, Lord_Farin, user26486, Mark BennetMay 28 '15 at 20:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

• @Michael No, I've already solved it using that approach. I'm interested in a combinatorial approach. – Henry May 28 '15 at 15:49
• What you describe at the end is not really making full use of the situation, because the separate factors $(2m)!/m!^2$, $(2n)!/n!^2$, and $(2m)!/((m-n)!(m+n)!)$ if $m \geq n$ (or analogous expression if $n \geq m$) are all integers. – KCd May 28 '15 at 16:15
• Could the following link be of relevance?cs.uwaterloo.ca/journals/JIS/VOL8/Gessel/xin.pdf – wiskundeliefhebber May 28 '15 at 16:33

## 1 Answer

We just have to prove that $\binom{m+n}{m}$ divides $\binom{2m}{m}\cdot\binom{2n}{n}$.

So, we may imagine to have a parliament, with $2m$ members in the right wing and $2n$ members in the left wing. We may choose a committee with $n$ people from the left wing and $m$ people from the right wing in $\binom{2n}{n}\cdot\binom{2m}{m}$ ways, then we may choose $m$ chiefs of the committee in $\binom{m+n}{n}=\binom{m+n}{m}$ ways.

Now ask yourself: if all the choices are random, what is the probability that a left-wing or a right-wing member of the parliament will be elected chief of the committee?

Can you deduce that $\binom{m+n}{n}$ has to be a divisor of $\binom{2n}{n}\cdot\binom{2m}{m}$?

• I still don't get it. Can you please explain ? – Henry May 29 '15 at 5:04
• Sorry to bother you again. I haven't learnt theorems of probability yet (like Baye's Theorem etc.), but if you are asking that what is the probability that a left-wing or a right-wing member of the parliament will be elected chief of the committee, I think the answer would be $1$ (since there are only left and right wing members and chief of the committee would be chosen from them only) . If so, how does that answer my question? Please Help. – Henry May 29 '15 at 19:08
• Can you pleaseeeeeeeeeeeeeeee explain your method to me ???????????? – Henry May 30 '15 at 5:59
• @Samurai: only $m$ people out of $2m+2n$ are elected as chiefs, hence the probability for a single person to become chief is not one, for sure. – Jack D'Aurizio May 30 '15 at 8:38