2025/10/08 by G. Richomme, Richomme, Gwenaël
Computer Science · #Cellular Automata and Applications #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2510.07159
openalex publication_date 2025/10/08 · openalex created_date 2025/10/11 · openalex updated_date 2026/07/28
The binomial notation (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 (w ab) and (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 prove 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 (w ab) with (w a) parts and greatest part bounded by (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 ((w ab) = (w ba)). In particular, we prove a recent conjecture related to a special case of the least square approximation.