Binomial^3 : coefficients, equivalence, complexity…

The binomial coefficient (x,y) of the words x and y is the number of times y appears as a (scattered) subword of x. This concept has received a lot of attention, e.g., Simon's congruence, Parikh matrices, reconstruction problem, ... A few years ago, we introduced the k-binomial equivalence: Two words u and v are k-binomially equivalent if the binomial coefficients (u,x) and (v,x) agree for all words x of length up to k. This is a refinement of the usual abelian equivalence.

First, I will review several results (joint work with P. Salimov, M. Lejeune, J. Leroy, M. Rosenfeld) related to k-binomial complexity (where factors of length n are counted up to k-binomial equivalence) for Sturmian words, Thue-Morse word and Tribonacci word. Then I will concentrate on k-binomial equivalence classes for finite words. In particular, I will discuss the fact that the submonoid generated by the generators of the free nil-2 group on m generators is isomorphic to the quotient of the free monoid {1,...,m}^∗ by the 2-binomial equivalence (joint work with M. Lejeune, M. Rosenfeld).