Combinaciones

La idea

¿De cuántas maneras se puede elegir un equipo de 3 personas entre 5? Si el orden importara (presidente, secretario, tesorero), habría $5\cdot 4\cdot 3=60$ formas: son las permutaciones. Pero en un equipo sin cargos, el grupo {Ana, Beto, Caro} es el mismo en cualquier orden, y cada grupo de 3 se contó $3!=6$ veces. Por lo tanto hay $\frac{60}{6}=10$ equipos distintos.

Por qué funciona

En general, elegir $k$ objetos de $n$ en orden se puede hacer de $\frac{n!}{(n-k)!}$ maneras. Cada grupo sin orden aparece $k!$ veces en esa cuenta, así que:

Se lee "$n$ en $k$". Algunas propiedades:

• Simetría: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right)$. Elegir 3 que van es lo mismo que elegir 2 que se quedan.
• Regla de Pascal: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. Un elemento dado, o está en el grupo, o no. Esta regla construye el triángulo de Pascal, fila por fila.
• Suma total: ${\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$, el número de subconjuntos de un conjunto de $n$ elementos.

El triángulo de Pascal

Sus filas (1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1...) son los coeficientes del binomio de Newton: $(a+b{)}^n=\sum (\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k$. Por eso también se llaman coeficientes binomiales.

Dónde se usa hoy

• Loterías: en un juego de elegir 6 números entre 45, hay $\left(\genfrac{}{}{0ex}{}{45}{6}\right)=8145060$ combinaciones posibles; acertar con un único billete tiene probabilidad de 1 en más de 8 millones.
• Probabilidad: la distribución binomial y casi todo el cálculo de probabilidades "contando casos".
• Genética: contar combinaciones de alelos o de mutaciones posibles.
• Informática: análisis de algoritmos, códigos correctores de errores y criptografía.