[en] Many digital functions studied in the literature, e.g., the summatory function
of the base-k sum-of-digits function, have a behavior showing some periodic fluctuation.
Such functions are usually studied using techniques from analytic number
theory or linear algebra. In this paper we develop a method based on exotic numeration
systems and we apply it on two examples motivated by the study of generalized
Pascal triangles and binomial coefficients of words.
Disciplines :
Mathematics
Author, co-author :
Leroy, Julien ; Université de Liège > Département de mathématique > Mathématiques discrètes
Rigo, Michel ; Université de Liège > Département de mathématique > Mathématiques discrètes
Stipulanti, Manon ; Université de Liège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Behavior of digital sequences through exotic numeration systems
Publication date :
03 March 2017
Journal title :
Electronic Journal of Combinatorics
ISSN :
1097-1440
eISSN :
1077-8926
Publisher :
Electronic Journal of Combinatorics, United States - Georgia
J.-P. Allouche, K. Scheicher, R. F. Tichy, Regular maps in generalized number systems, Math. Slovaca 50 (2000), 41-58.
J.-P. Allouche, J. Shallit, The ring of k-regular sequences, Theoret. Comput. Sci., 98 (1992), 163-197.
J.-P. Allouche, J. Shallit, The ring of k-regular sequences. II. Theoret. Comput. Sci.307 (2003), 3-29.
J.-P. Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge University Press, (2003).
V. Berthé, M. Rigo (Eds.), Combinatorics, automata and number theory, Encycl. of Math. and its Appl. 135, Cambridge Univ. Press, (2010).
H. Delange, Sur la fonction sommatoire de la fonction "somme des chiffres", Enseignement Math. 21 (1975), 31-47.
P. Dumas, Joint spectral radius, dilation equations, and asymptotic behavior of radixrational sequences, Linear Algebra Appl. 438 (2013), no. 5, 2107-2126.
P. Dumas, Asymptotic expansions for linear homogeneous divide-and-conquer recurrences:algebraic and analytic approaches collated, Theoret. Comput. Sci. 548 (2014), 25-53.
P. Grabner, M. Rigo, Additive functions with respect to numeration systems on regular languages, Monatsh. Math. 139(3) (2003), 205-219.
P. J. Grabner, J. Thuswaldner, On the sum of digits function for number systems with negative bases, Ramanujan J. 4 (2000), 201-220.
C. Heuberger, S. Kropf, H. Prodinger, Output sum of transducers: limiting distribution and periodic fluctuation, Electron. J. Combin. 22(2) #P2.19 (2015).
J. Leroy, M. Rigo, M. Stipulanti, Generalized Pascal triangle for binomial coefficients of words, Adv. Appl. Math. 80 (2016), 24-47.
J. Leroy, M. Rigo, M. Stipulanti, Counting the number of non-zero coefficients in rows of generalized Pascal triangles, Discrete Math. 340 (2017), 862-881.
M. Lothaire, Combinatorics on Words, Cambridge Mathematical Library, Cambridge University Press, (1997).
M. Lothaire, Algebraic Combinatorics on Words, Encyclopedia of Mathematics and its Applications, Cambridge University Press, (2002).
I. Simon, Piecewise testable events, in: Proc. 2nd GI Conf. on Automata Theory and Formal Languages, Lecture Notes in Computer Science 33, Springer, (1975), 214-222.
J. Theys, Joint spectral radius: theory and approximations, Ph. D. thesis, Univ. Catholique de Louvain (2005).
J. R. Trollope, An explicit expression for binary digital sums, Math. Mag. 41 1968 21-25.
É. Zeckendorf, Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liège 41 (1972), 179-182.