Gaussianos » Composiciones de números y números de Fibonacci

Composiciones de números y números de Fibonacci

Vamos a comentar una propiedad curiosa que me mandó fede por mail hace tiempo:

Podemos expresar un número, por ejemplo el $3$ , como suma de números de varias formas diferentes:
$3=1+1+1,3=2+1,3=1+2,3=3$
(admitimos sumas con un solo sumando).

Una de estas sumas se llama partición del número si consideramos que el orden de los sumandos no importa. La suma se llama composición cuando el orden de los sumandos importa. Según ésto el número de particiones de $3$ es 3 y el número de composiciones de $3$ es 4. En general, el número de composiciones de $N$ es $2^{N-1}$ .

Las teoría de particiones (de números) es una famosa rama de la combinatoria y de la teoría de números. Las composiciones no tienen tanta fama (no parece que haya tanto que decir de ellas), pero tenemos el siguiente resultado curioso:

Si multiplicamos los sumandos de cada composición de un número $N$ y sumamos todos los productos, el resultado es el $2 \cdot N$ -ésimo número de la sucesión de Fibonacci $F(N)$ ( $N=1,1,2,3,5,8,13 \ldots$ ). Por ejemplo, para $N=3$ tenemos que $1 \cdot 1 \cdot 1 + 1 \cdot 2 + 2 \cdot 1 + 3 = 8$ , que es igual a $F(2 \cdot 3)=F(6)$ .

Curiosa e interesante propiedad de las composiciones de números y los números de Fibonacci. Os dejo un par de enlaces con otras curiosidades de estos números publicadas ya en Gaussianos:

Escrito por ^DiAmOnD^, 2 de Mayo de 2008 en Curiosidades, Números enteros

3 comentarios

Trackback para este post

Omar-P - 2 de Mayo de 2008 19:18

Interesante propiedad. Un orden para las 4 composiciones de 3 podría ser:
(3), (2,1), (1,2), (1,1,1)
Domingo H.A. - 3 de Mayo de 2008 21:18

podríamos poner la prueba de que todo número natural se expresa como suma de números de Fibonacci, sin repetir ninguno de los sumandos. Son válidas sumas de un solo sumando.
fede - 6 de Mayo de 2008 10:02

Cierto Domingo, además la representación de $N = F(k_1) + F(k_2) + \ldots + F(k_m)$ es única si exigimos que $k_1 \ge 2$ y $k_{i+1} \ge k_i + 2$ .

En el tema de la relación entre composiciones y números de Finonacci, podemos considerar $S(N) = \sum \prod f(k)$ , donde la suma recorre todas las composiciones de N y el producto los términos de cada composición,
por ejemplo S(3) = f(3) + f(2)f(1) + f(1)f(2) + f(1)f(1)f(1).

Entonces Si f(k) = 1 para todo k, S(N) = $2^{N-1}$ , pero tambíen:

a. Si f(1) = f(2) = 1 y f(k) = 0 en otro caso, S(N) = F(N+1)
b. si f(1) = 0 y f(k) = 1 en otro caso, S(N) = F(N-1)
c. si f(k) = 1 si k es impar y f(k)=0 si k es par, S(N) = F(N)
d. si f(1) = 2 y f(k) = 1 en otro caso, S(N) = F(2N+1)
e. si f(k) = k, S(N) = F(2N) (es la proposición del post)
f. si f(k) = $2^{k-1}-1$ , S(N) = F(2N-2)

Todo esto se puede demostrar elementalmente estableciendo biyecciones entre el conjunto que se mide en (a) y los que se miden en los demás puntos.

Deja un comentario

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios.
Para ello sólo tienes que escribir $ latex código-latex$ (sin el espacio entre $ y la palabra latex).
Si tienes alguna duda sobre cómo insertar algún símbolo puede ayudarte la siguiente web:
Wikipedia: Usando TeX
Utiliza la Vista Previa antes de publicar tu comentario para asegurarte de que las fórmulas están correctamente escritas.