Résumé
Two finite words$u$and$v$are$k$ -binomially equivalent if, for each word$x$of length at most$k$ ,$x$appears the same number of times as a subsequence (i.e., as a scattered subword) of both$u$and$v$ . This notion generalizes abelian equivalence. In this paper, we study the equivalence classes induced by the$k$ -binomial equivalence with a special focus on the cardinalities of the classes. We provide an algorithm generating the$2$ -binomial equivalence class of a word. For$k \geq 2$and alphabet of$3$or more symbols, the language made of lexicographically least elements of every$k$ -binomial equivalence class and the language of singletons, i.e., the words whose$k$ -binomial equivalence class is restricted to a single element, are shown to be non context-free. As a consequence of our discussions, we also prove 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, \ldots , m\}^{*}$by the$2$ -binomial equivalence.