show the formula always gives an integer
$$\frac{(2m)!(2n)!}{m!n!(m+n)!}$$
I don't remember where I read this problem, but it said this can be proved using a simple counting argument (like observing that $\frac{(3m)!}{m!m!m!}$ is just the number of ways of permuting m identical things of type 1, m of type-2 and m of type-3).
I found this paper
whose abstract says:
It is well known that the numbers $\frac{(2m)!(2n)!}{m!n!(m+n)!}$ are integers, but in general there is no known combinatorial interpretation for them. When $m = 0$ these numbers are the middle binomial coefficients ${2n \choose n}$, and when $m = 1$ they are twice the Catalan numbers. In this paper, we give combinatorial interpretations for these numbers when $m = 2$ or $3$.
According to the authors, the first appearance of the problem of whether it's always an integer is in this note by Catalan:
E. Catalan, Question 1135, Nouvelles Annales de Mathematiques 13 (1874), 207.
Barry's comments to this post below point out an incorrect solution to the problem in a more general form was given by Bourguet here:
and the error was pointed out (and corrected?) by Catalan here:
E. Catalan, Correspondance, Nouvelles Annales de Mathematiques 14 (1875) 178-180.
Also in a comment to this post, Karan gave a link to a paper that proves the numbers in question are integers by a recurrence relation:
Edit: The numbers in question are apparently called super Catalan numbers, and I just found this paper whose abstract says, "we show that the super Catalan numbers are special values of the Krawtchouk polynomials by deriving an expression for the super Catalan numbers in terms of a signed set."
You can show that $\frac{(2m)!(2n)!}{m!n!(m+n)!}$ is an integer by showing that each prime number $p$ divides the numerator at least as many times as it divides the denominator. For that it suffices to show that $$\lfloor\frac{2m}{p^k}\rfloor+\lfloor\frac{2n}{p^k}\rfloor\ge\lfloor\frac{m}{p^k}\rfloor+\lfloor\frac{n}{p^k}\rfloor+\lfloor\frac{m+n}{p^k}\rfloor$$ for natural $k$, i.e., that $$\lfloor2x\rfloor+\lfloor2y\rfloor\ge\lfloor x\rfloor+\lfloor y\rfloor+\lfloor x+y\rfloor$$ where $x=\frac{m}{p^k},y=\frac{n}{p^k}$. In fact, the latter inequality is easily seen to hold for all $x$ and $y$.
In an answer to "Integer valued factorial ratios," Aaron Meyerowitz pointed out that
$$f(m,n) = \frac{(2m)! (2n)!}{m! n! (m+n)!}$$
satisfies $f(0,t) = {2t \choose t}$ and $f(i+1,j) = 4f(i,j) - f(i,j+1)$. So, by induction on the first parameter, $f(m,n)$ is an integer.
This leads to the summation
$$f(m,n) = \sum_{k=0}^m (-1)^k 4^{m-k} {m\choose k} {2(n+k)\choose n+k}.$$
This is similar, but not the same as the recurrence for $f(m,n)/2$ in Callan's paper mentioned by karan and in Yuichiro Fujiwara's answer:
$$f(m,n)/2 = \sum_{k \ge 0} 2^{n-m-2k} {n-m \choose 2k} f(m,k)/2.$$
These are both consequences of $4f(m,n) = f(m+1,n) + f(m,n+1)$ in Gessel, Super Ballot Numbers, J. Symbolic Computation 14 (1992), 179–194. Section 6 of that paper covers the above recurrences and more, including
$$f(m,n) = \sum_k (-1)^k {2m \choose m+k}{2n \choose n-k}$$
$$f(m,n) = (-1)^m 4^{m+n} {m-1/2 \choose m+n}.$$
Here are two comments. First, the formula $f(m,n) = (-1)^m 4^{m+n}\binom{m-1/2}{m+n}$ noted by Douglas Zare should be $$f(m,n) = (-1)^n 4^{m+n}\binom{m-1/2}{m+n}.$$ (The mistake is in my paper.) It follows that $f(m,n)$ is $(-1)^m$ times the coefficient of $x^{m+n}$ in $$(1-4x)^{m-1/2} = \left(\frac{1}{\sqrt{1-4x}}\right)^{1-2m} =\biggl(\sum_{k=0}^\infty \binom{2k}{k} x^k\biggr)^{1-2m}. $$ and is therefore an integer.
Second, the recurrence $$f(m,n) = \sum_{k \ge 0} 2^{n-m-2k} {n-m \choose 2k} f(m,k)$$ mentioned by Douglas (equivalent to a special case of Vandermonde's theorem), together with the symmetry $f(m,n) = f(n,m)$, shows by induction that the $f(m,n)$ are positive integers. (Other formulas show either that $f(m,n)$ is an integer or that it is positive, but not both.) So it gives a combinatorial interpretation for $f(m,n)$ in the sense that one can use this recurrence to recursively construct a set of cardinality $f(m,n)$. But no one has so far been able to give a nonrecursive description of these objects in general. (David Callan did this in the case $m=2$, for $f(2,n)/2$.)
For what it's worth, the problem (and a related one) was posed in the American Mathematical Monthly, 1910 (vol. 17, no. 6/7, pg. 150) and a solution given in 1911 (vol. 18, no. 2, pp. 41-43).
I am unable to suggest a $\textbf{combinatorial}$ interpretation of the fact that $~Q(m,n)=\dfrac{(2m)!(2n)!}{m!n!(m+n)!}~$ is an integer (and I do not pretend that what follows is original...) but the result itself is a easy consequence of the two simple propositions :
a) $~\forall x\in \mathbb{R}~~\forall y\in \mathbb{R}~~\lfloor x \rfloor+\lfloor x+y \rfloor+\lfloor y \rfloor~\leq~\lfloor 2x \rfloor+\lfloor 2y \rfloor,~$
b) if, for $~p~$ prime and $~m~$ integer $~\geq 1,~$ we name $~v_p(m)~$ the exponent of $~p~$ in the prime decomposition of $~m,~$ then $~v_p(m!)=\sum\limits_{k\geq 1}\Big\lfloor\dfrac{m}{p^k}\Big\rfloor.~$
Indeed, for all prime $~p~$ and all integers $~m,~n~$ $\geq 1,~$
$v_p(Q(m,n))=\sum\limits_{k\geq 1}\Big(\Big\lfloor\dfrac{2m}{p^k}\Big\rfloor+\Big\lfloor\dfrac{2n}{p^k}\Big\rfloor-\Big\lfloor\dfrac{m}{p^k}\Big\rfloor-\Big\lfloor\dfrac{n}{p^k}\Big\rfloor-\Big\lfloor\dfrac{m+n}{p^k}\Big\rfloor\Big)~\geq 0,$ what was to be shown.
