¿De cuántas maneras diferentes puedo levantarme un vuelo (de escalera) con 11 pasos?

Question

Usted puede subir a cualquiera de las $1$ o $2$ escaleras en un momento, en cualquier momento dado. De cuántas formas se puede obtener hasta $11$ escaleras?

He intentado usar diferentes casos, para resolver esto.

Así lo hice: Caso 1: Todos los $1$ -- > $11 $pasos --> número de combinaciones = $1$

Caso 2: $9 $uno de los pasos, $1$ dos paso --> número de combinaciones = $\binom{n}{2} $??

Caso 3: $7$ uno de los pasos, $2$ dos pasos --> número de combinaciones?

No entiendo cómo proceder en el futuro. ¿Hay alguna manera más fácil de hacer esto?

Answer 1

Sugerencia: Empezar por el principio, no el final.

Paso $1$: Si hay un paso, sólo hay una manera de usar las escaleras.

Paso $2$: Si hay dos pasos, usted puede tomar $2$ pasos de un solo paso o dos veces, dando lugar a dos formas de tomar las escaleras.

Paso $3$: Considerar el primer paso, si usted comienza con $1$ paso, a continuación, $2$ pasos permanecen y sabemos que hay dos formas de subir dos escaleras. Por otro lado, si usted comienza con $2$ pasos, esto deja a un paso y sabemos que hay un solo camino para subir una escalera. Esto le da a $1+2=3$ maneras de subir tres escalones.

Paso $4$: Considerar el primer paso, si usted comienza con $1$ paso, a continuación, $3$ pasos permanecen y sabemos que hay tres formas de subir tres escalones. Por otro lado, si usted comienza con $2$ pasos, a continuación, sólo hay dos pasos a la izquierda, y sabemos que hay $2$ maneras de ir hasta $2$ pasos. Esto le da a $2+3=5$ maneras de ir hasta $4$ pasos.

Continuar de esta manera. Usted puede reconocer los números que usted recibe como en un popular de la secuencia.

Answer 2

He aquí una manera de ver esto visualmente. Dibujar el camino posibilidades:

En este grafo dirigido, empiece en el paso 0 y siga las flechas para el paso 11. Flechas horizontales representan dos pasos, y diagonal flechas representan un paso. Usted puede ver que si una persona toma cada paso, que va en zig zag a través de la gráfica. Si una persona salta tantos pasos como sea posible, vamos a viajar en su mayoría de forma horizontal de izquierda a derecha con una diagonal paso en alguna parte.

Ahora vamos a contar las posibilidades a partir del paso 10. Sólo hay una manera de ir desde el paso 10 paso 11, así que vamos a escribir 1 en el paso 10. Hay dos maneras de ir desde el paso 9 paso 11, una de esas maneras va a través del paso 10, así que vamos a escribir 2 junto al paso 9. Desde el paso 8, las opciones son, o bien seguir los pasos 9 o 10. Desde el paso 9 tienes 2 posibilidades para que continúe con el paso 11, y a partir del paso 10 usted tiene sólo uno. Añadiendo que significa que a partir del paso 8 usted tiene 3 posibilidades, así que vamos a escribir 3 junto al paso 8. Continuando hacia atrás, se puede ver que en cada paso, el número de posibilidades es la suma de la cantidad de posibilidades de los dos próximos pasos inmediatos. El llenado de esta en este aspecto:

Ahora se puede ver que el número total de posibilidades es de 144.

Answer 3

Se puede definir $n$-ésimo número de Fibonacci (*) como el número de maneras que usted puede escribir $n$ como la suma de los %#% de #% y $1$'s.

Por lo tanto, su respuesta es la $2$-ésimo número de Fibonacci.

(*) Nota que hay varias definiciones de la Fibonacci números en común uso, así que asegúrese de utilizar el derecho de uno, que coincide con esta definición (tenga en cuenta que $11$).

Answer 4

En el fin de seguir su plan original:

Caso $1$: Todos los $1$-pasos, esto se traduce en una forma de subir las escaleras.

Caso $2$: $9$ uno de los pasos y $1$ dos pasos. Desde que usted se mueva $10$ tiempos y uno de los movimientos es un paso de dos, esto da $\binom{9+1}{1}=\binom{10}{1}$ formas para seleccionar el paso de dos de las $10$ veces que usted se mueva.

Caso $3$: $7$ uno de los pasos y $2$ dos pasos. Puesto que usted tome $9$ se mueve y dos de ellos son de dos pasos, debe seleccionar cual de los pasos es un paso de dos. Esto le da a $\binom{7+2}{2}=\binom{9}{2}$ formas de subir las escaleras de esta manera.

Continuar con el cálculo hasta que usted no puede agregar más de dos pasos.

Answer 5

Lo más que podemos paso dos a la vez es cinco veces. Tenemos una secuencia: $$2,2,2,2,2,1$ $ ¿Cómo formas diferentes puede pedir? Tenga en cuenta, el patrón de la secuencia tiene que cambiar con cada sustitución.

Entonces podemos paso a dos escaleras cuatro veces: $$2,2,2,2,1,1,1$ $

.. y así sucesivamente hasta que paso dos veces solo una vez y el resto son solo pasos. Contar el número de posibilidades en cada escenario y les sume y agregue uno al resultado. ¿Por qué?