Permutaciones

La idea

¿De cuántas maneras pueden ubicarse 4 personas en una fila? Para el primer lugar hay 4 candidatos; elegido ese, quedan 3 para el segundo, 2 para el tercero y 1 para el último. Por el principio multiplicativo, $4\cdot 3\cdot 2\cdot 1=24$. En general, $n$ objetos se ordenan de

maneras. Si solo se llenan $k$ lugares, el producto se corta a los $k$ factores: $P(n,k)=n(n-1)\cdots (n-k+1)=\frac{n!}{(n-k)!}$.

Un crecimiento explosivo

El factorial crece más rápido que cualquier potencia: $10!=3628800$, $20!\approx 2,4\times 10^{18}$. Un mazo de 52 cartas puede ordenarse de $52!\approx 8\times 10^{67}$ maneras, un número tan grande que casi con certeza cada mezcla bien hecha produce un orden que jamás existió en la historia. Para estimar factoriales enormes se usa la aproximación de Stirling, $n!\approx \sqrt{2\pi n}{\left(\frac{n}{e}\right)}^n$.

¿Por qué $0!=1$? Porque hay exactamente una manera de ordenar nada, y porque así funcionan todas las fórmulas, como $\frac{n!}{(n-n)!}=n!$.

Con repetición

Si hay objetos repetidos, se divide por los órdenes indistinguibles. Las letras de PARAGUAY (8 letras, con la A repetida 3 veces) se reordenan de $\frac{8!}{3!}=6720$ formas distintas.

Dónde se usa hoy

• Contraseñas y seguridad: cuántas claves posibles hay determina cuánto tarda un ataque de fuerza bruta.
• Logística: el problema del viajante, encontrar la ruta más corta entre $n$ ciudades, tiene $\frac{(n-1)!}{2}$ recorridos posibles, por eso es tan difícil para las computadoras.
• El cubo de Rubik: sus más de $4,3\times 10^{19}$ posiciones se cuentan con permutaciones.
• Química y física: contar configuraciones de moléculas es la base de la entropía de Boltzmann.