1.2: Coeficientes binomiales

Template:MathJaxLevin

¡Investiga!

En el ajedrez, una grada solo puede moverse en líneas rectas (no diagonalmente). Rellena cada cuadrado del tablero de ajedrez de abajo con el número de diferentes caminos más cortos que la grada, en la esquina superior izquierda, puede tomar para llegar a esa plaza. Por ejemplo, ya está rellenado un cuadrado. Hay seis caminos diferentes desde la grada hasta la plaza: DDRR (abajo a la derecha), DRDR, DRRD, RDDR, RDRD y RRDD.

Aquí hay algunos objetos discretos aparentemente diferentes que podemos contar: subconjuntos, cadenas de bits, rutas de celosía y coeficientes binomiales. Vamos a dar un ejemplo de cada tipo de problema de conteo (y decir cuáles son estas cosas incluso). Como veremos, estos problemas de conteo son sorprendentemente similares.

Subconjuntos

Los subconjuntos deberían ser familiares, de lo contrario, leer de nuevo la Sección 0.3. Supongamos que miramos el conjunto$A = \{1,2,3,4,5\}$. ¿Cuántos subconjuntos de$A$ contienen exactamente 3 elementos?

Primero, una pregunta más sencilla: ¿Cuántos subconjuntos de$A$ hay totales? En otras palabras, ¿qué es$|\pow(A)|$ (la cardinalidad del conjunto de poder de$A$)? Piensa en cómo construiríamos un subconjunto. Tenemos que decidir, para cada uno de los elementos de$A\text{,}$ si incluir o no el elemento en nuestro subconjunto. Entonces tenemos que decidir “sí” o “no” para el elemento 1. Y para cada elección que hagamos, tenemos que decidir “sí” o “no” para el elemento 2. Y así sucesivamente. Para cada uno de los 5 elementos, tenemos 2 opciones. Por lo tanto, el número de subconjuntos es simplemente$2\cdot 2\cdot 2 \cdot 2\cdot 2 = 2^5$ (por el principio multiplicativo).

De esos 32 subconjuntos, ¿cuántos tienen 3 elementos? Esto no es obvio. Tenga en cuenta que no podemos simplemente usar el principio multiplicativo. A lo mejor queremos decir que tenemos 2 opciones (sí/no) para el primer elemento, 2 opciones para el segundo, 2 opciones para el tercero, y luego solo 1 opción para los otros dos. Pero, ¿y si dijéramos “no” a uno de los tres primeros elementos? Entonces tendríamos dos opciones para el 4to elemento. ¡Qué desastre!

Otra (mala) idea: necesitamos escoger tres elementos para estar en nuestro subconjunto. Hay 5 elementos para elegir. Entonces hay 5 opciones para el primer elemento, y para cada una de esas 4 opciones para el segundo, y luego 3 para el tercer (último) elemento. El principio multiplicativo diría entonces que hay un total de$5 \cdot 4 \cdot 3 = 60$ formas de seleccionar el subconjunto de 3 elementos. Pero esto no puede ser correcto ($60 > 32$por una cosa). Uno de los resultados que obtendríamos de estas elecciones sería el conjunto$\{3,2,5\}\text{,}$ eligiendo primero el elemento 3, luego el elemento 2, luego el elemento 5. Otro resultado sería$\{5,2,3\}$ elegir primero el elemento 5, luego el elemento 2, luego el elemento 3. ¡Pero estos son el mismo conjunto! Podemos corregir esto dividiendo: para cada conjunto de tres elementos, hay 6 resultados contados entre nuestros 60 (ya que hay 3 opciones para qué elemento enumeramos primero, 2 para las cuales enumeramos en segundo lugar, y 1 para la que enumeramos el último). Por lo que esperamos que haya 10 subconjuntos de 3 elementos de$A$.

¿Es esto correcto? Bueno, podríamos enumerar los 10, siendo muy sistemáticos al hacerlo, para asegurarnos de que no nos faltemos ninguno ni enumeremos dos veces. O podríamos intentar contar cuántos subconjuntos de$A$ no tienen 3 elementos en ellos. ¿Cuántos no tienen elementos? Sólo 1 (el conjunto vacío). ¿Cuántos tienen 5? Nuevamente, apenas 1. Estos son los casos en los que decimos “no” a todos los elementos, o “sí” a todos los elementos. Bien, ¿qué pasa con los subconjuntos que contienen un solo elemento? Hay 5 de estos. Debemos decir “sí” a exactamente un elemento, y hay 5 para elegir. Este es también el número de subconjuntos que contienen 4 elementos. Esos son los que debemos decir “no” a exactamente un elemento.

Hasta el momento hemos contado 12 de los 32 subconjuntos. Aún no hemos contado los subconjuntos con cardinalidad 2 y con cardinalidad 3. Quedan un total de 20 subconjuntos por dividir entre estos dos grupos. ¡Pero el número de cada uno debe ser el mismo! Si decimos “sí” a exactamente dos elementos, eso se puede lograr exactamente de la misma cantidad de formas que el número de formas podemos decir “no” a exactamente dos elementos. Entonces, el número de subconjuntos de 2 elementos es igual al número de subconjuntos de 3 elementos. En conjunto hay 20 de estos subconjuntos, por lo que 10 cada uno.

Número de elementos:	0	1	2	3	4	5
Número de subconjuntos:	1	5	10	10	5	1

Cuerdas de bits

“Bit” es la abreviatura de “dígito binario”, por lo que una cadena de bits es una cadena de dígitos binarios. Los dígitos binarios son simplemente los números 0 y 1. Todas las siguientes son cadenas de bits:

\ begin {equation*} 1001\ quad 0\ quad 1111\ quad 1010101010\ end {ecuación*}

El número de bits (0's o 1's) en la cadena es la longitud de la cadena; las cadenas anteriores tienen longitudes 4, 1, 4 y 10 respectivamente. También podemos preguntar cuántos de los bits son 1. El número de 1 en una cadena de bits es el peso de la cadena; los pesos de las cadenas anteriores son 2, 0, 4 y 5 respectivamente.

Definición: Bit Strings

• Una cadena$n$ -bit es una cadena de bits de longitud$n$. Es decir, es una cadena que contiene$n$ símbolos, cada uno de los cuales es un bit, ya sea 0 o 1.
• El peso de una cadena de bits es el número de 1's en ella.
• $\B^n$es el conjunto de todas las$n$ cadenas de bits.
• $\B^n_k$es el conjunto de todas las cadenas de peso de$n$ -bit$k$.

Por ejemplo, los elementos del conjunto$\B^3_2$ son las cadenas de bits 011, 101 y 110. Esas son las únicas cadenas que contienen tres bits exactamente dos de los cuales son 1's.

Las preguntas de conteo: ¿Cuántas cadenas de bits tienen longitud 5? ¿Cuántos de esos tienen peso 3? Es decir, estamos pidiendo las cardinalidades$|\B^5|$ y$|\B^5_3|$.

Encontrar el número de cadenas de 5 bits es sencillo. Tenemos 5 bits, y cada uno puede ser un 0 o un 1. Así que hay 2 opciones para el primer bit, 2 opciones para el segundo, y así sucesivamente. Por el principio multiplicativo, existen$2 \cdot 2 \cdot 2\cdot 2 \cdot 2 = 2^5 = 32$ tales cadenas.

Encontrar el número de cadenas de 5 bits de peso 3 es más difícil. Piensa en cómo podría comenzar una cadena así. El primer bit debe ser un 0 o un 1. En el primer caso (la cadena comienza con un 0), entonces debemos decidir cuatro bits más. Para tener un total de tres 1's, entre esos cuatro bits restantes debe haber tres 1's. Para contar todas estas cadenas, debemos incluir todas las cadenas de 4 bits de peso 3. En el segundo caso (la cadena comienza con un 1), todavía tenemos cuatro bits para elegir, pero ahora solo dos de ellos pueden ser 1's, así que deberíamos mirar todas las cadenas de 4 bits de peso 2. Entonces las cadenas en$\B^5_3$ todas tienen la forma$1\B^4_2$ (es decir, un 1 seguido de una cadena de$\B^4_2$) o$0\B^4_3$. Estos dos conjuntos son disjuntos, por lo que podemos usar el principio aditivo:

\ begin {ecuación*} |\ B^5_3| = |\ B^4_2| + |\ B^4_3|. \ end {ecuación*}

Este es un ejemplo de una relación de recurrencia. Representamos una instancia de nuestro problema de conteo en términos de dos instancias más simples del problema. Si tan sólo supiéramos las cardinalidades de$\B^4_2$ y$\B^4_3$. Repitiendo el mismo razonamiento,

\ begin {ecuación*} |\ B^4_2| = |\ B^3_1| + |\ B^3_2|\ quad\ mbox {y}\ quad |\ B^4_3| = |\ B^3_2| + |\ B^3_3|. \ end {ecuación*}

Podemos seguir bajando, pero esto debería ser lo suficientemente bueno. Ambos$\B^3_1$ y$\B^3_2$ contienen cadenas de 3 bits: debemos elegir uno de los tres bits para que sea un 1 (tres formas de hacerlo) o uno de los tres bits para que sea un 0 (tres formas de hacerlo). Además,$\B^3_3$ contiene solo una cadena: 111. Así$|\B^4_2| = 6$ y$|\B^4_3| = 4\text{,}$ que pone$\B^5_3$ en un total de 10 cuerdas.

Pero espera —32 y 10 fueron las respuestas a las preguntas de conteo sobre subconjuntos. ¿Coincidencia? En absoluto. Cada cadena de bits se puede considerar como un código para un subconjunto. Para el conjunto$A = \{1,2,3,4,5\}\text{,}$ usaríamos cadenas de 5 bits, un bit por cada elemento de$A$. Cada bit en la cadena es un 0 si su elemento correspondiente de no$A$ está en el subconjunto, y un 1 si el elemento de$A$ está en el subconjunto. Recuerde, decidir el subconjunto ascendió a una secuencia de cinco votos sí/no para los elementos de$A$. En vez de sí, ponemos un 1; en lugar de no, ponemos un 0.

Por ejemplo, la cadena de bits$11001$ representa el subconjunto$\{1,2,5\}$ ya que el primer, segundo y quinto bits son 1. El subconjunto$\{3,5\}$ estaría codificado por la cadena$00101$. Lo que realmente tenemos aquí es una bijección de$\pow(A)$ a$\B^5$.

Ahora, para que un subconjunto contenga exactamente tres elementos, la cadena de bits correspondiente debe contener exactamente tres 1's, es decir, el peso debe ser 3. Así, contar el número de subconjuntos de 3 elementos de$A$ es lo mismo que contar el número de cadenas de 5 bits de peso 3.

Caminos de celosía

La celosía entera es el conjunto de todos los puntos en el plano cartesiano para los que tanto las$y$ coordenadas$x$ y son números enteros. Si te gusta dibujar gráficas en papel cuadriculado, la celosía es el conjunto de todas las intersecciones de las líneas de la cuadrícula.

Un camino de celosía es uno de los caminos más cortos posibles que conecta dos puntos en la celosía, moviéndose solo horizontal y verticalmente. Por ejemplo, aquí hay tres posibles caminos de celosía desde los puntos$(0,0)$ hasta$(3,2)\text{:}$

Aviso para asegurar que el camino sea el más corto posible, cada movimiento debe ser ya sea a la derecha o hacia arriba. Adicionalmente, en este caso, tenga en cuenta que no importa qué camino tomemos, debemos hacer tres pasos correctos y dos escalones hacia arriba. No importa qué orden hagamos estos pasos, siempre habrá 5 pasos. Así, cada camino tiene una longitud 5.

La pregunta de conteo: cuántos caminos de celosía hay entre$(0,0)$ y$(3,2)\text{?}$ Podríamos tratar de dibujar todos estos, o en lugar de dibujarlos, tal vez solo enumerar qué dirección viajamos en cada uno de los 5 pasos. Un camino podría ser RRUUR, o tal vez UURRR, o quizás RURRU (esos corresponden a los tres caminos dibujados arriba). Entonces, ¿cuántas cadenas de R y U hay?

Observe que cada una de estas cadenas debe contener 5 símbolos. Exactamente 3 de ellos deben ser R's (ya que nuestro destino es 3 unidades a la derecha). Esto me parece muy familiar. De hecho, ¿y si$1$ usáramos's en lugar de R y 0 en lugar de U? Entonces solo tendríamos cadenas de 5 bits de peso 3. Hay 10 de esos, por lo que hay 10 caminos de celosía de (0,0) a (3,2).

La correspondencia entre las cadenas de bits y las rutas de celosía no se detiene ahí. Aquí hay otra forma de contar los caminos de celosía. Considere la celosía que se muestra a continuación:

Cualquier camino de celosía de (0,0) a (3,2) debe pasar exactamente por uno de$A$ y$B$. El punto$A$ está a 4 pasos de (0,0) y dos de ellos están hacia la derecha. El número de rutas de celosía a$A$ es el mismo que el número de cadenas de 4 bits de peso 2, es decir, 6. El punto$B$ está a 4 pasos de (0,0), pero ahora 3 de ellos están hacia la derecha. Entonces el número de rutas a punto$B$ es el mismo que el número de cadenas de 4 bits de peso 3, es decir, 4. Entonces el número total de rutas a (3,2) es justo$6+4$. Esta es la misma forma en que calculamos el número de cadenas de 5 bits de peso 3. El punto: existe exactamente la misma relación de recurrencia para las cadenas de bits y para las rutas de celosía.

Coeficientes binomiales

Los coeficientes binomiales son los coeficientes en la versión expandida de un binomio, como$(x+y)^5$. ¿Qué pasa cuando multiplicamos tal binomio? Ampliaremos$(x+y)^n$ por diversos valores de$n$. Cada uno de estos se hace multiplicando todo (es decir, Foil-ing) y luego recolectando términos similares.

\ begin {ecuación*} (x+y) ^1 = x + y\ end {ecuación*}\ begin {ecuación*} (x+y) ^2 = x^2 + 2xy + y^2\ end {ecuación*}\ begin {ecuación*} (x+y) ^3 = x^3 + 3x^2y + 3xy^2 + y^3\ end {ecuación* *}\ comenzar {ecuación*} (x+y) ^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4. \ end {ecuación*}

De hecho, hay una manera más rápida de expandir los binomios anteriores. Por ejemplo, considere el siguiente,$(x+y)^5$. Lo que realmente estamos haciendo es multiplicar,

\ begin {ecuación*} (x+y) (x+y) (x+y) (x+y) (x+y) (x+y). \ end {ecuación*}

Si eso parece desalentador, volver al caso de$(x+y)^3 = (x+y)(x+y)(x+y)$. ¿Por qué solo tenemos uno$x^3$ y$y^3$ pero tres$x^2y$ y$xy^2$ términos? Cada vez que distribuimos sobre una$(x+y)$ creamos dos copias de lo que queda, una multiplicada por$x\text{,}$ la otra multiplicada por$y$. Para conseguir$x^3\text{,}$ tenemos que escoger el lado “multiplicado por$x$” cada vez (no tenemos$y$ ningunos en el término). Esto sólo sucederá una vez. Por otro lado, para conseguir$x^2y$ necesitamos seleccionar el$x$ lado dos veces y el$y$ lado una vez. Es decir, tenemos que escoger uno de los tres$(x+y)$ términos para “aportar” su$y$.

De igual manera, en la expansión de sólo$(x+y)^5\text{,}$ habrá un$x^5$ término y un$y^5$ término. Esto se debe a que para obtener una$x^5\text{,}$ necesitamos usar el$x$ término en cada una de las copias del binomio$(x+y)\text{,}$ y de manera similar para$y^5$. Y$x^4y\text{?}$ para obtener términos como este, necesitamos usar cuatro$x$ y uno$y\text{,}$ así necesitamos exactamente uno de los cinco binomios para contribuir a$y$. Hay 5 opciones para esto, por lo que hay 5 formas de obtener$x^4y\text{,}$ así que el coeficiente de$x^4y$ es 5. Este es también el coeficiente$xy^4$ para por la misma razón (pero opuesta): hay 5 formas de escoger cuál de los 5 binomios aporta el sencillo$x$. Hasta el momento tenemos

\ begin {ecuación*} (x+y) ^5 = x^5 + 5x^4y +\ subrayado {~? ~} ~x^3y^2 +\ subrayado {~? ~} ~x^2y^3 + 5 xy^4 + y^5. \ end {ecuación*}

Todavía necesitamos los coeficientes de$x^3y^2$ y$x^2y^3$. En ambos casos, necesitamos escoger exactamente 3 de los 5 binomios para aportar una variable, los otros dos para aportar la otra. Espera. Esto suena familiar. Tenemos 5 cosas, cada una puede ser una de dos cosas, y necesitamos un total de 3 de una de ellas. Eso es como tomar 5 bits y asegurarse que exactamente 3 de ellos son 1's Así que el coeficiente de$x^3y^2$ (y también$x^2y^3$) será exactamente el mismo que el número de cadenas de bits de longitud 5 y peso 3, que antes encontramos que era 10. Así que tenemos:

\ begin {ecuación*} (x+y) ^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5 xy^4 + y^5. \ end {ecuación*}

Estos números seguimos viendo una y otra vez. Son el número de subconjuntos de un tamaño particular, el número de cadenas de bits de un peso particular, el número de trayectorias de celosía y los coeficientes de estos productos binomiales. Los llamaremos coeficientes binomiales. Incluso tenemos un símbolo especial para ellos:${n \choose k}$.

Definición: Coeficientes binomiales

Para cada entero$n \ge 0$ y entero$k$ con$0 \le k \le n$ hay un número

\ comenzar {ecuación*} {n\ elige k}\ final {ecuación*}

leer “$n$elegir”$k$. Contamos con:

• ${n\choose k} = |\B^n_k|\text{,}$el número de cadenas de$n$ -bit de peso$k$.
• ${n \choose k}$es el número de subconjuntos de un conjunto de tamaños$n$ cada uno con cardinalidad$k$.
• ${n \choose k}$es el número de trayectorias de celosía de longitud$n$ que contienen$k$ escalones a la derecha.
• ${n \choose k}$es el coeficiente de$x^ky^{n-k}$ en la expansión de$(x+y)^n$.
• ${n \choose k}$es el número de formas de seleccionar$k$ objetos de un total de$n$ objetos.

El último punto de viñeta suele tomarse como definición de${n \choose k}$. De los$n$ objetos debemos elegir$k$ de ellos, así que hay$n$ elegir$k$ formas de hacerlo. Cada uno de nuestros problemas de conteo anteriores se puede ver de esta manera:

• ¿Cuántos subconjuntos de$\{1,2,3,4,5\}$ contienen exactamente 3 elementos? Debemos elegir$3$ de los 5 elementos para estar en nuestro subconjunto. Hay${5 \choose 3}$ formas de hacer esto, por lo que hay${5 \choose 3}$ tales subconjuntos.
• ¿Cuántas cadenas de bits tienen longitud 5 y peso 3? Debemos elegir$3$ de los 5 bits para que sean 1's Hay${5 \choose 3}$ formas de hacerlo, así que hay${5 \choose 3}$ tales cadenas de bits.
• ¿Cuántas trayectorias de celosía hay de (0,0) a (3,2)? Debemos elegir 3 de los 5 pasos para estar hacia la derecha. Hay${5 \choose 3}$ formas de hacer esto, entonces hay${5 \choose 3}$ tales caminos de celosía.
• Cuál es el coeficiente de$x^3y^2$ en la expansión de$(x+y)^5\text{?}$ Debemos elegir 3 de los 5 ejemplares del binomio para aportar un$x$. Hay${5 \choose 3}$ formas de hacer esto, entonces el coeficiente es${5 \choose 3}$.

Debe quedar claro que en cada caso anterior, tenemos la respuesta correcta. Todo lo que teníamos que hacer es formular la pregunta correctamente y se hizo evidente que${5 \choose 3}$ es correcto. No obstante, esto no nos dice que la respuesta es de hecho 10 en cada caso. Eventualmente encontraremos una fórmula para${n \choose k}\text{,}$ pero por ahora, mira hacia atrás a cómo llegamos a la respuesta 10 en nuestros problemas de conteo anteriores. Todo se redujo a cadenas de bits, y tenemos una relación de recurrencia para las cadenas de bits:

\ begin {ecuación*} |\ b^n_k| = |\ B^ {n-1} _ {k-1} | + |\ B^ {n-1} _k|. \ end {ecuación*}

Recuerda, esto se debe a que podemos iniciar la cadena de bits con un 1 o un 0. En ambos casos, tenemos$n-1$ más pedacitos que escoger. Las cadenas que comienzan con 1 deben contener$k-1$ más 1's, mientras que las cadenas que comienzan con 0 todavía necesitan$k$ más 1's.

Dado que$|\B^n_k| = {n \choose k}\text{,}$ la misma relación de recurrencia se mantiene para los coeficientes binomiales:

Relación de recurrencia para${n \choose k}$

\ comenzar {ecuación*} {n\ elige k} = {n-1\ elige k-1} + {n-1\ elige k}\ final {ecuación*}

Triángulo de Pascal

Arreglemos los coeficientes binomiales${n \choose k}$ en un triángulo como sigue:

Esto puede continuar tan abajo como nos guste. La relación de recurrencia para nos${n \choose k}$ dice que cada entrada en el triángulo es la suma de las dos entradas por encima de él. Las entradas a los lados del triángulo son siempre 1. Esto se debe a que${n \choose 0} = 1$ para todos$n$ ya que solo hay una manera de escoger 0 de$n$ los objetos y${n \choose n} = 1$ ya que hay una manera de seleccionar todos$n$ fuera de los$n$ objetos. Usando la relación de recurrencia, y el hecho de que los lados del triángulo son 1's, podemos reemplazar fácilmente todas las entradas anteriores con los valores correctos de${n \choose k}$. Hacerlo nos da el triángulo de Pascal.

Podemos usar el triángulo de Pascal para calcular los coeficientes binomiales. Por ejemplo, usando el triángulo de abajo, podemos encontrar${12 \choose 6} = 924$.