26. Conteo mediante complemento

26.1 Introducción

Algunos problemas piden contar configuraciones que cumplen una condición complicada. En lugar de contar directamente cada caso válido, puede ser más sencillo contar todos los casos y quitar los que no cumplen la condición.

El conjunto de casos que no cumplen una propiedad se llama complemento de los casos válidos.

26.2 Principio del complemento

Si U es el conjunto universal de todos los casos y A es el conjunto de casos válidos, entonces:

En palabras:

La estrategia funciona porque cada caso pertenece exactamente a una de las dos categorías: válido o inválido.

26.3 Cuándo conviene usarlo

El complemento resulta útil cuando:

• El total de casos se calcula fácilmente.
• Los casos inválidos tienen una estructura simple.
• La condición válida contiene muchas posibilidades.
• Es más sencillo describir lo que se quiere evitar.

26.4 Ejemplo con cadenas

Supongamos que construimos cadenas de 4 posiciones con los símbolos A, B y C, permitiendo repetición. Hay:

Si queremos contar las cadenas que contienen al menos una A, contamos el complemento: las cadenas que no contienen A. Cada posición puede ser B o C:

26.5 Simulación del complemento

Indica la cantidad total de casos y cuántos son inválidos. La simulación calcula los válidos y representa ambas partes proporcionalmente.

26.6 Ejemplo de al menos una coincidencia

Para contar códigos de 3 posiciones con al menos un símbolo repetido, contamos primero todos los códigos y restamos los que tienen todos sus símbolos diferentes.

26.7 Un ejemplo en JavaScript

El complemento puede calcularse con una función sencilla.

function casosValidos(total, invalidos) {
  return total - invalidos;
}

const todasLasCadenas = 3 ** 4;
const cadenasSinA = 2 ** 4;

console.log(casosValidos(todasLasCadenas, cadenasSinA));

El resultado es 65 cadenas con al menos una A.

26.8 Complemento y eventos

La misma idea se utiliza en probabilidad:

Si calcular la probabilidad de que ocurra A es difícil, pero es sencillo calcular la probabilidad de que no ocurra, utilizamos el complemento.

26.9 Complemento de una unión

Las leyes de De Morgan relacionan complementos con uniones e intersecciones:

Por ejemplo, “no ocurre A ni B” equivale a “no ocurre A y no ocurre B”. Estas transformaciones ayudan a describir el complemento de una condición.

26.10 Ejemplo con restricciones

Si contamos secuencias que no contienen dos símbolos iguales consecutivos, puede ser difícil construir directamente todas las válidas. El complemento está formado por las secuencias que contienen al menos una pareja consecutiva igual.

Cuando el complemento también requiere inclusión y exclusión, podemos combinar ambas técnicas.

26.11 Verificar por enumeración

Para un caso pequeño, podemos generar todos los casos, probar la condición y comparar el conteo directo con el conteo por complemento.

const simbolos = ["A", "B", "C"];
let total = 0;
let validos = 0;

for (const primero of simbolos) {
  for (const segundo of simbolos) {
    total += 1;
    if (primero !== segundo) validos += 1;
  }
}

const invalidos = total - validos;
console.log({ total, validos, invalidos });

La enumeración sirve para comprobar el razonamiento en ejemplos pequeños, pero el complemento evita generar todos los casos cuando el espacio crece.

26.12 Aplicaciones en informática

• Contar cadenas que contienen al menos una característica.
• Calcular configuraciones que evitan un patrón prohibido.
• Analizar casos de prueba que cumplen una condición.
• Contar registros que no pertenecen a una categoría.
• Estudiar probabilidades de que ocurra al menos un evento.
• Reducir búsquedas contando primero los casos fáciles de excluir.

26.13 Errores frecuentes

• Restar casos inválidos que no forman parte del total.
• Contar un caso inválido dos veces antes de restarlo.
• Confundir “al menos uno” con “exactamente uno”.
• Olvidar que válido e inválido deben cubrir todos los casos.
• Aplicar complemento sin poder calcular correctamente el conjunto excluido.

26.14 Qué debes recordar de este tema

• El complemento contiene los casos que no cumplen la condición.
• Casos válidos = casos totales - casos inválidos.
• Conviene usarlo cuando el complemento es más fácil de contar.
• Puede combinarse con el principio del producto y con inclusión y exclusión.
• En probabilidad, P(A) = 1 - P(A^c).
• La enumeración de casos pequeños permite verificar el resultado.

26.15 Conclusión

El conteo mediante complemento cambia el punto de vista del problema: en lugar de construir directamente los casos válidos, cuenta el total y elimina los que deben excluirse.

En el próximo tema estudiaremos el conteo con restricciones, donde analizaremos condiciones que limitan las configuraciones posibles.