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.


marked as duplicate by Empy2, Cheerful Parsnip, Lord_Farin, user26486, Mark Bennet May 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.

  • 2
    $\begingroup$ @Michael No, I've already solved it using that approach. I'm interested in a combinatorial approach. $\endgroup$ – Henry May 28 '15 at 15:49
  • $\begingroup$ 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. $\endgroup$ – KCd May 28 '15 at 16:15
  • $\begingroup$ Could the following link be of relevance?cs.uwaterloo.ca/journals/JIS/VOL8/Gessel/xin.pdf $\endgroup$ – wiskundeliefhebber May 28 '15 at 16:33

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}$?

  • $\begingroup$ I still don't get it. Can you please explain ? $\endgroup$ – Henry May 29 '15 at 5:04
  • $\begingroup$ 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. $\endgroup$ – Henry May 29 '15 at 19:08
  • $\begingroup$ Can you pleaseeeeeeeeeeeeeeee explain your method to me ???????????? $\endgroup$ – Henry May 30 '15 at 5:59
  • $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio May 30 '15 at 8:38

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