39. Relaciones de recurrencia aplicadas al conteo

39.1 Introducción

En el tema anterior introdujimos la recurrencia. Ahora construiremos relaciones a partir de problemas concretos de conteo.

La técnica consiste en observar cómo puede terminar una configuración, clasificar esos casos y expresar cada grupo mediante un problema más pequeño.

39.2 Modelo general

Una relación de recurrencia puede tener la forma:

Los coeficientes indican cuántas decisiones o variantes producen cada tipo de caso menor.

39.3 Ejemplo: cubrir una fila

Una fila de n posiciones puede cubrirse con piezas de longitud 1 o 2. Al observar la última pieza:

El primer término representa una última pieza de longitud 1 y el segundo una última pieza de longitud 2.

39.4 Simulación de recurrencias de conteo

Elige un modelo combinatorio y observa cómo se construyen sus valores para distintos tamaños.

39.5 Cadenas binarias sin unos consecutivos

Sea B(n) la cantidad de cadenas binarias de longitud n que no contienen dos unos consecutivos. Si la cadena termina en 0, el prefijo puede ser cualquiera; si termina en 1, el símbolo anterior debe ser 0.

Una forma de expresar el conteo es:

39.6 Caminos con varios tamaños de paso

Si un recorrido puede avanzar 1, 2 o 3 posiciones, la última decisión produce tres tamaños menores:

Los casos base dependen de cómo definamos el recorrido vacío y las posiciones iniciales.

39.7 Un ejemplo en JavaScript

Esta función calcula la cantidad de coberturas con piezas de tamaño 1 o 2.

function contarCoberturas(n) {
  const valores = [1, 1];
  for (let posicion = 2; posicion <= n; posicion += 1) {
    valores[posicion] = valores[posicion - 1] + valores[posicion - 2];
  }
  return valores[n];
}

console.log(contarCoberturas(8));

39.8 Descomposición por la última decisión

La clasificación por el último paso evita contar una misma configuración en dos categorías. Cada configuración tiene una última pieza, símbolo o movimiento bien definido.

Los grupos deben ser excluyentes y cubrir todas las formas de terminar.

39.9 Recurrencias con coeficientes

Si existen varias formas distintas de realizar una misma última etapa, aparece un coeficiente:

El término 2a_n-1 indica que cada configuración de tamaño n-1 puede extenderse de dos maneras diferentes.

39.10 Recursión directa e iteración

Una implementación recursiva expresa la definición de forma natural, pero puede repetir los mismos cálculos. La versión iterativa guarda los valores ya obtenidos.

39.11 Verificar una relación

Para comprobar una recurrencia podemos generar algunos casos pequeños mediante enumeración y comparar los valores con la relación propuesta.

function verificarRecurrencia(valores) {
  for (let indice = 2; indice < valores.length; indice += 1) {
    const esperado = valores[indice - 1] + valores[indice - 2];
    if (valores[indice] !== esperado) return false;
  }
  return true;
}

console.log(verificarRecurrencia([1, 1, 2, 3, 5, 8]));

39.12 Aplicaciones en informática

• Contar caminos y recorridos.
• Analizar cadenas con patrones prohibidos.
• Calcular formas de cubrir posiciones.
• Construir tablas de programación dinámica.
• Modelar decisiones sucesivas.
• Verificar algoritmos que dividen casos.

39.13 Errores frecuentes

• No justificar por qué los casos son excluyentes.
• Omitir una forma posible de terminar la configuración.
• Elegir casos base incompatibles con la interpretación.
• Usar un índice incorrecto en la tabla.
• Confundir una relación de conteo con una fórmula cerrada.

39.14 Qué debes recordar de este tema

• Una recurrencia aplicada al conteo divide soluciones por casos finales.
• Los casos deben ser completos y no superponerse.
• Los casos base representan tamaños pequeños resolubles directamente.
• Los coeficientes indican variantes de una misma extensión.
• La programación dinámica evita repetir cálculos.
• La enumeración de casos pequeños ayuda a validar la relación.

39.15 Conclusión

Las relaciones de recurrencia convierten problemas de conteo en una secuencia de decisiones más pequeñas. Analizar la última etapa permite construir fórmulas que luego pueden implementarse con recursión, iteración o programación dinámica.

En el próximo tema estudiaremos sucesiones combinatorias y sus patrones de crecimiento.