Combinatoria - 12. Permutaciones con elementos repetidos

12.1 Introducción

En una permutación simple todos los elementos son diferentes. Si aparecen elementos repetidos, intercambiar dos copias iguales no produce un ordenamiento nuevo.

Por ejemplo, las secuencias AABC y AABC obtenidas al intercambiar las dos A son visualmente la misma. Si calculáramos 4!, contaríamos varias veces una configuración idéntica.

12.2 El problema del conteo duplicado

Supongamos que tenemos las letras A, A, B y C. Si tratamos las dos A como si fueran diferentes, podemos marcarlas temporalmente como A₁ y A₂.

Elementos marcados: A₁, A₂, B, C
Ordenamientos aparentes: 4! = 24

Pero cada ordenamiento visible aparece 2! veces: una con A₁ antes que A₂ y otra intercambiando sus etiquetas. Por eso debemos dividir por 2!.

12.3 Fórmula general

Si tenemos n elementos en total y hay grupos repetidos de tamaños n₁, n₂, ..., nᵣ, la cantidad de permutaciones diferentes es:

P = n! / (n₁! × n₂! × ... × nᵣ!)

El denominador elimina las repeticiones producidas por intercambiar elementos iguales.

12.4 Ejemplo con AABC

La palabra AABC tiene 4 letras, pero la A aparece 2 veces. Por lo tanto:

Total = 4! / 2!
Total = 24 / 2 = 12 permutaciones diferentes

El resultado es menor que 4! porque algunos intercambios no generan una palabra nueva.

12.5 Simulación: generar ordenamientos únicos

Escribe entre 3 y 7 símbolos. La simulación calcula la fórmula y genera las permutaciones distintas cuando la cantidad de resultados es manejable.

12.6 Ejemplo con dos grupos repetidos

Consideremos los elementos A, A, B, B y C. Hay 5 elementos en total, dos A y dos B.

P = 5! / (2! × 2!)
P = 120 / 4 = 30

El denominador contiene un factorial por cada grupo de elementos iguales.

12.7 Todos los elementos iguales

Si los n elementos son iguales, solo existe un ordenamiento visible. La fórmula lo confirma:

P = n! / n! = 1

Intercambiar elementos iguales no produce una configuración nueva.

12.8 Un ejemplo en JavaScript

Podemos contar la frecuencia de cada elemento y aplicar la fórmula dividiendo el factorial total por los factoriales de las frecuencias.

function factorial(n) {
  let resultado = 1;
  for (let valor = 2; valor <= n; valor += 1) resultado *= valor;
  return resultado;
}

const elementos = ["A", "A", "B", "C"];
const frecuencias = new Map();
for (const elemento of elementos) {
  frecuencias.set(elemento, (frecuencias.get(elemento) || 0) + 1);
}

const divisor = [...frecuencias.values()]
  .reduce((producto, cantidad) => producto * factorial(cantidad), 1);
const total = factorial(elementos.length) / divisor;

console.log(`Permutaciones diferentes: ${total}`);

12.9 Generar sin duplicados

Una estrategia para generar permutaciones únicas es elegir cada valor disponible solo una vez en cada posición. Si un valor aparece varias veces, se reduce su cantidad disponible y se restaura al volver atrás.

function permutarUnicas(elementos) {
  const cantidades = new Map();
  elementos.forEach(elemento => {
    cantidades.set(elemento, (cantidades.get(elemento) || 0) + 1);
  });
  const resultados = [];

  function construir(actual) {
    if (actual.length === elementos.length) {
      resultados.push(actual.join(""));
      return;
    }
    for (const [elemento, cantidad] of cantidades) {
      if (cantidad === 0) continue;
      cantidades.set(elemento, cantidad - 1);
      construir([...actual, elemento]);
      cantidades.set(elemento, cantidad);
    }
  }

  construir([]);
  return resultados;
}

console.log(permutarUnicas(["A", "A", "B"]));

La tabla de frecuencias evita crear copias artificialmente diferenciadas y produce cada ordenamiento visible una sola vez.

12.10 Comparación con permutaciones simples

Tipo	Condición	Fórmula	Ejemplo
Simples	Todos diferentes	n!	A, B, C → 3! = 6
Con repetición	Hay grupos iguales	n! / (n₁! × ...)	A, A, B, C → 4! / 2! = 12

12.11 Aplicaciones en informática

Contar cadenas que contienen símbolos repetidos.
Analizar configuraciones de datos con valores iguales.
Generar casos únicos sin duplicar resultados.
Estudiar arreglos de categorías repetidas.
Contar distribuciones y secuencias con frecuencias conocidas.
Optimizar búsquedas que podrían explorar estados equivalentes.

12.12 Errores frecuentes

Usar n! sin corregir las repeticiones.
Dividir por las cantidades repetidas en lugar de por sus factoriales.
Olvidar uno de los grupos de elementos iguales.
Generar permutaciones marcadas y considerarlas diferentes visualmente.
No comprobar si dos resultados producidos son realmente iguales.

12.13 Qué debes recordar de este tema

Los elementos iguales no generan ordenamientos visibles nuevos al intercambiarse.
La fórmula es n! dividido por los factoriales de las repeticiones.
El denominador corrige el conteo duplicado.
La frecuencia de cada elemento permite aplicar la fórmula.
Una generación correcta debe producir cada permutación única una sola vez.
Estas permutaciones aparecen en cadenas, categorías y configuraciones con valores repetidos.

12.14 Conclusión

Las permutaciones con elementos repetidos permiten contar ordenamientos visibles sin incluir duplicados. La fórmula conserva el factorial total y divide por los factoriales de cada grupo repetido.

En el próximo tema estudiaremos las permutaciones circulares, donde los ordenamientos se organizan alrededor de un círculo.

Volver al índice

12. Permutaciones con elementos repetidos