Binomial^4: Coefficients, equivalence, complexity, and beyond

In combinatorics on words, for two finite words u and v, the binomial coefficient
of u and v is the number of times v appears as a subsequence of u (also called (scattered) subword). For example, with u = alphalpha and v = al, there are = 36 ways to select 2
2 letters among 9, but only 3 of them give back v. Generalizing famous binomial coefficients of integers, the word version has recently received a lot of attention within the combinatorics-on-words community. In particular, a few years ago, in 2015, Michel Rigo and Pavel Salimov introduced the notion of binomial equivalence: for an integer k ≥ 1, two words u and v are k-binomially equivalent if they share equal binomial coefficients for all words of length up to k. This relation gives birth to a refinement of the usual abelian equivalence and Simon’s congruence. Very naturally, one can then associate the corresponding binomial complexity function which, for a given infinite word x, maps an integer n ≥ 0 to the number of length-n factors of x up to the k-binomial equivalence relation. In this talk, I will present a broad overview of the theory of binomial coefficients, equivalence, and complexity functions, focusing on some recent results obtained by Michel Rigo, Markus A. Whiteland, and myself.