jump to navigation

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

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

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?

otra vez supongamos que f(i) es la cantidad de formas distintas que puede el niño bajar hasta el i-esimo peldaño, es muy fácil ver en éste peldaño pudo haber bajado hasta el peldaño anterior y bajar un solo peldaño, o bajar hasta el i-2 y dar un salto. De ahi sabemos que:
f(i) = f(i-1) + f(i-2) y como para el primer peldaño solo hay una forma y para no bajar también solo hay una forma, entonces son exactamente los números de Fibonacci.

Otra aparición muy afortunada de los números de Fibonacci es en caminos:
¿Cuántos caminos hay entre el punto 1 y el punto n en la siguiente figura si solo se puede ir hacia la derecha?

malla de caminos

ir del 1 al n

Otros problemas básicos del estilo son los siguientes:

¿Cuántos subconjuntos hay del conjunto {1,2,3…n} tales que no falten 2 números consecutivos?

¿Cuánto vale la siguiente suma?
\displaystyle \sum_{a+b=n} {a \choose b}

usando la notacion de que {a \choose b} = 0 si a < b o si b < 0

Además usando esas equivalencias se pueden resolver problemas sobre los números de fibonacci, por ejemplo:

Demostrar que f(2n+1) = f(n)^2 + f(n+1)^2

Comentarios»

1. Álvaro - Octubre 28, 2008

La pista que resuelve el último problema es justo el dibujo de los caminos. hay que representar un dibujo que tenga f(2n+1) caminos distintos

Responder
2. Álvaro - Octubre 28, 2008

sabiendo que {a \choose b-1}+{a\choose b}={a+1\choose b} podemos escribir:

\displaystyle \sum_{a+b=n} {a \choose b} = \sum_{a+b=n} {a-1 \choose b-1}+{a-1\choose b}
\displaystyle = \sum_{a+b=n} {a-1 \choose b-1} + \sum_{a+b=n} {a-1 \choose b}

\displaystyle = \sum_{a+b=n-2} {a \choose b} + \sum_{a+b=n-1} {a \choose b}

OJO: usamos como notación que {a \choose b} = 0 si b > a o b < 0

Responder