6
$\begingroup$

I think it is quite a well known fact that $\binom{m+n}{n}$ divides $\binom{2n}{n}\cdot \binom{2m}{m}$.

Unfortunately, every proof I'm aware of of this theorem consists of estimating the $p$-adic exponents (I mean, I'm familiar only with purely algebraic proofs).

What I'm looking for is purely combinatorial interpretation of this identity. Any ideas?

$\endgroup$
  • $\begingroup$ The quotients are the "super-Catalan numbers" from www-users.math.umn.edu/~reiner/REU/ChenWang2012.pdf . A combinatorial interpretation is an open question, as far as I can recall. The paper I linked gives a combinatorial proof, but not via a counting interpretation. $\endgroup$ – darij grinberg Mar 15 '17 at 18:26
2
$\begingroup$

They could publish this if someone figures this out... it's an open problem.

When dividing, this problem boils down to showing that S(n,m) is an integer where S(m,n) is defined as such,

$$ S(m,n) = \frac{(2n)!(2m)!}{(m+n)!n!m!} $$

These are known as the super-Catalan numbers, a generalization of the Catalan numbers and I believe a general combinatorial interpretation of the super-Catalan numbers is still an open problem since the 1870s. There have been characterizations of the sequences for restricted values of $n$ and $m$, for example, $m=1$ gives the Catalan numbers, $m=2$ can be characterized by "balanced blossom trees" and "pairs of Dyck paths".

This paper by David Callan has a few more examples.

If anyone else is interested, the algebraic proof is fairly straight forward (from this student's dissertation).

Landau states the exact highest power of the prime to divide $n!$ is

$$\sum_{i=1}^\infty\left\lfloor \frac{n}{p^i}\right\rfloor$$

Thus, we must simply show that for all primes $p$ the highest power of the denominator is at most that of the numerator.

$$\sum_{i=1}^\infty\left\lfloor \frac{m}{p^i}\right\rfloor + \left\lfloor \frac{n}{p^i}\right\rfloor + \left\lfloor \frac{m+n}{p^i}\right\rfloor \leq \sum_{i=1}^\infty\left\lfloor \frac{2m}{p^i}\right\rfloor +\left\lfloor \frac{2n}{p^i}\right\rfloor$$

follows from the identity $\lfloor x\rfloor + \lfloor y\rfloor + \lfloor x+y\rfloor \leq \lfloor 2x\rfloor + \lfloor 2y\rfloor$ for all $x$, $y$.

$\endgroup$
  • $\begingroup$ Well, thanks anyway :) $\endgroup$ – VanDerWarden Mar 15 '17 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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