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…)

Contar subconjuntos Julio 15, 2008

Posted by Álvaro in combinatoria, teoremas, trucos, varios.
Tags: , ,
1 comment so far

Una de las técnicas básicas para resolver problemas es contar de varias formas, ésta vez veremos las formas de contar subconjuntos de un conjunto que para propósitos prácticos es [n] = {1, 2,….,n}.

De hecho la notación {n \choose k} se inventó para expresar la cantidad de subconjuntos con k elementos en [n]. Pero primero hay que pensar en cosas mas fáciles…
¿cuántas opciones tenemos para escoger un elemento en [n]?
¿de qué formas distintas podemos escoger los n elementos?
¿de cuántas formas podemos hacer una lista de k elementos de [n]?
(más…)