11
$\begingroup$

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

  • 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.2012-12-15

1 Answers 1

6

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.

  • 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.2012-12-15