Binomial coefficients; Pascal triangle; Subwords; Stern-Brocot tree; Farey tree; Trie of sub words
Résumé :
[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 :
Mathématiques
Auteur, co-auteur :
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
Langue du document :
Anglais
Titre :
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.
