Mostrar $\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$ interpretación cuadra caminando de Pascal ' triángulo s

Question

Una combinatoria prueba de la identidad $$\binom{n}{k}\binom{k}{a} = \binom{n}{a}\binom{n-a}{k-a}$$

es el siguiente "comité" argumento, que parece ser el más común.

Hay $\binom{n}{k}$ formas de seleccionar $k$ a partir de un conjunto de $n$ para entrar en el comité, y, a continuación, $\binom{k}{a}$ formas de seleccionar $a$ a partir de que el comité de $k$ ir en un sub-comité de tamaño $a$. Esto es equivalente a cambiar el orden de selección para la primera elección de la sub-comité de $a$ a partir del conjunto de $n$, entonces la elección de los restantes $k-a$ sobre el comité de $n-a$ posible.

Para cualquiera que esté familiarizado con el "bloque de caminar" interpretación del triángulo de Pascal, ¿cómo podría usted mostrar la misma identidad con un bloque de caminar argumento?

Para aquellos no familiarizados con el bloque de pie, por favor observe las siguientes, sin un riguroso argumento. Hay $\binom{4}{2}$ rutas posibles para llegar al punto de $(4,2)$ en el triángulo de abajo, ya que cada camino de $(4,2)$ requiere $2$ recorridos en la dirección de derecho de $4$ recorridos total. Como otro ejemplo, hay $\binom{2}{0}$ rutas para llegar a $(2,0)$. En general,hay $\binom{n}{k}$ formas de llegar al punto de $(n,k$).

Un ejemplo de un "bloque de caminar" combinatoria argumento de Pascal de la identidad podría ser como sigue. Se observa que el recuento de las formas posibles para llegar a un punto de $(n,k)$ es exactamente la suma de las formas posibles para llegar a los dos puntos que conducen a ella, es decir,$(n-1,k-1), (n-1,k)$. A decir de esta manera algebraica, $\binom{n-1}{k-1} + \binom{n-1}{k} = \binom{n}{k} $.

Answer 1

Yo no soy capaz de salir con un argumento que es fundamentalmente diferente de la "comisión de argumento", pero es posible emitir la totalidad de la prueba en términos geométricos, si uno está dispuesto a pasar a la tercera dimensión.

Considere la posibilidad de una cuadrícula de tres dimensiones análogas a la de sus dos dimensiones. El grid es un cuadrante de un infinito cuadrícula bidimensional; las tres dimensiones analogía sería un octante de una infinita red tridimensional. En la cuadrícula, hay dos direcciones en las que uno se puede mover a izquierda y derecha. Un punto en la cuadrícula está dada por las coordenadas de $(n,k),$ donde $n\ge0$ es el número total de pasos y $k$ ($0\le k\le n$) es el número de pasos correctos. En la versión tridimensional, hay tres direcciones en las que uno se puede mover, que vamos a llamar a la izquierda, la derecha y la espalda. (Piense en "volver" como la dirección en la página). Un punto en la cuadrícula puede ser dada en coordenadas $(n,k,a),$ donde $n$ es el número total de pasos, $k$ ($0\le k\le n$) es el número de la izquierda y a la derecha los pasos (es decir, la no-pasos), y $a$ ($0\le a\le k$) es el número de pasos a la izquierda.

Los dos lados de la identidad de ambos es igual al número de red tridimensional rutas de unirse a $(0,0,0)$ $(n,k,a),$y corresponden a diferentes formas de descomposición de una red tridimensional de ruta en dos de dos dimensiones de la cuadrícula de caminos. En dos dimensiones, las dos direcciones de movimiento podría ser dado de coordenadas $$ L:\ \left(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right)\qquad R:\ \left(\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}}\right). $$ En tres dimensiones, las tres direcciones, se le podría dar coordenadas $$ L:\ \left(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{3}}\right)\qquad R:\ \left(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{3}}\right),\qquad B:\ \izquierdo(0,-\sqrt{\frac{2}{3}},-\frac{1}{\sqrt{3}}\right). $$ Si proyectamos la $x$-coordinar en este sistema de coordenadas, luego a la izquierda y a la derecha los pasos de la misma apariencia: ambas corresponden a un movimiento que podríamos llamar "de frente", $$ F:\ \izquierdo(0,\frac{1}{\sqrt{6}},-\frac{1}{\sqrt{3}}\right). $$ Un camino de $(0,0,0)$ $(n,k,a)$a continuación, se compone de $k$ frente pasos y $n-k$ pasos. El número de rutas es $\binom{n}{k}.$ Si tenemos en proyecto la parte de atrás de coordenadas, es decir, proyectamos en el plano de la izquierda y la derecha pasos, entonces podemos eliminar de manera eficaz todos los pasos de la ruta de acceso. Este camino consiste entonces en $k$, $a$ de los que están a la izquierda pasos, y $k-a$ de los cuales son los pasos correctos. Hay $\binom{k}{a}$ rutas de acceso. El número de trayectorias tridimensionales está dada por el producto de los números de las rutas en estos dos proyecciones, que es el lado izquierdo de su identidad.

Para obtener el lado derecho de la identidad, se realiza una proyección de modo que la derecha y la espalda pasos parecen unos a otros y a la izquierda los pasos son iguales. (No es terriblemente relevante a la combinatoria, pero esta proyección se logra mediante el mapa de $v\mapsto v-(n\cdot v)n$ donde $$ n=\left(\frac{1}{2},-\frac{\sqrt{3}}{2},0\right) $$ es el vector unitario ortogonal a la $L$ dirección y el $z$ eje. Bajo esta proyección, el $R$ $B$ direcciones se asignan a $$ N:\ \left(-\frac{1}{2\sqrt{2}},-\frac{1}{2\sqrt{6}},-\frac{1}{\sqrt{3}}\right). $$ Aquí $N$ es sinónimo de "no-izquierda".) Las tres dimensiones de la ruta, a continuación, los proyectos en una ruta que consta de $a$ a la izquierda pasos y $n-a$ no-izquierda pasos. Hay $\binom{n}{a}$ rutas de acceso. Si proyectamos en el plano de la derecha y de nuevo los pasos, que elimina de forma efectiva a la izquierda pasos, nos quedamos con un camino de $n-a$, $k-a$ de los cuales son los pasos correctos y $n-k$ de los cuales son de nuevo los pasos. Hay $\binom{n-a}{k-a}$ rutas de acceso. De nuevo, el número de trayectorias tridimensionales está dada por el producto de los números de las rutas en estos dos proyecciones.

Este es, por supuesto, el comité argumento: el de la izquierda y a la derecha los pasos son los miembros del comité, y a la izquierda los pasos son los miembros de las comisiones especiales. Los pasos son los no-miembros de la comisión.

Añadido: En mi opinión, la mejor manera de buscar una identidad fue dado en Marc van Leeuwen la respuesta aquí. Deje $b=k-a$ y deje $c=n-k$, de modo que $k=a+b$$n=a+b+c.$, Entonces la identidad se convierte en $$\binom{n}{a+b}\binom{a+b}{a}=\binom{n}{a}\binom{n-a}{b},$$ la cual puede escribirse como $$\binom{n}{c}\binom{n-c}{a}=\binom{n}{a}\binom{n-a}{b}.$$ Este último consta de dos piezas de la seis-forma de identidad $$\begin{aligned} \binom{n}{a}\binom{n-a}{b}=\binom{n}{a}\binom{n-a}{c}&=\binom{n}{b}\binom{n-b}{a}=\binom{n}{b}\binom{n-b}{c}\\ &=\binom{n}{c}\binom{n-c}{a}=\binom{n}{c}\binom{n-c}{b} \end{aligned}$$ en la que los roles de $a,$ $b,$ y $c$ han sido permutada en todas las formas posibles. Estos corresponden a seis maneras diferentes de escribir el trinomio coeficiente de $$ \binom{n}{a,b,c}=\frac{n!}{a!\,b!\,c!}. $$ Las seis vías de la identidad es fácil de demostrar ya que todos los seis expresiones telescopio para dar el lado derecho de la fórmula anterior. Por ejemplo, $$ \binom{n}{b}\binom{n-b}{a}=\frac{n!}{b!(n-b)!}\frac{(n-b)!}{una!(n-a-b)!}=\frac{n!}{a!\,b!\,c!}, $$ donde hemos utilizado $n-a-b=c.$ La misma prueba en las obras para las seis expresiones.

En términos de la imagen geométrica que describí anteriormente, las dos primeras de las seis expresiones corresponden a la proyección de lo que la derecha y la espalda pasos parecidos y, a continuación, la proyección sobre el plano de la derecha y de nuevo los pasos; el segundo, dos corresponden a la proyección, de modo que la espalda y la izquierda pasos parecidos y, a continuación, la proyección sobre el plano de atrás y de izquierda pasos; los dos últimos corresponden a la proyección, de modo que a la izquierda y a la derecha los pasos parecidos y, a continuación, proyectando sobre el plano de la izquierda y a la derecha los pasos. En cada par, ambas expresiones contar la misma cosa: por ejemplo, en el primer par, $\binom{n-a}{b}$ $\binom{n-a}{c}$ tanto en contar el número de rutas de acceso que consta de $b$ pasos correctos y $c$ pasos.

Tenga en cuenta que el $6=3!$ telescópica expresiones para que el trinomio coeficiente de convertirse $\ell!$ expresiones en el caso de los coeficientes multinomiales (con $n=a_1+a_2+\ldots+a_\ell$): $$ \begin{aligned} &\binom{n}{a_1,a_2,\ldots,a_\ell}=\frac{n!}{a_1!\,a_2!\,\ldots,a_\ell!}\\ &\quad=\frac{n!}{a_1!(n-a_1)!}\frac{(n-a_1)!}{a_2!(n-a_1-a_2)!}\frac{(n-a_1-a_2)!}{a_3!(n-a_1-a_2-a_3)!}\ldots\frac{(n-a_1-\ldots-a_{\ell-1})!}{a_\ell!(n-a_1-\ldots-a_\ell)!}\\ &\quad=\binom{n}{a_1}\binom{n-a_1}{a_2}\binom{n-a_1-a_2}{a_3}\ldots\binom{n-a_1-\ldots-a_{\ell-1}}{a_\ell}. \end{aligned} $$ Se observa que el $\ell^\text{th}$ coeficiente binomial en el producto siempre es igual a $1$ y puede ser omitido ya que $n-a_1-\ldots-a_{\ell-1}=a_\ell.$ Esto es lo que se hizo en su identidad original. Permutaciones de las $a_j$ dar $\ell!$ diferentes expresiones para el multinomomial coeficiente. Tales expresiones deben ser interpretables en términos de diferentes series de proyecciones de un $\ell$-dimensiones de la cuadrícula.

Comentarios adicionales: La dificultad con la interpretación de esta identidad geométricamente es que contiene los productos de los coeficientes binomiales. El producto podría representar la concatenación de caminos, pero el conjunto de rutas descritas en la izquierda no se miran como el conjunto de rutas descritas en el derecho. (Tienen diferentes puntos finales, diferentes números de pasos, y así sucesivamente.) Uno puede idear un bijection entre el conjunto de rutas de contado por el lado izquierdo y el conjunto de rutas a contar por la derecha, pero esto es esencialmente el comité argumento, y no es en absoluto natural—al menos de la manera que se me ocurrió no lo es. Mi respuesta fue un intento de interpretar la multiplicación en términos de la combinación de diferentes proyecciones en lugar de en términos de la concatenación. Todavía no he sido capaz de llegar a cualquier otra interpretación geométrica de la multiplicación.

Answer 2

Vamos a ver en las rutas de la parte superior del triángulo con la longitud de la $n$ $k$ pasos a la izquierda (e $n-k$ a la derecha). Supongamos también que hay $a$ 'especial' pasos a la izquierda. (El conjunto de pasos especiales es un subconjunto del conjunto de todos los pasos a la izquierda.) Vamos a calcular el número de rutas en dos maneras.

En primer lugar, sólo miramos todas las rutas sin tener en cuenta los pasos especiales. Hay $\binom nk$ este tipo de rutas. Para cada ruta tenemos que seleccionar $a$ $k$ a la izquierda pasos para ser especial. Podemos hacer esto en $\binom ka$ formas para cada ruta, así que en total, obtenemos $\binom nk\binom ka$.

Ahora, supongamos que seleccionar primero $a$ $n$ pasos a pasos especiales (a la izquierda). Esto le da a $\binom na$ de posibilidades (a partir de la definición de la binomial). Ahora, desde el restante $n-a$ pasos, tenemos que seleccionar $k-a$ pasos a la izquierda: $\binom {n-a}{k-a}$ posibilidades.
Juntos, obtenemos la siguiente igualdad: $$ \binom nk\binom ka=\binom na\binom{n}{k} $$

(¿alguien sabe cómo hacer que todos los binomios del mismo tamaño?)