On some 2-binomial coefficients of binary words: geometrical interpretation, partitions of integers, and fair words

Abstract: The binomial notation $\binom{w}{u}$ represents the number of occurrences of the word $u$ as a (scattered) subword in $w$. We first introduce and study possible uses of a geometrical interpretation of $\binom{w}{ab}$ and \binom{w}{ba} when $a$ and $b$ are distinct letters. We then study the structure of the $2$-binomial equivalence class of a binary word $w$ (two words are $2$-binomially equivalent if they have the same binomial coefficients, that is, the same numbers of occurrences, for each word of length at most $2$). Especially we explain the existence of an isomorphism between the graph of the $2$-binomial equivalence class of $w$ with respect to a particular rewriting rule and the lattice of partitions of the integer \binom{w}{ab} with \binom{w}{a} parts and greatest part bounded by \binom{w}{b}. Finally we study binary fair words, the words over $\{a, b\}$ having the same numbers of occurrences of $ab$ and $ba$ as subwords $(\binom{w}{ab} = \binom{w}{ba})$. In particular, we sketch a proof of a recent conjecture related to a special case of the least square approximation.

formal languages and automata theorycombinatoricsdynamical systems

Audience: researchers in the topic

( slides | video )

One World Combinatorics on Words Seminar

Series comments: Please write to Anna Frid to receive the Zoom password and further announcements.