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:

Autor: ^DiAmOnD^

Miguel Ángel Morales Medina. Licenciado en Matemáticas y autor de Gaussianos y de El Aleph. Puedes seguirme en Twitter o indicar que te gusta mi página de Facebook.

3 Comentarios

  1. Interesante propiedad. Un orden para las 4 composiciones de 3 podría ser:
    (3), (2,1), (1,2), (1,1,1)

    Publica una respuesta
  2. 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.

    Publica una respuesta
  3. 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.

    Publica una respuesta

Puedes utilizar código LaTeX para insertar fórmulas en los comentarios. Sólo tienes que escribir
[latex]código-latex-que-quieras-insertar[/latex]
o
$latex código-latex-que-quieras-insertar$.

Si tienes alguna duda sobre cómo escribir algún símbolo puede ayudarte la Wikipedia.

Y si los símbolos < y > te dan problemas al escribir en LaTeX te recomiendo que uses los códigos html & lt; y & gt; (sin los espacios) respectivamente.

Envía un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *