Palabra fibonacci

La palabra de Fibonacci es una secuencia de dígitos binarios (o símbolos de cualquier alfabeto de dos letras ). La palabra de Fibonacci se forma por concatenación repetida de la misma manera que los números de Fibonacci se forman por sumas repetidas.

La palabra Fibonacci es un ejemplo de libro de texto de la palabra Sturm .

El nombre "palabra de Fibonacci" también se usa para designar miembros del lenguaje formal L , que contiene cadenas de ceros y unos sin los adyacentes. Cualquier parte de una palabra de Fibonacci en particular pertenece a L , pero hay muchas otras cadenas en el lenguaje. En L , el número de cadenas de cada longitud posible es un número de Fibonacci.

Definición

Que sea igual a "0" e igual a "01". Ahora (concatenación del miembro anterior y el miembro anterior). $S_{0}$ $S_{1}$ ${\displaystyle S_{n}=S_{n-1}S_{n-2))$

La palabra infinita de Fibonacci es el límite . ${\ Displaystyle S_ {\ infinito}}$

Enumerar los miembros de la secuencia de la definición anterior da:

$S_{0}$ 0

$S_{1}$ 01

$S_{2}$ 010

$S_{3}$ 01001

$S_4$ 01001010

$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 OEIS )

Expresión de forma cerrada para dígitos específicos

El dígito con el número n de la palabra es igual a , donde es la proporción áurea , y es la función "piso" ("piso"). $2+\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$ $\varphi$ ${\ estilo de visualización \ izquierda \ lpiso x \ derecho \ r piso}$

Reglas de sustitución

Otra forma de pasar de S n a S n + 1 es reemplazar cada 0 en S n con un par de 0, 1 y reemplazar cada 1 con un 0.

Alternativamente, uno puede imaginar generar la palabra infinita completa de Fibonacci con el siguiente proceso. Empezamos con el carácter 0, colocamos el cursor sobre él. En cada paso, si el cursor apunta a 0, agregue 1 y 0 al final de la palabra, y si el cursor apunta a 1, agregue 0 al final de la palabra. En cualquier caso, el paso se completa moviéndose una posición a la derecha.

Una palabra infinita similar, a veces llamada cadena dorada o secuencia de conejo , se forma mediante un proceso infinito similar, pero la regla de sustitución es diferente: si el cursor apunta a 0, agregue 1, y si apunta a 1, agregue 0, 1. La secuencia resultante comienza con

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 de Fibonacci trivialmente: los ceros se reemplazan por unos y la secuencia completa se desplaza por uno.

La expresión de forma cerrada para la cuerda dorada es:

El dígito con el número n de la palabra es igual a , donde es la proporción áurea , y es la función “piso” . $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$ $\varphi$ ${\ estilo de visualización \ izquierda \ lpiso x \ derecho \ r piso}$

Discusión

La palabra está relacionada con la famosa secuencia del mismo nombre ( la secuencia de Fibonacci ) en la que la suma de números enteros en la definición inductiva se reemplaza por la concatenación de cadenas. Esto da como resultado 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 y finalmente no es periódica [1] .
Los dos últimos dígitos de la palabra de Fibonacci son "01" o "10".
Quitar las dos últimas letras de la palabra de Fibonacci o agregar las dos últimas letras al comienzo del complemento crea un palíndromo . Ejemplo: 01 =0101001010 es un palíndromo. La densidad palindrómica de una palabra infinita de Fibonacci es 1/φ, donde φ es la proporción áurea . Este es el mayor valor posible para palabras no periódicas [2] . $S_4$
En una palabra infinita de Fibonacci, la razón (número de dígitos)/(número de ceros) es igual a φ, al igual que la razón del número de ceros al número de unos.
La palabra infinita de Fibonacci es una secuencia equilibrada . Tome dos subcadenas de la misma longitud en cualquier parte de la palabra de Fibonacci. La diferencia entre sus pesos Hamming (número de unidades) nunca supera 1 [3] .
Las subpalabras 11 y 000 nunca ocurren.
La función de complejidad una palabra infinita de Fibonacci es n + 1: contiene n + 1 subpalabras distintas de longitud n . Ejemplo: Hay 4 subpalabras diferentes de longitud 3: "001", "010", "100" y "101". Al ser una secuencia no periódica, la palabra tiene "complejidad mínima", y por lo tanto es una palabra Sturm [4] con pendiente. Una palabra infinita de Fibonacci es una palabra estándar formada por la secuencia directiva (1,1,1,….). ${\ estilo de visualización 1/\ phi ^ {2}}$
La palabra infinita de Fibonacci es recurrente. Es decir, cualquier subpalabra ocurre infinitamente a menudo.
Si es una subpalabra de una palabra infinita de Fibonacci, entonces la subpalabra es su inversa, denotada por . $tu$ ${\ estilo de visualización u^ {R}}$
Si es una subpalabra de una palabra infinita de Fibonacci, entonces el período más pequeño es un número de Fibonacci. $tu$ $tu$
La concatenación de dos secuencias de palabras de Fibonacci es "casi conmutativa". y difieren solo en las dos últimas letras. ${\displaystyle S_{n+1}=S_{n}S_{n-1))$ ${\ Displaystyle S_ {n-1} S_ {n}}$
Como consecuencia, un número infinito de Fibonacci puede describirse mediante una secuencia de secciones de una línea recta con pendiente o . Vea la imagen de arriba. $\fi$ ${\ estilo de visualización \ phi-1}$
El número 0,010010100…, cuyas cifras decimales son las cifras de la infinita palabra de Fibonacci, es trascendental .
Las letras "1" se pueden encontrar en posiciones dadas por valores sucesivos de la secuencia superior de Wythoff ( OEIS A001950): $\lpiso n\fi ^{2}\rpiso$
Las letras "0" se pueden encontrar en posiciones dadas por valores sucesivos de la secuencia de Wythoff inferior (OEIS A000201): ${\ estilo de visualización \ lpiso n \ phi \ rpiso}$
Una distribución de puntos en el círculo unitario , colocados secuencialmente en el sentido de las agujas del reloj en el ángulo áureo , forma un patrón de dos longitudes en el círculo unitario. Aunque el proceso de formación de palabras de Fibonacci descrito anteriormente no corresponde directamente a la división secuencial de segmentos circulares, este patrón es igual a cuando se comienza desde el punto más cercano en el sentido de las agujas del reloj, con 0 correspondiente a una distancia larga y 1 correspondiente a una distancia corta. ${\ Displaystyle n = F_ {k}}$ ${\ estilo de visualización {\ frac {2 \ pi} {\ phi ^ {2}}}}$ ${\displaystyle {\frac {2\pi }{\phi ^{k-1))},{\frac {2\pi }{\phi ^{k))))$ ${\ Displaystyle S_ {k-1}}$
Una palabra infinita de Fibonacci puede contener 3 subpalabras idénticas consecutivas, pero nunca 4 de tales subpalabras. El índice crítico para una palabra infinita de Fibonacci es igual a las repeticiones [5] . Este es el índice más pequeño (o índice crítico) entre todas las palabras de Sturm. ${\ estilo de visualización 2 + \ phi = 3,618}$
La palabra infinita de Fibonacci se cita a menudo como el peor de los casos para los algoritmos de detección de repetición de cadenas
Una palabra infinita de Fibonacci es una palabra mórfica formada a partir de {0,1}* por el endomorfismo 0 → 01, 1 → 0 [6] .

Aplicaciones

Las construcciones de palabras de Fibonacci se utilizan para modelar sistemas físicos con un orden no periódico, como los cuasicristales , y para estudiar las propiedades de dispersión de la luz de los cristales con capas de Fibonacci [7] .

Véase también

Matemáticas y Bellas Artes
La palabra tribonacci

Notas

↑ Una secuencia se llama finalmente periódica con parámetros si la condición para , donde y son números enteros, , . El menor de estos números se llama período de la sucesión. Una secuencia se llama -periódico si ( Lipnitsky y Chesalin 2008 , p. 27). $v=(v_{0},v_{1},\ldots)$ ${\ estilo de visualización (T, \ tau)}$ $v_{k+T}=v_{k}$ $k\geqslant\tau$ $T$ $\tau$ $T>0$ ${\ estilo de visualización \ tau> 0}$ $T$ $T$ ${\ estilo de visualización \ tau = 0}$
↑ Adamczewski, Bugeaud, 2010 , pág. 443.
↑ Lotario, 2011 , pág. 47.
↑ de Lucas (1995) .
↑ Allouche, Shallit, 2003 , pág. 37.
↑ Lotario, 2011 , pág. once.
↑ Dharma-wardana, MacDonald, Lockwood, Baribeau, Houghton, 1987 .

Literatura

Jean-Paul Allouche, Jeffrey Shallit. Secuencias Automáticas: Teoría, Aplicaciones, Generalizaciones. - Prensa de la Universidad de Cambridge , 2003. - ISBN 978-0-521-82332-6 .
Dharma-wardana MWC, MacDonald AH, Lockwood DJ, Baribeau J.-M., Houghton DC Raman dispersión en superredes de Fibonacci // Physical Review Letters . - 1987. - T. 58 . - S. 1761-1765 . -doi : 10.1103/ physrevlett.58.1761 .
Lothaire M. Combinatoria en palabras. — 2do. - Cambridge University Press , 1997. - V. 17. - (Enciclopedia de las Matemáticas y sus Aplicaciones). - ISBN 0-521-59924-5 .
Lothaire M. Combinatoria algebraica de palabras. - Cambridge University Press , 2011. - V. 90. - (Enciclopedia de las Matemáticas y sus Aplicaciones). . Reimpresión de la tapa dura de 2002.
Aldo de Lucas. Una propiedad de división de la palabra de Fibonacci // Letras de procesamiento de información . - 1995. - T. 54 , núm. 6 _ — S. 307–312 . - doi : 10.1016/0020-0190(95)00067-M .
Mignosi F., Pirillo G. Repeticiones en la palabra infinita de Fibonacci // Informatique théorique et application. - 1992. - T. 26 , núm. 3 . — S. 199–204 .
Boris Adamczewski, Yann Bugeaud. Capítulo 8. Trascendencia y aproximación diofántica // Combinatoria, autómatas y teoría de números / Valérie Berthé, Michael Rigo. - Cambridge: Cambridge University Press , 2010. - V. 135. - P. 443. - (Enciclopedia de las Matemáticas y sus Aplicaciones). - ISBN 978-0-521-51597-9 .
Lipnitsky V. A., Chesalin N. V. Códigos lineales y secuencias de códigos: método de libro de texto. Manual para estudiantes mech.-mat. falso BGU . - Minsk: BGU, 2008.

Enlaces

Una descripción detallada y accesible, en el sitio de Ron Knott
Weisstein, Eric W. Rabbit Sequence (inglés) en el sitio web de Wolfram MathWorld .
vídeo de YouTube _