38
$\begingroup$

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

$\endgroup$
11
  • 2
    $\begingroup$ 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. $\endgroup$
    – Tony Huynh
    May 11, 2013 at 6:58
  • 9
    $\begingroup$ @Tony: is it? That isn't clear to me. What embedding do you have in mind? $\endgroup$ May 11, 2013 at 7:01
  • 2
    $\begingroup$ @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. $\endgroup$
    – Tony Huynh
    May 11, 2013 at 7:21
  • 4
    $\begingroup$ See also: mathoverflow.net/questions/26336/… $\endgroup$ May 11, 2013 at 14:36
  • 9
    $\begingroup$ 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. $\endgroup$ May 11, 2013 at 16:14

6 Answers 6

45
$\begingroup$

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.

$\endgroup$
6
46
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ This is a nice solution, but I think the definitions of $x$ and $y$ should have the floor function notation removed. $\endgroup$
    – S. Carnahan
    May 11, 2013 at 14:44
  • 2
    $\begingroup$ It might be worth mentioning Landau's theorem, digreg.mathguide.de/cgi-bin/ssgfi/…, which gives this argument in a much more general setting. $\endgroup$
    – Ira Gessel
    May 13, 2013 at 19:42
20
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ As Ira Gessel pointed out, that last $(-1)^m$ should be $(-1)^n$. $\endgroup$ May 13, 2013 at 18:47
16
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks. It's easy to relate the cases $|m-n| \le 2$ to standard objects, too. $\endgroup$ May 12, 2013 at 19:17
14
$\begingroup$

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

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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 $\endgroup$ Feb 26, 2014 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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