Palabra de Fibonacci

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.​

Caracterización mediante la secuencia de corte con una línea de pendiente $1/\varphi$ o $\varphi -1$, siendo $\varphi$ el número áureo

$S_{10}$

$S_{17}$

Fractales de la palabra de Fibonacci generados con la 10ª y la 17ª palabras de Fibonacci ​

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 formal L 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

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

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

La enumeración de elementos de la definición anterior produce:

$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, .. . (sucesión A003849 en OEIS)

Expresión de forma cerrada para dígitos individuales

El dígito n^ésimo de la palabra es $2+\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n+1}\right)\,\varphi }\right\rfloor$, donde $\varphi$ es el número áureo y $\left\lfloor x\right\rfloor$ 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 $1/\phi$ o $\phi -1$ (véase 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, 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,​ 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

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 una posición.

La siguiente es una expresión cerrada para la llamada secuencia de conejo:

El dígito n^ésimo de la palabra es $\left\lfloor {{n}\,\varphi }\right\rfloor -\left\lfloor {\left({n-1}\right)\,\varphi }\right\rfloor -1$, donde $\varphi$ es el número áureo y $\left\lfloor x\right\rfloor$ es la parte entera.

Discusión

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 S_n sea F_n + 2, el (n + 2) ésimo 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 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$S_{4}$ = 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.​
• 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.​
• 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,​ con pendiente $1/\phi ^{2}$. 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 $u$ es una subpalabra de la palabra infinita de Fibonacci, entonces también lo es su inversión, denotada como $u^{R}$.
• Si $u$ es una subpalabra de la palabra infinita de Fibonacci, entonces el período mínimo de $u$ es un número de Fibonacci.
• La concatenación de dos palabras de Fibonacci sucesivas es "casi conmutativa". $S_{n+1}=S_{n}S_{n-1}$ y $S_{n-1}S_{n}$ 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.​
• 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): $\lfloor n\phi ^{2}\rfloor$
• 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): $\lfloor n\phi \rfloor$
• La distribución de puntos $n=F_{k}$ en el círculo unitario, colocados consecutivamente en el sentido de las agujas del reloj por el ángulo dorado ${\frac {2\pi }{\phi ^{2}}}$, genera un patrón de dos longitudes en el círculo unitario tales que ${\frac {2\pi }{\phi ^{k-1}}},{\frac {2\pi }{\phi ^{k}}}$. 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 $S_{k-1}$ 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 $2+\phi \approx 3.618$.​ 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.​
• El elemento n^ésimo de una palabra de Fibonacci, $s_{n}$, 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​ módulo 2.​

Aplicaciones

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.​ 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.​

Véase también

• Matemáticas y arte
• Palabra tribonacci

Bibliografía

• 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, 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 ..
• Bombieri, E.; Taylor, J. E. (1986), «Which distributions of matter diffract? An initial investigation», Le Journal de Physique 47 (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 Letters 58 (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. (1997), Combinatorics on Words, Encyclopedia of Mathematics and Its Applications 17 (2nd edición), Cambridge University Press, ISBN 0-521-59924-5 ..
• Lothaire, M. (2011), Algebraic Combinatorics on Words, Encyclopedia of Mathematics and Its Applications 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), «Repetitions in the Fibonacci infinite word», 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), «A generalization of the Fibonacci word fractal and the Fibonacci snowflake», Theoretical Computer Science 528: 40-56, MR 3175078, arXiv:1212.1368, doi:10.1016/j.tcs.2014.02.003 ..

Enlaces externos

• Una descripción detallada y accesible, en Ron Knott sitio
• Weisstein, Eric W. «Rabbit Sequence». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Fibonacci Word (First 200,000 bits) en YouTube.

• Datos: Q749729