Algèbre de mélange

Le produit de mélange ${\displaystyle x}$ ш ${\displaystyle y}$ de deux mots ${\displaystyle x}$ de longueur N et ${\displaystyle y}$ de longueur M est la somme des ${\displaystyle {\frac {(N+M)!}{N!M!}}}$ mots ${\displaystyle x_{1}y_{1}x_{2}y_{2}\cdots x_{n}y_{n}}$, où les ${\displaystyle x_{i}}$ et les ${\displaystyle y_{i}}$ sont des mots, tels que ${\displaystyle x=x_{1}x_{2}\dots x_{n}}$ et ${\displaystyle y=y_{1}y_{2}\dots y_{n}}$. Par exemple,

${\displaystyle aab}$ ш ${\displaystyle ab=6aaabb+3aabab+abaab}$.

On peut aussi le définir par récurrence^[3] par :

${\displaystyle ua}$ ш ${\displaystyle vb}$=${\displaystyle (u}$ ш ${\displaystyle vb)a+(ua}$ ш ${\displaystyle v)b}$.

Le produit de mélange est associatif et commutatif^[4].

Le produit d'infiltration est une opération semblable, introduite par Chen, Fox et Lyndon 1958. Il est défini par récurrence sur la longueur des mots, pour deux mots ${\displaystyle f}$ et ${\displaystyle g}$ et deux lettres ${\displaystyle a\neq b}$ (le mot vide est noté ${\displaystyle \varepsilon }$) comme suit :

${\displaystyle f\uparrow \varepsilon =\varepsilon \uparrow f=f}$ ;

${\displaystyle fa\uparrow ga=(f\uparrow ga)a+(fa\uparrow g)a+(f\uparrow g)a}$ ;

${\displaystyle fa\uparrow gb=(f\uparrow gb)a+(fa\uparrow g)b}$.

Par exemple,

${\displaystyle a\uparrow a=(\varepsilon \uparrow a)a+(a\uparrow \varepsilon )a+(\varepsilon \uparrow \varepsilon )a=2aa+a}$.

${\displaystyle a\uparrow b=(\varepsilon \uparrow b)a+(a\uparrow \varepsilon )b=ba+ab}$.

De même,

${\displaystyle ab\uparrow ab=ab+2aab+2abb+4aabb+2abab}$ ;

${\displaystyle ab\uparrow ba=aba+bab+abab+2abba+2baab+baba}$ .

Le produit d'infiltration est également associatif et commutatif^[5].