Palabra de Fibonacci

Secuencia binaria a partir de la recurrencia de Fibonacci

Caracterización mediante una secuencia de corte con una línea de pendiente o , con la proporción áurea . ${\displaystyle 1/\varphi }$ ${\displaystyle \varphi -1}$ ${\displaystyle \varphi }$

Curvas de Fibonacci formadas a partir de las palabras de Fibonacci 10 y 17 ^[1]

Una palabra de Fibonacci es una secuencia específica de dígitos binarios (o símbolos de cualquier alfabeto de dos letras ). La palabra de Fibonacci se forma mediante concatenaciones repetidas de la misma manera que los números de Fibonacci se forman mediante sumas repetidas.

Se trata de un ejemplo paradigmático de palabra sturmiana y, en concreto, de palabra mórfica .

El nombre "palabra de Fibonacci" también se ha utilizado para referirse a los miembros de un lenguaje formal L que consiste en cadenas de ceros y unos sin dos unos repetidos. Cualquier prefijo de la palabra de Fibonacci específica pertenece a L , pero también lo hacen muchas otras cadenas. L tiene un número de Fibonacci de miembros de cada longitud posible.

Definición

Sea "0" y "01". Ahora (la concatenación de la secuencia anterior y la anterior a esta). ${\displaystyle S_{0}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{n}=S_{n-1}S_{n-2}}$

La palabra infinita de Fibonacci es el límite , es decir, la secuencia infinita (única) que contiene cada , por finito , como prefijo. ${\displaystyle S_{\infty }}$ ${\displaystyle S_{n}}$ ${\displaystyle n}$

Enumerar elementos de la definición anterior produce:

${\displaystyle S_{0}}$    0

${\displaystyle S_{1}}$    01

${\displaystyle S_{2}}$    010

${\displaystyle S_{3}}$    01001

${\displaystyle S_{4}}$    01001010

${\displaystyle S_{5}}$    0100101001001

...

Los primeros elementos de la palabra infinita de Fibonacci son:

0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ... (secuencia A003849 en la OEIS )

Expresión de forma cerrada para dígitos individuales

El ^dígito n de la palabra es donde es la proporción áurea y es la función de suelo (secuencia A003849 en la OEIS ). Como consecuencia, la palabra de Fibonacci infinita puede caracterizarse por una secuencia de corte de una línea de pendiente o . Véase la figura anterior. ${\displaystyle 2+\lfloor n\varphi \rfloor -\lfloor (n+1)\varphi \rfloor }$ ${\displaystyle \varphi }$ ${\displaystyle \lfloor \,\ \rfloor }$ ${\displaystyle 1/\varphi }$ ${\displaystyle \varphi -1}$

Reglas de sustitución

Otra forma de ir de S _n a S _{n  +1} es reemplazar cada símbolo 0 en S _n con el par de símbolos consecutivos 0, 1 en S _{n  +1} , y reemplazar cada símbolo 1 en S _n con el símbolo único 0 en S _{n  +1} .

Como alternativa, se puede imaginar la generación directa de toda la palabra infinita de Fibonacci mediante el siguiente proceso: empezar con un cursor que apunte al dígito único 0. Luego, en cada paso, si el cursor apunta a un 0, añadir 1, 0 al final de la palabra, y si el cursor apunta a un 1, añadir 0 al final de la palabra. En cualquier caso, completar el paso moviendo el cursor una posición a la derecha.

Una palabra infinita similar, a veces llamada secuencia del conejo , se genera mediante un proceso infinito similar con una regla de reemplazo diferente: siempre que el cursor apunte a un 0, agregue 1, y siempre que el cursor apunte a un 1, agregue 0, 1. La secuencia resultante comienza

0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, ...

Sin embargo, esta secuencia difiere de la palabra Fibonacci sólo trivialmente, intercambiando los 0 por 1 y desplazando las posiciones en uno.

Una expresión en forma cerrada para la llamada secuencia del conejo:

El n- ^ésimo dígito de la palabra es ${\displaystyle \lfloor n\varphi \rfloor -\lfloor (n-1)\varphi \rfloor -1.}$

Discusión

La palabra está relacionada con la famosa secuencia del mismo nombre (la secuencia de Fibonacci ) en el sentido de que la adición de números enteros en la definición inductiva se reemplaza por la concatenación de cadenas. Esto hace que la longitud de S _n sea F _{n  +2} , el ( n  +2)º número de Fibonacci. Además, la cantidad de 1 en S _n es F _n y la cantidad de 0 en S _n es F _{n  +1} .

Otras propiedades

• La palabra infinita de Fibonacci no es periódica ni, en última instancia, periódica. ^[2]
• Las dos últimas letras de una palabra de Fibonacci son alternativamente "01" y "10".
• Suprimiendo las dos últimas letras de una palabra de Fibonacci, o anteponiendo el complemento de las dos últimas letras, se crea un palíndromo . Ejemplo: 01 S ₄ = 0101001010 es un palíndromo. La densidad palindrómica de la palabra infinita de Fibonacci es, por tanto, 1/φ, donde φ es la proporción áurea : este es el mayor valor posible para palabras aperiódicas. ^[3]
• En la palabra infinita de Fibonacci, la relación (número de letras)/(número de ceros) es φ, al igual que la relación entre ceros y unos. ^[4]
• La palabra infinita de Fibonacci es una secuencia equilibrada : tome dos factores de la misma longitud en cualquier parte de la palabra de Fibonacci. La diferencia entre sus pesos de Hamming (la cantidad de ocurrencias de "1") nunca excede 1. ^[5]
• Las subpalabras 11 y 000 nunca aparecen. ^[6]
• La función de complejidad de la palabra infinita de Fibonacci es n  + 1: contiene n  + 1 subpalabras distintas de longitud n . Ejemplo: Hay 4 subpalabras distintas de longitud 3: "001", "010", "100" y "101". Al ser también no periódica, es entonces de "complejidad mínima", y por lo tanto una palabra de Sturm , ^[7] con pendiente . La palabra infinita de Fibonacci es la palabra estándar generada por la secuencia directiva (1,1,1,....). ${\displaystyle 1/\varphi }$
• La palabra infinita de Fibonacci es recurrente; es decir, cada subpalabra aparece infinitas veces.
• Si es una subpalabra de la palabra infinita de Fibonacci, entonces también lo es su inversión, denotada . ${\displaystyle u}$ ${\displaystyle u^{R}}$
• Si es una subpalabra de la palabra infinita de Fibonacci, entonces el menor período de es un número de Fibonacci. ${\displaystyle u}$ ${\displaystyle u}$
• La concatenación de dos palabras de Fibonacci sucesivas es "casi conmutativa" y se diferencian únicamente por sus dos últimas letras. ${\displaystyle S_{n+1}=S_{n}S_{n-1}}$ ${\displaystyle S_{n-1}S_{n}}$
• El número 0,010010100..., cuyas cifras están construidas con los dígitos de la palabra infinita de Fibonacci, es trascendental .
• Las letras "1" se pueden encontrar en las posiciones dadas por los valores sucesivos de la secuencia Upper Wythoff (secuencia A001950 en la OEIS ): ${\displaystyle \lfloor n\varphi ^{2}\rfloor }$
• Las letras "0" se pueden encontrar en las posiciones dadas por los valores sucesivos de la secuencia Lower Wythoff (secuencia A000201 en la OEIS ): ${\displaystyle \lfloor n\varphi \rfloor }$
• La distribución de puntos en el círculo unitario , colocados consecutivamente en el sentido de las agujas del reloj por el ángulo áureo , genera un patrón de dos longitudes en el círculo unitario. Aunque el proceso de generación anterior de la palabra de Fibonacci no corresponde directamente a la división sucesiva de segmentos del círculo, este patrón es si el patrón comienza en el punto más cercano al primer punto en el sentido de las agujas del reloj, con lo cual 0 corresponde a la distancia larga y 1 a la distancia corta. ${\displaystyle n=F_{k}}$ ${\displaystyle {\frac {2\pi }{\varphi ^{2}}}}$ ${\displaystyle {\frac {2\pi }{\varphi ^{k-1}}},{\frac {2\pi }{\varphi ^{k}}}}$ ${\displaystyle S_{k-1}}$
• La palabra infinita de Fibonacci contiene repeticiones de 3 subpalabras idénticas sucesivas, pero ninguna de 4. ^[2] El exponente crítico de la palabra infinita de Fibonacci es . ^[8] Es el índice más pequeño (o exponente crítico) entre todas las palabras de Sturm. ${\displaystyle 2+\varphi \approx 3.618}$
• La palabra Fibonacci infinita se cita a menudo como el peor caso para los algoritmos que detectan repeticiones en una cadena.
• La palabra infinita de Fibonacci es una palabra mórfica , generada en {0,1}* por el endomorfismo 0 → 01, 1 → 0. ^[9]
• El n- ésimo elemento de una palabra de Fibonacci, , es 1 si la representación Zeckendorf (la suma de un conjunto específico de números de Fibonacci) de n incluye un 1, y 0 si no incluye un 1. ${\displaystyle s_{n}}$
• Los dígitos de la palabra de Fibonacci se pueden obtener tomando la secuencia de números fibinarios módulo 2. ^[10]

Aplicaciones

Las construcciones basadas en Fibonacci se utilizan actualmente para modelar sistemas físicos con orden aperiódico como los cuasicristales , y en este contexto la palabra Fibonacci también se denomina cuasicristal de Fibonacci . ^[11] Se han utilizado técnicas de crecimiento de cristales para hacer crecer cristales en capas de Fibonacci y estudiar sus propiedades de dispersión de luz. ^[12]

Véase también

• Matemáticas y arte
• Palabra de Tribonacci

Notas

1. Ramírez, Rubiano y De Castro (2014).
2. Berstel (1986), pág. 13.
3. Adamczewski y Bugeaud (2010).
4. Sloane, N. J. A. (ed.), "Secuencia A003849", La enciclopedia en línea de secuencias de números enteros , OEIS Foundation
5. Lothaire (2011), pág. 47.
6. Para las subpalabras que aparecen, véase Berstel (1986), págs. 14 y 18 (usando las letras a y b en lugar de los dígitos 0 y 1).
7. de Luca (1995).
8. Allouche y Shallit (2003), pág. 37.
9. Lothaire (2011), pág. 11.
10. Kimberling (2004).
11. Bombieri y Taylor (1986).
12. Dharma-wardana et al. (1987).

Referencias

• Adamczewski, Boris; Bugeaud, Yann (2010), "8. Trascendencia y aproximación diofántica", en Berthé, Valérie ; Rigo, Michael (eds.), Combinatoria, autómatas y teoría de números , Enciclopedia de matemáticas y sus aplicaciones, vol. 135, Cambridge: Cambridge University Press , p. 443, ISBN 978-0-521-51597-9, Zbl1271.11073 ​.
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Secuencias automáticas: teoría, aplicaciones, generalizaciones , Cambridge University Press , ISBN 978-0-521-82332-6.
• Berstel, Jean (1986), "Palabras de Fibonacci: una encuesta" (PDF) , en Rozenberg, G.; Salomaa, A. (eds.), El libro de L , Springer, págs. 13-27, doi :10.1007/978-3-642-95486-3_2, ISBN 9783642954863
• Bombieri, E. ; Taylor, JE (1986), "¿Qué distribuciones de materia se difractan? Una investigación inicial" (PDF) , Le Journal de Physique , 47 (C3): 19–28, doi :10.1051/jphyscol:1986303, MR  0866320, S2CID  54194304.
• Dharma-wardana, MWC; MacDonald, AH; Lockwood, DJ; Baribeau, J.-M.; Houghton, DC (1987), "Dispersión Raman en superredes de Fibonacci", Physical Review Letters , 58 (17): 1761–1765, Bibcode :1987PhRvL..58.1761D, doi :10.1103/physrevlett.58.1761, PMID  10034529.
• Kimberling, Clark (2004), "Ordenar palabras y conjuntos de números: el caso de Fibonacci", en Howard, Frederic T. (ed.), Aplicaciones de los números de Fibonacci, Volumen 9: Actas de la Décima Conferencia Internacional de Investigación sobre los números de Fibonacci y sus aplicaciones , Dordrecht: Kluwer Academic Publishers, págs. 137-144, doi :10.1007/978-0-306-48517-6_14, ISBN 978-90-481-6545-2, Sr.  2076798.
• Lothaire, M. (1997), Combinatoria de palabras , Enciclopedia de matemáticas y sus aplicaciones, vol. 17 (2.ª ed.), Cambridge University Press , ISBN 0-521-59924-5.
• Lothaire, M. (2011), Combinatoria algebraica en palabras , Enciclopedia de matemáticas y sus aplicaciones, vol. 90, Cambridge University Press , ISBN 978-0-521-18071-9. Reimpresión de la edición de tapa dura de 2002.
• de Luca, Aldo (1995), "Una propiedad de división de la palabra de Fibonacci", Information Processing Letters , 54 (6): 307–312, doi :10.1016/0020-0190(95)00067-M.
• Mignosi, F.; Pirillo, G. (1992), "Repeticiones en la palabra infinita de Fibonacci", Informatique Théorique et Application , 26 (3): 199–204, doi : 10.1051/ita/1992260301991.
• Ramírez, José L.; Rubiano, Gustavo N.; De Castro, Rodrigo (2014), "Una generalización del fractal de Fibonacci y del copo de nieve de Fibonacci", Theoretical Computer Science , 528 : 40–56, arXiv : 1212.1368 , doi : 10.1016/j.tcs.2014.02.003, MR  3175078, S2CID  17193119.

Enlaces externos

• Una descripción detallada y accesible, en el sitio de Ron Knott
• Weisstein, Eric W. , "Secuencia de conejo", MathWorld
• Palabra de Fibonacci (primeros 200.000 bits) en YouTube