I think it is quite a well known fact that $\binom{m+n}{n}$ divides $\binom{2n}{n}\cdot \binom{2m}{m}$.
Unfortunately, every proof I'm aware of of this theorem consists of estimating the $p$-adic exponents (I mean, I'm familiar only with purely algebraic proofs).
What I'm looking for is purely combinatorial interpretation of this identity. Any ideas?
They could publish this if someone figures this out... it's an open problem.
When dividing, this problem boils down to showing that S(n,m) is an integer where S(m,n) is defined as such,
$$ S(m,n) = \frac{(2n)!(2m)!}{(m+n)!n!m!} $$
These are known as the super-Catalan numbers, a generalization of the Catalan numbers and I believe a general combinatorial interpretation of the super-Catalan numbers is still an open problem since the 1870s. There have been characterizations of the sequences for restricted values of $n$ and $m$, for example, $m=1$ gives the Catalan numbers, $m=2$ can be characterized by "balanced blossom trees" and "pairs of Dyck paths".
This paper by David Callan has a few more examples.
If anyone else is interested, the algebraic proof is fairly straight forward (from this student's dissertation).
Landau states the exact highest power of the prime to divide $n!$ is
$$\sum_{i=1}^\infty\left\lfloor \frac{n}{p^i}\right\rfloor$$
Thus, we must simply show that for all primes $p$ the highest power of the denominator is at most that of the numerator.
$$\sum_{i=1}^\infty\left\lfloor \frac{m}{p^i}\right\rfloor + \left\lfloor \frac{n}{p^i}\right\rfloor + \left\lfloor \frac{m+n}{p^i}\right\rfloor \leq \sum_{i=1}^\infty\left\lfloor \frac{2m}{p^i}\right\rfloor +\left\lfloor \frac{2n}{p^i}\right\rfloor$$
follows from the identity $\lfloor x\rfloor + \lfloor y\rfloor + \lfloor x+y\rfloor \leq \lfloor 2x\rfloor + \lfloor 2y\rfloor$ for all $x$, $y$.