Counting Subwords Occurrences in Base-b Expansions Leroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Integers: Electronic Journal of Combinatorial Number Theory (2018) Detailed reference viewed: 20 (2 ULiège)An extension of the Pascal triangle and the Sierpiński gasket to finite words Stipulanti, Manon Conference (2017, December 15) The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance ... [more ▼] The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance, (abbabab,ab)=4. This concept naturally extends the classical binomial coefficients of integers, and has been widely studied for about thirty years (see, for instance, Simon and Sakarovitch). In this talk, I present the research lead from October 2015: I give the main ideas that lead to an extension of the Pascal triangles to base-2 expansions of integers and also give an overview of the results obtained so far, linked to this generalization. [less ▲] Detailed reference viewed: 16 (0 ULiège)Pascal triangles and Sierpiński gasket extended to binomial coefficients of words Stipulanti, Manon Conference (2017, November 29) The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance ... [more ▼] The binomial coefficient (u,v) of two finite words u and v (on a finite alphabet) is the number of times the word v appears inside the word u as a subsequence (or, as a "scattered" subword). For instance, (abbabab,ab)=4. This concept naturally extends the classical binomial coefficients of integers, and has been widely studied for about thirty years (see, for instance, Simon and Sakarovitch). In this talk, I present the research lead from October 2015 on an extension of the Pascal triangles to base-2 expansions of integers. In a first part, I define two new objects that both generalize the classical Pascal triangle and the Sierpinski gasket. In a second part, I define a new sequence extracted from the Pascal triangle in base 2 and study its regularity. In a third part, I exhibit an exact formula for the behavior of the summatory function of the latter sequence. [less ▲] Detailed reference viewed: 16 (1 ULiège)Generalized Pascal triangles for binomial coefficients of finite words Stipulanti, Manon Conference (2017, June 19) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. Then we create a new sequence from this extended Pascal triangle that counts, on each row of this triangle, the number of positive binomial coefficients. We show that this sequence is 2-regular. To extend our work, we construct a Pascal triangle using the Fibonacci representations of all the nonnegative integers and we define the corresponding sequence of which we study the regularity. This regularity is an extension of the classical k-regularity of sequences. [less ▲] Detailed reference viewed: 30 (9 ULiège)Generalized Pascal triangles for binomial coefficients of finite words Stipulanti, Manon Conference (2017, June 16) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. Then we create a new sequence from this extended Pascal triangle that counts, on each row of this triangle, the number of positive binomial coefficients. We show that this sequence is 2-regular. To extend our work, we construct a Pascal triangle using the Fibonacci representations of all the nonnegative integers and we define the corresponding sequence of which we study the regularity. This regularity is an extension of the classical k-regularity of sequences. [less ▲] Detailed reference viewed: 21 (6 ULiège)Triangles de Pascal et compagnie Stipulanti, Manon Conference (2017, April 19) Le triangle de Pascal classique ainsi que le triangle de Sierpiński sont des objets largement étudiés. Ils montrent des aspects auto-similaires et ont des liens avec les systèmes dynamiques, les automates ... [more ▼] Le triangle de Pascal classique ainsi que le triangle de Sierpiński sont des objets largement étudiés. Ils montrent des aspects auto-similaires et ont des liens avec les systèmes dynamiques, les automates cellulaires, la théorie des nombres et les suites dites automatiques. Dans ce séminaire, nous présentons un travail en collaboration avec Julien Leroy et Michel Rigo. Dans un premier temps, nous introduisons une généralisation du triangle de Pascal basée sur les coefficients binomiaux de mots finis et nous étudions le cas plus particulier des représentations en base 2. Ces coefficients comptent le nombre de fois qu’un mot fini apparaît comme sous-suite d’un autre mot fini. De la même façon que le triangle de Sierpiński peut être construit comme l’ensemble limite, pour la distance de Hausdorff, d’une suite convergente de compacts renormalisés extraits du triangle de Pascal classique modulo 2, nous décrivons et étudions les premières propriétés du sous-ensemble de [0, 1] × [0, 1] associé à ce triangle de Pascal généralisé modulo un nombre premier p. Dans un second temps, nous étudions la suite qui compte, sur chaque ligne du triangle de Pascal généralisé en base 2, le nombre de coefficients binomiaux strictement positifs. Cette suite présente une régularité étonnante qui peut être mise en évidence en utilisant une structure particulière de graphes, appelée arbre des sous-mots. [less ▲] Detailed reference viewed: 39 (12 ULiège)Behavior of digital sequences through exotic numeration systems Leroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Electronic Journal of Combinatorics (2017), 24(1), 14436 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 67 (21 ULiège)Des triangles de Pascal généralisés aux coefficients binomiaux de mots finis Stipulanti, Manon Conference (2017, January 23) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpinski gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we show the existence of a subset of [0, 1]×[0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲] Detailed reference viewed: 26 (4 ULiège)Generalized Pascal triangles for binomial coefficients of words: a short introduction Stipulanti, Manon Conference (2017, January 09) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲] Detailed reference viewed: 28 (7 ULiège)Counting the number of non-zero coefficients in rows of generalized Pascal triangles Leroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Discrete Mathematics (2017), 340 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 ... [more ▼] 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. [less ▲] Detailed reference viewed: 82 (13 ULiège)Chapter VIII "Equations and languages" in J.-É. Pin, Mathematical Foundations of Automata Theory Stipulanti, Manon Conference (2016, December 16) We present the chapter VIII titled "Equations and Langages" in Jean-Éric Pin, Mathematical Foundations of Automata Theory. Detailed reference viewed: 47 (11 ULiège)Generalized Pascal triangles and binomial coefficients of words Stipulanti, Manon Poster (2016, December 01) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpinski gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. From the extended Pascal triangle obtained when p is equal to 2, we derive a sequence of which we study the regularity and the asymptotic behavior of the summatory function. Inspired from this regularity, we extend our results to another famous numeration systems, namely the Zeckendorff numeration system. [less ▲] Detailed reference viewed: 39 (7 ULiège)Generalized Pascal triangle for binomial coefficients of words : an overview Stipulanti, Manon Conference (2016, September 07) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a finite word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. Then we create a new sequence from this extended Pascal triangle that counts, on each row of this triangle, the number of positive binomial coefficients. We study some properties of this sequence. To be precise, we investigate some properties regarding the regularity of the sequence. To extend our work, we construct a Pascal triangle using the Fibonacci representations of all the nonnegative integers and we define the corresponding sequence of which we study the regularity. This regularity is an extension of the classical k-regularity of sequences. [less ▲] Detailed reference viewed: 39 (15 ULiège)Generalized Pascal triangle for binomial coefficients of finite words Stipulanti, Manon Poster (2016, April 05) Abstract. We introduce a generalization of Pascal triangle based on bino- mial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite ... [more ▼] Abstract. We introduce a generalization of Pascal triangle based on bino- mial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpinski gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲] Detailed reference viewed: 75 (32 ULiège)Une généralisation du triangle de Pascal et la suite A007306 Stipulanti, Manon Conference (2016, March 25) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word ... [more ▼] We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpinski gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1]×[0, 1] associated with this extended Pascal triangle modulo a prime p. We consider a sequence (S(n))n≥0 counting the number of positive entries on each row of the generalized Pascal triangle. By introducing a convenient tree structure, we provide a recurrence relation for (S(n))n≥0, we prove that the sequence is 2-regular, give a linear representation and make the connection with the sequence of denominators occurring in the Farey tree. [less ▲] Detailed reference viewed: 68 (37 ULiège)Une généralisation du triangle de Pascal Stipulanti, Manon Conference (2016, March 22) We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpinski gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1]×[0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲] Detailed reference viewed: 57 (34 ULiège)Generalized Pascal triangle for binomial coefficients of words Leroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Advances in Applied Mathematics (2016), 80 We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲] Detailed reference viewed: 180 (86 ULiège)Chapter 2 "Substitutions, arithmetic and finite automata: an introduction" in Pytheas Fogg, Substitutions in Dynamics, Arithmetics and Combinatorics Stipulanti, Manon Conference (2015, February 23) This presentation is about the chapter 2 titled "Substitutions, arithmetic and finite automata: an introduction" in Pytheas Fogg N., Substitutions in dynamics, arithmetics, and combinatorics. Berlin ... [more ▼] This presentation is about the chapter 2 titled "Substitutions, arithmetic and finite automata: an introduction" in Pytheas Fogg N., Substitutions in dynamics, arithmetics, and combinatorics. Berlin : Springer, 2002. [less ▲] Detailed reference viewed: 46 (8 ULiège)Comportement asymptotique des morphismes et théorème de Cobham pour les morphismes effaçants Stipulanti, Manon Master's dissertation (2015) Detailed reference viewed: 116 (47 ULiège) |
||