Asymptotic bit frequency in Fibonacci words

Baril, Jean-Luc; Kirgizov, Sergey; Vajnovszki, Vincent

doi:10.2478/puma-2022-0005

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.

References

[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 Back to article
[2] J.-L Baril, S. Kirgizov and V. Vajnovszki, Gray codes for Fibonacci q-decreasing words, arXiv:2010.09505.
Search in Google Scholar Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[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 Back to article
[7] F. Dubeau, On r-generalized Fibonacci numbers, Fibonacci Quart., 27 (1989) 221–229.
Search in Google Scholar Back to article
[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 Back to article
[9] I. Flores, Direct calculation of k-generalized Fibonacci numbers, Fibonacci Quart., 5 (1967) 259–266.
Search in Google Scholar Back to article
[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 Back to article
[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 Back to article
[12] D. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998.
Search in Google Scholar Back to article
[13] P. A. Martin, The Galois group of xn − xn − 1 − . . . − x − 1, J. Pure Appl. Algebra, 190 (2004) 213–223.10.1016/j.jpaa.2003.10.028
Search in Google Scholar Back to article
[14] E. Miles, Generalized Fibonacci numbers and associated matrices, Amer. Math. Monthly, 67 (1960) 745–752.10.1080/00029890.1960.11989593
Search in Google Scholar Back to article
[15] M. D. Miller, On generalized Fibonacci numbers, Amer. Math. Monthly, 78 (1971) 1108–1109.10.1080/00029890.1971.11992952
Search in Google Scholar Back to article
[16] R. Sedgewick and P. Flajolet, An introduction to the analysis of algorithms, 2nd ed., Addison-Wesley, 2013.
Search in Google Scholar Back to article
[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 Back to article
[18] E. Rouché, Mémoire sur la série de Lagrange, Journal de l’École Polytechnique, 22 (1862) 193–224.
Search in Google Scholar Back to article
[19] D. A. Wolfram, Solving generalized Fibonacci recurrences, Fibonacci Quart., 36 (1998) 129–145.
Search in Google Scholar Back to article

Asymptotic bit frequency in Fibonacci words

Abstract

Paradigm

My account