Una palabra de Fibonacci es una secuencia específica de dígitos binarios (o símbolos de cualquier alfabeto de dos letras ). La palabra Fibonacci se forma por concatenación repetida de la misma manera que los números de Fibonacci se forman por suma repetida.
Es un ejemplo paradigmático de una palabra sturmiana y específicamente, una palabra mórfica .
El nombre "palabra de Fibonacci" también se ha utilizado para referirse a los miembros de un lenguaje formal L que consta de cadenas de ceros y unos sin dos repetidos. Cualquier prefijo de la palabra 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
Dejar ser "0" y ser "01". Ahora (la concatenación de la secuencia anterior y la anterior).
La palabra infinita de Fibonacci es el límite , es decir, la secuencia infinita (única) que contiene cada , por finito , como prefijo.
La enumeración de elementos de la definición anterior produce:
0
01
010
01001
01001010
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 n- ésimo dígito de la palabra es dónde es la proporción áurea yes la función de piso (secuencia A003849 en la OEIS ). Como consecuencia, la palabra infinita de Fibonacci se puede caracterizar por una secuencia de corte de una línea de pendiente o . Vea la figura de arriba.
Reglas de sustitución
Otra forma de pasar 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 .
Alternativamente, uno puede imaginarse generando directamente toda la palabra infinita de Fibonacci mediante el siguiente proceso: comience con un cursor apuntando al dígito 0. Luego, en cada paso, si el cursor apunta a un 0, agregue 1, 0 al final de la palabra, y si el cursor apunta a un 1, agregue 0 al final de la palabra. En cualquier caso, complete 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 solo trivialmente, al intercambiar 0 por 1 y cambiar las posiciones en uno.
Una expresión de forma cerrada para la llamada secuencia de conejo:
El n- ésimo dígito de la palabra es dónde es la proporción áurea yes la función de piso .
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 con 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, el número de unos en S n es F n y el número de ceros en S n es F n + 1 .
Otras propiedades
- La palabra infinita de Fibonacci no es periódica ni, en última instancia, periódica.
- Las dos últimas letras de una palabra de Fibonacci son alternativamente "01" y "10".
- Suprimir las dos últimas letras de una palabra de Fibonacci, o prefijar el complemento de las dos últimas letras, crea un palíndromo . Ejemplo: 01= 0101001010 es un palíndromo. La densidad palindrómica de la palabra infinita de Fibonacci es entonces 1 / φ, donde φ es la proporción áurea : este es el valor más grande posible para palabras aperiódicas. [2]
- En la palabra infinita de Fibonacci, la proporción (número de letras) / (número de ceros) es φ, al igual que la proporción de ceros a unos.
- La palabra Fibonacci infinita es una secuencia equilibrada : tome dos factores de la misma longitud en cualquier parte de la palabra Fibonacci. La diferencia entre sus pesos Hamming (el número de apariciones de "1") nunca excede 1. [3]
- Las subpalabras 11 y 000 nunca aparecen.
- 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". Siendo también no periódica, es entonces de "complejidad mínima", y por lo tanto una palabra Sturmian , [4] con pendiente. La palabra infinita de Fibonacci es la palabra estándar generada por la secuencia directiva (1,1,1, ....).
- La palabra infinita de Fibonacci es recurrente; es decir, cada subpalabra aparece con una frecuencia infinita.
- Si es una subpalabra de la palabra infinita de Fibonacci, entonces también lo es su inversión, denotada .
- Si es una subpalabra de la palabra infinita de Fibonacci, entonces el período mínimo de es un número de Fibonacci.
- La concatenación de dos palabras sucesivas de Fibonacci es "casi conmutativa". y difieren solo por sus dos últimas letras.
- El número 0.010010100 ..., cuyos decimales se construyen 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 ):
- Las letras "0" se pueden encontrar en las posiciones dadas por los valores sucesivos de la secuencia Lower Wythoff (secuencia A000201 en la OEIS ):
- La distribución de puntos en el círculo unitario, colocados consecutivamente en el sentido de las agujas del reloj por el ángulo dorado , genera un patrón de dos longitudes en el círculo unitario. Aunque el proceso de generación anterior de la palabra Fibonacci no se corresponde directamente con la división sucesiva de segmentos circulares, 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, donde 0 corresponde a la distancia larga y 1 a la distancia corta.
- La palabra infinita de Fibonacci contiene repeticiones de 3 subpalabras idénticas sucesivas, pero ninguna de 4. El exponente crítico para la palabra infinita de Fibonacci es. [5] Es el índice más pequeño (o exponente crítico) entre todas las palabras sturmianas.
- La palabra infinita de Fibonacci se cita a menudo como el peor de los casos 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. [6]
- El n- ésimo elemento de una palabra Fibonacci,, es 1 si la representación de 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.
Aplicaciones
Las construcciones basadas en Fibonacci se utilizan actualmente para modelar sistemas físicos con un orden aperiódico como los cuasicristales , y en este contexto la palabra Fibonacci también se denomina cuasicristal de Fibonacci . [7] Se han utilizado técnicas de crecimiento de cristales para cultivar cristales en capas de Fibonacci y estudiar sus propiedades de dispersión de luz. [8]
Ver también
Notas
- ^ Ramírez, Rubiano y De Castro (2014) .
- ^ Adamczewski y Bugeaud (2010) .
- ^ Lothaire (2011) , p. 47.
- ↑ de Luca (1995) .
- ^ Allouche y Shallit (2003) , p. 37.
- ^ Lothaire (2011) , p. 11.
- ^ Bombieri y Taylor (1986) .
- ^ 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 , Encyclopedia of Mathematics and its Applications, 135 , Cambridge: Cambridge University Press , p. 443, ISBN 978-0-521-51597-9, Zbl 1271.11073.
- Allouche, Jean-Paul; Shallit, Jeffrey (2003), Secuencias automáticas: teoría, aplicaciones, generalizaciones , Cambridge University Press , ISBN 978-0-521-82332-6.
- Bombieri, E .; Taylor, JE (1986), "¿Qué distribuciones de materia difractan? Una investigación inicial", Le Journal de Physique , 47 (C3): 19-28, doi : 10.1051 / jphyscol: 1986303 , MR 0866320.
- Dharma-wardana, MWC; MacDonald, AH; Lockwood, DJ; Baribeau, J.-M .; Houghton, DC (1987), "Dispersión Raman en superredes de Fibonacci", Physical Review Letters , 58 : 1761-1765, doi : 10.1103 / physrevlett.58.1761 , PMID 10034529.
- Lothaire, M. (1997), Combinatoria en palabras , Enciclopedia de las matemáticas y sus aplicaciones, 17 (2a ed.), Cambridge University Press , ISBN 0-521-59924-5 CS1 maint: parámetro desalentado ( enlace ).
- Lothaire, M. (2011), Combinatoria algebraica en palabras , Enciclopedia de las matemáticas y sus aplicaciones, 90 , Cambridge University Press , ISBN 978-0-521-18071-9. Reimpresión de la tapa dura de 2002.
- de Luca, Aldo (1995), "A division property of the Fibonacci word", 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.
- Ramírez, José L .; Rubiano, Gustavo N .; De Castro, Rodrigo (2014), "A generalization of the Fibonacci word fractal and the Fibonacci snowflake", Theoretical Computer Science , 528 : 40–56, doi : 10.1016 / j.tcs.2014.02.003 , MR 3175078.
enlaces externos
- Una descripción detallada y accesible, en el sitio de Ron Knott
- Weisstein, Eric W. , "Secuencia de conejo" , MathWorld
- Fibonacci Word (primeros 200.000 bits) en YouTube