Una palabra de Fibonacci es una secuencia específica de dígitos binaria (o de dos símbolos distintos o dos letras de cualquier alfabeto). Está formada por concatenación repetida, de la misma manera que la sucesión de Fibonacci se forma mediante la suma sucesiva de los dos términos anteriores.[2]
Es un ejemplo paradigmático de una palabra sturmiana, y en concreto, de una palabra mórfica.
El nombre "palabra de Fibonacci" también se ha utilizado para referirse a los miembros de un lenguaje formalL que consta de cadenas de ceros y unos sin unos sucesivos. Cualquier prefijo de la palabra de Fibonacci específica pertenece a L, pero también lo hacen muchas otras cadenas. L posee un número de Fibonacci de miembros de cada longitud posible.
Definición
editar
Sea igual a "0" y igual a "01". Entonces, (la concatenación de la secuencia anterior y la anterior a esta).
La palabra infinita de Fibonacci es el límite , es decir, la secuencia infinita (única) que contiene cada , para 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:
Expresión de forma cerrada para dígitos individuales
editar
El dígito nésimo de la palabra es , donde es el número áureo y es la parte entera (sucesión A003849 en OEIS). Como consecuencia, la palabra infinita de Fibonacci se puede caracterizar por una secuencia de corte de una línea de pendiente o (véase la figura de arriba).
Reglas de sustitución
editar
Otra forma de pasar de Sn a Sn + 1 es reemplazar cada símbolo 0 en Sn con el par de símbolos consecutivos 0, 1 en Sn + 1, y reemplazar cada símbolo 1 en Sn con el símbolo único 0 en Sn + 1.
Alternativamente, puede imaginarse la generación directa de toda la palabra infinita de Fibonacci mediante el siguiente proceso: comiéncese con un cursor apuntando al dígito 0. Luego, a cada paso, si el cursor apunta a un 0, agregar la pareja 1, 0 al final de la palabra, y si el cursor apunta a un 1, agregar un 0 al final de la palabra. En cualquier caso, el ciclo se continúa el moviendo el cursor una posición hacia la derecha.
Una palabra infinita similar, a veces llamada secuencia del conejo,[3] se genera mediante un proceso infinito similar con una regla de reemplazo diferente: siempre que el cursor apunte a un 0, agregar un 1, y siempre que el cursor apunte a un 1, agregar la pareja 0, 1. La secuencia resultante comienza con la forma
La palabra está relacionada con la famosa secuencia del mismo nombre (la sucesión de Fibonacci) en el sentido de que la suma de números enteros en forma recursiva se reemplaza por la concatenación de cadenas. Esto hace que la longitud de Sn sea Fn + 2, el (n + 2) ésimo número de Fibonacci. Además, el número de unos en Sn es Fn y el número de ceros en Sn es Fn + 1.
Otras propiedades
editar
La palabra infinita de Fibonacci no es periódica, y tampoco en última instancia
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. Por ejemplo: 01 = 0101001010 es un palíndromo. El palíndromo de la palabra infinita de Fibonacci es entonces 1/φ, donde φ es el número áureo: este es el valor más grande posible para palabras aperiódicas.[4]
En la palabra infinita de Fibonacci, la razón (número de letras)/(número de ceros) es φ, al igual que la razón de ceros a unos.
La palabra de Fibonacci infinita es una secuencia equilibrada: si se toman dos factores de la misma longitud en cualquier lugar de la palabra de Fibonacci, la diferencia entre sus pesos de Hamming (el número de apariciones de "1") nunca excede 1.[5]
Las subpalabras 11 y 000 nunca aparecen.
La función 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 sturmiana,[6] 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;[7] 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 como .
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 de Fibonacci sucesivas es "casi conmutativa". y solo se diferencian 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 transcendente.[8]
Las letras "1" se pueden encontrar en las posiciones dadas por los valores sucesivos de la secuencia de Wythoff superior (sucesión A001950 en OEIS):
Las letras "0" se pueden encontrar en las posiciones dadas por los valores sucesivos de la secuencia de Wythoff inferior (sucesión A000201 en 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 tales que . Aunque el proceso de generación anterior de la palabra de Fibonacci no corresponde directamente a 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 de Fibonacci infinita contiene repeticiones de 3 subpalabras idénticas sucesivas, pero ninguna de 4. El exponente crítico de la palabra de Fibonacci infinita es .[9] Es el índice más pequeño (o exponente crítico) entre todas las palabras sturmianas.
La palabra infinita de Fibonacci a menudo se cita como peor caso para 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.[10]
El elemento nésimo de una palabra de Fibonacci, , es 1 si su 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.
Los dígitos de la palabra de Fibonacci se pueden obtener tomando la secuencia de números fibbinarios[11] módulo 2.[12]
Aplicaciones
editar
Las construcciones basadas en el procedimiento de Fibonacci se utilizan actualmente para modelar sistemas físicos con un orden aperiódico como los cuasicristales, y en este contexto la palabra de Fibonacci también se denomina cuasicristal de Fibonacci.[13] Se han utilizado técnicas de crecimiento de cristales para cultivar cristales en capas de Fibonacci y estudiar sus propiedades de dispersión de la luz.[14]
↑Applications of Fibonacci Numbers: Proceedings of ‘The Fifth International Conference on Fibonacci Numbers and Their Applications’, The University of St. Andrews, Scotland, July 20—July 24, 1992. Springer Science & Business Media. 2012. pp. 114 de 625. ISBN9789401120586. Consultado el 3 de enero de 2022.
↑M.R. Schroeder (2005). Number Theory in Science and Communication: With Applications in Cryptography, Physics, Digital Information, Computing, and Self-Similarity. Springer Science & Business Media. pp. 320 de 367. ISBN9783540265962. Consultado el 3 de enero de 2022.
↑Fabien Durand, Dominique Perrin (2022). Dimension Groups and Dynamical Systems. Cambridge University Press. pp. 21 de 760. ISBN9781108838689. Consultado el 3 de enero de 2022.
↑Gheorghe Paeaun, Grzegorz Rozenberg, Arto Salomaa (2004). Current Trends in Theoretical Computer Science: The Challenge of the New Century, Volumen 2. World Scientific. p. 663. ISBN9789812387837. Consultado el 3 de enero de 2022.
↑Gems in Experimental Mathematics: AMS Special Session on Experimental Mathematics, January 5, 2009, Washington. American Mathematical Soc. 2010. pp. 101 de 413. ISBN9780821848692. Consultado el 3 de enero de 2022.
Adamczewski, Boris; Bugeaud, Yann (2010), «8. Transcendence and diophantine approximation», en Berthé, Valérie; Rigo, Michael, eds., Combinatorics, automata, and number theory, Encyclopedia of Mathematics and its Applications 135, Cambridge: Cambridge University Press, p. 443, ISBN978-0-521-51597-9, Zbl 1271.11073..
Bombieri, E.; Taylor, J. E. (1986), «Which distributions of matter diffract? An initial investigation», Le Journal de Physique47 (C3): 19-28, MR 866320, doi:10.1051/jphyscol:1986303..
Dharma-wardana, M. W. C.; MacDonald, A. H.; Lockwood, D. J.; Baribeau, J.-M.; Houghton, D. C. (1987), «Raman scattering in Fibonacci superlattices», Physical Review Letters58 (17): 1761-1765, PMID 10034529, doi:10.1103/physrevlett.58.1761..
Kimberling, Clark (2004), «Ordering words and sets of numbers: the Fibonacci case», en Howard, Frederic T., ed., Applications of Fibonacci Numbers, Volume 9: Proceedings of The Tenth International Research Conference on Fibonacci Numbers and Their Applications, Dordrecht: Kluwer Academic Publishers, pp. 137-144, MR 2076798, doi:10.1007/978-0-306-48517-6_14..
Lothaire, M. (2011), Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications 90, Cambridge University Press, ISBN978-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 Letters54 (6): 307-312, doi:10.1016/0020-0190(95)00067-M..
Mignosi, F.; Pirillo, G. (1992), «Repetitions in the Fibonacci infinite word», Informatique théorique et application26 (3): 199-204, doi:10.1051/ita/1992260301991..
Ramírez, José L.; Rubiano, Gustavo N.; De Castro, Rodrigo (2014), «A generalization of the Fibonacci word fractal and the Fibonacci snowflake», Theoretical Computer Science528: 40-56, MR 3175078, arXiv:1212.1368, doi:10.1016/j.tcs.2014.02.003..
Enlaces externos
editar
Una descripción detallada y accesible, en Ron Knott sitio