6.3: Combinaciones

Todas las cosas con permutaciones han enfatizado el orden. Alguien obtiene el primer lugar en el torneo de golf, y alguien más obtiene el segundo, y tú apuestas tu último dólar a que importa cuál es cuál es cuál. ¿Y si resulta que no nos importa el pedido? A lo mejor no nos importa quién consiguió qué lugar, sino qué golfistas estaban entre los diez primeros. A lo mejor no nos importa qué película se esté mostrando en qué franja horaria, pero solo qué películas están en la alineación de películas de esta noche.

Este escenario de conteo implica algo llamado combinaciones en lugar de permutaciones. Una combinación de\(k\) objetos fuera de un posible\(n\) es una elección de cualquier conjunto\(k\) de ellos, sin importar el orden. Por ejemplo, supongamos que los tres niños Davies quieren jugar en la Wii, pero solo dos pueden jugar a la vez. ¿Quién va a llegar a jugar primero después de la escuela? Una posibilidad es Lizzy y T.J., otra es Lizzy y Johnny, y la última es T.J. y Johnny. Estas son las tres (y sólo tres) combinaciones de 2 objetos de 3.

Para ver cómo contar estos en general, volvamos al ejemplo del torneo de golf. Supongamos que además de ganar dinero, los tres primeros finalistas de nuestro torneo local también avanzarán al torneo regional. Este es un gran honor, y trae consigo un potencial ganador adicional mucho mayor que el dinero local. Pregunta: ¿cuántos tríos posibles diferentes podríamos enviar a la competencia regional?

A primera vista, esto parece igual que el problema de “cuántas asignaciones de premios en efectivo” de antes, excepto que estamos tomando 3 en lugar de 10. Pero hay un giro. En el problema anterior, importaba quién era primero vs segundo vs tercero. Ahora el orden es irrelevante. Si terminas entre los tres primeros, avanzas, punto. No “avanzas con más fuerza” para terminar primero localmente en lugar de tercero.

No es tan obvio cómo contar esto, pero claro que hay un truco. El truco es contar las permutaciones parciales, pero luego darnos cuenta de lo mucho que superamos, y luego compensarlo en consecuencia.

Si contamos las permutaciones parciales de 3 de 45 golfistas, tenemos\(45^{\underline{3}}\) tales permutaciones. Una de esas permutaciones parciales es:

1.Phil 2.Bubba 3.Tigre

Otro es:

1.Phil 2.Tigre 3.Bubba

y otro más es:

1.Tigre 2.Phil 3.Bubba

Ahora lo importante a reconocer es que en nuestro problema actual —contando el posible número de tríos de golf regionales— las tres diferentes permutaciones parciales representan la misma combinación. En los tres casos, son Bubba, Phil y Tiger quienes representarán a nuestra asociación de golf local en la competencia regional. Entonces, al contar los tres como permutaciones parciales separadas, hemos sobrecontado las combinaciones.

Obviamente queremos contar Bubba/Phil/Tiger solo una vez. Bien entonces. ¿Cuántas veces lo superamos cuando contamos las permutaciones parciales? La respuesta es que contamos a este trío una vez por todas las formas en que se puede permutar. Las tres permutaciones, arriba, fueron ejemplos de ello, y así son estas tres:

1.Tigre 2.Bubba 3.Phil
1.Bubba 2.Tiger 3.Phil
1.Bubba 2.Phil 3.Tigre

Esto hace un total de seis veces que nosotros (redundantemente) contamos la misma combinación cuando contamos las permutaciones parciales. ¿Por qué 6? ¡Porque ese es el valor de 3! , por supuesto. ¡Hay 3! diferentes formas de organizar Bubba, Phil y Tiger, ya que eso es solo una permutación directa de tres elementos. Y así nos encontramos con que cada trío que queremos dar cuenta, hemos contado 6 veces.

La forma de obtener la respuesta correcta, entonces, es obviamente corregir este exceso dividiendo por 6:\[\dfrac{45^{\underline{3}}}{3!} = \dfrac{45 \times 44 \times 43}{6} = \text{14,190 different threesomes}.\] Y en general, eso es todo lo que tenemos que hacer. Para encontrar el número de combinaciones de\(k\) cosas tomadas de un total de\(n\) cosas que tenemos:\[\dfrac{n^{\underline{k}}}{k!} = \dfrac{n!}{(n-k)!k!}\ \text{combinations}.\] Este patrón, también, surge tan a menudo que los matemáticos han inventado (aún) otra notación especial para ello. Se ve un poco extraño al principio, casi como una fracción sin barra horizontal:\[\binom{n}{k} = \dfrac{n!}{(n-k)!k!}.\] Esto se pronuncia “\(n\)-elegir-\(k\)”.

Nuevamente abundan los ejemplos. ¿Cuántas manos diferentes de póquer de 5 cartas hay? Respuesta:\(\binom{52}{5}\), ya que no importa en qué orden te reparten las cartas, solo cuáles cinco cartas obtienes. Si hay 1024 sectores en nuestro disco, pero solo 256 bloques de caché en memoria para retenerlos, ¿cuántas combinaciones diferentes de sectores pueden haber en la memoria a la vez? \(\binom{1024}{256}\). Si queremos elegir 4 o 5 de nuestros 10 principales clientes para participar en un grupo focal, ¿cuántas combinaciones diferentes de participantes podríamos tener? \(\binom{10}{4}+\binom{10}{5}\), ya que queremos la cantidad de formas de elegir 4 de ellas más la cantidad de formas de elegir 5 de ellas. Y para nuestro canal de películas nocturnas, por supuesto, hay\(\binom{500}{4}\) posibles alineaciones de películas para atraer al público, si no nos importa qué película se emite en qué momento.

Coeficientes binomiales

La notación “n-choose-k”\(\binom{n}{k}\) tiene otro nombre: los valores de este tipo se denominan coeficientes binomiales. Esto se debe a que una forma de generarlos, creerlo o no, es multiplicar repetidamente un binomio por sí mismo (o, equivalentemente, tomar un binomio a un poder).

Un binomio, recordar, es un polinomio con solo dos términos:\[x+y.\] Los coeficientes para este binomio son por supuesto 1 y 1, ya que “\(x\)" realmente significa “”\(1\cdot x\). Ahora bien, si multiplicamos esto por sí mismo, obtenemos:\[\begin{aligned} (x+y)\cdot(x+y) = x^2 + 2xy + y^2.\end{aligned}\] Los coeficientes de los términos son 1, 2 y 1. Lo hacemos de nuevo:\[\begin{aligned} (x^2+2xy+y^2)\cdot(x+y) = x^3 + 3x^2y + 3xy^2 + y^3.\end{aligned}\] para conseguir 1, 3, 3 y 1, y hacerlo de nuevo:\[\begin{aligned} (x^3+3x^2y+3xy^2+y^3)\cdot(x+y) = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4.\end{aligned}\] para conseguir 1, 4, 6, 4, y 1. En este punto podrías estar teniendo flashbacks del triángulo de Pascal, del que quizás aprendiste en la primaria, en el que cada entrada en fila es la suma de las dos entradas inmediatamente por encima de él (a la izquierda y a la derecha), como en la Figura\(\PageIndex{1}\). (Si nunca aprendiste eso, no te preocupes por ello.)

Figura\(\PageIndex{1}\): Las primeras seis filas del triángulo de Pascal.

Ahora tal vez te estés preguntando a dónde voy con esto. ¿Qué tienen que ver los trucos divertidos de álgebra con el conteo de combinaciones de elementos? La respuesta es que los valores de\(\binom{n}{k}\) son precisamente los coeficientes de estos polinomios multiplicados. \(n\)Sea 4, que corresponde al último polinomio que multiplicamos. Entonces podemos calcular todas las combinaciones de elementos tomados de un grupo de cuatro:\[\binom{4}{0}=1, \binom{4}{1}=4, \binom{4}{2}=6, \binom{4}{3}=4, \text{and}\ \binom{4}{4}=1.\] En otras palabras, hay exactamente una manera de sacar ningún artículo de 4 (simplemente no tomas ninguno). Hay cuatro formas de sacar un artículo de 4: podrías tomar el primero, o el segundo, o el tercero, o el cuarto. Hay seis formas de sacar dos elementos de cuatro; a saber:

1. la primera y segunda
2. la primera y tercera
3. la primera y cuarta
4. la segunda y tercera
5. la segunda y cuarta
6. la tercera y cuarta

Y así sucesivamente.

Ahora de alguna manera estamos en un poco de tangente, ya que el hecho de que los valores “n-choose-k” resultan ser los mismos que los coeficientes binomiales es en su mayoría solo una coincidencia interesante. Pero lo que realmente quiero que se den cuenta aquí —y lo que el triángulo de Pascal deja claro— es la simetría de los coeficientes. Esto sorprende a muchos estudiantes. ¿Y si te pregunto cuál de los siguientes números era mayor:\(\binom{1000}{18}\) o\(\binom{1000}{982}\)? La mayoría de los estudiantes adivinan que el segundo de estos números es mucho mayor. De hecho, sin embargo, ambos trabajan\(\frac{1000!}{18!982!}\) y, por lo tanto, son exactamente los mismos. Y en el ejemplo anterior, vemos que\(\binom{4}{0}\) es igual a\(\binom{4}{4}\), y eso\(\binom{4}{1}\) es igual a\(\binom{4}{3}\).

¿Por qué es esto? Bueno, puedes mirar hacia atrás en la fórmula para\(\binom{n}{k}\) y ver cómo funciona algebraicamente. Pero también es bueno tener una sensación intuitiva para ello. Así es como pienso de ello. Regresa a los chicos Davies y a la Wii. Dijimos que había tres formas diferentes de elegir a 2 niños para jugar primero en la Wii después de la escuela. En otras palabras,\(\binom{3}{2} = 3.\) Muy bien. Pero si lo piensas, entonces también debe haber tres formas diferentes de dejar fuera exactamente a un niño. Si cambiamos lo que estamos contando de “combinaciones de jugadores” a “combinaciones de no jugadores” —ambas deben ser iguales, ya que pase lo que pase, estaremos particionando a los niños Davies en jugadores y no jugadores— entonces vemos que también\(\binom{3}{1}\) deben ser 3.

Y esto es cierto en todos los ámbitos. Si hay\(\binom{500}{4}\) diferentes alineaciones de cuatro películas, entonces hay el mismo número de alineaciones de 496 películas, ya que\(\binom{500}{4} = \binom{500}{496}\). Conceptualmente, en el primer caso elegimos un grupo de cuatro y los mostramos, y en el segundo caso elegimos un grupo de cuatro y mostramos todo menos ellos.

También observe que la forma de obtener el mayor número de combinaciones de\(n\) artículos es\(k\) que sea la mitad de\(n\). Si tenemos 100 libros en nuestra biblioteca, hay muchas más formas de checar 50 de ellos entonces hay de check out solo 5, o de check out 95. Extraño pero cierto.

Por último, asegúrate de entender los extremos finales de este fenómeno. \(\binom{n}{0}\)y ambos\(\binom{n}{n}\) son siempre 1, no importa lo que\(n\) sea. Eso es porque si no estás recogiendo artículos, no tienes ninguna opción: solo hay una manera de salir vacío. Y si vas a recoger todos los artículos, tampoco tienes opciones: te ves obligado a elegir todo.