Counting the number of non-zero coefficients in rows of generalized Pascal triangles

Leroy, Julien; Rigo, Michel; Stipulanti, Manon

doi:10.1016/j.disc.2017.01.003

Download

Article (Scientific journals)

Counting the number of non-zero coefficients in rows of generalized Pascal triangles

Leroy, Julien; Rigo, Michel; Stipulanti, Manon

2017 • In Discrete Mathematics, 340, p. 862-881

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/205077

DOI
10.1016/j.disc.2017.01.003

Files (1)Send to Details Statistics Bibliography Similar publications

Files

Full Text

postprint auteur.pdf

Author postprint (383.26 kB)

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

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

Publication date :

2017

Journal title :

Discrete Mathematics

ISSN :

0012-365X

eISSN :

1872-681X

Publisher :

Elsevier Science, Amsterdam, Netherlands

Volume :

340

Pages :

862-881

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 09 January 2017

Statistics

Number of views

344 (19 by ULiège)

Number of downloads

235 (5 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

[1] Allouche, J.-P., Scheicher, K., Tichy, R.F., Regular maps in generalized number systems. Math. Slovaca 50 (2000), 41–58.
[2] Allouche, J.-P., Shallit, J., The ring of k-regular sequences. Theoret. Comput. Sci. 98 (1992), 163–197.
[3] Allouche, J.-P., Shallit, J., Automatic Sequences. Theory, Applications, Generalizations, 2003, Cambridge University Press.
[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.