palabra fibonacci

Secuencia binaria de la recurrencia de Fibonacci

Caracterización por una secuencia de corte con línea de pendiente o , con la proporción áurea . ${\displaystyle 1/\varphi }$ ${\displaystyle \varphi -1}$ ${\displaystyle \varphi }$

Curvas de Fibonacci hechas a partir de las palabras de Fibonacci 10.ª y 17.ª ^[1]

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

Se trata de un ejemplo paradigmático de palabra sturmiana y en concreto, de 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 unos 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

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

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

La enumeración de 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 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 en forma cerrada para dígitos individuales

El enésimo ^dígito de la palabra es donde está la proporción áurea y es la función suelo (secuencia A003849 en la OEIS ). Como consecuencia, la palabra infinita de Fibonacci se puede caracterizar por una secuencia cortante de una línea de pendiente o . Vea la figura de arriba. ${\displaystyle 2+\lfloor n\varphi \rfloor -\lfloor (n+1)\varphi \rfloor }$ ${\displaystyle \varphi }$ ${\displaystyle \lfloor \,\ \rfloor }$ ${\displaystyle 1/\varphi }$ ${\displaystyle \varphi -1}$

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 _{norte  +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 hacia la derecha.

Una palabra infinita similar, a veces llamada secuencia de 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 de Fibonacci sólo trivialmente, al intercambiar 0 por 1 y cambiar las posiciones en uno.

Una expresión en forma cerrada para la llamada secuencia del conejo:

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

Discusión

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

Otras propiedades

• La palabra infinita de Fibonacci no es periódica ni, en última instancia, periódica. ^{[ cita necesaria ]}
• 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 palindrómica de la palabra infinita de Fibonacci es, por tanto, 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. ^{[ cita necesaria ]}
• La palabra infinita de Fibonacci es una secuencia equilibrada : tome dos factores de la misma longitud en cualquier parte de la palabra de 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. ^{[ cita necesaria ]}
• 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". Al ser también no periódico, es entonces de "complejidad mínima", y de ahí una palabra sturmiana , ^[4] con pendiente . La palabra infinita de Fibonacci es la palabra estándar generada por la secuencia directiva (1,1,1,....). ${\displaystyle 1/\varphi }$
• 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 . ${\displaystyle u}$ ${\displaystyle u^{R}}$
• Si es una subpalabra de la palabra infinita de Fibonacci, entonces el período mínimo es un número de Fibonacci. ${\displaystyle u}$ ${\displaystyle u}$
• La concatenación de dos palabras sucesivas de Fibonacci es "casi conmutativa". y se diferencian sólo por sus dos últimas letras. ${\displaystyle S_{n+1}=S_{n}S_{n-1}}$ ${\displaystyle S_{n-1}S_{n}}$
• El número 0,010010100..., cuyas cifras se construyen con las cifras 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 el OEIS ): ${\displaystyle \lfloor n\varphi ^{2}\rfloor }$
• Las letras "0" se pueden encontrar en las posiciones dadas por los valores sucesivos de la secuencia Lower Wythoff (secuencia A000201 en la OEIS ): ${\displaystyle \lfloor n\varphi \rfloor }$
• La distribución de puntos en el círculo unitario , colocados consecutivamente en el sentido de las agujas del reloj por el ángulo áureo , genera un patrón de dos longitudes en el círculo unitario. Aunque el proceso de generación de la palabra Fibonacci anterior 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 corta distancia. ${\displaystyle n=F_{k}}$ ${\displaystyle {\frac {2\pi }{\varphi ^{2}}}}$ ${\displaystyle {\frac {2\pi }{\varphi ^{k-1}}},{\frac {2\pi }{\varphi ^{k}}}}$ ${\displaystyle S_{k-1}}$
• La palabra infinita de Fibonacci contiene repeticiones de 3 subpalabras idénticas sucesivas, pero ninguna de 4. El exponente crítico de la palabra infinita de Fibonacci es . ^[5] Es el índice más pequeño (o exponente crítico) entre todas las palabras de Sturmian. ${\displaystyle 2+\varphi \approx 3.618}$
• La palabra infinita de Fibonacci se cita a menudo como el peor caso 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 enésimo elemento de una palabra de 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. ${\displaystyle s_{n}}$
• Los dígitos de la palabra Fibonacci se pueden obtener tomando la secuencia de números fibbinarios módulo 2. ^[7]

Aplicaciones

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 . ^[8] Se han utilizado técnicas de crecimiento de cristales para hacer crecer cristales en capas de Fibonacci y estudiar sus propiedades de dispersión de luz. ^[9]

Ver también

• Matemáticas y arte.
• palabra tribonacci

Notas

1. Ramírez, Rubiano y De Castro (2014).
2. Adamczewski y Bugeaud (2010).
3. Lotario (2011), pág. 47.
4. de Luca (1995).
5. Allouche y Shallit (2003), pág. 37.
6. Lotario (2011), pág. 11.
7. Kimberling (2004).
8. Bombieri y Taylor (1986).
9. 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 , 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), 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 se 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, CMM; 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 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 Números de Fibonacci y Sus aplicaciones , Dordrecht: Kluwer Academic Publishers, págs. 137–144, doi :10.1007/978-0-306-48517-6_14, MR  2076798.
• Lothaire, M. (1997), Combinatoria de palabras , Enciclopedia de las matemáticas y sus aplicaciones, vol. 17 (2ª ed.), Cambridge University Press , ISBN 0-521-59924-5.
• Lothaire, M. (2011), Combinatoria algebraica de palabras , Enciclopedia de las matemáticas y sus aplicaciones, vol. 90, Prensa de la Universidad de Cambridge , ISBN 978-0-521-18071-9. Reimpresión del libro de tapa dura de 2002.
• de Luca, Aldo (1995), "Una propiedad de división de la palabra de Fibonacci", Cartas de procesamiento de información , 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 la palabra Fibonacci y el copo de nieve de Fibonacci", Informática teórica , 528 : 40–56, arXiv : 1212.1368 , doi : 10.1016/j.tcs.2014.02.003, MR  3175078 , S2CID  17193119.

enlaces externos

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