29. Conteo de cadenas y secuencias

29.1 Introducción

Una cadena es una secuencia ordenada de símbolos. Puede representar un código, una palabra, una señal, una secuencia de estados o una entrada para un algoritmo.

Contar cadenas es una aplicación directa del principio del producto: cada posición tiene un conjunto de opciones y el número total se obtiene combinando esas elecciones.

29.2 Cadenas de longitud fija

Si un alfabeto tiene n símbolos y una cadena tiene k posiciones, permitiendo repetir símbolos, la cantidad es:

Con 3 símbolos y 4 posiciones:

29.3 Cadenas sin repetición

Si los símbolos no pueden repetirse, las opciones disminuyen en cada posición:

Con 5 símbolos y cadenas de longitud 3 sin repetir:

29.4 Simulación de cadenas

Escribe un alfabeto pequeño, define la longitud y decide si se permiten repeticiones. La simulación genera las cadenas y muestra el total.

29.5 Cadenas con primera posición restringida

Si una cadena de longitud k debe comenzar con un símbolo determinado, la primera posición deja de tener n opciones:

Con 4 símbolos y longitud 3, las cadenas que comienzan con A son 4² = 16.

29.6 Cadenas que contienen un símbolo

Para contar cadenas que contienen al menos una A, usamos complemento:

29.7 Un ejemplo en JavaScript

Esta función genera cadenas permitiendo repetir cada símbolo.

function cadenas(alfabeto, longitud, actual = [], resultados = []) {
  if (actual.length === longitud) {
    resultados.push(actual.join(""));
    return resultados;
  }
  for (const simbolo of alfabeto) {
    cadenas(alfabeto, longitud, [...actual, simbolo], resultados);
  }
  return resultados;
}

console.log(cadenas(["A", "B", "C"], 2));

29.8 Cadenas sin símbolos consecutivos iguales

Si no se permite repetir el símbolo inmediatamente anterior, la primera posición tiene n opciones y cada posición posterior tiene n-1.

Con 3 símbolos y longitud 4:

29.9 Cadenas con cantidad exacta de símbolos

Si una cadena binaria de longitud n debe contener exactamente k unos, elegimos las posiciones de los unos:

Por ejemplo, las cadenas binarias de longitud 5 con exactamente 2 unos se cuentan con C(5,2) = 10.

29.10 Cadenas de longitud variable

Si se permiten longitudes de 1 hasta k y cada posición tiene n opciones, sumamos las cantidades de cada longitud:

El principio de la suma aparece porque las longitudes distintas son alternativas excluyentes.

29.11 Aplicaciones en informática

• Contar códigos y contraseñas posibles.
• Analizar secuencias de estados.
• Generar casos de prueba de longitud fija.
• Estudiar cadenas binarias y configuraciones de bits.
• Validar formatos con restricciones de posición.
• Estimar espacios de búsqueda en procesamiento de texto.

29.12 Errores frecuentes

• Usar n^k cuando no se permite repetir.
• Olvidar que las posiciones de una cadena están ordenadas.
• Contar símbolos en vez de posiciones.
• Ignorar una restricción sobre el primer o último símbolo.
• Confundir “al menos una vez” con “exactamente una vez”.

29.13 Qué debes recordar de este tema

• Una cadena es una secuencia ordenada de símbolos.
• Con repetición permitida, n símbolos y k posiciones producen n^k cadenas.
• Sin repetición se utiliza un producto descendente.
• Las restricciones modifican las opciones de determinadas posiciones.
• El complemento cuenta cadenas que contienen al menos un símbolo.
• Las combinaciones cuentan posiciones ocupadas por un símbolo específico.

29.14 Conclusión

El conteo de cadenas y secuencias reúne muchos conceptos de la combinatoria: producto, variaciones, combinaciones, complemento y restricciones. Identificar el alfabeto y analizar cada posición permite construir el modelo correcto.

En el próximo tema estudiaremos el conteo de subconjuntos, una aplicación directa de las combinaciones y los coeficientes binomiales.