A way of extending Pascal and Sierpinski triangles to finite words

Combinatorics on words is a relatively new domain of discrete mathematics, which focuses on the study of words and formal languages. In this context, a finite word is simply a finite sequence of letters, or symbols, that belong to a finite set called the alphabet. For instance, 01101 and 01 are two finite (binary) words over the binary alphabet {0, 1}. The binomial coefficient (􏰄u,v)􏰅 of two finite words u and v is the number of occurrences of v as a v subsequence of u. For example, (􏰄01101,01)􏰅 = 4. This concept, which is a natural generalization of the classical binomial coefficients of nonnegative integers, has been widely studied for the last thirty years or so. In this talk, I will first recall the link between the classical Pascal triangle and the Sierpiński gasket, and then present a way of extending both objects to binomial coefficients of (binary) words.