Combinatorics on words; Generating Dirichlet series; Automatic sequences; Missing digits; Restricted words
Abstract :
[en] Generating series are crucial in enumerative combinatorics,
analytic combinatorics, and combinatorics on words. Though it
might seem at first view that generating Dirichlet series are less
used in these fields than ordinary and exponential generating series,
there are many notable papers where they play a fundamental role, as
can be seen in particular in the work of Flajolet and several of his
co-authors. In this paper, we study Dirichlet series of integers with
missing digits or blocks of digits in some integer base $b$; i.e.,
where the summation ranges over the integers whose
expansions form some language strictly included in the set of all
words over the alphabet $\{0, 1, \dots, b-1\}$ that do not begin with
a $0$. We show how to unify and extend results proved by Nathanson
in 2021 and by K\"ohler and Spilker in 2009.
En route, we encounter several sequences from Sloane's On-Line Encyclopedia of Integer Sequences, as well as some famous $b$-automatic sequences or $b$-regular sequences.
We also consider a specific sequence that is not $b$-regular.
Disciplines :
Mathematics
Author, co-author :
Allouche, Jean-Paul
Shallit Jeffrey
Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Combinatorics on words and generating Dirichlet series of automatic sequences
scite shows how a scientific paper has been cited by providing the context of the citation, a classification describing whether it supports, mentions, or contrasts the cited claim, and a label indicating in which section the citation was made.
Bibliography
Alkauskas, G., Dirichlet series associated with strongly q-multiplicative functions. Ramanujan J. 8:1 (2004), 13–21, 10.1023/B:RAMA.0000027195.05101.2d.
Allouche, J.-P., Cohen, H., Dirichlet series and curious infinite products. Bull. Lond. Math. Soc., 17(6), 1985, 10.1112/blms/17.6.531.
Allouche, J.-P., Shallit, J., The ring of k-regular sequences. II. Theor. Comput. Sci. 307:1 (2003), 3–29, 10.1016/S0304-3975(03)00090-2.
Berthé, V., Rigo, M., (eds.) Combinatorics, Automata and Number Theory Encyclopedia of Mathematics and Its Applications, vol. 135, 2010, Cambridge University Press, Cambridge, 10.1017/CBO9780511777653.
Birmajer, D., Gil, J.B., Weiner, M.D., On the enumeration of restricted words over a finite alphabet. J. Integer Seq., 19(1), 2016, 16.1.3 16 https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html.
Brauer, A., On algebraic equations with all but one root in the interior of the unit circle. Math. Nachr. 4 (1951), 250–257, 10.1002/mana.3210040123.
de Bruijn, N.G., Knuth, D.E., Rice, S.O., The average height of planted plane trees. Graph Theory and Computing, 1972, Academic Press, New York, 15–22.
Burnol, J.-F., Digamma function and general Fischer series in the theory of kempner sums. Expo. Math., 42(6), 2024, 125604, 10.1016/j.exmath.2024.125604 https://www.sciencedirect.com/science/article/pii/S0723086924000719.
Burnol, J.-F., Measures for the summation of Irwin series. preprint available at https://arxiv.org/abs/2402.09083, 2024.
Burnol, J.-F., Sur l'asymptotique des sommes de Kempner pour de grandes bases. preprint available at https://arxiv.org/abs/2403.01957, 2024.
Cobham, A., Uniform tag sequences. Math. Syst. Theory, 6(164–192), 1972, 10.1007/BF01706087.
Coons, M., (Non)automaticity of number theoretic functions. J. Théor. Nr. Bordx. 22:2 (2010), 339–352 http://jtnb.cedram.org/item?id=JTNB_2010__22_2_339_0.
Coons, M., Lind, J., Radial asymptotics of generating functions of k-regular sequences. Bull. Aust. Math. Soc. 110:3 (2024), 528–534, 10.1017/S0004972724000480.
Cumberbatch, J., Digitally restricted sets and the Goldbach conjecture: an exceptional set result. preprint available at https://arxiv.org/abs/2402.07921, 2024.
Drmota, M., Grabner, P.J., Analysis of digital functions and applications. Combinatorics, Automata and Number Theory Encyclopedia Math. Appl., vol. 135, 2010, Cambridge Univ. Press, Cambridge, 452–504.
Dumas, P., Lipmaa, H., Wallén, J., Asymptotic behaviour of a non-commutative rational series with a nonnegative linear representation. Discrete Math. Theor. Comput. Sci. 9:1 (2007), 247–272 www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/issue/view/85/showToc.html.
Dumas, P., Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences. Linear Algebra Appl. 438:5 (2013), 2107–2126, 10.1016/j.laa.2012.10.013.
Dumas, P., Asymptotic expansions for linear homogeneous divide-and-conquer recurrences: algebraic and analytic approaches collated. Theoret. Comput. Sci. 548 (2014), 25–53, 10.1016/j.tcs.2014.06.036.
Dumont, J.-M., Thomas, A., Systèmes de numération et fonctions fractales relatifs aux substitutions. Theor. Comput. Sci. 65:2 (1989), 153–169, 10.1016/0304-3975(89)90041-8.
Ekhad, S.B., Zeilberger, D., Counting clean words according to the number of their clean neighbors. ACM Commun. Comput. Algebra 57:1 (2023), 5–9, 10.1145/3610377.3610379.
Everlove, C., Dirichlet series associated to sum-of-digits functions. Int. J. Number Theory 18:4 (2022), 777–798, 10.1142/S1793042122500415.
Flajolet, P., Sedgewick, R., Analytic Combinatorics. 2009, Cambridge University Press, Cambridge, 10.1017/CBO9780511801655.
Fogg, N.P., Substitutions in dynamics arithmetics and combinatorics. Berthé, V., Ferenczi, S., Mauduit, C., Siegel, A., (eds.) Lecture Notes in Mathematics, vol. 1794, 2002, Springer-Verlag, Berlin, 10.1007/b13861.
Graham, R.L., Knuth, D.E., Patashnik, O., Concrete Mathematics. second edn., 1994, Addison-Wesley Publishing Company, Reading, MA a foundation for computer science.
Guibas, L.J., Odlyzko, A.M., String overlaps, pattern matching, and nontransitive games. J. Comb. Theory, Ser. A 30:2 (1981), 183–208, 10.1016/0097-3165(81)90005-4.
von Haeseler, F., Automatic Sequences. De Gruyter Expositions in Math., vol. 36, 2003, Walter de Gruyter & Co., Berlin, 10.1515/9783110197969.
Heuberger, C., Krenn, D., Asymptotic analysis of regular sequences. Algorithmica 82:3 (2020), 429–508, 10.1007/s00453-019-00631-3.
Janjić, M., On linear recurrence equations arising from compositions of positive integers. J. Integer Seq., 18(4), 2015, 15.4.7 14 https://cs.uwaterloo.ca/journals/JIS/VOL18/Janjic/janjic63.html.
Janjić, M., Binomial coefficients and enumeration of restricted words. J. Integer Seq., 19(7), 2016, 16.7.3 18 https://cs.uwaterloo.ca/journals/JIS/VOL19/Janjic/janjic73.html.
Janjić, M., Some formulas for numbers of restricted words. J. Integer Seq., 20(6), 2017, 17.6.5 10 https://cs.uwaterloo.ca/journals/JIS/VOL20/Janjic/janjic83.html.
Janjić, M., Pascal matrices and restricted words. J. Integer Seq., 21(5), 2018, 18.5.2 13 https://cs.uwaterloo.ca/journals/JIS/VOL21/Janjic2/janjic103.html.
Janjić, M., Words and linear recurrences. J. Integer Seq., 21(1), 2018, 18.1.4 17 https://cs.uwaterloo.ca/journals/JIS/VOL21/Janjic/janjic93.html.
Kärki, T., Lacroix, A., Rigo, M., On the recognizability of self-generating sets. Mathematical Foundations of Computer Science 2009 Lecture Notes in Comput. Sci., vol. 5734, 2009, Springer, Berlin, 525–536, 10.1007/978-3-642-03816-7_45.
Kärki, T., Lacroix, A., Rigo, M., On the recognizability of self-generating sets. J. Integer Seq., 13(2), 2010, 10.2.2 18 https://cs.uwaterloo.ca/journals/JIS/VOL13/Rigo/rigo6.html.
Knill, O., Lesieutre, J., Analytic continuation of Dirichlet series with almost periodic coefficients. Complex Anal. Oper. Theory 6:1 (2012), 237–255, 10.1007/s11785-010-0064-7.
Kwon, D., A one-parameter family of Dirichlet series whose coefficients are Sturmian words. J. Number Theory 147 (2015), 824–835, 10.1016/j.jnt.2014.08.018.
Mandelbrojt, S., Dirichlet Series. Principles and Methods. 1972, D. Reidel Publishing Co., Dordrecht.
Mukherjee, R., Sarkar, N., A short note on a curious convergent series. Asian-Eur. J. Math., 14(9), 2021, 2150158, 10.1142/S1793557121501588.
Nathanson, M.B., Dirichlet series of integers with missing digits. J. Number Theory 222 (2021), 30–37, 10.1016/j.jnt.2020.10.002.
Noonan, J., Zeilberger, D., The Goulden-Jackson cluster method: extensions, applications and implementations. J. Differ. Equ. Appl. 5:4–5 (1999), 355–377, 10.1080/10236199908808197.
Queffélec, H., Queffélec, M., Diophantine Approximation and Dirichlet Series. second edn. Texts and Readings in Mathematics, vol. 80, 2020, Hindustan Book Agency/Springer, New Delhi/Singapore, 10.1007/978-981-15-9351-2.
Rowland, E., IntegerSequences software package. https://github.com/ericrowland/IntegerSequences.
Rowland, E., IntegerSequences: a package for computing with k-regular sequences. Mathematical Software – ICMS 2018. 6th International Conference, South Bend, IN, USA, July 24–27, 2018. Proceedings, 2018, Springer, Cham, 414–421, 10.1007/978-3-319-96418-8_49.
Shallit, J., The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut. London Mathematical Society Lecture Note Series, vol. 482, 2023, Cambridge University Press, Cambridge.
Sloane, N.J.A., et al. The on-line encyclopedia of integer sequences. https://oeis.org.
Sourmelidis, A., On the meromorphic continuation of Beatty zeta-functions and Sturmian Dirichlet series. J. Number Theory, 194(303–318), 2019, 10.1016/j.jnt.2018.07.009.
Titchmarsh, E.C., The Theory of Functions. second edn., 1939, Oxford University Press, Oxford.
Tóth, L., Linear combinations of Dirichlet series associated with the Thue-Morse sequence. Integers, 22, 2022, A98 9.
Wilf, H.S., Generatingfunctionology. third edn., 2006, A K Peters, Ltd., Wellesley, MA https://web.archive.org/web/20230322192727/https://www2.math.upenn.edu/~wilf/DownldGF.html.
Wintner, A., On Riemann's reduction of Dirichlet series to power series. Am. J. Math. 69 (1947), 769–789, 10.2307/2371798.
Similar publications
Sorry the service is unavailable at the moment. Please try again later.
This website uses cookies to improve user experience. Read more
Save & Close
Accept all
Decline all
Show detailsHide details
Cookie declaration
About cookies
Strictly necessary
Performance
Strictly necessary cookies allow core website functionality such as user login and account management. The website cannot be used properly without strictly necessary cookies.
This cookie is used by Cookie-Script.com service to remember visitor cookie consent preferences. It is necessary for Cookie-Script.com cookie banner to work properly.
Performance cookies are used to see how visitors use the website, eg. analytics cookies. Those cookies cannot be used to directly identify a certain visitor.
Used to store the attribution information, the referrer initially used to visit the website
Cookies are small text files that are placed on your computer by websites that you visit. Websites use cookies to help users navigate efficiently and perform certain functions. Cookies that are required for the website to operate properly are allowed to be set without your permission. All other cookies need to be approved before they can be set in the browser.
You can change your consent to cookie usage at any time on our Privacy Policy page.
