Combinaciones

Usamos las combinaciones cuando elegimos un cierto número de objetos de un conjunto y no importa el orden en que los elegimos. Un problema típico es La Primitiva: en el bombo tenemos 49 números y sacamos 6 de ellos, y da igual en qué orden los saquemos.

Deducción de la fórmula

Rueda de la fortuna

Sea un conjunto M, por ejemplo M = {a, b, c, d, e}. Entonces una combinación de k elementos es un subconjunto K ⊆ M que contiene exactamente k elementos. Como K es un conjunto, naturalmente no importa el orden. Una combinación de tres elementos del conjunto M podría ser, pues, {a, b, d} o {b, c, d}.

La diferencia con las variaciones es que en las variaciones importaba el orden, de modo que (a, b, e) y (e, b, a) son variaciones distintas, pero son la misma combinación, porque tanto (a, b, e) como (e, b, a) contienen los mismos elementos; que estén en otro orden no nos interesa en las combinaciones.

Pero podemos aprovechar las variaciones para obtener la fórmula del número de todas las combinaciones distintas. Sabemos que el número de variaciones de k elementos de un conjunto de n elementos es exactamente

$V_{n, k} = \frac{n!}{(n - k)!} .$

Si calculáramos, pues, el número de todas las variaciones de tres elementos del conjunto anterior M = {a, b, c, d, e}, obtendríamos V_5,3 = 60 variaciones distintas. Sin embargo, para cada terna tendríamos también todas sus permutaciones. Es decir, tendríamos la terna abc, pero también las ternas acb, bac, bca, cab y cba. Son seis variaciones distintas, pero es una sola combinación, porque todas tienen los mismos elementos.

Si tenemos, pues, una terna, ¿cuántas permutaciones distintas de esa terna existen? Exactamente 3!. Dicho de otro modo, existen exactamente 3! veces más variaciones de tres elementos que combinaciones de tres elementos. En lugar de contar una combinación, contamos 3! variaciones más, una con cada permutación de la terna dada. Así que si dividimos el número de variaciones entre 3!, obtenemos el número de combinaciones.

El procedimiento anterior se puede generalizar y podemos decir que, si buscamos el número de todas las combinaciones distintas de k elementos de un conjunto de tamaño n, este número, que denotamos C_n,k, es igual a

$C_{n, k} = \frac{V_{n, k}}{k!},$

es decir, el número de variaciones dividido entre k!, que es el número de permutaciones de cada k-upla. La fórmula se puede modificar desarrollando la fórmula de las variaciones:

$C_{n, k} = \frac{V_{n, k}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Ejemplo: el número de combinaciones de dos elementos del conjunto {a, b, c} es

$C_{3, 2} = \frac{3!}{1! \cdot 2!} = 3$

y son estas combinaciones: {a, b}, {a, c} y {b, c}. Para las combinaciones de tres elementos del conjunto original M = {a, b, c, d, e} obtendríamos el número

$C_{5, 3} = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

y son estas combinaciones: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Número combinatorio

La notación anterior de la fórmula con C_n,k se usa poco y en su lugar se usa el llamado número combinatorio. El número combinatorio tiene esta forma

$(\binom{n}{k})$

es una especie de fracción sin raya de fracción (que de todos modos escribirás por costumbre), pero con paréntesis (que no son opcionales, tienen que estar). El número combinatorio se lee «n sobre k». El valor del número combinatorio es igual que C_n,k.

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Así que si tenemos un conjunto de 5 elementos y elegimos de él grupos de cuatro, su número total será

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Relaciones básicas

Para el número combinatorio y n ∈ ℕ se cumple:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Además, para n, k ∈ ℕ ∪ {0} y k ≤ n se cumple

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

Y para n, k ∈ ℕ ∪ {0} y k < n se cumple

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Calculadora

La siguiente calculadora calcula el número combinatorio n sobre k.

Ejercicios resueltos

Empecemos con La Primitiva, que ya hemos mencionado. En ella se sacan 6 bolas de un bombo en el que hay 49 bolas. ¿Cuántas combinaciones distintas pueden salir?

Lo primero: ¿importa el orden en que se sacan los números? No importa, apostamos solo por los números, no por su orden. Usaremos combinaciones. Tenemos en total 49 bolas, sacamos 6 bolas, así que obtenemos el número combinatorio

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13.983 .816$

Existen en total 13.983.816 combinaciones que pueden salir. Lo que nos da, por cierto, la probabilidad de ganar con una sola apuesta, 1/13.983.816, que es 0,00000715112 %.
Sergio, un conocido ligón, está en una verbena de pueblo, donde hay en total 13 chicas guapas que le interesarían. Sergio sabe que es capaz de hacer feliz en una noche a 4 chicas distintas. ¿Entre cuántos grupos distintos de cuatro puede elegir Sergio?

Es de nuevo un ejemplo sencillo de combinaciones: el orden no importa, Sergio será igual de bueno con la primera chica que con la última. Obtenemos así un conjunto de 13 chicas, de las que elegimos siempre 4. Eso lleva al número combinatorio

$(\binom{13}{4}) = 715.$
Tienes un grupo de cincuenta personas, la mitad hombres y la otra mitad mujeres. ¿Cuántas ternas distintas de personas existen si no pueden estar formadas por personas de un solo sexo (es decir, en la terna no pueden aparecer tres hombres ni tres mujeres)?

Esta es una combinación algo más complicada. Si excluimos las ternas de personas de un solo sexo, nos quedan solo dos posibilidades para la composición de la terna: dos hombres y una mujer, o un hombre y dos mujeres, y el número de combinaciones del primer grupo (dos hombres y una mujer) será igual al número de combinaciones del segundo grupo. Nos basta, pues, calcular el número de combinaciones del primer grupo y multiplicarlo después por dos. Ahora vuelve a ser pan comido. Determinamos el número de combinaciones de pares distintos de hombres, que es veinticinco sobre dos, y lo multiplicamos por el número de combinaciones de una mujer (que es veinticinco, mira las relaciones básicas de arriba, en concreto la segunda línea). Este resultado solo falta multiplicarlo por dos y tenemos el resultado final.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
En una caja hay 15 productos, de los cuales 4 son defectuosos. ¿De cuántas formas se pueden elegir 6 productos de modo que
- ninguno sea defectuoso? En este caso elegimos 6 productos entre los 15 − 4 = 11 productos que no son defectuosos. Obtenemos así el número combinatorio
  
  $(\binom{11}{6}) = 462.$
- haya exactamente un producto defectuoso? Elegimos así un conjunto que contiene 5 productos en buen estado y 1 defectuoso. Productos en buen estado tenemos en total 11, defectuosos tenemos 4. Aplicamos el principio de multiplicación y obtenemos el resultado:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- haya como máximo un producto defectuoso? Para resolverlo usamos los resultados anteriores. Sabemos que tenemos 462 posibilidades de elegir exactamente 6 productos en buen estado y tenemos 1848 posibilidades de elegir cinco en buen estado y uno defectuoso. Aplicamos, pues, el principio de adición, sumamos estos resultados y tenemos el resultado que queremos, es decir, como máximo un producto defectuoso (= o ningún producto defectuoso, o exactamente uno). El resultado es: 462 + 1848 = 2310.

Capítulos: Combinatoria, Variaciones, Permutaciones, Combinaciones, Variaciones con repetición, Combinaciones con repetición, ¿Cuántos PIN distintos existen?

« Anterior: Permutaciones

Siguiente: Variaciones con repetición »