# 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

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