27. Conteo con restricciones

27.1 Introducción

Los principios básicos de conteo funcionan mejor cuando todas las opciones son válidas. En problemas reales suelen aparecer condiciones: un símbolo no puede ocupar una posición, dos tareas no pueden estar juntas o una selección debe incluir cierto elemento.

Contar con restricciones consiste en describir esas condiciones y determinar cómo modifican el espacio de posibilidades.

27.2 Tipos de restricciones

27.3 Restricción en una etapa

Si un código tiene 4 posiciones y se forma con 5 símbolos, el total sin restricciones es:

Si el primer símbolo no puede ser A, hay 4 opciones para la primera posición y 5 para las restantes:

27.4 Simulación de configuraciones válidas

Elige la cantidad de símbolos, la longitud de la secuencia y una restricción. La simulación genera el espacio completo para casos pequeños y conserva solo las secuencias válidas.

27.5 Restricción por inclusión

Para contar secuencias de longitud k que contienen al menos una A, podemos usar complemento:

Si n = 3 y k = 4:

27.6 Un ejemplo en JavaScript

Esta función cuenta secuencias que comienzan con un símbolo específico.

function contarConInicioFijo(cantidadSimbolos, longitud) {
  if (longitud === 0) return 0;
  return cantidadSimbolos ** (longitud - 1);
}

console.log(contarConInicioFijo(5, 4));

La primera posición ya está fijada, por lo que quedan 5 opciones para cada una de las 3 posiciones restantes.

27.7 Restricciones sin repetición

Si no se permite repetir y además una posición está fija, las opciones restantes disminuyen. Por ejemplo, con 6 elementos, A fijo en la primera posición y 3 posiciones totales:

27.8 Restricciones de adyacencia

Si dos elementos deben estar juntos, podemos tratarlos como un bloque. En una fila con A y B juntos, el bloque puede aparecer como AB o BA.

Si dos elementos no pueden estar juntos, contamos todos los ordenamientos y restamos los que los tienen como vecinos.

27.9 Complemento e inclusión y exclusión

Una restricción puede producir varios tipos de casos inválidos. Si esos casos se superponen, debemos combinar el complemento con inclusión y exclusión para no restar dos veces.

27.10 Verificación por enumeración

Para un espacio pequeño, podemos generar todas las configuraciones y comprobar la condición una por una.

const simbolos = ["A", "B", "C"];
const validas = [];

for (const primero of simbolos) {
  for (const segundo of simbolos) {
    const secuencia = primero + segundo;
    if (!secuencia.startsWith("A")) validas.push(secuencia);
  }
}

console.log(validas);
console.log(`Total válido: ${validas.length}`);

La enumeración ayuda a comprobar la fórmula, pero no debe ser la estrategia principal cuando el espacio de búsqueda es grande.

27.11 Aplicaciones en informática

• Generar códigos que cumplan reglas de formato.
• Contar configuraciones permitidas por un sistema.
• Filtrar casos de prueba con condiciones específicas.
• Analizar rutas con movimientos prohibidos.
• Asignar recursos respetando incompatibilidades.
• Reducir espacios de búsqueda mediante poda y descarte.

27.12 Errores frecuentes

• Contar configuraciones inválidas como si fueran válidas.
• Aplicar el producto sin modificar las opciones restringidas.
• Restar casos superpuestos más de una vez.
• Confundir “al menos una vez” con “exactamente una vez”.
• Generar todas las configuraciones sin evaluar su crecimiento.

27.13 Qué debes recordar de este tema

• Una restricción elimina o modifica configuraciones posibles.
• Las opciones pueden cambiar de una etapa a otra.
• El complemento cuenta los casos que incumplen una condición.
• Las restricciones de adyacencia pueden resolverse con bloques.
• Las restricciones superpuestas pueden requerir inclusión y exclusión.
• La enumeración sirve para verificar espacios pequeños.

27.14 Conclusión

Contar con restricciones exige describir qué configuraciones están permitidas y cómo las condiciones afectan las decisiones. Las herramientas estudiadas —producto, complemento, bloques e inclusión y exclusión— permiten construir conteos precisos.

En el próximo tema estudiaremos el conteo de posiciones y asignaciones, donde las restricciones se aplicarán a lugares y recursos concretos.