Recursiones básicas en conteo

¿Qué es una recurrencia combinatoria?

Muchos problemas de conteo tienen la siguiente estructura: el número de objetos de "tamaño $n$" se puede expresar en función del número de objetos de tamaño $n-1$, $n-2$, etc. Esta relación se llama una recurrencia (o relación de recurrencia).

La recurrencia más famosa en combinatoria es la de Fibonacci: $F_n = F_{n-1} + F_{n-2}$, con $F_1 = F_2 = 1$. Aparece de forma natural al contar el número de formas de cubrir una tira de $n$ casillas con fichas de tamaño 1 y 2.

El método para resolver problemas con recurrencias tiene tres pasos: (1) definir claramente la cantidad $a_n$ que se quiere contar, (2) hallar la relación que conecta $a_n$ con valores anteriores observando cómo se "construye" una configuración de tamaño $n$ a partir de configuraciones más pequeñas, (3) usar los casos base para calcular los primeros términos y, si se pide una fórmula cerrada, resolver la ecuación característica.

La sucesión de Fibonacci: conteo de caminos y coberturas

Problema modelo: ¿de cuántas formas se puede cubrir una tira $1 \times n$ usando fichas $1 \times 1$ y fichas $1 \times 2$?

Sea $F_n$ el número de coberturas de la tira de longitud $n$. La última ficha colocada es de tamaño 1 (cubriendo la casilla $n$) o de tamaño 2 (cubriendo las casillas $n-1$ y $n$). En el primer caso las casillas $1, \ldots, n-1$ quedan por cubrir de $F_{n-1}$ formas; en el segundo, las casillas $1, \ldots, n-2$ quedan por cubrir de $F_{n-2}$ formas. Luego $F_n = F_{n-1} + F_{n-2}$.

Casos base: $F_1 = 1$ (solo una ficha de tamaño 1) y $F_2 = 2$ (dos fichas de tamaño 1, o una ficha de tamaño 2). Los primeros valores son $1, 2, 3, 5, 8, 13, 21, \ldots$, que son los números de Fibonacci corridos un índice.

La identidad $F_n = F_{n-1} + F_{n-2}$ es la herramienta. No necesitas la fórmula de Binet $F_n = \frac{\phi^n - \psi^n}{\sqrt{5}}$ para problemas regionales; basta con la recurrencia y los casos base.

Resolución de recurrencias lineales de orden 2

Una recurrencia lineal homogénea de orden 2 tiene la forma $a_n = p \cdot a_{n-1} + q \cdot a_{n-2}$. Para resolverla, se buscan soluciones de la forma $a_n = r^n$; sustituyendo: $r^n = p r^{n-1} + q r^{n-2}$, lo que da la ecuación característica $r^2 = pr + q$, o bien $r^2 - pr - q = 0$.

Si las raíces $r_1$ y $r_2$ son distintas, la solución general es $a_n = A r_1^n + B r_2^n$, con $A$ y $B$ determinados por los casos base. Si $r_1 = r_2 = r$ (raíz doble), la solución general es $a_n = (A + Bn) r^n$.

Ejemplo: resuelve $a_n = 3a_{n-1} - 2a_{n-2}$ con $a_0 = 1$, $a_1 = 3$. La ecuación característica es $r^2 - 3r + 2 = 0$, con raíces $r_1 = 1$ y $r_2 = 2$. La solución general es $a_n = A + B \cdot 2^n$. Con los casos base: $A + B = 1$ y $A + 2B = 3$, que da $B = 2$, $A = -1$. Luego $a_n = 2^{n+1} - 1$. Verificación: $a_2 = 3 \cdot 3 - 2 \cdot 1 = 7 = 2^3 - 1$. ✓

Para problemas olímpicos regionales, el paso más importante es establecer la recurrencia correctamente; la resolución algebraica es secundaria y a menudo se puede evitar calculando los términos uno a uno.

Recurrencias no homogéneas y cambio de variable

Una recurrencia de la forma $a_n = p \cdot a_{n-1} + f(n)$ (con $f(n) \ne 0$) se llama no homogénea. La estrategia es encontrar una solución particular $a_n^*$ y sumar la solución de la parte homogénea.

Ejemplo: $a_n = 2a_{n-1} + 1$ con $a_0 = 0$. La solución particular constante satisface $c = 2c + 1$, que da $c = -1$. La solución general de la homogénea $a_n^{(h)} = 2a_{n-1}^{(h)}$ es $A \cdot 2^n$. Entonces $a_n = A \cdot 2^n - 1$; con $a_0 = 0$: $A = 1$, luego $a_n = 2^n - 1$.

Cambio de variable alternativo: define $b_n = a_n + 1$; entonces $b_n = a_n + 1 = 2a_{n-1} + 2 = 2b_{n-1}$. Con $b_0 = 1$: $b_n = 2^n$, luego $a_n = 2^n - 1$. Este truco —sumar una constante para "homogeneizar"— es muy eficiente en olimpiadas.

La regla práctica: cuando la recurrencia tiene un término constante o lineal en $n$, prueba primero soluciones particulares constantes; si no funcionan, prueba polinomios de grado 1.

Identificar recurrencias en problemas de conteo

La habilidad crucial es reconocer que un problema de conteo admite una recurrencia. Las señales son: la respuesta depende del "tamaño" $n$ de algún parámetro, y añadir un elemento más (casilla, persona, objeto) produce una configuración que "casi" es la de tamaño $n-1$.

Pregunta guía: ¿cuál es la última decisión tomada? Si la última decisión tiene $k$ opciones posibles, y cada opción reduce el problema a uno de tamaño menor, obtienes $a_n =$ suma de los $k$ casos. Este es el "árbol de decisiones" convertido en fórmula.

Ejemplo adicional: el número de cadenas de longitud $n$ con letras $\{A, B\}$ que no contienen dos $B$ consecutivas. Sea $a_n$ este número. Si la $n$-ésima letra es $A$, las primeras $n-1$ pueden ser cualquier cadena válida de longitud $n-1$: $a_{n-1}$ opciones. Si la $n$-ésima es $B$, la $(n-1)$-ésima debe ser $A$ (para evitar dos $B$ seguidas), y las primeras $n-2$ pueden ser cualquier cadena válida de longitud $n-2$: $a_{n-2}$ opciones. Luego $a_n = a_{n-1} + a_{n-2}$ — de nuevo Fibonacci, con $a_1 = 2$ ($A$ o $B$) y $a_2 = 3$ ($AA$, $AB$, $BA$).