# Show that this ratio of factorials is always an integer

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 am not sure this is appropriate for MO. That being said, the numerator is the size of the group $S_{2m} \times S_{2n}$ while the denominator is the size of the group $S_{m} \times S_{n} \times S_{m+n}$. The latter is easily seen to be a subgroup of the former. – Tony Huynh May 11 '13 at 6:58
@Tony: is it? That isn't clear to me. What embedding do you have in mind? – Qiaochu Yuan May 11 '13 at 7:01
@Qiaochu and Karan. Sorry, I think I spoke too soon. I was thinking of the case m=n in which the embedding was clear to me. I see that it's not clear what to do if m≠n. – Tony Huynh May 11 '13 at 7:21
I do not understand the closing of this question. A combinatorial interpretation of these integers seems to be lacking and this is surely a (nice, in my opinion) research question. Thus the question for a nice counting argument seems to be a valuable one. – Roland Bacher May 11 '13 at 16:14

I found this paper

I. M. Gessel, G. Xin, A Combinatorial Interpretation of the Numbers $6(2n!)/n!(n+2)!$, Journal of Integer Sequences 8 (2005) Article 05.2.3

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:

M. L. Barbier, Solutions des questions proposées dans les Nouvelles annales, Nouvelles Annales de Mathematiques 14 (1875) 66-92,

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:

D. Callan, A Combinatorial Interpretation for a Super-Catalan Recurrence, Journal of Integer Sequences, 8 (2005) Article 05.1.8.

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."

E. Georgiadis, A. Munemasa, H. Tanaka, A Note on Super Catalan Numbers, Interdisciplinary Information Sciences, 18 (2012) 23-24.

-
It's both comforting (given the effort spent) and unsettling to know that there's no simple combinatorial interpretation known, but I wonder what they refer to when they say "It is well know they are integers". – karan May 11 '13 at 8:03
cs.uwaterloo.ca/journals/JIS/VOL8/Callan/callan301.pdf does give a recurrence relation to show it's an integer, but it's still way too complicated – karan May 11 '13 at 8:20
The Catalan reference can be found at archive.numdam.org/ARCHIVE/NAM/NAM_1874_2_13_/… -- it's not really a paper, it's presented as a problem (with a footnote that I haven't been able to trace). Gessel and Xin only say the result was "observed" there.... – Barry Cipra May 11 '13 at 12:57
...A solution to Catalan's question is given by Bourguet at archive.numdam.org/ARCHIVE/NAM/NAM_1875_2_14_/… who proves a more general form, but Catalan points out an error at archive.numdam.org/ARCHIVE/NAM/NAM_1875_2_14_/… – Barry Cipra May 11 '13 at 12:57
Note: I found the reference to Catalan's correction in the bibliography of Bell and Catalan numbers compiled by Gould and Glatzer at math.wvu.edu/~gould/BibGood%20final.pdf – Barry Cipra May 11 '13 at 13:01

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.

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

-
As Ira Gessel pointed out, that last $(-1)^m$ should be $(-1)^n$. – Douglas Zare May 13 '13 at 18:47

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$.)

-
Thanks. It's easy to relate the cases $|m-n| \le 2$ to standard objects, too. – Douglas Zare May 12 '13 at 19:17

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.

-
Here is a comment to a deleted answer : It might be worth mentioning Landau's theorem, digreg.mathguide.de/cgi-bin/ssgfi/… which gives this argument in a much more general setting. – Ira Gessel May 13 '13 at 19:42 – Chandan Singh Dalawat Feb 26 '14 at 11:55