Formas de escribir n como suma de 1s y 2s.
Una composición de un entero $n$ es una forma de escribir $n$ como la suma de una secuencia de enteros positivos. Cuando te limitas a partes de tamaño 1 y 2, este problema te pide hallar el número de secuencias ordenadas distintas de 1s y 2s que sumen $n$. Por ejemplo, puedes escribir el número 3 como $1+1+1$, $1+2$ o $2+1$. Esta estructura combinatoria específica es isomorfa a varios problemas clásicos, sobre todo al "Problema de subir escaleras" (hallar el número de formas de subir $n$ escalones dando pasos de tamaño 1 o 2) y al "Problema de pavimentación con dominós" (hallar el número de formas de cubrir un tablero de $2 \times n$ con dominós de $2 \times 1$).
Este concepto es fundamental en las matemáticas de competencia porque te da la interpretación combinatoria principal de la sucesión de Fibonacci. Aunque la sucesión de Fibonacci la encuentras seguido con su definición recursiva, si reconoces que un problema es una "composición con 1s y 2s", puedes identificar de inmediato que la respuesta es un número de Fibonacci sin tener que contar a mano. Esta técnica sirve de puente entre el álgebra recursiva y las estrategias de conteo.
La idea clave está en analizar la estructura de la suma desde el final (o el principio). Para formar una suma de $n$, el...