Números cuya representación binaria no contiene dos unos consecutivos
En matemáticas , los números fibbinarios son los números cuya representación binaria no contiene dos consecutivos. Es decir, son sumas de potencias de dos distintas y no consecutivas . [1] [2]
Relación con los números binarios y de Fibonacci
Los números fibbinarios recibieron su nombre de Marc LeBrun, porque combinan ciertas propiedades de los números binarios y los números de Fibonacci : [1]
- El número de números fibbinarios menores que cualquier potencia de dos dada es un número de Fibonacci. Por ejemplo, hay 13 números fibinarios menores que 32, los números 0, 1, 2, 4, 5, 8, 9, 10, 16, 17, 18, 20 y 21. [1]
- La condición de no tener dos unos consecutivos, utilizada en binario para definir los números fibbinarios, es la misma condición utilizada en la representación Zeckendorf de cualquier número como una suma de números de Fibonacci no consecutivos. [1]
- El enésimo número fibinario (contando 0 como el número 0) se puede calcular expresando en su representación Zeckendorf y reinterpretando la secuencia binaria resultante como la representación binaria de un número. [1] Por ejemplo, la representación de Zeckendorf de 19 es 101001 (donde los 1 marcan las posiciones de los números de Fibonacci utilizados en la expansión 19 = 13 + 5 + 1 ), la secuencia binaria 101001, interpretada como un número binario, representa 41 = 32 + 8 + 1 , y el decimonoveno número fibinario es 41.
![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- El enésimo número fibinario (nuevamente, contando 0 como 0) es par o impar si y sólo si el valor enésimo en la palabra de Fibonacci es 0 o 1, respectivamente. [3]
![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle n}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Propiedades
Debido a que la propiedad de no tener dos consecutivos define un lenguaje regular , las representaciones binarias de los números fibinarios pueden ser reconocidas por un autómata finito , lo que significa que los números fibinarios forman un conjunto de 2 automáticos . [4]
Los números fibbinarios incluyen la secuencia Moser-de Bruijn , sumas de distintas potencias de cuatro. Así como los números fibbinarios se pueden formar reinterpretando las representaciones de Zeckendorff como binarias, la secuencia Moser-de Bruijn se puede formar reinterpretando las representaciones binarias como cuaternarias. [5]
Un número es fibinario si y sólo si el coeficiente binomial es impar. [1] De manera relacionada, es fibinario si y solo si el número de Stirling central del segundo tipo es impar. [6]
![{\displaystyle {\tbinom {3n}{n}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle \textstyle \left\{{2n \atop n}\right\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Cada número fibinario toma una de las dos formas o , donde es otro número fibinario. [3] [7]
Correspondientemente, la serie de potencias cuyos exponentes son números fibinarios,
obedece a la ecuación funcional [2]![{\ Displaystyle f_ {i}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 2f_{j}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 4f_{j}+1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\ Displaystyle f_ {j}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B(x)=1+x+x^{2}+x^{4}+x^{5}+x^{8}+\cdots,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle B(x)=xB(x^{4})+B(x^{2}).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Madritsch y Wagner (2010) proporcionan fórmulas asintóticas para el número de particiones enteras en las que todas las partes son fibbinarias. [7]
Si un gráfico de hipercubo de dimensión está indexado por números enteros de 0 a , de modo que dos vértices son adyacentes cuando sus índices tienen representaciones binarias con distancia de Hamming uno, entonces el subconjunto de vértices indexados por los números fibbinarios forma un cubo de Fibonacci como su subgrafo inducido . [8]![{\displaystyle Q_{d}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle d}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle 2^{d}-1}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Todo número tiene un múltiplo fibinario. Por ejemplo, 15 no es fibinario, pero multiplicarlo por 11 produce 165 (10100101 2 ), que sí lo es. [9]
Referencias
- ^ abcdef Sloane, N. J. A. (ed.), "Secuencia A003714 (números fibbinarios)", La enciclopedia en línea de secuencias enteras , Fundación OEIS
- ^ ab Arndt, Jörg (2011), Asuntos computacionales: ideas, algoritmos, código fuente (PDF) , Springer, págs.62, 755–756.
- ^ ab 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 Fibonacci Números y sus aplicaciones , Dordrecht: Kluwer Academic Publishers, págs. 137–144, doi :10.1007/978-0-306-48517-6_14, MR 2076798
- ^ Allouche, JP; Shalit, J .; Skordev, G. (2005), "Conjuntos autogeneradores, números enteros con bloques faltantes y sustituciones", Matemáticas discretas , 292 (1–3): 1–15, doi : 10.1016/j.disc.2004.12.004 , SEÑOR 2131083
- ^ Sloane, N. J. A. (ed.), "Secuencia A000695 (secuencia de Moser-de Bruijn)", La enciclopedia en línea de secuencias enteras , Fundación OEIS
- ^ Chan, O-Yeat; Manna, Dante (2010), "Congruencias de números de Stirling de segunda especie" (PDF) , Gems in Experimental Mathematics , Contemporary Mathematics, vol. 517, Providence, Rhode Island: Sociedad Matemática Estadounidense, págs. 97–111, doi :10.1090/conm/517/10135, SEÑOR 2731094
- ^ ab Madritsch, Manfred; Wagner, Stephan (2010), "Un teorema del límite central para particiones enteras", Monatshefte für Mathematik , 161 (1): 85–114, doi :10.1007/s00605-009-0126-y, MR 2670233, S2CID 15008932
- ^ Klavžar, Sandi (2013), "Estructura de los cubos de Fibonacci: una encuesta", Journal of Combinatorial Optimization , 25 (4): 505–522, doi :10.1007/s10878-011-9433-z, MR 3044155, S2CID 5557314
- ^ Sloane, N. J. A. (ed.), "Secuencia A300867 (La k menos positiva tal que k * n es un número fibbinario)", La enciclopedia en línea de secuencias enteras , Fundación OEIS