Fibonacci palabra

${\displaystyle S_{10}}$

${\displaystyle S_{17}}$

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

En matemáticas , más concretamente en combinatoria de palabras , una palabra de Fibonacci es una secuencia específica de dígitos binarios (o símbolos de cualquier alfabeto de dos letras ) formada por concatenación repetida , del mismo modo que los números de Fibonacci se forman por suma repetida.

Es un ejemplo paradigmático de una palabra de Sturm y, específicamente, de una palabra mórfica .

El término «palabra de Fibonacci» también se ha utilizado para referirse a los miembros de un lenguaje formal L compuesto por cadenas de ceros y unos sin repetición de dos unos. Cualquier prefijo de la palabra de Fibonacci específica pertenece a L , al igual que muchas otras cadenas. L tiene un número de Fibonacci de miembros de cada longitud posible.

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

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

Enumerar los 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 de Fibonacci infinita 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, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 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 el OEIS )

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

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 único símbolo 0 en S _{n +1} .

Como alternativa, se puede generar directamente la palabra de Fibonacci completa mediante el siguiente proceso: comenzar con un cursor apuntando al dígito 0. Luego, en cada paso, si el cursor apunta a un 0, agregar 1, 0 al final de la palabra; y si apunta a un 1, agregar 0 al final. En ambos casos, 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, se agrega un 1, y siempre que el cursor apunte a un 1, se agregan 0 y 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 de Fibonacci solo trivialmente, al intercambiar 0s por 1s y desplazar las posiciones en una unidad.

Una expresión de forma cerrada para la denominada secuencia del conejo:

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

La palabra está relacionada con la famosa secuencia del mismo nombre (la secuencia de Fibonacci ) en el sentido de que la suma de 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)-ésimo número de Fibonacci. Además, el número de 1s en S _n es F _n y el número de 0s en S _n es F _{n +1} .

• La palabra de Fibonacci infinita no es periódica y, en última instancia, no es periódica. ^{[ 2 ]}
• 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 anteponer el complemento de las dos últimas letras, crea un palíndromo . Ejemplo: 01 S ₄ = 0101001010 es un palíndromo. La densidad palíndroma de la palabra de Fibonacci infinita es, por lo tanto, 1/φ, donde φ es la proporción áurea : este es el mayor valor posible para palabras aperiódicas. ^{[ 3 ]}
• En la palabra de Fibonacci infinita, la razón (número de letras)/(número de ceros) es φ, al igual que la razón de ceros a unos. ^{[ 4 ]}
• La palabra de Fibonacci infinita es una secuencia equilibrada : tome 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 ocurrencias de "1") nunca excede 1. ^{[ 5 ]}
• Las subpalabras 11 y 000 nunca aparecen. ^{[ 6 ]}
• La función de complejidad de la palabra de Fibonacci infinita 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, tiene entonces una "complejidad mínima" y, por lo tanto, es una ^palabra de Sturm [ ^{7 ]} con pendiente${\displaystyle 1/\varphi }$. La palabra de Fibonacci infinita es la palabra estándar generada por la secuencia directiva (1,1,1,....).
• La palabra de Fibonacci infinita es recurrente; es decir, cada subpalabra aparece infinitamente a menudo.
• Si${\displaystyle u}$es una subpalabra de la palabra infinita de Fibonacci, entonces también lo es su reversión, denotada${\displaystyle u^{R}}$.
• Si${\displaystyle u}$es una subpalabra de la palabra infinita de Fibonacci, entonces el período más pequeño de${\displaystyle u}$es un número de Fibonacci.
• La concatenación de dos palabras sucesivas de Fibonacci es "casi conmutativa".${\displaystyle S_{n+1}=S_{n}S_{n-1}}$y${\displaystyle S_{n-1}S_{n}}$Se diferencian únicamente por sus dos últimas letras.
• El número 0,010010100..., cuyos dígitos se construyen con los dígitos de la palabra de Fibonacci infinita, es trascendental .
• Las letras "1" se pueden encontrar en las posiciones dadas por los valores sucesivos de la secuencia de 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 de Lower Wythoff (secuencia A000201 en la OEIS ) :${\displaystyle \lfloor n\varphi \rfloor }$
• La distribución de${\displaystyle n=F_{k}}$puntos en el círculo unitario , colocados consecutivamente en el sentido de las agujas del reloj según el ángulo áureo.${\displaystyle {\frac {2\pi }{\varphi ^{2}}}}$genera un patrón de dos longitudes${\displaystyle {\frac {2\pi }{\varphi ^{k-1}}},{\frac {2\pi }{\varphi ^{k}}}}$en el círculo unitario. Aunque el proceso generador anterior de la palabra Fibonacci no se corresponde directamente con la división sucesiva de segmentos de círculo, este patrón es${\displaystyle S_{k-1}}$Si el patrón comienza en el punto más cercano al primer punto en sentido horario, entonces 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. ^{[ 2 ]} El exponente crítico para la palabra de Fibonacci infinita es${\displaystyle 2+\varphi \approx 3.618}$. ^{[ 8 ]} Es el índice más pequeño (o exponente crítico) entre todas las palabras de Sturm.
• La palabra de Fibonacci infinita se cita a menudo como el peor caso para los algoritmos que detectan repeticiones en una cadena.
• La palabra de Fibonacci infinita es una palabra morfológica , generada en {0,1}* por el endomorfismo 0 → 01, 1 → 0. ^{[ 9 ]}
• El enésimo elemento de una palabra de Fibonacci,${\displaystyle s_{n}}$, 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.
• Los dígitos de la palabra de Fibonacci se pueden obtener tomando la secuencia de números fibinos módulo 2. ^{[ 10 ]}
• La palabra de Fibonacci infinita es esencialmente la única palabra binaria infinita que evita las potencias de 11, 000, 10101 y 4.

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 cultivar cristales estratificados de Fibonacci y estudiar sus propiedades de dispersión de la luz. ^{[ 12 ]}

• Matemáticas y arte
• Palabra de Tribonacci

• 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ág.  443, ISBN 978-0-521-51597-9, Zbl 1271.11073 .
• Allouche, Jean-Paul; Shallit, Jeffrey (2003), Automatic Sequences: Theory, Applications, Generalizations , Cambridge University Press , ISBN 978-0-521-82332-6.
• Berstel, Jean (1986), "Fibonacci Words – A Survey" (PDF) , en Rozenberg, G.; Salomaa, A. (eds.), The Book of L , Springer, pp. 13–27 , doi : 10.1007/978-3-642-95486-3_2 , ISBN  9783642954863
• Bombieri, E.; Taylor , JE (1986), "¿Qué distribuciones de materia 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, pp. 137–144 , doi : 10.1007/978-0-306-48517-6_14 , ISBN  978-90-481-6545-2, MR 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 sobre palabras , Enciclopedia de matemáticas y sus aplicaciones, vol.  90, Cambridge University Press , ISBN 978-0-521-18071-9Reimpresió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 palabras de Fibonacci y el 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  .

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