# On the impossibility of proving certain problems using double counting.

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

-
$\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
@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
@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
@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

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.

-
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
@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