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:

Posts aleatorios

Autor: ^DiAmOnD^ | Publicado el 2 de May de 2008
Categorías: Curiosidades, Números enteros | Imprime este post

Sin comentarios

Omar-P | 2 de May 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 May 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 May 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.