Article Dans Une Revue Theoretical Computer Science Année : 2025

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

Résumé

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.

Fichier principal
Vignette du fichier
around_fair_words.pdf (411.46 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Licence

Dates et versions

lirmm-05302654 , version 1 (07-10-2025)

Licence

Identifiants

Citer

Gwenaël Richomme. On some 2-binomial coefficients of binary words: geometrical interpretation, partitions of integers, and fair words. Theoretical Computer Science, 2025, 1066, pp.115732. ⟨10.1016/j.tcs.2025.115732⟩. ⟨lirmm-05302654⟩
1486 Consultations
180 Téléchargements

Altmetric

Partager

  • More