Permutaciones y combinaciones explicadas

El principio fundamental del conteo

Los problemas de conteo preguntan de cuántas formas puede ocurrir algo. La base es el principio fundamental del conteo, o principio multiplicativo: si una elección puede hacerse de $m$ formas y una segunda elección, independiente, de $n$ formas, las dos juntas pueden hacerse de $m \times n$ formas. La idea se extiende a cualquier número de etapas.

Si tienes 3 camisas, 4 pantalones y 2 pares de zapatos, puedes formar $3 \times 4 \times 2 = 24$ conjuntos distintos. Un PIN de cuatro cifras con los dígitos del 0 al 9, permitiendo repeticiones, tiene $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ posibilidades. Todas las fórmulas de este artículo son atajos de esta multiplicación, así que cuando un problema te resulte extraño, volver a contar etapa por etapa es siempre un recurso seguro.

Los factoriales

Al colocar en fila $n$ objetos distintos hay $n$ opciones para la primera posición, $n - 1$ para la segunda, y así sucesivamente hasta 1. Este producto se llama factorial de $n$:

Así, $5! = 120$: cinco libros pueden colocarse en una estantería en 120 órdenes distintos. Por definición, $0! = 1$, lo que mantiene coherentes las fórmulas siguientes, ya que hay exactamente una forma de ordenar la nada. Los factoriales crecen a una velocidad asombrosa: $10! = 3{,}628{,}800$, y una baraja de cartas mezclada tiene $52!$ órdenes posibles, un número de 68 cifras.

Permutaciones: el orden importa

Una permutación, o variación en la terminología de muchos libros de texto españoles, es una ordenación de $r$ objetos elegidos entre $n$ objetos distintos. Como el orden importa, primero-segundo-tercero es distinto de tercero-segundo-primero. El número de permutaciones es

Sentar a personas alrededor de una mesa circular es un caso especial. Mover a todos un asiento da la misma disposición, así que $n$ personas pueden sentarse de $(n-1)!$ formas distintas. Seis personas alrededor de una mesa redonda tienen $5! = 120$ disposiciones, no 720.

Combinaciones: el orden no importa

Una combinación es una selección en la que solo cuenta quién forma parte de ella. Elegir a Ana, Ben y Cara para un comité da el mismo comité en cualquier orden. Cada grupo de $r$ objetos corresponde a $r!$ permutaciones, así que se divide entre ese número:

Las combinaciones son simétricas: $\binom{n}{r} = \binom{n}{n-r}$, porque elegir a 3 personas que entran es lo mismo que elegir a las 5 que se quedan fuera. También son los números del triángulo de Pascal (o de Tartaglia) y los coeficientes del desarrollo del binomio $(a + b)^n$.

Cómo saber cuál usar

Hazte una sola pregunta: si intercambio dos de los elementos elegidos, ¿obtengo un resultado distinto? Si la respuesta es sí, el orden importa y necesitas permutaciones. Si es no, usa combinaciones.

• Puestos, clasificaciones, contraseñas, distribuciones de asientos y horarios: permutaciones.
• Equipos, comités, manos de cartas, boletos de lotería e ingredientes de una pizza: combinaciones.
• Los cargos dentro de un grupo, como presidente y tesorero, hacen que el orden importe aunque las personas salgan de un mismo grupo.

Una comprobación rápida: el número de permutaciones es siempre $r!$ veces el número de combinaciones. Si tus dos resultados no cumplen esa relación, uno de ellos está mal.

Conteo con repetición y letras repetidas

Cuando los elementos pueden repetirse, las fórmulas cambian. Las selecciones ordenadas con repetición son $n^r$, como en el ejemplo del PIN. Las selecciones no ordenadas con repetición, como elegir 3 bolas de helado entre 5 sabores pudiendo repetir sabor, son

Ordenar letras con repeticiones exige un ajuste más: dividir entre el factorial de cada número de repeticiones, porque intercambiar letras idénticas no cambia nada. La palabra MISSISSIPPI tiene 11 letras, con 4 letras I, 4 letras S y 2 letras P, así que tiene $\frac{11!}{4!\,4!\,2!} = 34{,}650$ ordenaciones distintas.

El conteo para calcular probabilidades

Cuando los resultados son igual de probables, una probabilidad es el número de casos favorables dividido entre el número de casos posibles, así que las permutaciones y las combinaciones hacen la mayor parte del trabajo. Los fundamentos de ese cociente se explican en probabilidad básica.

Los juegos de cartas ofrecen más práctica. Hay $\binom{52}{5} = 2{,}598{,}960$ manos posibles de cinco cartas. Una mano con los cuatro ases solo necesita una carta más, elegida entre las otras 48, así que la probabilidad es $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$.

Errores frecuentes

• Usar permutaciones para un equipo o un comité, lo que cuenta de más en un factor $r!$.
• Olvidar que $0! = 1$, lo que estropea fórmulas como $\binom{n}{n}$.
• No tener en cuenta los elementos idénticos, como en las ordenaciones de letras con repeticiones.
• Multiplicar etapas que no son independientes sin ajustar los recuentos posteriores.

La calculadora de permutaciones y combinaciones evalúa ${}_nP_r$ y ${}_nC_r$ mostrando los pasos con factoriales, y la calculadora de probabilidad convierte esos recuentos en probabilidades.

El triángulo de Pascal y los subconjuntos

Cada número del triángulo de Pascal es la suma de los dos que tiene encima, y la fila $n$ contiene los valores $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$. La fila 4 es 1, 4, 6, 4, 1, que son exactamente los coeficientes de $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$. La regla que construye el triángulo es en sí misma un resultado de conteo:

Para ver por qué, fija un elemento concreto. Toda selección de $r$ elementos o bien lo incluye, y quedan $r - 1$ por elegir entre los otros $n - 1$, o bien lo excluye, y quedan los $r$ por elegir entre los otros $n - 1$. Al sumar una fila entera se obtiene $2^n$, el número total de subconjuntos de un conjunto de $n$ elementos, ya que cada elemento está dentro o fuera. Por tanto, una pizzería con 8 ingredientes puede preparar $2^8 = 256$ pizzas distintas, contando la que no lleva ninguno.

Ejercicios

1. ¿De cuántas formas pueden colocarse en una estantería 4 de 7 libros distintos? Solución: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. ¿De cuántas formas puedes elegir 4 ingredientes entre 10? Solución: $\binom{10}{4} = 210$.
3. ¿Cuántas ordenaciones distintas tiene la palabra BANANA? Solución: $\frac{6!}{3!\,2!} = 60$.
4. ¿Cuántos códigos de cinco letras pueden formarse con 26 letras si se permiten repeticiones? Solución: $26^5 = 11{,}881{,}376$.

Preguntas frecuentes