1. bookVolume 30 (2022): Issue 1 (June 2022)
Journal Details
License
Format
Journal
eISSN
1788-800X
First Published
30 Mar 2015
Publication timeframe
4 times per year
Languages
English
access type Open Access

Asymptotic bit frequency in Fibonacci words

Published Online: 18 Jun 2022
Volume & Issue: Volume 30 (2022) - Issue 1 (June 2022)
Page range: 23 - 30
Received: 31 Mar 2022
Accepted: 15 May 2022
Journal Details
License
Format
Journal
eISSN
1788-800X
First Published
30 Mar 2015
Publication timeframe
4 times per year
Languages
English
Abstract

It is known that binary words containing no k consecutive 1s are enumerated by k-step Fibonacci numbers. In this note we discuss the expected value of a random bit in a random word of length n having this property.

Keywords

MSC 2010

[1] D. Bajic, On construction of cross-bifix-free kernel sets, 2nd MCM COST 2100, TD(07)237, Lisbon, Portugal, 2007. Search in Google Scholar

[2] J.-L Baril, S. Kirgizov and V. Vajnovszki, Gray codes for Fibonacci q-decreasing words, arXiv:2010.09505. Search in Google Scholar

[3] A. Bernini, S. Bilotta, R. Pinzani and V. Vajnovszki, A Gray code for cross-bifix-free sets, Math. Structures Computer Sci., 27 (2017) 184–196.10.1017/S0960129515000067 Search in Google Scholar

[4] A. Brauer, On algebraic equations with all but one root in the interior of the unit circle. To my teacher and former colleague Erhard Schmidt on his 75th birthday, Math. Nachr., 4 (1950) 250–257.10.1002/mana.3210040123 Search in Google Scholar

[5] Y. M. Chee, H. M. Kiah, P. Purkayastha and C. Wang, Cross-bifix-free codes within a constant factor of optimality, IEEE Trans. Inform. Theory, 59 (2013) 4668—4674.10.1109/TIT.2013.2252952 Search in Google Scholar

[6] M. Cipu and F. Luca, On the Galois group of the generalized Fibonacci polynomial, An. Ştiinţ. Univ. “Ovidius” Constanţa Ser. Mat., 9 (2001) 27—38. Search in Google Scholar

[7] F. Dubeau, On r-generalized Fibonacci numbers, Fibonacci Quart., 27 (1989) 221–229. Search in Google Scholar

[8] Ö. Eğecioğlu and V. Iršič, Fibonacci-run graphs I: Basic properties, Discrete Appl. Math., 295 (2021) 70–84.10.1016/j.dam.2021.02.025 Search in Google Scholar

[9] I. Flores, Direct calculation of k-generalized Fibonacci numbers, Fibonacci Quart., 5 (1967) 259–266. Search in Google Scholar

[10] G. W. Grossman and S. K. Narayan, On the characteristic polynomial of the j-th order Fibonacci sequence, Applications of Fibonacci Numbers, 8, Springer, Dordrecht, 1999, pp. 165–177.10.1007/978-94-011-4271-7_17 Search in Google Scholar

[11] K. Hare, H. Prodinger and J. Shallit, Three series for the generalized golden mean, Fibonacci Quart., 52 (2014) 307–314 Search in Google Scholar

[12] D. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998. Search in Google Scholar

[13] P. A. Martin, The Galois group of xnxn − 1 − . . . − x − 1, J. Pure Appl. Algebra, 190 (2004) 213–223. Search in Google Scholar

[14] E. Miles, Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly, 67 (1960) 745–752. Search in Google Scholar

[15] M. D. Miller, On generalized Fibonacci numbers, Amer. Math. Monthly, 78 (1971) 1108–1109. Search in Google Scholar

[16] R. Sedgewick and P. Flajolet, An introduction to the analysis of algorithms, 2nd ed., Addison-Wesley, 2013. Search in Google Scholar

[17] E. S. Selmer, On the irreducibility of certain trinomials, Math. Scand., 4 (1956) 287–302.10.7146/math.scand.a-10478 Search in Google Scholar

[18] E. Rouché, Mémoire sur la série de Lagrange, Journal de l’École Polytechnique, 22 (1862) 193–224. Search in Google Scholar

[19] D. A. Wolfram, Solving generalized Fibonacci recurrences, Fibonacci Quart., 36 (1998) 129–145. Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo