Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Usually in combinatorics, I love proofs by double counting. It gives me a very happy feeling to know a double counting proof. I feel I understand the problem better. A close younger sibling of this technique is to interpret a given expression as a solution to a smartly constructed counting problem.

So whenever somebody asks me to prove that a ratio involving factorials is an integer, I try to interpret the ratio as a solution to a counting problem. But throughout my counting life, I have encountered certain expressions which never admit an interpretative proof. One of them is jasoncube's question posted here.

I searched online and I could not find a slick proof for jasoncube's question. So this post has the following two questions:

1) For $m,n \in \mathbb{N}$ can you find a counting problem whose solution is $\dfrac{(2m)! (2n)!}{m! n! (m+n)!}$?

2) Is there any literature on the extent of this technique or it's limitations? That is, has anybody proved impossibility results for certain expressions?

Thanks,
Iso

share|improve this question
    
$\frac{(2 m)! (2 n)!}{m! n! (m + n)!}$ is the ratio of the number of ways of dividing $2 m + 2 n$ things into boxes of $m$, $n$, and $m + n$ things, vs the number of ways of dividing $2 m + 2 n$ things into boxes of $2 m$ and $2 n$ things. This is obviously a positive integer because given boxes of $2 m$ and $2 n$ things, just pick $m$ things from the first box and $n$ things from the second box and put the remainder into a third box. –  Zhen Lin Dec 15 '12 at 21:03
    
@ZhenLin: The numerator for your counting problem is $(2m+2n)!$, but in my problem it is $(2m)!(2n)!$. –  Isomorphism Dec 15 '12 at 21:04
3  
@ZhenLin: Okay. But I still don't get your argument that it is "obviously an integer" -- a partition into $m+n+(m+n)$ can arise from several different $2m+2n$ partitions using the procedure you describe, and vice versa. –  Henning Makholm Dec 15 '12 at 21:15
2  
@ZhenLin: No, I don't get it. You seem to be arguing that $\binom{2m+2n}{m,\;n,\;(m+n)}$ is "obviously" an integer multiple of $\binom{2m+2n}{2m}$, but that is not at all obvious to me. –  Henning Makholm Dec 15 '12 at 21:18
5  
@Zhen: I think your intuition would be correct if there were overcounting only in one direction; that is, if your argument exhibited the ratio as the ratio of the cardinalities of two sets $A$, $B$ such that one element of $A$ corresponds to $r$ elements of $B$ but every element of $B$ only corresponds to one element of $A$; then the ratio would be the integer $r$. That's not the case here, however; every element of $B$ also corresponds to $s$ elements of $A$, and then the ratio is the ratio $r/s$ of two integers, and it remains to be explained why that ratio is itself an integer. –  joriki Dec 15 '12 at 22:29

1 Answer 1

up vote 6 down vote accepted

According to this question on Math Overflow ("Recursions which define polynomials") there is no known combinatorial interpretation of the numbers $$A(m,n) = \frac{(2m)! (2n)!}{m! n! (m+n)!}.$$

The question does link to Ira Gessel's paper "Super Ballot Numbers" (Journal of Symbolic Computation 14 (1992) 179--194). In Section 6 Gessel calls these "super Catalan numbers" and gives a few proofs of their integrality. Equation (32) consists of the formula $$\sum_n 2^{p-2n} \binom{p}{2n} A(m,n) = A(m,m+p), \:\:\: p \geq 0.$$ Gessel says that this formula, together with $A(0,0) = 1$ and $A(m,n) = A(n,m)$, "in principle... gives a combinatorial interpretation to $A(m,n)$, although it remains to be seen whether [the formula] can be interpreted in a 'natural' way."

So "no known combinatorial interpretation, but a recursive formula that might lead to one" appears to be the state of things at this point.

share|improve this answer
1  
The number is also a solution to the recursion: $B(m,n) = 4 B(m,n-1) - B(m+1,n-1)$ where $B(m,m) = \binom{2m}{m}$ according to the IMO 1972 solution at cs.cornell.edu/~asdas/imo/imo/isoln/isoln723.html –  Isomorphism Dec 15 '12 at 22:38
    
@Isomorphism: That recurrence is at the end of Section 6 of Gessel's paper as well. –  Mike Spivey Dec 15 '12 at 22:41
    
I had not seen the link to the paper. I am reading it now, looks wonderful! Thank you very much :)) P.S: do you know any literature on the impossibility of proving a number cannot be obtained as a counting problem (I don't mind if the counting methods are restricted, I want to learn proof techniques). Thanks! –  Isomorphism Dec 15 '12 at 22:45
2  
@Isomorphism: I've never heard of anyone proving that a certain identity has no combinatorial proof. In fact, I would be surprised if someone did so. I cannot imagine how such a proof (of the non-existence of a combinatorial proof) would be constructed. But then proofs about proofs is getting far from my area of expertise. –  Mike Spivey Dec 15 '12 at 22:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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