Un ejemplo donde $\frac{(2m)! () 2N)!} {m ¡ n! (m + n)!} ¿$ es el número de maneras de contar algo?

Question

Demostrar que para todos los enteros no negativos m$, n$, $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ es un número entero.

Hay una respuesta para esta pregunta aquí.

He visto cómo puede ser comprobada mediante ecuaciones en recurrencia así. Cuando yo estaba tratando de resolver este problema que me estaba buscando, para que la represente como el número de maneras de contar algo. ¿Alguien puede dar un ejemplo, demostrando así la pregunta de otra y de forma natural?

Answer 1

Introducción: El MO enlace proporcionado por @JoeJohnson en la sección de comentarios indica claramente que se trata de un problema difícil encontrar una combinatoria de interpretación para los enteros positivos \begin{align*} S(m,n)=\frac{(2m)!(2n)!}{m!n!(m+n)!}\la etiqueta{1} \end{align*} Ira Gessel introducido para $S(m,n)$ el término Super catalán Números en su artículo sobre el Super Boleta de Números a partir de 1992. Véase la respuesta de @GrigoryM proporcionar información sobre él. En este trabajo (sección 6) Ira Gessel también introduce la identidad

\begin{align*} \sum_{n\geq 0}2^{p-2n}\binom{p}{2n}S(m,n)=S(m,m+p)\qquad\qquad p\geq 0\etiqueta{2} \end{align*}

que junto con el valor inicial $S(0,0)=1$ y la simetría $S(m,n)=S(n,m)$ muestra $S(m,n)$ es un número entero positivo.

Ay, él también escribe que queda por verse si (2) puede ser interpretado de una manera natural.

En 2004, doce años más tarde(!) podemos leer en otro papel por Ira Gessel en la sección introductoria:

Una intrigante problema es encontrar una combinatoria de interpretación para el super catalán números.

Conclusión: Una combinatoria de interpretación para $S(m,n)$ es un problema difícil.

---

Sin embargo, me gustaría darle, al menos, una propuesta o una invitación para el lector que busca una combinatoria interpretación en términos de celosía pathes.

Observar, que $S(m,n)$ puede ser escrito como

\begin{align*} S(m,n)=\frac{\binom{2m}{m}\binom{2n}{n}}{\binom{m+n}{n}}\etiqueta{3} \end{align*}

La interpretación de esta fracción, en los términos de celosía pathes, que contiene únicamente de $(1,0)$-pasos en $x$-dirección y $(0,1)$-pasos en $y$-dirección, podemos ver

el numerador \begin{align*} \binom{2m}{m}\binom{2n}{n}\etiqueta{4} \end{align*} cuenta el número de pathes de longitud $2m+2n$ de $(0,0)$ $(m+n m+n)$ pasando por el punto $(m,m)$ o, equivalentemente, que cuenta el número de pathes de $(0,0)$ $(m,m)$ veces el número de pathes de $(0,0)$ $(n,n)$.

En el otro lado

el denominador \begin{align*} \binom{m+n}{m}\etiqueta{5} \end{align*} cuenta el número de pathes de longitud $m+n$ de $(0,0)$ $(m,n)$ o simétricamente el número de pathes de $(0,0)$ $(n,m)$.

---

Idea: Puesto que sabemos que la fracción en (3) es un entero positivo, debería ser posible encontrar un mapeo de cada uno de los $\binom{m+n}{m}$ pathes en (5) para un conjunto de pathes correspondiente a la interpretación en (4).

Para cada uno de los $\binom{m+n}{m}$ pathes esta asignación de partición de la $\binom{2m}{m}\binom{2n}{n}$ pathes en igual tamaño de las clases y el reto es encontrar un natural de asignación para esta partición.

Veamos un ejemplo sencillo con $m=2,n=1$ y codificar pathes usando $0$ para un paso en $x$-dirección y $1$ para un paso en $y$de la dirección. Observamos

\begin{array}{cccc} \binom{4}{2}=6&\binom{2}{1}=2&\qquad&\binom{3}{1}=3\\ \hline 0011&01&\qquad&001\\ 0101&10&\qquad&010\\ 0110&&\qquad y 100\\ 1001&&\qquad&\\ 1010&&\qquad&\\ 1100&&\qquad&\\ \end{array}

Para cada uno de los $\binom{m+n}{m}=\binom{3}{1}=3$ pathes $001,010$ y $100$ tenemos que encontrar una clase que contiene 4 pares de pathes de $$\{0011,0101,0110,1001,1010,1100\}\times\{01,10\}$$ que nos proporciona una natural combinatoria interpretación. En el momento en que yo no era capaz de encontrar uno, aunque estoy bastante seguro de que la información sea correctamente codificado dentro de estos pathes.

Una idea era ver el $\binom{2m}{m}$ pathes como parte de un cuadrado de la cuadrícula en el $(x\times y)$-avión y $\binom{m+n}{m}$ pathes dentro de una cuadrícula rectangular de longitud $m$ y altura $n$ como parte de un $(x\times z)$-plano. De esta manera se forman dos caras de un sólido rectangular y la pathes son proyecciones de un área dentro de este sólido para las caras. Pero no pude encontrar una interpretación adecuada de esta manera.

Así, invito al lector a hacer un pequeño ejercicio de meditación sobre el siguiente problema:

Reto: Imaginar el $\binom{2m}{m}$ pathes son parte de un $m\times m$ grid dentro de un $(u_1\times u_2)$-avión y $\binom{2n}{n}$ pathes son parte de una $n \times n$ grid dentro de un $(v_1 \times v_2)$-plano. Encontrar una asignación o descifrar la información codificada en el $\binom{m+n}{m}$ pathes que son parte de un $m \times n$ grid en un $(w_1 \times w_2)$-plano que resulta en una forma natural, de igual tamaño de partición de la $\binom{2m}{m}\binom{2n}{n}$ pathes.

Answer 2

Siguientes I. Gessel, vamos a denotar $\frac{(2m)!(2n)!}{m!n!(m + n)!}$ $S(n,m)$ y llamar super catalán números.

En dicho documento Gessel demuestra Szily de la identidad: $$ S(m,n)=\sum_k(-1)^k\binom{2m}{m+k}\binom{2n}{n-k} $$ (sigue casi inmediatamente, por ejemplo, de $(1+x)^{m+n}(1-x)^{m+n}=(1-x^2)^{m+n}$). Ahora, cabe recordar que, sin signos RHS es un Vandermonde de convolución: $$ \sum_k\binom{2m}{m+k}\binom{2n}{n-k}=\binom{2(n+m)}{n+m}. $$ Así $S(n,m)$ cuenta entramado de caminos de $(0,0)$ $(n+m n+m)$ con algunos de los signos (determinado por la altura de un camino después de los primeros us $2 millones de dólares pasos).

Si esta combinatoria suficiente puede, por supuesto, ser debatido...

Answer 3

Siguiente de Grigory M del consejo aquí es una manera de interpretar estos super catalán números como contar entramado de caminos. También utilizamos parte de una prueba por Vladimir Nikolin, cuando tratamos con la Vandermonde de Convolución de la Fórmula y Szily de la identidad.

Szily la identidad es comprobado por la equiparación de la $x^{2m} $coeficiente en la siguiente expresión $(1+x)^{m+n}(1-x)^{m+n}=(1-x^2)^{m+n}$ y, a continuación, multiplicando ambos lados por $\frac{(-1)^m(2m)!(2n)!}{(m+n)!^2}$

Tenemos $$ S(m,n)=\sum_k(-1)^k\binom{2m}{m+k}\binom{2n}{n-k} $$

Esto demuestra que esta expresión nos ocupa es un entero. Incluso me parece que esto es lo suficientemente cerca como para contar algo, el número de maneras de escoger 1s de soporte expansiones multiplicada por una constante o algo. Pero podemos hacerlo mejor.

Grigory M sugirió considerar la Vandermonde de convolución de la fórmula; $$ \sum_k\binom{2m}{m+k}\binom{2n}{n-k}=\binom{2(n+m)}{n+m}. $$

donde la suma es sobre todos los k.

Esta identidad puede escribirse como $$ \sum_{k=0}\binom{2m}{k}\binom{2n}{m+n-k} $$ dejando m+k ir a k

Nuestro super expresión catalana que se transforma en $$ S(m,n)=\sum_{k=0}(-1)^{k-m}\binom{2m}{k}\binom{2n}{m+n-k} $$

Ahora considere la siguiente prueba de la Vandermonde de convolución de la fórmula; El número de rutas en una red desde el origen hasta un punto a a Un punto(m+n m+n) tomando sólo arriba y a la derecha los pasos es de $\binom{2(m+n)}{m+n}$ (elegir el que m+n pasos son pasos en la 2(m+n) pasos para llegar allí)

Considere el siguiente enfoque para contar el número de maneras; Mira la recta x + y = 2m

(el diagrama se representa el caso de la m en lugar de 2m)

Cada ruta cruza la línea en un punto único de $A_j$

Hay $\binom{2m}{k}$ maneras para llegar a $A_j$

A continuación, hay $\binom{2n}{m+n-k}$ se mueve de izquierda a elegir para llegar a Una(m+n m+n).

Así que hay $\binom{2m}{k}$$\binom{2n}{m+n-k}$ caminos que cruzan a través de $A_j$

Sumando sobre todos los j da a nuestros Vandermonde de identidad.

Ahora bien, si nos fijamos en nuestra más reciente expresión de estos super catalán números vemos que es simplemente contando el número de rutas de acceso desde el origen hasta Un(m+n m+n) que ir a través de incluso $A_i$ menos la cantidad que ir a través de una extraña $A_i$ o viceversa dependiendo de la paridad de m. Hemos interpretado esta expresión como contar algo. De ello se desprende que es un entero.

Aunque ya no lo puedo ver por qué tiene que ser un entero positivo, pero seguro hey, que es lo que la expresión original.