La propiedad hexagonal del triángulo de Pascal

Question

Cualquier hexágono del triángulo de Pascal, cuyos vértices son 6 coeficientes binomiales que rodean cualquier entrada, tiene la propiedad de que:

• el producto de los vértices no adyacentes es constante.

• el máximo común divisor de los vértices no adyacentes es constante.

A continuación se muestra uno de estos hexágonos. Como ejemplo, aquí tenemos que $4 \cdot 10 \cdot 15 = 6 \cdot 20 \cdot 5$ así como $\gcd(4, 10, 15) = \gcd(6,20,5)$ .

$$ 1 \\ 1 \qquad 1\\ 1\qquad 2\qquad 1\\ 1\qquad3\qquad3\qquad1\\ 1\qquad\mathbf{4}\qquad\mathbf{6}\qquad4\qquad1\\ 1\qquad\mathbf{5}\qquad10\qquad\mathbf{10}\qquad5\qquad1 \\ 1\qquad6\qquad\mathbf{15}\qquad\mathbf{20}\qquad15\qquad6\qquad1$$

Hay una prueba rápida aquí (pdf). La prueba original debe estar en V. E. Hoggatt, Jr. y W. Hansell. "Los cuadrados ocultos del hexágono". The Fibonacci Quarterly 9(1971):120, 133. pero no puedo acceder a ella.

Sin embargo, estoy interesado en un combinatoria prueba. No sé cómo enfocar esto en absoluto: no puedo ver lo que representan los vértices no adyacentes y/o no sé cómo remodelar su significado. ¿Alguien puede ayudar?

EDITAR: Para especificar mejor mi pregunta, lo que busco es alguna biyección natural entre los dos conjuntos de tríadas que crean el hexágono.

Gracias.

Answer 1

En símbolos, la identidad es

$$\left({n-1\atop m-1}\right)\left({n\atop m+1}\right)\left({n+1\atop m}\right) = \left({n\atop m-1}\right)\left({n-1\atop m}\right)\left({n+1\atop m+1}\right).$$

La interpretación combinatoria habitual de un coeficiente binomial $\left({n\atop m}\right)$ es que cuenta subconjuntos de tamaño $m$ de un conjunto de tamaño $n$ . La multiplicación suele interpretarse como una elección mutuamente excluyente ( $f(n)g(n)$ cuenta el proceso de recogida $f(n)$ configuraciones, y luego elegir (independientemente) $g(n)$ artículos.

Si lo unimos, el LHS cuenta subconjuntos de tamaño $m-1$ de un conjunto de tamaño $n-1$ , entonces subconjuntos de tamaño $m$ de un conjunto (independiente) de tamaño $n+1$ y luego (de nuevo de forma independiente) subconjuntos de tamaño $m+1$ de un conjunto de tamaño $n$ . Esto se corresponde uno a uno con el RHS porque las cosas contadas por el LHS pueden ser contadas de manera diferente por el RHS: Para el RHS distinguir un elemento del $n$ y uno de los $n+1$ conjunto. Lo que sobra para esos dos conjuntos puede ser elegido por $\left({n-1\atop (m+1)-1}\right)$ y $\left({(n+1)-1\atop m-1}\right)$ respectivamente, y entonces los dos elementos distinguidos pueden ser incluidos para ser (posiblemente) elegidos en el $n-1$ para tener en cuenta $\left({(n-1) +2 \atop (m-1)+2}\right)$ .

Para aclarar la interpretación combinatoria, hay tres conjuntos, de tamaño $n-1$ , $n$ y $n+1$ de la que se eligen subconjuntos de tamaño $m-1$ , $m+1$ y $m$ respectivamente. Otra forma de contar esta situación es, sacar 1 elemento de cada uno de los $n$ y $n+1$ y añadirlos al $n-1$ conjunto. Así que ahora estás contando con conjuntos de tamaño $n+1$ , $n-1$ y $n$ de la que se eligen subconjuntos de tamaño $m+1$ , $m$ y $m-1$ respectivamente.

Answer 2

He dejado algunas preguntas como comentarios a la respuesta de Mitch, y espero que mis confusiones sobre esa respuesta se aclaren pronto. Mientras tanto, me he puesto a pensar en cómo enfocaría yo este problema. Todavía no tengo una respuesta satisfactoria; lo mejor que se me ha ocurrido es introducir un factor adicional a ambos lados de la identidad. La identidad modificada (que es algebraicamente equivalente a la no modificada) tiene un claro significado combinatorio, pero aún no veo la forma de interpretar la identidad no modificada en términos combinatorios.

Es bueno generalizar un poco la identidad. Empezando por la identidad tal y como está escrita en la respuesta de Mitch, $$ \binom{n - 1}{m - 1} \binom{n}{m + 1} \binom{n + 1}{m} = \binom{n}{m - 1} \binom{n - 1}{m} \binom{n + 1}{m + 1}, $$ sustituimos el $1$ con $r$ en todas partes para obtener $$ \binom{n - r}{m - r} \binom{n}{m + r} \binom{n + r}{m} = \binom{n}{m - r} \binom{n - r}{m} \binom{n + r}{m + r}. $$ Esto también es una identidad, como mostramos a continuación. Al igual que en la identidad original, los coeficientes del binomio que aparecen forman los vértices de un hexágono (que podríamos llamar radio- $r$ hexágono) centrado en $\binom{n}{m}$ en el triángulo de Pascal. Obsérvese que la propiedad GCD mencionada en el post original sólo es válida para $r=1,$ mientras que la identidad se mantiene para todo $r.$ Sólo nos preocupa la identidad.

Demostramos el radio- $r$ identidad partiendo de una identidad elemental que relaciona diferentes formas de representar el coeficiente del trinomio como producto de coeficientes del binomio: $$ \binom{n}{k}\binom{k}{a}=\binom{n}{a}\binom{n-a}{k-a}=\binom{n}{n-k,k-a,a}. $$ Esto tiene una interpretación combinatoria, como se discute aquí . Las siguientes tres variantes de esta identidad son útiles aquí: $$ \begin{aligned} \binom{n}{r}\binom{n-r}{m-r}&=\binom{n-m+r}{r}\binom{n}{m-r}\\ \binom{m+r}{r}\binom{n}{m+r}&=\binom{n}{r}\binom{n-r}{m}\\ \binom{n-m+r}{r}\binom{n+r}{m}&=\binom{m+r}{r}\binom{n+r}{m+r}. \end{aligned} $$ Los factores más a la derecha del lado izquierdo de estas ecuaciones coinciden con los tres factores del lado izquierdo de la identidad, mientras que los factores más a la derecha del lado derecho de estas ecuaciones coinciden con los tres factores del lado derecho de la identidad. Además, los factores más a la izquierda del lado izquierdo de estas ecuaciones son los mismos, pero permutados, que los factores más a la izquierda del lado derecho de estas ecuaciones.

Estas observaciones sugieren la idea de multiplicar ambos lados del radio- $r$ identidad por $$ \binom{n}{r}\binom{m+r}{r}\binom{n-m+r}{r} $$ para conseguir $$ \begin{aligned} &\binom{n}{r}\binom{n - r}{m - r} \cdot \binom{m+r}{r}\binom{n}{m + r} \cdot \binom{n-m+r}{r}\binom{n + r}{m}\\ &\qquad= \binom{n-m+r}{r}\binom{n}{m - r} \cdot \binom{n}{r}\binom{n - r}{m} \cdot \binom{m+r}{r}\binom{n + r}{m + r}. \end{aligned} $$ Las dos caras de esta identidad pueden considerarse como formas diferentes de responder a la siguiente pregunta: hay $n$ estudiantes, $n$ profesores, y $n+r$ administradores. Se formará un comité con $m$ estudiantes $m+r$ profesores, y $m+r$ administradores. A partir de este comité, se formará un subcomité que tendrá $r$ estudiantes, $r$ profesores, y $r$ los administradores. ¿De cuántas maneras se puede hacer esto?

En el lado izquierdo, esto se logra mediante

• elegir $r$ estudiantes para formar parte del subcomité, eligiendo entonces $m-r$ estudiantes adicionales para completar el comité,
• elegir $m+r$ profesores para que formen parte del comité, entonces de estos elegir $r$ para estar en el subcomité,
• elegir $m$ administradores para estar en el comité pero no en el subcomité, entonces elegir $r$ administradores adicionales para formar parte del subcomité.

En el lado derecho, se logra mediante

• elegir $m-r$ estudiantes para estar en el comité pero no en el subcomité, entonces elegir $r$ estudiantes adicionales para formar parte del subcomité,
• elegir $r$ profesores para formar parte del subcomité, eligiendo entonces $m$ profesores adicionales para completar el comité,
• elegir $m+r$ administradores para estar en el comité, entonces de estos elegir $r$ para estar en el subcomité.

Está claro que de cualquier manera obtenemos el mismo conjunto de asignaciones de comisiones y subcomités, por lo que las dos partes deben ser iguales.

Esta prueba es insatisfactoria ya que hemos tenido que multiplicar la identidad por el factor extraño $$ \binom{n}{r}\binom{m+r}{r}\binom{n-m+r}{r} $$ para poder enunciar nuestra interpretación combinatoria. Todavía no he podido encontrar un método que evite esto.

Añadido el 26 de enero de 2014: Debería haber mirado el pdf enlazado en la pregunta antes de publicarla. Allí la identidad se generaliza a $$ \binom{n - r}{m - s} \binom{n}{m + r} \binom{n + s}{m} = \binom{n}{m - s} \binom{n - r}{m} \binom{n + s}{m + r},\qquad\qquad(*) $$ que corresponde a un hexágono con longitudes de lado alternativamente $r$ y $s.$ La prueba anterior funciona con pequeñas modificaciones. Multiplique ambos lados por $$ \binom{n}{r}\binom{m+r}{r}\binom{n-m+s}{r} $$ para conseguir $$ \begin{aligned} &\binom{n}{r}\binom{n - r}{m - s} \cdot \binom{m+r}{r}\binom{n}{m + r} \cdot \binom{n-m+s}{r}\binom{n + s}{m}\\ &\qquad= \binom{n-m+s}{r}\binom{n}{m - s} \cdot \binom{n}{r}\binom{n - r}{m} \cdot \binom{m+r}{r}\binom{n + s}{m + r}. \end{aligned} $$ La interpretación de los tres "pares de trinomios" que aparecen a la izquierda y a la derecha es similar a la anterior.

Añadido el 8 de febrero de 2014: Hay, de hecho, dos pruebas similares y relacionadas, pero distintas, en esta línea. Tras permutar los factores a ambos lados de la identidad $(*)$ en la sección anterior para obtener $$ \binom{n - r}{m - s} \binom{n + s}{m} \binom{n}{m + r} = \binom{n - r}{m} \binom{n}{m - s} \binom{n + s}{m + r}, $$ multiplicamos ambos lados por $$ \binom{n-m-r+s}{s}\binom{m}{s}\binom{n+s}{s} $$ y obtener $$ \begin{aligned} &\binom{n-m-r+s}{s}\binom{n - r}{m - s} \cdot \binom{m}{s}\binom{n + s}{m} \cdot \binom{n+s}{s}\binom{n}{m + r}\\ &\qquad = \binom{m}{s}\binom{n - r}{m} \cdot \binom{n+s}{s}\binom{n}{m - s} \cdot \binom{n-m-r+s}{s}\binom{n + s}{m + r}. \end{aligned} $$ En la sección anterior, el problema de recuento tenía los parámetros, $$ \begin{array}{l|ccc} & \text{number} & \text{number on} & \text{number on}\\ & \text{in pool} & \text{committee} & \text{subcommittee}\\ \hline \text{students} & n & m+r-s & r\\ \text{teachers} & n & m+r & r\\ \text{administrators} & n+s & m+r & r\\ \end{array} $$ mientras que en esta sección, los parámetros son $$ \begin{array}{l|ccc} & \text{number} & \text{number on} & \text{number on}\\ & \text{in pool} & \text{committee} & \text{subcommittee}\\ \hline \text{students} & n-r & m & s\\ \text{teachers} & n+s & m & s\\ \text{administrators} & n+s & m+r+s & s\\ \end{array} $$

Las dos pruebas se refieren al hexágono con longitudes de lado que alternan entre $r$ y $s$ . La demostración del apartado anterior se obtiene relacionando los coeficientes binomiales correspondientes a los extremos de los lados de longitud $r,$ mientras que la demostración en esta sección se obtiene relacionando los coeficientes binomiales correspondientes a los extremos de los lados de longitud $s.$

Añadido el 10 de octubre de 2018: Me faltó una tercera prueba, que es similar a las dos anteriores en que las tres implican la conversión de los coeficientes binomiales a coeficientes trinomiales. Después de permutar los factores de nuevo para obtener $$ \binom{n}{m + r} \binom{n - r}{m - s} \binom{n + s}{m} = \binom{n}{m - s} \binom{n + s}{m + r} \binom{n - r}{m}, $$ multiplicamos ambos lados por $$ \binom{m+r}{r+s}\binom{n+s}{r+s}\binom{n-m+s}{r+s} $$ y obtener $$ \begin{aligned} &\binom{n}{m + r}\binom{m+r}{r+s} \cdot \binom{n+s}{r+s}\binom{n - r}{m - s} \cdot \binom{n + s}{m}\binom{n-m+s}{r+s}\\ &\qquad= \binom{n}{m - s}\binom{n-m+s}{r+s} \cdot \binom{n + s}{m + r}\binom{m+r}{r+s} \cdot \binom{n+s}{r+s}\binom{n - r}{m}, \end{aligned} $$ En esta prueba, los parámetros del problema de recuento son $$ \begin{array}{l|ccc} & \text{number} & \text{number on} & \text{number on}\\ & \text{in pool} & \text{committee} & \text{subcommittee}\\ \hline \text{students} & n & m+r & r+s\\ \text{teachers} & n+s & m+r & r+s\\ \text{administrators} & n+s & m+r+s & r+s\\ \end{array} $$ En esta versión, los dos vértices del hexágono asociados a un coeficiente trinomial determinado son diametralmente opuestos, en lugar de ser adyacentes a lo largo de lados de longitud $r$ o $s$ .

Añadido el 4 de diciembre de 2018: No me resisto a añadir una generalización de la identidad para los coeficientes multinomiales que puede arrojar algo de luz sobre la estructura de la identidad en el caso binomial y sobre sus tres pruebas diferentes.

Dejemos que $\ell\ge2$ , dejemos que $k_1$ , $k_2$ , ..., $k_\ell$ , $r_0<r_1<\ldots<r_\ell$ sean números enteros tales que $k_i+r_0\ge0$ para todos $i\in\{1,2,\ldots,\ell\}$ . Establecer $n=\sum_{i=1}^\ell k_i+\sum_{i=0}^\ell r_i$ . Utilice $\pi$ para denotar una permutación de $(r_0,r_1,\ldots,r_\ell)$ . Entonces tenemos la identidad $$ \prod_{\text{sgn}(\pi)=1}\binom{n-\pi(r_0)}{k_1+\pi(r_1),\ldots,k_\ell+\pi(r_\ell)}=\prod_{\text{sgn}(\pi)=-1}\binom{n-\pi(r_0)}{k_1+\pi(r_1),\ldots,k_\ell+\pi(r_\ell)}. $$

Prueba: Obsérvese que la definición de $n$ y las restricciones a la $r_i$ garantizan que los coeficientes multinomiales están bien formados, es decir, que los números inferiores de cada coeficiente suman al número superior y que los números inferiores son todos no negativos. La afirmación se puede demostrar observando que si ambos lados se multiplican por una cantidad adecuada, entonces ambos se reducen a la misma $\left(\frac{1}{2}(\ell+1)!\right)$ -producto doble de $(\ell+1)$ -coeficientes nóminos.

Para encontrar un multiplicador adecuado, elige un par de índices $i<j$ del conjunto $\{0,1,\ldots,\ell\}$ . El multiplicador será un producto de coeficientes binomiales, uno asociado a cada factor de la identidad. Para cada coeficiente multinomial de la identidad (a ambos lados), el parámetro $r_j$ aparecerá exactamente en un argumento del coeficiente. Si aparece en uno de los argumentos inferiores, es decir, tenemos $k_a+r_j$ como argumento inferior, introducir el coeficiente binomial $$ \binom{k_a+r_j}{k_a+r_i,r_j-r_i}. $$ Si aparece en el argumento superior, es decir, si el argumento superior es $n-r_j$ , entonces introduzca el coeficiente binomial $$ \binom{n-r_i}{n-r_j,r_j-r_i}. $$ El producto de los coeficientes binomiales así introducidos es el mismo en cada uno de los dos lados ya que cada uno de los coeficientes binomiales $$ \binom{n-r_i}{n-r_j,r_j-r_i},\ \binom{k_1+r_j}{k_1+r_i,r_j-r_i},\ \ldots,\ \binom{k_\ell+r_j}{k_\ell+r_i,r_j-r_i} $$ se introducirá exactamente $\frac{1}{2}\ell!$ veces a la izquierda y el mismo número de veces a la derecha. Por lo tanto, hemos encontrado multiplicadores iguales para los dos lados.

Para mostrar que cuando se incluye el multiplicador, los dos lados se reducen a la misma cantidad, observe que para el coeficiente multinomial en la identidad asociada a la permutación $\pi$ hay un coeficiente multinomial correspondiente de paridad opuesta, que se obtiene siguiendo la permutación $\pi$ con el canje $(r_ir_j)$ . El resultado se desprende ahora del hecho de que cuando se incluyen los coeficientes binomiales introducidos, estos $\ell$ -los nómeros se hacen iguales $(\ell+1)$ -nomios. De hecho, \begin {align*} & \binom { \ldots }{ \ldots k_a+r_i, \ldots k_b+r_j, \ldots } \binom {k_b+r_j}{k_b+r_i,r_j-r_i} \\ & \quad = \binom { \ldots }{ \ldots k_a+r_j, \ldots k_b+r_i, \ldots } \binom {k_a+r_j}{k_a+r_i,r_j-r_i} \\ & \quad = \binom { \ldots }{r_j-r_i, \ldots k_a+r_i, \ldots k_b+r_i, \ldots } \end {align*} cuando $r_i$ y $r_j$ ambos aparecen en argumentos inferiores, mientras que \begin {align*} & \binom {n-r_i}{ \ldots k_a+r_j, \ldots } \binom {k_b+r_j}{k_b+r_i,r_j-r_i} \\ & \quad = \binom {n-r_j}{ \ldots k_a+r_i, \ldots } \binom {n-r_i}{n-r_i,r_j-r_i} \\ & \quad = \binom {n-r_i}{r_j-r_i, \ldots k_a+r_i, \ldots } \end {align*} cuando uno de ellos aparece en el argumento superior. $\square$

Obsérvese que la identidad hexagonal original es el caso $\ell=2$ , $r_1=-1$ , $r_2=0$ , $r_3=1$ y que la identidad hexagonal generalizada es el caso $\ell=2$ , $r_1=-s$ , $r_2=0$ , $r_3=r$ . Que haya tres coeficientes binomiales en cada lado de la identidad hexagonal refleja que hay $\frac{1}{2}(\ell+1)!=3$ permutaciones pares y el mismo número de permutaciones Impares.

La demostración de la versión multinomial de la identidad implicaba la elección arbitraria de los dos índices $i$ y $j$ . Esto significa que, de hecho, hay $\binom{\ell+1}{2}$ diferentes maneras de construir esta prueba, cada una con su propia interpretación combinatoria. Como antes, no son pruebas combinatorias, ya que implican la introducción del multiplicador. El hecho de que haya tres pruebas similares en el caso hexagonal refleja que, cuando $\ell=2$ Hay $\binom{\ell+1}{2}=3$ formas de elegir $i$ y $j$ .

Cabe destacar que la formación hexagonal en la identidad original del triángulo de Pascal es una traslación de la permutoedro de $\{r_0,r_1,r_2\}$ . Las identidades multinominales superiores se asocian a las formaciones de la pirámide de Pascal o a sus generalizaciones de dimensión superior que toman la forma de algún politopo de dimensión superior. Cuando $\ell=3$ por ejemplo, las permutaciones de $\{r_0,r_1,r_2,r_3\}$ forman los vértices de un octaedro truncado.

Por último, observe que hay una redundancia en los parámetros que aparecen en el enunciado de la identidad general. En concreto $r_0$ puede eliminarse definiendo $$ \begin{aligned} r'_0&:=0 \\ r'_1&:=r_1-r_0 & k'_1&:=k_1+r_0\\ &\vdots & &\vdots\\ r'_\ell&:=r_\ell-r_0 & k'_\ell&:=k_\ell+r_0 \end{aligned} $$ para que $n':=\sum_{i=1}^\ell k'_i+\sum_{i=0}^\ell r'_i=n-r_0$ y reescribir la identidad sustituyendo los parámetros originales por los primados.

Answer 3

Podemos demostrar la igualdad de $$\binom{n-1}{m-1}\binom{n}{m+1}\binom{n+1}{m}=\binom{n}{m-1}\binom{n-1}{m}\binom{n+1}{m+1}$$ contando los caminos de la red. Para ello, consideramos las trayectorias de $(0,0)$ a $(X,Y)$ con ciertas propiedades correspondientes al LHS de la ecuación y caminos de $(0,0)$ a $(X,Y)$ correspondiente al lado derecho y demostrar que existe una $1$ - $1$ correspondencia debido a la simetría entre estos.

Para ver la simetría más fácilmente, reescribimos la ecuación utilizando coeficientes multinomiales y variables de intercambio. Obtenemos

$$\binom{n-1}{m-1,n-m}\binom{n}{m+1,n-m-1}\binom{n+1}{m,n-m+1}=\binom{n}{m-1,n-m+1}\binom{n-1}{m,n-m-1}\binom{n+1}{m+1,n-m}$$ Utilizando la sustitución $y=n-m,x=m$ con $x+y=n$ da

$$\binom{x+y-1}{x-1,y}\binom{x+y}{x+1,y-1}\binom{x+y+1}{x,y+1}=\binom{x+y-1}{x,y-1}\binom{x+y}{x-1,y+1}\binom{x+y+1}{x+1,y}$$

Los factores del lado derecho se reordenan aumentando longitud de los caminos correspondiente al LHS.

Ahora analizamos el LHS: El factor de la izquierda $$\binom{x+y-1}{x-1,y}$$ es el número de trayectorias de longitud $x+y-1$ de $(0,0)$ a $(x-1,y)$ el siguiente es el número de caminos de longitud $x+y$ de $(0,0)$ a $(x+1,y-1)$ y el tercero es el número de caminos de longitud $x+y+1$ de $(0,0)$ a $(x,y+1)$ .

Ahora concatenar estos caminos, de modo que el punto final de la parte anterior sea el punto de partida de la siguiente. Así, la primera parte está formada por todos los caminos de longitud $x+y-1$ de $(0,0)$ a $(x-1,y)$ . La segunda parte consiste en todos los caminos de longitud $x+y$ a partir de $(x-1,y)$ y terminando en $(2x,2y-1)$ . La tercera parte consiste en todas las trayectorias de longitud $x+y+1$ a partir de $(2x,2y-1)$ y terminando en $(3x,3y)$ .

Para formularlo de forma más sencilla: el LHS da el número de todo caminos de longitud $3x+3y$ de $(0,0)$ a $(3x,3y)$ pasando por $(x-1,y)$ y $(2x,2y-1)$ .

$$LHS: (0,0)\longrightarrow(x-1,y)\longrightarrow(2x,2y-1)\longrightarrow(3x,3y)$$

El RHS es ahora el colgante simétrico del LHS. Comparte las mismas propiedades y se mantienen los mismos argumentos. Por lo tanto, el lado derecho da el número de todo caminos de longitud $3x+3y$ a partir de $(0,0)$ a $(3x,3y)$ y pasando por $(x,y-1)$ y $(2x-1,2y)$ .

$$RHS: (0,0)\longrightarrow(x,y-1)\longrightarrow(2x-1,2y)\longrightarrow(3x,3y)$$

Dado que los puntos de paso de las trayectorias del LHS y del RHS son simétricos con respecto a la línea $x=y$ y el punto inicial y el punto final están en esta diagonal el número de caminos es el mismo, lo que demuestra que el RHS y el LHS son iguales.

Nota: Algunas generalizaciones que se abordan en Will Orrick presumiblemente también se puede mostrar utilizando las simetrías de las trayectorias correspondientes. :-)

Añadido 2014-03-19: Atención - Esta prueba no es correcta. El razonamiento sólo es válido para el caso especial $x=y$ . En caso de $x\ne y$ falta una descripción explícita de una biyección entre las trayectorias de LHS y RHS (ver comentarios más abajo).

Añadido 2014-03-21: Esquema para una prueba. A continuación se presenta un esquema de cómo una biyección entre las trayectorias del LHS y el RHS para el caso general incluyendo $x \ne y$ podría crearse.

El plan es mostrar que todos los caminos del LHS pueden ser mapeados a un camino del RHS y viceversa.

Una representación geométrica de todas las trayectorias de LHS, resp. RHS está dada por un gráfico que consiste en tres cuadrículas rectangulares que tienen un vértice en común.

Más concretamente, todas las trayectorias de LHS $L$ están dentro de tres cuadrículas rectangulares $L=L_1L_2L_3$ con los puntos inferior izquierdo y superior derecho: $L_1: (0,0) \rightarrow (x-1,y)$ , $L_2: (x-1,y) \rightarrow (2x,2y-1)$ y $L_3: (2x,2y-1) \rightarrow (3x,3y)$ . Todas las rutas comienzan en $(0,0)$ pasan por los vértices $(x-1,y)$ y $(2x,2y-1)$ y terminan en $(3x,3y)$ .

Como no podemos cubrir completamente los rectángulos del lado derecho con los rectángulos del lado izquierdo, añadimos un paso adicional, que preserva la biyección y, por tanto, es admisible.

Una acción admisible es realizar uno o varios desplazamientos cíclicos en una trayectoria. Así, una trayectoria $P=(P_1P_2)$ se convierte en $(P_2P_1)$ después de un desplazamiento cíclico a la derecha de $length(P_2)$ . Esto implica que podemos ampliar la malla del LHS $L=L_1L_2L_3$ colocando una copia de $L$ a la derecha y también a la izquierda, simbólicamente: $LLL=L_1L_2L_3L_1L_2L_3L_1L_2L_3$ .

Ahora somos libres de cubrir partes de RHS $R=R_1R_2R_3$ con partes de $LLL=L_1L_2L_3L_1L_2L_3L_1L_2L_3$ e identificar los caminos de esta manera. También podemos utilizar diferentes recubrimientos moviendo $LLL$ en $x$ - y $y$ -dirección.

Cada cubierta identifica todos los caminos para el que se cumple lo siguiente: Están completamente dentro de $R$ y $LLL$ tienen longitud $3x+3y$ y siempre que la trayectoria atraviese regiones rectangulares $L_iL_j, L_iR_j, R_iL_j$ o $R_iR_j$ El camino tiene que pasar por el vértice correspondiente que une estas regiones.

Dado que los rectángulos del lado izquierdo y del lado derecho difieren como máximo en $2$ en $x$ - y $y$ - dirección, unas pocas coberturas deberían ser suficientes para cubrir todos los caminos de RHS por estas copias transformadas de LHS.

Del mismo modo, el LHS debería estar cubierto por copias transformadas del RHS. Tal vez algunos casos especiales ( $x=1,y=1$ ) deben considerarse por separado.

Answer 4

Esto no es una respuesta, sino una explicación de los problemas de la respuesta más votada (a 28 de septiembre de 2018) (por Mitch). Aunque los comentarios que explican los problemas existen desde hace muchos años, la respuesta no ha sido corregida ni eliminada, y sigue acumulando votos positivos (dos en los últimos dos meses), lo que me lleva a pensar que es necesaria una explicación más visible y detallada. Aprovecho también para instar a los lectores a que voten la respuesta de Markus Scheuer, que es la única respuesta publicada hasta la fecha que proporciona una prueba correcta y combinatoria.

El tipo más simple de prueba combinatoria cuenta un conjunto finito de dos maneras diferentes, lo que lleva a una igualdad entre dos fórmulas de conteo. Un tipo de prueba combinatoria más complicada cuenta dos conjuntos diferentes y luego da el paso adicional de establecer una biyección entre los dos conjuntos. La biyección muestra que los dos conjuntos tienen el mismo tamaño. Una vez más, se obtiene una igualdad de dos fórmulas de recuento. El primer tipo de prueba puede considerarse un caso especial del segundo tipo, en el que el mapa de identidad sirve de bijección.

La respuesta de Mitch pretende proporcionar el primer tipo de prueba, es decir, contar el mismo conjunto de dos maneras diferentes, pero, de hecho, no lo hace. Interpreta correctamente los dos lados como fórmulas de enumeración, pero estas fórmulas de enumeración son para conjuntos diferentes, no para el mismo conjunto. Para demostrar la igualdad, habría que demostrar que los conjuntos tienen el mismo tamaño, pero la respuesta no intenta hacerlo. La respuesta contiene las frases "Esto se corresponde uno a uno con el LHS porque las cosas contadas por el LHS pueden ser contadas de forma diferente por el RHS" y "Otra forma de contar esta situación es...", pero esto es o bien erróneo -las fórmulas cuentan cosas manifiestamente diferentes- o bien incoherente -¿qué significa contar una situación?

Explicación detallada: Una forma de interpretar el argumento de Mitch es que ambos lados de la identidad cuentan conjuntos de triples ordenados de subconjuntos tomados de conjuntos de tamaños específicos. El problema es que los dos lados no cuentan el mismo conjunto de triples ordenados de subconjuntos, sino dos conjuntos diferentes de triples ordenados de subconjuntos. Y, lo que es más importante, no se establece ninguna biyección entre los dos conjuntos de triples ordenados. Para concretar esto, miremos el hexágono que rodea al $2$ en la tercera fila del triángulo. Esto corresponde a $n=2$ , $m=1$ y la identidad, $$ \binom{n-1}{m-1}\binom{n}{m+1}\binom{n+1}{m}=\binom{n+1}{m+1}\binom{n-1}{m}\binom{n}{m-1}, $$ se convierte en $$ \binom{1}{0}\binom{2}{2}\binom{3}{1}=\binom{3}{2}\binom{1}{1}\binom{2}{0}. $$ (Si comparas con la formulación de Mitch, verás que he reordenado los factores de la derecha para hacerlos coincidir con el orden en que los conjuntos de la prescripción de Mitch se utilizan en su argumento). Ahora Mitch observa que la fórmula de la izquierda cuenta las formas de formar un triple ordenado de subconjuntos al no extraer ningún elemento del primer conjunto (de tamaño $1$ ), dos elementos del segundo conjunto (de tamaño $2$ ), y un elemento del tercer conjunto (de tamaño $3$ ). Mitch dice entonces que hay que quitar un elemento del segundo conjunto y un elemento del tercer conjunto, y colocar estos elementos en el primer conjunto. El lado derecho cuenta las formas de formar un triple ordenado de subconjuntos sacando dos elementos de este nuevo primer conjunto, un elemento de este nuevo segundo conjunto y ningún elemento de este nuevo tercer conjunto.

Si de alguna manera supiéramos que el número de formas de formar triples ordenados de subconjuntos de los tres conjuntos originales es igual al número de formas de formar triples ordenados de subconjuntos de los tres nuevos conjuntos, entonces tendríamos una prueba. Los números de triples ordenados en los dos lados son, de hecho, iguales -la identidad es verdadera-, pero la cuestión es cómo demostrarlo.

Para entender lo que ocurre, veamos cuáles son las triplas ordenadas de cada lado en nuestro ejemplo concreto. Para el lado izquierdo, dejemos que el primer conjunto sea $\{R\}$ el segundo conjunto $\{G_1,G_2\}$ y la tercera serie $\{B_1,B_2,B_3\}$ . El lado izquierdo de la identidad se calcula como $3$ y hay, efectivamente, tres triples ordenados de subconjuntos: $$ \begin{aligned} &(\{\},\{G_1,G_2\},\{B_1\})\\ &(\{\},\{G_1,G_2\},\{B_2\})\\ &(\{\},\{G_1,G_2\},\{B_3\}). \end{aligned} $$ Siguiendo la receta de Mitch para el lado derecho, se elimina un elemento de cada uno de los conjuntos $2$ y $3$ , digamos elementos $G_1$ y $B_1$ y estos elementos se colocan en el conjunto $1$ , dando conjuntos $\{R,G_1,B_1\}$ , $\{G_2\}$ , $\{B_2,B_3\}$ . El lado derecho de la identidad también es igual a $3$ y hay, de nuevo, tres triples ordenados de subconjuntos: $$ \begin{aligned} &(\{G_1,B_1\},\{G_2\},\{\})\\ &(\{R,B_1\},\{G_2\},\{\})\\ &(\{R,G_1\},\{G_2\},\{\}). \end{aligned} $$

Está claro que no esperamos los mismos triples ordenados en los dos lados ya que hemos movido elementos. Supongo que lo que se esperaba en la respuesta de Mitch era que el contenido de los triples, es decir, la unión de los tres subconjuntos que componen el triple, coincidiera en los dos lados. Pero el ejemplo muestra que esto tampoco ocurre. Pensando en $R$ como un objeto rojo, $G_i$ como objetos verdes, y $B_j$ como objetos azules, tenemos una composición de color fija (ningún rojo, dos verdes, un azul) para todos los triples de la izquierda, pero no para los triples de la derecha. De los triples de la derecha, sólo el triple $(\{G_1,B_1\},\{G_2\},\{\})$ tiene el mismo contenido que el triple de la izquierda.

Para completar una demostración en este sentido, habría que formular alguna regla para emparejar los triples de los dos lados, y habría que demostrar que esta regla funciona para $n$ y $m$ . Esto no se ha hecho. De hecho, no creo que la prueba pueda ser remendada, por la siguiente razón: nada en la lógica del argumento parece depender de que se retire un solo elemento de cada uno de los conjuntos segundo y tercero y se coloque en el primer conjunto. ¿Por qué no dos elementos de cada uno, o un elemento del segundo y dos del tercero, o alguna otra combinación de números de cada uno? Pero si eso es correcto, deberíamos obtener muchas identidades adicionales, a saber $$ \binom{n-1}{m-1}\binom{n}{m+1}\binom{n+1}{m}=\binom{n-1+k+\ell}{m-1+k+\ell}\binom{n-k}{m+1-k}\binom{n+1-\ell}{m-\ell}, $$ para la arbitrariedad $k$ y $\ell$ . Sin embargo, no existe tal identidad general, como se puede comprobar introduciendo números. Por ejemplo, dejemos que $n=4$ , $m=3$ , $k=\ell=2$ . Entonces $$ \binom{n-1}{m-1}\binom{n}{m+1}\binom{n+1}{m}=\binom{3}{2}\binom{4}{4}\binom{5}{3}=30, $$ mientras que $$ \binom{n-1+k+\ell}{m-1+k+\ell}\binom{n-k}{m+1-k}\binom{n+1-\ell}{m-\ell}=\binom{7}{6}\binom{2}{2}\binom{3}{1}=21. $$ Por otro lado, $k=\ell=1$ sí funciona: $$ \binom{5}{4}\binom{3}{3}\binom{4}{2}=30. $$ Las generalizaciones de la identidad que realmente se mantienen se dan en el artículo citado, como señalo en mi otra respuesta. Estas generalizaciones contienen parámetros adicionales, pero entran de forma diferente a los $k$ y $\ell$ en la fórmula anterior. Y entender el papel de estos parámetros adicionales permite comprender mejor lo que hace que la identidad funcione.

Answer 5

Un canal de televisión emitirá seis telenovelas de varias partes que tienen el siguiente número de partes:

• A: $m-1$ piezas
• B: $n-m$ piezas
• C: $m+1$ piezas
• D: $n-m-1$ piezas
• E: $m$ piezas
• F: $n-m+1$ piezas

El $3n$ Las franjas horarias en las que se emitirán están en $n-1$ Los lunes, $n$ Los miércoles y $n+1$ Los viernes. Hay dos horarios posibles, que son los siguientes:

Anexo 1:

• A y B los lunes
• C y D los miércoles
• E y F los viernes

Programa 2:

• D y E los lunes
• A y F los miércoles
• B y C los viernes

(En su mayor parte he tomado los 6 términos en el orden en que Mitch los puso en su ecuación, pero he intercambiado los dos primeros términos de su RHS para que la secuencia del numerador del RHS coincida con la del LHS).

Las partes de cada drama deben emitirse en su orden correcto. Sin embargo, las partes de diferentes dramas pueden intercalarse a voluntad.

Dejemos que $S_i$ sea el conjunto de órdenes de emisión que se ajustan a Schedule $i$ . El LHS de Mitch es $|S_1|$ . Su RHS es $|S_2|$ .

Elija un orden que se ajuste al programa 1. Esto determina el orden en el que los $n-1$ Las partes D y E (colectivamente) se emiten. Este es un orden válido para las franjas horarias del lunes del horario 2. Lo mismo ocurre con las franjas horarias del miércoles y del viernes. Esto determina un orden único que se ajusta al horario 2.

Un argumento similar, con los horarios intercambiados, también se aplica. Por tanto, existe una biyección entre $S_1$ y $S_2$ . Así, $|S_1|=|S_2|$ que demuestra la identidad especificada por Mitch.