Una prueba puramente combinatoria que divide a que $\binom{m+n}{n}$ $\binom{2n}{n}\cdot \binom{2m}{m}$

Question

Creo que es un hecho bien conocido que $\binom{m+n}{n}$ divide $\binom{2n}{n}\cdot \binom{2m}{m}$.

Por desgracia, cada prueba que conozco de este teorema consiste en estimar el $p$-adic exponentes (es decir, que conozco sólo las pruebas puramente algebraicas).

Lo que estoy buscando es puramente combinatoria interpretación de esta identidad. ¿Alguna idea?

Answer 1

Podrían publicar esto si alguien figuras de esto... es un problema abierto.

Cuando se divide, este problema se reduce a mostrar que S(n,m) es un número entero donde S(m,n) se define como tal,

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

Estos son conocidos como los super-catalán números, una generalización de los números de catalán y creo que una combinatoria general de interpretación de la super-catalán números es todavía un problema abierto desde la década de 1870. No han sido las caracterizaciones de las secuencias de restricción de los valores de $n$$m$, por ejemplo, $m=1$ da el catalán números, $m=2$ puede ser caracterizado por "equilibrado flor de los árboles" y "pares de Dyck caminos".

Este papel por David Callan tiene un par de ejemplos más.

Si alguien más está interesado, la prueba algebraica es bastante recta hacia adelante (a partir de este estudiante de la tesis doctoral).

Landau estados exacta de potencia más alto de la primer dividir $n!$ es

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

Por lo tanto, debemos demostrar que para todos los números primos $p$ de la mayor potencia del denominador es mayor que el numerador.

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

sigue a partir de la identidad $\lfloor x\rfloor + \lfloor y\rfloor + \lfloor x+y\rfloor \leq \lfloor 2x\rfloor + \lfloor 2y\rfloor$ para todos los $x$, $y$.