16. Combinaciones sin repetición

16.1 Introducción

En una variación, cambiar el orden produce un resultado diferente. En una combinación, solo importa qué elementos fueron seleccionados, no el orden en que se eligieron.

Por ejemplo, elegir a Ana y Luis para un equipo es la misma selección que elegir a Luis y Ana. Esta diferencia es el punto central de las combinaciones.

16.2 Qué es una combinación sin repetición

Una combinación sin repetición de n elementos tomados de k en k es un subconjunto de tamaño k formado con elementos distintos.

El conjunto {A, B} es igual al conjunto {B, A}; por eso solo se conserva una de las dos formas.

16.3 Condiciones principales

• Hay n elementos disponibles.
• Se seleccionan k elementos.
• El orden no importa.
• No se repiten elementos.
• Se cumple 0 ≤ k ≤ n.

Si el orden importara, el problema sería una variación. Si se permitiera repetir, estudiaríamos combinaciones con repetición.

16.4 Fórmula

La cantidad de combinaciones sin repetición de n elementos tomados de k en k se expresa como:

También se escribe como el coeficiente binomial:

El factorial k! corrige las distintas formas de ordenar los mismos k elementos seleccionados.

16.5 Ejemplo de selección de equipos

De un grupo de 6 personas queremos formar un equipo de 3. El orden dentro del equipo no importa.

El equipo Ana-Luis-Marta es el mismo equipo que Marta-Ana-Luis.

16.6 Simulación: generar combinaciones

Escribe entre 3 y 7 elementos y elige el tamaño de la selección. La simulación genera cada subconjunto una sola vez, sin considerar el orden.

16.7 Relación con las variaciones

Si primero ordenamos k elementos elegidos, cada combinación produce k! variaciones. Por eso:

La división por k! elimina los ordenamientos que representan la misma selección.

16.8 Un ejemplo en JavaScript

La función siguiente genera combinaciones utilizando un índice inicial. Así evita producir selecciones repetidas en distinto orden.

function combinaciones(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]);
    combinaciones(elementos, k, indice + 1, actual, resultados);
    actual.pop();
  }
  return resultados;
}

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

El siguiente índice siempre es mayor que el anterior. Por eso una combinación no puede volver a incluir un elemento anterior.

16.9 Calcular la cantidad sin enumerar

Cuando solo necesitamos el total, podemos utilizar factoriales:

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

function contarCombinaciones(n, k) {
  return factorial(n) / (factorial(k) * factorial(n - k));
}

console.log(contarCombinaciones(6, 3));

El resultado es 20. Para valores grandes conviene simplificar factores o utilizar métodos que eviten calcular factoriales completos.

16.10 Propiedades iniciales

La propiedad de simetría indica que elegir k elementos equivale a excluir n - k elementos.

16.11 Combinaciones y restricciones

Una condición puede exigir incluir o excluir determinados elementos. Por ejemplo, si A debe formar parte de un equipo de 3 elegido entre 6 personas, elegimos los otros 2 entre las 5 restantes:

Las restricciones se resuelven reduciendo el conjunto disponible o separando el problema en casos.

16.12 Aplicaciones en informática

• Formar equipos o grupos sin importar el orden.
• Seleccionar características para un modelo.
• Elegir subconjuntos de datos para pruebas.
• Analizar combinaciones de permisos o recursos.
• Calcular casos posibles en problemas de probabilidad.
• Explorar selecciones sin generar duplicados por orden.

16.13 Errores frecuentes

• Usar variaciones cuando el orden no importa.
• Olvidar dividir por k! en la fórmula.
• Generar {A, B} y {B, A} como si fueran grupos distintos.
• Permitir elementos repetidos.
• Usar valores donde k es mayor que n.

16.14 Qué debes recordar de este tema

• Una combinación selecciona elementos sin considerar el orden.
• No se repiten elementos.
• La fórmula es C(n, k) = n! / (k! × (n - k)!).
• El factor k! elimina ordenamientos repetidos.
• C(n, k) = C(n, n - k).
• Las combinaciones representan subconjuntos de tamaño k.

16.15 Conclusión

Las combinaciones sin repetición permiten seleccionar grupos de elementos diferentes cuando el orden no tiene importancia. Su fórmula corrige los ordenamientos duplicados que aparecen al contar primero como variaciones.

En el próximo tema estudiaremos las combinaciones con repetición, donde un mismo tipo de elemento puede seleccionarse más de una vez.