Permutaciones con repetición

El anagrama que detuvo al campeón

En la final regional de la ONEM, un problema pedía contar los anagramas —reordenamientos de letras— de una palabra. El campeón escribió $10!$ y perdió dos puntos. ¿Qué falló? La palabra tenía letras repetidas, y él no lo notó a tiempo.

Ese error, tan común como costoso, motiva esta lección entera. Antes de contar permutaciones hay que hacerse una sola pregunta: ¿todos los objetos son distinguibles entre sí, o algunos son idénticos?

Permutaciones sin repetición: el factorial

Si tenemos $n$ objetos todos distintos, el número de formas de ordenarlos en fila es $n!$ (factorial de $n$). La razón: en la primera posición hay $n$ opciones, en la segunda quedan $n-1$, en la tercera $n-2$, y así sucesivamente. Por el principio multiplicativo:

$$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$$

Ejemplo: las letras de la palabra OLIMPO (7 letras, todas distintas) pueden ordenarse de $7! = 5040$ maneras distintas.

Convención importante: $0! = 1$. Esto no es capricho; es la única manera de que las fórmulas que veremos a continuación sean consistentes cuando algún grupo tiene cero elementos.

Permutaciones de multiconjuntos: dividir por las repeticiones

Ahora los objetos ya no son todos distintos. Supón que tienes $n$ objetos donde el objeto de tipo 1 se repite $n_1$ veces, el de tipo 2 se repite $n_2$ veces, ..., y el de tipo $k$ se repite $n_k$ veces, con $n_1 + n_2 + \cdots + n_k = n$.

Si etiquetáramos artificialmente los objetos idénticos (tipo 1 se convierte en tipo $1_a$, $1_b$, ...) obtendríamos $n!$ arreglos. Pero al quitar las etiquetas, cada arreglo real aparece $n_1! \cdot n_2! \cdots n_k!$ veces (porque permutar copias idénticas entre sí no da un arreglo nuevo). Dividiendo:

$$\frac{n!}{n_1! \cdot n_2! \cdots n_k!}$$

Esta fórmula aparece en la ONEM disfrazada de muchas maneras: anagramas de palabras, distribuciones de objetos iguales, recorridos en cuadrículas (que veremos en el capítulo 6).

Problema resuelto: los anagramas de MATEMATICA

¿Cuántos anagramas distintos tiene la palabra MATEMATICA?

Paso 1 — contar las letras y sus frecuencias. M-A-T-E-M-A-T-I-C-A tiene 10 letras: A aparece 3 veces, M aparece 2 veces, T aparece 2 veces, E una vez, I una vez, C una vez.

Paso 2 — aplicar la fórmula. $n=10$, $n_A=3$, $n_M=2$, $n_T=2$, $n_E=n_I=n_C=1$.

$$\frac{10!}{3! \cdot 2! \cdot 2! \cdot 1! \cdot 1! \cdot 1!} = \frac{3\,628\,800}{6 \cdot 2 \cdot 2 \cdot 1 \cdot 1 \cdot 1} = \frac{3\,628\,800}{24} = 151\,200$$

Así que hay $151\,200$ anagramas distintos de MATEMATICA. El campeón que escribió $10! = 3\,628\,800$ sobrecontó por un factor de 24.

Permutaciones circulares: el collar y la mesa

Cuando los objetos se colocan en un círculo, no hay una "primera posición" fija. Dos arreglos que son rotaciones uno del otro se consideran el mismo. Para $n$ personas sentadas en una mesa circular, fijamos una persona (eliminando rotaciones equivalentes) y permutamos las restantes $n-1$:

$$(n-1)!$$

Ejemplo: 6 amigos en una mesa circular pueden sentarse de $(6-1)! = 5! = 120$ maneras distintas.

Cuidado con los collares: si además las reflexiones (voltear el collar) se consideran iguales (como en un collar real que puede girarse), el número se divide entre 2, dando $\frac{(n-1)!}{2}$. Siempre lee el problema con cuidado: ¿el collar tiene frente y revés distinguibles o no?

Conexión olímpica: en la ONEM suele aparecer como "¿de cuántas formas pueden sentarse $n$ personas en una mesa redonda?" La respuesta inmediata es $(n-1)!$, sin necesidad de listar casos.

Resumen y señales de alerta

Tres preguntas para elegir la fórmula correcta: (1) ¿todos los objetos son distintos? → usa $n!$. (2) ¿hay repetidos? → usa $n!/n_1!\cdots n_k!$. (3) ¿los objetos están en círculo? → usa $(n-1)!$ (y divide por 2 si reflexiones son equivalentes).

Señal de alerta en competencia: cuando el problema menciona palabras con letras repetidas, banderas con colores repetidos, o distribución de objetos idénticos, la fórmula del multiconjunto es casi siempre la herramienta correcta.