Binomial^3: coefficient, equivalence, and complexities

In combinatorics on words, for two words u and v, the binomial coefficient (u,v) of u and v is the number of times v appears as a (scattered) subword of u. For example, with u=ababba and v=aba, there are (6,3)=15 ways to select 3 letters among 6, but only (u,v)=6 of them give back v. Generalizing famous binomial coefficients of integers, the word version has received a lot of attention within the combinatorics-on-words community. A few years ago, M. Rigo and P. Salimov introduced the notion of k-binomial equivalence: two words u and v are k-binomially equivalent if the binomial coefficients (u,x) and (v,x) are equal for all words x of length up to k. This is a refinement of the usual abelian equivalence and Simon's congruence. Very naturally, one can then associate the corresponding k-binomial complexity function which, for a given infinite word x, maps n to the number of length-n factors of x up to the k-binomial equivalence relation. In this talk, I present a broad overview of the theory of binomial coefficients, equivalence, and complexities, focusing on some recent results obtained by M. Rigo, M. Whiteland, and myself.