3.2: Combinaciones

A veces el orden en que se eligen los individuos no importa; lo único que importa es si fueron elegidos o no. Un ejemplo de esto es elegir un conjunto de problemas para un examen. Si bien el orden en que se arreglan las preguntas puede hacer que el examen sea más o menos intimidante, lo que realmente importa es qué preguntas están en el examen, y cuáles no. Otro ejemplo sería elegir camisas para empacar para un viaje (asumiendo que todas tus camisas son distinguibles entre sí). Llamamos a una elección como esta una “combinación”, para indicar que es la colección de cosas elegidas lo que importa, y no el orden.

Definición:\(r\)-Combination

Sea n un número natural positivo, y\(0 ≤ r ≤ n\). Supongamos que tenemos\(n\) distintos objetos. Una\(r\) combinación -de los\(n\) objetos es un subconjunto que\(r\) consiste en los objetos.

Entonces, una combinación implica elegir elementos de una población finita en la que cada ítem se identifica de manera única, pero el orden en que se toman las elecciones no es importante.

Nuevamente, no debería sorprenderse al aprender (ya que estamos estudiando la enumeración) que lo que vamos a estar preguntando es cuántas combinaciones hay, en una variedad de circunstancias. Una diferencia significativa con respecto a las permutaciones es que no es interesante preguntarse cuántas n combinaciones hay de\(n\) objetos; solo hay una, ya que debemos elegir todos los objetos.

Comencemos con un ejemplo en el que calcularemos el número de\(3\) -combinaciones de diez objetos (o en este caso, personas).

Ejemplo\(\PageIndex{1}\)

De los diez deportistas que compiten por las medallas olímpicas en patinaje de velocidad femenino (1000 metros), tres deben ser elegidos para formar un comité que revise las reglas para futuras competencias. ¿Cuántos comités diferentes podrían formarse?

Solución

Determinamos en el Ejemplo 3.1.1 que hay\(\dfrac{10!}{7!}\) formas en las que se pueden asignar las medallas. Una manera fácil de elegir el comité sería hacerlo constar de los tres ganadores de la medalla. No obstante, fíjense que si (por ejemplo) Wong gana el oro, Sajna gana la plata y Andersen gana el bronce, terminaremos con el mismo comité que si Sajna gana el oro, Andersen gana la plata y Wong gana el bronce. De hecho, lo que hemos aprendido sobre las permutaciones nos dice que hay\(3!\) diferentes resultados de medallas que cada uno daría como resultado que el comité se formara por Wong, Sajna y Andersen.

De hecho, no hay nada especial en Wong, Sajna y Andersen —para que cualquier elección de tres personas esté en el comité, hay\(3! = 6\) formas en que esos individuos podrían haber sido galardonados con las medallas. Por lo tanto, cuando contamos el número de formas en que se podrían asignar las medallas, contamos cada posible comité de 3 miembros exactamente\(3! = 6\) veces. Entonces el número de comisiones diferentes es\(\dfrac{10!}{(7!3!)} = 10 · 9 · \dfrac{8}{6} = 120\).

Podemos usar el mismo razonamiento para determinar una fórmula general para el número de\(r\) -combinaciones de\(n\) objetos:

Teorema\(\PageIndex{1}\)

El número de\(r\) -combinaciones de\(n\) objetos es

\[\dfrac{n!}{r!(n − r)!}\]

Prueba

Por Teorema 3.1.1, hay\(\dfrac{n!}{(n − r)!}\)\(r\) -permutaciones de n objetos. Supongamos que sabíamos que hay\(r\) -subconjuntos\(k\) desordenados de\(n\) objetos (es decir,\(r\) -combinaciones). Para cada uno de estos subconjuntos\(k\) desordenados, hay\(r!\) formas en las que podríamos ordenar los elementos. Esto nos dice eso\(k · r! = \dfrac{n!}{(n − r)!}\). Reordenando la ecuación, obtenemos\(k = \dfrac{n!}{(r!(n − r)!)}\).

También resultará extremadamente útil tener una forma corta para el número de\(r-\) combinaciones de\(n\) objetos.

Nota

Usamos\(\binom{n}{r}\) para denotar el número de\(r\) -combinaciones de\(n\) objetos, por lo que

\[\binom{n}{r} = \dfrac{n!}{r!(n-r)!}\]

Definición

Leemos\(\binom{n}{r}\) como “\(n\)elegir”\(r\), así que\(n\) elegir\(r\) es\(\dfrac{n!}{[r!(n − r)!]}\)

Observe que cuando\(r = n\), tenemos

\[\binom{n}{r} = \dfrac{n!}{n!(n-n)!} = \dfrac{n!}{n!0!} = \dfrac{n!}{n!} = 1 \]

coincidiendo con nuestra observación anterior de que sólo hay una manera en la que se pueden elegir todos\(n\) los objetos. Del mismo modo,

\[\binom{n}{0} = \dfrac{n!}{0!(n-0)!} = 1 \]

hay exactamente una manera de elegir ninguno de los\(n\) objetos.

Repasemos otro ejemplo que implica la combinación

Ejemplo\(\PageIndex{2}\)

Jasmine sostiene tres cartas de una baraja normal de naipes. Ella te dice que todos son corazones, y que sostiene al menos una de las dos cartas más altas del palo (As y Rey). Si quisieras enumerar todos los posibles juegos de cartas que podría estar sosteniendo, ¿cuánto tiempo tardaría tu lista?

Solución

Consideraremos tres casos: que Jasmine esté sosteniendo al As (pero no al Rey); que esté sosteniendo al Rey (pero no al As), o que esté sosteniendo tanto al As como al Rey

Si Jasmine sostiene al As pero no al Rey, de las otras once cartas en el palo de corazones debe estar sosteniendo dos. Hay opciones\(\binom{11}{2}\) posibles para las tarjetas que sostiene en este caso.

De igual manera, si Jazmín sostiene al Rey pero no al As, de las otras once cartas en el palo de corazones debe estar sosteniendo dos. Nuevamente, hay\(\binom{11}{2}\) posibles opciones para las tarjetas que sostiene en este caso.

Por último, si Jasmine sostiene al As y al Rey, entonces sostiene una de las otras once cartas en el palo de corazones. Hay opciones\(\binom{11}{1}\) posibles para las tarjetas que sostiene en este caso.

En total, tendrías que enumerar

\(\binom{11}{2} + \binom{11}{2} +\binom{11}{1} = \dfrac{11!}{2!9!} + \dfrac{11!}{2!9!} + \dfrac{11!}{1!10!} = \dfrac{11 \cdot 10}{2} + \dfrac{11 \cdot 10}{2} + 11 = 55 + 55 + 11 = 121 \)posibles juegos de cartas.

Aquí hay otro análisis que también funciona: Jasmine tiene al menos uno del As y el Rey, así que vamos a dividir el problema en dos casos: ella podría estar sosteniendo el As, o podría estar sosteniendo al Rey pero no al As. Si está sosteniendo el As, entonces de los otros doce corazones, sostiene dos; estos se pueden elegir de\(\binom{12}{2} = 66\) maneras. Si está sosteniendo al Rey pero no al As, entonces como antes, sus otras dos cartas pueden ser elegidas de\(\binom{11}{2} = 55\) maneras, para un total (nuevamente) de\(121\).

Un error común en un ejemplo como este es dividir el problema en los casos en los que Jasmine está sosteniendo el As, o que está sosteniendo al Rey, y determinar que cada uno de estos casos incluye\(\binom{12}{2} = 66\) posibles combinaciones de cartas, para un total de\(132\). El problema con este análisis es que hemos contado las combinaciones que incluyen tanto al As como al Rey dos veces: una como combinación que incluye al As, y otra como combinación que incluye al Rey. Si haces esto, necesitas compensar restando al final el número de combinaciones que se han contado dos veces: es decir, las que incluyen al As y al Rey. Como nos resolvimos en el ejemplo, hay\(\binom{11}{1} = 11\) de estos, haciendo un total de\(132−11 = 121\) combinaciones.

Ejercicio\(\PageIndex{1}\)

Usa lo que has aprendido sobre las combinaciones para resolver los siguientes problemas. También se pueden requerir permutaciones y otras reglas de conteo que hemos cubierto.

1. Para un truco de magia, le pides a un amigo que saque tres cartas de una baraja de\(52\) cartas estándar. ¿Cuántos juegos de cartas posibles podría haber elegido?
2. Por el mismo truco, insistes en que tu amiga siga reemplazando su primer sorteo hasta que saque una carta que no sea una pala. Ella puede elegir cualquier tarjeta para sus otras dos tarjetas. ¿Con cuántos juegos de cartas posibles podría terminar? (Precaución: elegir\(5\) ♣,\(6\) ♦,\(3\) ♠ en ese orden, no es diferente de elegir\(6\) ♦,\(5\) ♣,\(3\) ♠ en ese orden. No es necesario tomar en cuenta que algunos conjuntos tendrán más probabilidades de ocurrir que otros).
3. \(5\)¿Cuántos números de dígitos contienen exactamente dos ceros? (Insistimos en que el número contenga exactamente\(5\) dígitos.)
4. Sandeep, Hee, Sara y Mohammad juegan euchre con una baraja estándar que consiste en\(24\) cartas (\(\text{A}\),\(\text{K}\),\(\text{Q}\),\(\text{J}\)\(10\), y\(9\) de cada uno de los cuatro trajes de una baraja regular de naipes). ¿De cuántas formas se puede repartir la baraja para que cada jugador reciba\(5\) cartas, quedando\(4\) cartas en el centro, una de las cuales está volteada boca arriba? El orden de las\(3\) cartas que quedan boca abajo en el medio no importa, pero quien recibe un determinado conjunto de\(5\) cartas (por ejemplo, Sara o Sandeep) sí importa.
5. Una heladería tiene\(10\) sabores de helado y\(7\) coberturas. Su mega-sundae consiste en su elección de cualquier\(3\) sabor de helado y cualquier\(4\) aderezo. (Un cliente debe elegir exactamente tres sabores diferentes de helado y cuatro coberturas diferentes). ¿Cuántos mega-sundaes diferentes hay?