¿Por qué funciona el triángulo de Pascal?

Suponga que desea elegir r objetos de una colección de n objetos. ¿De cuántas maneras hay para hacerlo [matemáticas] ^ {n} C_ {r} [/ matemáticas]? Elija cualquier objeto de entre los n objetos y llámelo A. Si va a elegir r objetos, estos r objetos incluyen A o no.

¿De cuántas maneras hay para escoger objetos r incluyendo A ? Bueno, tenemos que elegir A , por lo que debemos elegir r-1 más objetos de una colección de n-1 objetos (excluyendo A ). Esa es solo la cantidad de formas de elegir objetos r-1 de n-1 objetos [matemática] ^ {n-1} C_ {r-1} [/ matemática].

¿De cuántas maneras hay para escoger objetos r excluyendo A ? Eso es solo elegir objetos r de una colección de n-1 objetos (excluyendo A ). Eso es [matemáticas] ^ {n-1} C_ {r} [/ matemáticas].

Sumando estos dos, obtienes el resultado que deseas. Así es como se forma el triángulo de Pascal (agregando dos términos para obtener el término correspondiente a continuación), por lo que si comienza con 1C0 y 1C1 (la segunda fila) y hace la suma, todo mientras agrega los casos de borde en el exterior, Funciona muy bien.

Me resulta más fácil de entender en términos de caminos más cortos en una red como el de la izquierda arriba que se muestra con coordenadas de ejemplo. La cuadrícula de la derecha muestra el número de caminos más cortos para cada coordenada de la red, pero llegaremos a eso.

Tome una cuadrícula de coordenadas estándar (o retícula ), cada punto de cruce de las líneas de la cuadrícula tiene coordenadas enteras [matemáticas] (x, y) [/ matemáticas] donde, como es habitual, [matemáticas] x [/ matemáticas] representa la coordenada horizontal y [matemáticas] y [/ matemáticas] la vertical. Ahora imaginamos atravesando una ruta desde el origen [math] \ text {O} (0,0) [/ math] a alguna coordenada [math] (x, y) [/ math], esta ruta viaja a lo largo de las líneas de la cuadrícula, por lo que que tomamos el camino más corto a [math] (x, y) [/ math], estos son los “caminos más cortos” mencionados anteriormente.

Claramente, puede haber muchos de estos caminos a algún punto general [matemática] (x, y) [/ matemática], pero todos tienen pasos horizontales [matemáticos] x [/ matemáticos] y escalones verticales [matemáticos] y [/ matemáticos]. Nuestro objetivo es contar el número total de caminos más cortos para cada [matemática] (x, y) [/ matemática] en la red. La primera forma en que podemos hacer esto es contando literalmente los caminos más cortos a cada punto de la red. Sin embargo, no hacemos esto de manera aleatoria, lo hacemos de la manera más fácil comenzando en el origen y trabajando o atravesando la cuadrícula:

  • Hay 1 camino más corto desde [math] (0,0) [/ math] a [math] (0,0) [/ math] este es el camino donde no nos movemos.
  • Hay 1 ruta más corta de [matemáticas] (0,0) [/ matemáticas] a [matemáticas] (1,0) [/ matemáticas] y 1 ruta más corta a [matemáticas] (0,1) [/ matemáticas] de hecho podemos ver que solo habrá 1 ruta a cada punto en el eje xy cada punto en el eje y. Entonces completamos esos números en cada punto de la red a lo largo de los ejes (como la cuadrícula de la derecha arriba).
  • ¿Cuántos caminos más cortos deben apuntar [math] (1,1) [/ math] entonces? Bueno, hay 1 ruta más corta a [matemáticas] (1,0) [/ matemáticas] y 1 ruta más corta a [matemáticas] (0,1) [/ matemáticas] y para llegar a [matemáticas] (1,1 ) [/ math] nuestra ruta debe llevarnos a través de [math] (1,0) [/ math] o [math] (0,1) [/ math] por lo que sumamos esto: [math] 1 + 1 = 2 [/ math] y este es el número que entra en nuestra coordenada [math] (1,1) [/ math] en la cuadrícula de la derecha.

A partir de este último ejemplo, puede ver que cualquier ruta más corta a [math] (x, y) [/ math] debe llegar a través de [math] (x-1, y) [/ math] o [math] (x, y-1) [/ math] y de ninguna otra manera , todos los caminos más cortos deben pasar por estas dos coordenadas vecinas. Por lo tanto, podemos agregar los números en los puntos de la red [math] (x-1, y) [/ math] y [math] (x, y-1) [/ math] para dar el número en el punto de la red [math] (x , y) [/ matemáticas]. Como puede ver, así es como se completó la cuadrícula de la derecha arriba, cada entrada en [math] (x, y) [/ math] es el número de rutas de red más cortas desde [math] (0,0) [ / matemáticas] a ese punto.

Ahora todo esto “agregando entradas vecinas” debería sonar algunas campanas porque si ahora giramos la rejilla de la derecha 135 ° en el sentido de las agujas del reloj, tenemos el familiar Triángulo de Pascal (al menos, hasta la diagonal “1, 4, 6, 4, 1 “, Sin embargo, si continuamos rellenando la cuadrícula obtendríamos el resto del Triángulo de Pascal). En este punto, debería comenzar a ver emerger una interpretación completamente nueva, ¿cómo podríamos explotar esto para comprender las entradas del Triángulo de Pascal en términos de elegir cosas?

Para responder la última pregunta, veamos un ejemplo específico de una ruta más corta

Esto muestra una ruta más corta desde [matemática] (0,0) [/ matemática] a [matemática] (7,5) [/ matemática] y para clasificar esta ruta de manera única podemos representarla como un conjunto de instrucciones como si estábamos dirigiendo a alguien a lo largo de las líneas de la cuadrícula. Podríamos decidir instruir usando “right” y “up”, por ejemplo, entonces las instrucciones de ruta comenzarían: “right”, “up”, “right”, “up”, “up” y así sucesivamente. Podríamos usar “Este” y “Norte” o cualquier instrucción similar.

Todo esto es demasiado largo para escribirlo, por lo que podríamos simplificar simplemente usando las letras “R” para “derecha”, “U” para “arriba”, nuestra ruta de ejemplo en la imagen sería la instrucción RURUURRURUR R. Observe que hay son 7 Rs y 5 Us, esto será cierto para cualquier ruta más corta desde [math] (0,0) [/ math] a [math] (7,5) [/ math].

En el diagrama puede ver que la instrucción “1” reemplaza nuestra “R” y “0” reemplaza nuestra “U”. Realmente no importa, pero siendo matemáticamente inclinados, sigamos con “0” y “1”.

Ahora, asignemos un número a cada paso de nuestra ruta para que sepamos lo que estamos haciendo en cualquier punto de nuestra ruta, el paso 1 es “correcto” o “1”, el paso 2 es “arriba” o “0” y así sucesivamente. El camino se ve como

[matemáticas] \ begin {array} {ccccccccccccc} \ text {Número de paso:} y 1 y 2 y 3 y 4 y 5 y 6 y 7 y 8 y 9 y 10 y 11 y 12 \\ \ text {Instrucción:} y 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 1 \ end {array} [/ math]

Esta ruta particular tiene “1” s en las posiciones 1, 3, 6, 7, 9, 11 y 12. Se podría interpretar que significa que esta ruta ” elige ” esos 7 números de los 12 números 1 a 12. De hecho, ya que cada ruta más corta desde [matemática] (0,0) [/ matemática] a [matemática] (7,5) [/ matemática] tendrá 12 movimientos totales (“derecha” o “arriba”, “0” o “1 “) Y 7 movimientos a la derecha que se pueden expresar como un orden de 5” 0 “sy 7” 1 “s, existe una correspondencia directa uno a uno entre cada ruta más corta desde [matemáticas] (0,0) [/ matemática] a [matemática] (7,5) [/ matemática] y cada elección de 7 números del conjunto [matemática] \ {1,2,3,4,5,6,7,8,9,10,11 , 12 \} [/ matemáticas]. Esos 7 números están siendo elegidos por la posición de los “1” s en nuestras instrucciones de ruta, por lo tanto, el número de rutas de [matemáticas] (0,0) [/ matemáticas] a [matemáticas] (7,5) [/ matemáticas ] es la cantidad de formas en que podemos elegir 7 números de 12 (o 7 + 5), que es el coeficiente binomial

[matemáticas] \ dbinom {12} {7} = [/ matemáticas] [matemáticas] ^ {12} C_ {7} = C ^ {12} _ {7} = [/ matemáticas] [matemáticas] _ {12} C_ {7} = \ dfrac {12!} {7! \, 5!} [/ Math]

Este es claramente el número de formas de organizar 7 “1” sy 5 “0” s.

En general, una ruta desde [matemáticas] (0,0) [/ matemáticas] a [matemáticas] (x, y) [/ matemáticas] tendrá una longitud de ruta de [matemáticas] x + y [/ matemáticas] y sus instrucciones serán tener [math] x [/ math] “1” s que elegirá [math] x [/ math] de los elementos [math] x + y [/ math] del conjunto [math] \ {1,2, \ cdots, x + y \} [/ math] por lo tanto hay

[matemáticas] \ dbinom {x + y} {x} [/ matemáticas]

caminos desde [matemáticas] (0,0) [/ matemáticas] a [matemáticas] (x, y) [/ matemáticas].

Podemos ver girando una cuadrícula 135 ° que la entrada en la coordenada [math] (x, y) [/ math] está en la fila [math] x + y [/ math] del triángulo de Pascal y [math] y [/ matemáticas] lugares desde la izquierda

pero por simetría [matemáticas] \ binom {x + y} {x} = \ binom {x + y} {y} [/ matemáticas] así que esto no es un problema, de hecho para cualquier ruta desde [matemáticas] (0, 0) [/ math] a [math] (x, y) [/ math] y es un conjunto de instrucciones que también podríamos dejar que “0” s elija elementos [math] y [/ math] de nuestro conjunto de [math ] 1 [/ math] a [math] x + y [/ math] y esto habría contado [math] \ binom {x + y} {y} [/ math] rutas.


Todas las imágenes son cortesía de Google Images.

Este video aquí muestra cómo funciona en relación con la expansión binomial

La función de elección nCr, como detalla Hongwan Liu, puede relacionarse con las filas y las columnas del triángulo que se visualiza muy bien como una cuadrícula cuando el triángulo se desplaza sobre 🙂