jump to navigation

Contar con los números de Fibonacci Julio 26, 2008

Posted by Álvaro in combinatoria, introductorios, trucos, varios.
Tags: , , , , ,
2 comments

Otra técnica para contar es establecer alguna recurrencia, un ejemplo muy fácil:

¿Cuántos subconjuntos hay del conjunto {1, 2, 3… n}?
si definimos f(i) como la cantidad de subconjuntos que incluyen números menores o iguales a i podemos decir que f(i+1) = 2f(i) pues por cada conjunto que no contiene a i, se puede formar otro subconjunto igual pero que si lo contiene. Como f(0) = 1 se puede ver que f(n) = 2^n

Además una de las relaciones de recurrencia mas estudiadas es la de los números de Fibonacci, que cumplen con que
f_(i+1) = f(i) + f(i-1) y f(0) = 0, f(1) = 1

Es muy común encontrar esta relación de recurrencia en problemas, por ejemplo:

Un niño baja una escalera de n peldaños dando a veces saltos de 2 peldaños. ¿de cuántas formas distintas puede bajar la escalera?
 (más…)