Binomial coefficients; Pascal triangle; Subwords; Stern-Brocot tree; Farey tree; Trie of sub words
Abstract :
[en] This paper is about counting the number of distinct (scattered) subwords occurring in a given word. More precisely, we consider the generalization of the Pascal triangle to binomial coefficients of words and the sequence (S(n))n≥0 counting the number of positive entries on each row. By introducing a convenient tree structure, we provide a recurrence relation for (S(n))n≥0. This leads to a connection with the 2-regular Stern–Brocot sequence and the sequence of denominators occurring in the Farey tree. Then we extend our construction to the Zeckendorf numeration system based on the Fibonacci sequence. Again our tree structure permits us to obtain recurrence relations for and the F-regularity of the corresponding sequence.
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 :
Counting the number of non-zero coefficients in rows of generalized Pascal triangles
[4] Bates, B., Bunder, M., Tognetti, K., Locating terms in the Stern–Brocot tree. European J. Combin. 31 (2010), 1020–1033.
[5] Berstel, J., An exercise on Fibonacci representations. Theoret. Inform. Appl. 35:6 (2001), 491–498.
[6] Berstel, J., Reutenauer, C., Noncommutative Rational Series with Applications Encycl. of Math. and its Appl., vol. 137, 2011, Cambridge Univ. Press.
[7] Berthé, V., Rigo, M., (eds.) Combinatorics, Automata and Number Theory Encycl. of Math. and its Appl., vol. 135, 2010, Cambridge Univ. Press.
[8] Bright, C., Devillers, R., Shallit, J., Subwords, regular languages, and prime numbers. Exp. Math. 25:3 (2016), 321–331.
[9] Calkin, N.J., Wilf, H.S., Binary Partitions of Integers and Stern–Brocot-Like Trees, 1998 (unpublished). Updated version August 5, 2009, 19 pages.
[10] Carpi, A., Maggi, C., On synchronized sequences and their separators. Theor. Inform. Appl. 35 (2001), 513–524.
[11] Coons, M., Shallit, J., A pattern sequence approach to Stern's sequence. Discrete Math. 311:22 (2011), 2630–2633.
[12] Dress, A.W.M., Erdős, P.L., Reconstructing words from subwords in linear time. Ann. Comb. 8 (2004), 457–462.
[13] C.H. Du, H. Mousavi, L. Schaeffer, J. Shallit, Decision algorithms for fibonacci-automatic words, III: Enumeration and Abelian properties, Preprint, 2016.
[14] Dumas, P., Joint spectral radius, dilation equations, and asymptotic behavior of radix-rational sequences. Linear Algebra Appl. 438:5 (2013), 2107–2126.
[15] Eilenberg, S., Automata, Languages and Machines, Vol. A, 1974, Academic Press, New York.
[16] Fraenkel, A.S., Systems of numeration. Amer. Math. Monthly 92 (1985), 105–114.
[17] D.D. Freydenberger, P. Gawrychowski, J. Karhumäki, F. Manea, W. Rytter, Testing k-binomial equivalence, arXiv:1509.00622.
[18] Glasby, S.P., Enumerating the rationals from left to right. Amer. Math. Monthly 118 (2011), 830–835.
[19] Goč, D., Schaeffer, L., Shallit, J., Subword complexity and k-synchronization. Developments in Language Theory Lect. Notes in Comput. Sci., vol. 7907, 2013, 252–263.
[20] Greinecker, F., On the 2-abelian complexity of the Thue–Morse word. Theoret. Comput. Sci. 593 (2015), 88–105.
[21] Karandikar, P., Kufleitner, M., Schnoebelen, Ph., On the index of Simon's congruence for piecewise testability. Inform. Process. Lett. 15 (2015), 515–519.
[22] Karandikar, P., Niewerth, M., Schnoebelen, Ph., On the state complexity of closures and interiors of regular languages with subwords and superwords. Theoret. Comput. Sci. 610 (2016), 91–107.
[23] Lecomte, P.B.A., Rigo, M., Numeration systems on a regular language. Theory Comput. Syst. 34 (2001), 27–44.
[24] Leroy, J., Rigo, M., Stipulanti, M., Generalized Pascal triangle for binomial coefficients of words. Adv. Appl. Math. 80 (2016), 24–47.
[25] J. Leroy, M. Rigo, M. Stipulanti, Summatory function of sequences counting subwords occurrences, Elec. J. Combin. (2016) (in press).
[26] Lothaire, M., Combinatorics on Words, 1997, Cambridge Mathematical Library, Cambridge University Press.
[27] Parreau, A., Rigo, M., Rowland, E., Vandomme, É., A new approach to the 2-regularity of the ℓ-abelian complexity of 2-automatic sequences. Electron. J. Combin. 22 (2015), 1–27.
[28] Rao, M., Rigo, M., Salimov, P., Avoiding 2-binomial squares and cubes. Theoret. Comput. Sci. 572 (2015), 83–91.
[29] Rigo, M., Formal Languages, Automata and Numeration Systems, Vol. 1, Introduction to Combinatorics on Words, 2014, ISTE, London; John Wiley & Sons Inc., Hoboken, NJ.
[30] Rigo, M., Maes, A., More on generalized automatic sequences. J. Autom. Lang. Comb. 7 (2002), 351–376.
[31] Schaeffer, L., Shallit, J., Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences. Electron. J. Combin., 23(1), 2016 paper 1.25.
[32] Shallit, J., A generalization of automatic sequences. Theoret. Comp. Sci. 61:1 (1988), 1–16.
[33] N.J.A. Sloane, The on-line encyclopedia of integer sequences, oeis.org.
[34] 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.
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.
