17. Combinaciones con repetición

17.1 Introducción

En una combinación sin repetición se seleccionan elementos diferentes. En una combinación con repetición, podemos seleccionar varias veces el mismo tipo, pero el orden de selección sigue sin importar.

Por ejemplo, elegir dos sabores de helado entre vainilla, chocolate y frutilla permite seleccionar vainilla dos veces. Vainilla-chocolate y chocolate-vainilla representan la misma elección.

17.2 Qué es una combinación con repetición

Una combinación con repetición de n tipos tomados de k en k es una selección de tamaño k en la que:

• El orden no importa.
• Un tipo puede aparecer más de una vez.
• La cantidad de cada tipo puede variar.

Las selecciones BA, CA y CB no se agregan porque representan las mismas elecciones que AB, AC y BC.

17.3 Fórmula

La cantidad de combinaciones con repetición de n tipos tomados de k en k es:

Usando factoriales:

La fórmula convierte una selección con repetición en una combinación sin repetición sobre un conjunto ampliado.

17.4 Ejemplo con sabores

Si hay 3 sabores y se eligen 4 porciones, permitiendo repetir sabores:

Una selección puede ser cuatro porciones de vainilla, o dos de vainilla, una de chocolate y una de frutilla.

17.5 Simulación: generar selecciones con repetición

Escribe entre 2 y 4 tipos y elige la cantidad de elementos seleccionados. La simulación muestra cada selección en orden no decreciente para evitar duplicados.

17.6 Método de estrellas y barras

Una forma de entender la fórmula es representar los elementos seleccionados como estrellas y separar los tipos mediante barras.

En total colocamos k estrellas y n - 1 barras. Hay n + k - 1 posiciones, y elegimos cuáles ocupan las k estrellas.

17.7 Un ejemplo en JavaScript

Para generar combinaciones con repetición, el índice de la siguiente elección puede comenzar en el mismo índice utilizado, permitiendo repetir el tipo actual.

function combinacionesConRepeticion(elementos, k, inicio = 0, actual = [], resultados = []) {
  if (actual.length === k) {
    resultados.push([...actual]);
    return resultados;
  }

  for (let indice = inicio; indice < elementos.length; indice += 1) {
    actual.push(elementos[indice]);
    combinacionesConRepeticion(elementos, k, indice, actual, resultados);
    actual.pop();
  }
  return resultados;
}

const resultado = combinacionesConRepeticion(["A", "B", "C"], 2);
console.log(resultado.map(combinacion => combinacion.join("")));

La diferencia con las combinaciones sin repetición está en usar indice y no indice + 1 para la llamada recursiva.

17.8 Calcular la cantidad

Si solo necesitamos el total, calculamos el coeficiente binomial correspondiente:

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

function contarCombinacionesConRepeticion(n, k) {
  return factorial(n + k - 1) / (factorial(k) * factorial(n - 1));
}

console.log(contarCombinacionesConRepeticion(3, 4));

El resultado es 15. Para cantidades grandes conviene simplificar o usar un cálculo de coeficientes binomiales más estable.

17.9 Comparación con otros métodos

17.10 Restricciones

La fórmula básica supone que cada tipo puede utilizarse cualquier cantidad de veces. Si hay límites, como “no más de dos unidades de A”, debemos separar casos o utilizar técnicas adicionales de conteo.

Las restricciones transforman el problema en una distribución de cantidades entre categorías.

17.11 Aplicaciones en informática

• Distribuir recursos de tipos repetibles.
• Seleccionar cantidades de categorías sin importar el orden.
• Contar configuraciones de productos o componentes.
• Analizar soluciones de problemas de asignación.
• Modelar frecuencias de símbolos en una secuencia.
• Generar subconjuntos múltiples sin duplicar por orden.

17.12 Errores frecuentes

• Usar C(n, k) cuando se permite repetir.
• Usar n^k aunque el orden no importe.
• Generar ABC y CBA como selecciones diferentes.
• Olvidar el término n + k - 1 de la fórmula.
• Ignorar límites máximos de cada tipo.

17.13 Qué debes recordar de este tema

• Las combinaciones con repetición no consideran el orden.
• Un tipo de elemento puede seleccionarse varias veces.
• La fórmula es CR(n, k) = C(n + k - 1, k).
• El método de estrellas y barras explica la fórmula.
• Las selecciones pueden generarse en orden no decreciente para evitar duplicados.
• Las restricciones de cantidad requieren un análisis adicional.

17.14 Conclusión

Las combinaciones con repetición permiten seleccionar cantidades de distintos tipos sin que el orden importe. Su fórmula transforma el problema en una combinación sin repetición de posiciones ocupadas por estrellas y barras separadoras.

En el próximo tema compararemos en profundidad permutaciones, variaciones y combinaciones.