¿Cuántas formas distintas de subir escaleras en 1 o 2 pasos a la vez?

Question

Me encontré con un interesante rompecabezas:

Estás subiendo una caja de escalera. Se necesita $n$ pasos para llegar a la cima. Cada vez puedes subir $1$ o $2$ pasos. ¿En cuántos pasos distintos formas en que puedes subir a la cima?

¿Hay una solución de forma cerrada para el problema? Se puede computacional creando un "árbol" de posibilidades de cada paso. Es decir, puedo dar 1 o 2 pasos en cada etapa y terminar una rama una vez que sume $n$ . Pero esto se volvería muy difícil de manejar muy rápidamente, ya que el número máximo de nodos en un árbol binario es $2^{n+1}-1$ es decir, exponencial. ¿Hay una forma más fácil de resolver este rompecabezas?

Answer 1

Dejemos que $F_n$ sea el número de vías de ascenso $n$ escaleras tomando sólo $1$ o $2$ pasos. Sabemos que $F_1 = 1$ y $F_2 = 2$ . Ahora, considere $F_n$ para $n\ge 3$ . El último paso será de tamaño $1$ o $2$ Así que $F_n$ = $F_{n-1} + F_{n-2}$ . Esta es la recurrencia de Fibonacci.

Answer 2

La solución a este problema corresponde, efectivamente, a los números de Fibonacci, como menciona @fahrbach.

He aquí una ilustración de lo que se intenta resolver para el caso de $n=4$ pasos (tomados de este sitio web que también da una solución combinatoria)

Cualquier escalera con $n$ pasos que permiten recorridos con incrementos de 1 o 2 pasos a la vez terminarán en uno de los dos estados antes de que se tome el último camino: o bien hemos subido $(n-1)$ pasos ya y han $\color{red}{one}$ paso más que dar, o hemos subido $(n-2)$ pasos ya y tenemos $\color{blue}{two}$ más pasos que dar (si sólo diéramos un paso aquí, acabaríamos en un acuerdo del primer estado).

Así, para obtener el número total de formas posibles de subir $n$ pasos, simplemente sumamos el número de formas posibles de subir $(n-1)$ escalones y el número de caminos posibles que podemos subir $(n-2)$ pasos, dando la conocida relación de recurrencia:

\begin {equation*} F_n = \left\ { \begin {array}{l@{}l@{}l} 1 & n = 0,1 \\ \color {rojo}{F_{n-1}} + \color {azul}{F_{n-2}} & n \ge 2 \end {array} \right. \end {equation*}

Answer 3

Podemos cambiar esta pregunta por: ¿De cuántas maneras es posible escribir un número como la suma ordenada de 1s y 2s?

Podemos demostrarlo con una prueba directa.

Hipótesis: Para el número de Fibbonaci $F_1=1, F_2=1, F_{n}=F_{n-1}+F_{n-2}$ , $Q(k)=F_{k+1}$

Decimos que hemos construido cada orden de $Q(n)$ . A continuación, construimos $Q(n+1)$ de esta manera:

1. Para todos los pedidos, añadimos $+1$ para cambiar $n$ a $n+1$ . (Ahora hay $Q(n)$ números). Nota: todos los números que se construyen aquí terminan en $+1$ .
2. Para todos los pedidos que terminan en $+1$ lo cambiamos por $+2$ . Demostraremos que el importe será $Q(n-1)$ para completar la prueba. Nota: todos los números que se construyen aquí terminan en $+2$ .

Se puede ver que al construir de esta manera contiene todos los órdenes.

Prueba del paso 2: Si construimos $Q(n)$ de la forma anterior, entonces todos los números terminados en $+1$ será la cantidad $Q(n-1)$ por el paso 1. anterior, y hemos terminado.

Answer 4

Se trata de los números de Fibonacci - Una interpretación del número n-ésimo de Fibonacci es el número de formas de componer $n$ con piezas en $\{1,2\}$ (es decir, el número n-ésimo de fibonacci cuenta el número de secuencias cuyos valores están en $\{1,2\}$ cuyas sumas son $n$ ). Esto se suele llamar "Golfs y Cadillacs" o algo similar.