# Étude algébrique de certains problèmes d'Analyse Combinatoire et du Calcul des Probabilités

Dominique Foata

► To cite this version:

Dominique Foata. Étude algébrique de certains problèmes d'Analyse Combinatoire et du Calcul des Probabilités. Annales de l'ISUP, 1965, XIV, pp.81-241. hal-04084815

HAL Id: hal-04084815

https://hal.science/hal-04084815

Submitted on 28 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# ÉTUDE ALGÉBRIQUE
DE CERTAINS PROBLÈMES D'ANALYSE COMBINATOIRE
ET DU CALCUL DES PROBABILITÉS(*)

Dominique FOATA

## Table des matières

<table><thead><tr><th></th><th>Pages</th></tr></thead><tbody><tr><td>1. INTRODUCTION</td><td>85</td></tr><tr><td>2. NOTATIONS ET PRELIMINAIRES ALGEBRIQUES</td><td>93</td></tr><tr><td>2.1. Monoïdes libres</td><td>93</td></tr><tr><td>2.2. Monoïdes abéliens libres</td><td>95</td></tr><tr><td>2.3. Mots non décroissants</td><td>95</td></tr><tr><td>2.4. Algèbre large d'un monoïde</td><td>96</td></tr><tr><td>2.5. Topologie des séries formelles</td><td>99</td></tr><tr><td>3. UNE IDENTITE COMBINATOIRE NON COMMUTATIVE</td><td>101</td></tr><tr><td>3.1. Introduction</td><td>101</td></tr><tr><td>3.2. Le monoïde d'intercalement $\mathcal{X}_I^*$</td><td>101</td></tr><tr><td>3.3. Une identité combinatoire non commutative</td><td>104</td></tr><tr><td>3.4. Le "Master Theorem" de Mac Mahon</td><td>106</td></tr></tbody></table>

<footnote>(*) Thèse Doctorat Sc. Math. Paris 1965</footnote>
<table><tbody><tr><td>4. LA REPRESENTATION EN CYCLES DU MONOÏDE LIBRE</td><td>113</td></tr><tr><td>4.1. Introduction</td><td>113</td></tr><tr><td>4.2. Quelques lemmes préliminaires</td><td>115</td></tr><tr><td>4.3. L'opérateur δ</td><td>119</td></tr><tr><td>4.4. Les opérateurs τ</td><td>124</td></tr><tr><td>4.5. Le monoïde @</td><td>127</td></tr><tr><td>4.6. L'identité sur les ζ</td><td>134</td></tr><tr><td>5. LES FACTORISATIONS DE MONOÏDES LIBRES</td><td>141</td></tr><tr><td>5.1. Introduction</td><td>141</td></tr><tr><td>5.2. Le théorème de factorisation de Schützenberger</td><td>141</td></tr><tr><td>5.3. Quelques applications et définitions</td><td>142</td></tr><tr><td>6. UNE APPLICATION DE LA REPRESENTATION EN CYCLES DU MONOÏDE LIBRE</td><td>147</td></tr><tr><td>6.1. Introduction</td><td>147</td></tr><tr><td>6.2. L'opérateur δ'</td><td>149</td></tr><tr><td>6.3. Un théorème combinatoire non commutatif</td><td>156</td></tr><tr><td>7. LES FACTORISATIONS SPECIALES</td><td>161</td></tr><tr><td>7.1. Introduction</td><td>161</td></tr><tr><td>7.2. Préliminaires algébriques</td><td>163</td></tr><tr><td>7.3. Les factorisations spéciales</td><td>168</td></tr><tr><td>7.4. Factorisation en mots lexicographiques standards</td><td>176</td></tr><tr><td>7.5. La factorisation de Spitzer</td><td>180</td></tr><tr><td>7.6. Factorisation spéciale induite par une fonction continue strictement monotone</td><td>184</td></tr><tr><td>8. APPLICATIONS DES FACTORISATIONS SPECIALES. UN THEOREME COMBINATOIRE NON COMMUTATIF</td><td>187</td></tr><tr><td>8.1. Introduction</td><td>187</td></tr><tr><td>8.2. Rappel de définitions</td><td>188</td></tr></tbody></table>
TABLE DES MATIÈRES

83

<table><thead><tr><th></th><th></th><th>Pages</th></tr></thead><tbody><tr><td>8.3.</td><td>Construction de la permutation φ</td><td>190</td></tr><tr><td>8.4.</td><td>Exemple</td><td>202</td></tr><tr><td>9.</td><td>STATISTIQUES D'ORDRE. FORMULE DE SPITZER</td><td>207</td></tr><tr><td>9.1.</td><td>Introduction</td><td>207</td></tr><tr><td>9.2.</td><td>Un théorème sur les statistiques d'ordre</td><td>208</td></tr><tr><td>9.3.</td><td>Une identité sur les fonctions caractéristiques des statistiques d'ordre</td><td>212</td></tr><tr><td>9.4.</td><td>Quelques applications probabilistes des factorisations spéciales</td><td>222</td></tr><tr><td>10.</td><td>APPLICATIONS COMBINATOIRES. FORMULE DE DIXON</td><td>225</td></tr><tr><td>10.1.</td><td>Introduction</td><td>225</td></tr><tr><td>10.2.</td><td>Un résultat combinatoire</td><td>226</td></tr><tr><td>10.3.</td><td>L'identité de Dixon</td><td>230</td></tr><tr><td>10.4.</td><td>L'identité de Fjeldstad</td><td>232</td></tr><tr><td>LISTE DES PRINCIPAUX SYMBOLES UTILISES</td><td></td><td>235</td></tr><tr><td>REFERENCES</td><td></td><td>239</td></tr></tbody></table>

<figure><img src="image_2.png" /></figure>

Pages

113

113

115

119

124

127

134

141

141

141

142

147

147

149

156

161

161

163

168

176

180

184

187

187

188
## INTRODUCTION

1. 1. Introduction of the General Theory of Relativity

2. 2. The General Theory of Relativity

3. 3. The General Theory of Relativity and its Applications

4. 4. The General Theory of Relativity and its Applications

5. 5. The General Theory of Relativity and its Applications

6. 6. Applications of the General Theory of Relativity

7. 7. Applications of the General Theory of Relativity

8. 8. Applications of the General Theory of Relativity

9. 9. Applications of the General Theory of Relativity

10. 10. Applications of the General Theory of Relativity

11. 11. Applications of the General Theory of Relativity

12. 12. Applications of the General Theory of Relativity

13. 13. Applications of the General Theory of Relativity

14. 14. Applications of the General Theory of Relativity

15. 15. Applications of the General Theory of Relativity

16. 16. Applications of the General Theory of Relativity
# 1. Introduction

Avec la théorie des fluctuations de sommes variables aléatoires, l'étude des problèmes combinatoires en Calcul des Probabilités a été remise en faveur dans les vingt dernières années. De nombreux résultats ont été trouvés à partir de théorèmes combinatoires sur des suites de nombres. Citons, par exemple, le principe d'équivalence de Sparre Andersen [1] ou l'identité dite de Spitzer [38], déjà connue de Pollaczek [30]. Si $\mathcal{R}$ et $\mathcal{R}'$ sont deux propriétés définies sur l'ensemble $S_n$ des suites $(x_1, x_2, ..., x_n)$ de nombres réels, la démonstration de ces théorèmes combinatoires consiste souvent à construire une permutation $\varphi$ de $S_n$ qui assochie à tout $x = (x_1, x_2, ..., x_n)$ de $S_n$ ayant la propriété $\mathcal{R}$ une autre suite $(x'_1, x'_2, ..., x'_n)$ ayant la propriété $\mathcal{R}'$ et où la suite $(x'_1, x'_2, ..., x'_n)$ est un certain réarrangement de la suite $(x_1, x_2, ..., x_n)$.

C'est ce problème de réarrangement des suites de nombres, ou plus généralement des séquences d'objets appartenant à un certain ensemble $\mathcal{X}$ que nous allons étudier ici. Nous serons conduits à définir sur le monoïde libre $\mathcal{X}^*$ engendré par $\mathcal{X}$, supposé totalement ordonné (car c'est bien la structure algébrique qui semble s'imposer pour cette étude), une nouvelle opération associative $\Gamma$, telle que le couple formé par l'ensemble des éléments de $\mathcal{X}^*$ et cette opération est un nouveau monoïde, qu'on appellera *monoïde d'intercalement*, noté $\mathcal{X}_{\Gamma}^*$ (§ 3.2). Une identité combinatoire (formule 1.2 ci-dessous) sera alors établie dans son algèbre large (non commutative), relative à un anneau $\Omega$, qui, en particulier, explicitera et généralisera au cas $\mathcal{X}$ infini l'identité du "Master Theorem" de MacMahon. Ces méthodes combinatoires non commutatives nous donneront encore la construction d'une permutation $\varphi$ de $S_n$ associée à deux propriétés nouvelles $\mathcal{R}$ et $\mathcal{R}'$ (théorèmes 6.1 et 8.1), d'où nous déduirons un nouveau résultat sur les statistiques d'ordre (théorème 9.1) et une identité ayant la même structure formelle que celle de Spitzer (théorème 9.5). Enfin, nous donnerons une nouvelle interprétation combinatoire à des identités conte-
(vf = 1 si f = 1 (mot unité)). Pour X fini, le "Master Theorem" affirme que

$$
\Sigma \{ \alpha f. \vee f : f \in \mathcal{X}^* \} = (\det(I - x B))^{-1} \quad (1.1)
$$

où x est la matrice diagonale diag (x₁, x₂, ..., xₙ)
(n = card X), I la matrice unité d'ordre n et B la matrice
(b(x_k, x_k'))_{k_1 \le k < k' \le n} (1.1) est donc une identité dans l'algèbre large
Ω[[X*]] et sous cette forme, il semble naturel de chercher une ex-
pression analogue pour la série formelle Σ{f.vf : f ∈ X*} de l'algèbre
non commutative Ω[[X*]], sans aucune hypothèse sur la cardinalité
de X. Nous sommes ainsi amenés à expliciter le déterminant du
second membre de (1.1) qui n'a évidemment pas de sens dans une
algèbre non commutative. Nous avons ainsi obtenu pour un ensemble
X quelconque l'identité

$$
\Sigma \{ f. \vee f : f \in \mathcal{X}^* \} = (1 - \Sigma \{ f. \zeta f. \vee f : f \in \mathcal{N} \})^{-1} \quad (1.2)
$$

entre deux séries formelles d'une algèbre large Ω[[X_T]] d'un mo-
nôide non abélien X_T. Celui-ci est défini comme le couple formé
de tous les mots de X* et d'une opération T associative (dis-
tincte du produit de juxtaposition mais telle que α(fTf') = α(ff')
pour tout f, f' ∈ X*). Dans la formule (1.2), N est un certain
sous-ensemble de X* et ζ une fonction définie sur N et pre-
nant les valeurs +1 ou -1. Nous en déduisons, en particulier,
le "Master Theorem" pour une infinité de variables commutatives
en prenant l'image par α des deux membres.

Ce résultat est explicité dans le chapitre 3. Toutefois, la
preuve de l'identité (1.2) ne sera complétée qu'à la fin du cha-
pitre 4 ("La représentation en cycles du monoïde libre") qui contient
de nombreux lemmes combinatoires, qui sont assez longs à véri-
fier. Soit θ : Y → X* une bijection ; il s'agit, en fait, par
analogie avec la théorie du groupe symétrique, où toute permutation
peut s'écrire comme produit de cycles disjoints, d'associer à tout
mot f ∈ X* un sous-ensemble Uf de Y* (le monoïde libre en-
gendré par Y) tel que si g = yl₁ yl₂ ... yls ∈ Uf et si l'on pose

$$
\theta y_{l_p} = x_{v_{K_{p-1}}+1} \ x_{v_{K_{p-1}}+2} \ \dots \ x_{v_{K_p}} \quad (K_o = 0; 1 \le p \le s), \quad (6.1.3)
$$

f = x_{l_1} x_{l_2} ... x_{l_r} et βf = x_{j_1} x_{j_2} ... x_{j_r}, il correspond à tout
k \in [1, r] un et un seul k' \in [1, r] tel que x_{j_k} = x_{v_{k_k}}, et

$$
x_{i_k} = x_{v_{k'-1}} \quad \text{si} \quad k' \neq K_{p-1} + 1 \quad \text{pour tout} \quad p \in [1, s]
$$

$$
= x_{v_{K_p}} \quad \text{si} \quad k' = K_{p-1} + 1.
$$
Nous disons alors que $g \in U_f$ est une représentation en cycles du mot $f$. Pour chaque problème combinatoire considéré, tout revient à définir, pour tout mot $f \in \mathcal{X}^*$, une représentation en cycles de ce mot, unique. Par exemple, pour prouver l'identité (1.2), nous montrerons que tout sous-ensemble $U_f$ contient un et un seul mot $g = y_{l_1} y_{l_2} \dots y_{l_s}$ tel que $\theta_{y_{l_p}} \in \mathfrak{S}_o$ où $\mathfrak{S}_o$ est un sous-ensemble totalement ordonné de $\mathfrak{M}$ et que si les deux mots $\theta_{y_{l_p}}$ et $\theta_{y_{l_{p+1}}}$ n'ont pas de lettre en commun, alors $\theta_{y_{l_p}} > \theta_{y_{l_{p+1}}}$. Un tel mot sera appelé canonique (définition 4.1) et noté Cf.

Dans le chapitre 5 ("Les factorisations de monoïdes libres"), nous rappelons le théorème de factorisation des monoïdes libres de Schützenberger qui joue un rôle fondamental dans toute cette étude et en donnons quelques applications, utilisées dans le chapitre suivant.

Dans le chapitre 6 ("Une application de la représentation en cycles du monoïde libre"), nous explicitons combinatoirement le résultat numérique suivant, que nous décrirons sur un exemple :

Soit $h$ l'ensemble des 12 suites $x = (x_{i_1}, x_{i_2}, x_{i_3}, x_{i_4})$ d'entiers contenant exactement deux fois le nombre 1 et une fois les nombres 2 et 3. Posons $(x_{j_1}, x_{j_2}, x_{j_3}, x_{j_4}) = (1, 1, 2, 3)$ et définissons sur $h$ les fonctions $v$ et $\xi$ à valeurs entières en posant pour $x = (x_{i_1}, x_{i_2}, x_{i_3}, x_{i_4})$

$v x$ = nombre d'indices $k$ tels que $x_{i_k} < x_{j_k}$ ($1 \le k \le 4$)

$\xi x$ = nombre d'indices $k$ tels que $x_{i_{k-1}} < x_{i_k}$ ($2 \le k \le 4$).

Déterminons pour chacune de ces suites $x$ les nombres $v x$ et $\xi x$ ; nous avons le tableau

<table><thead><tr><th>suites x</th><th>v x</th><th>ξ x</th></tr></thead><tbody><tr><td>1 1 2 3</td><td>0</td><td>2</td></tr><tr><td>1 1 3 2</td><td>1</td><td>1</td></tr><tr><td>1 2 1 3</td><td>1</td><td>2</td></tr><tr><td>1 2 3 1</td><td>1</td><td>2</td></tr><tr><td>1 3 1 2</td><td>2</td><td>2</td></tr><tr><td>1 3 2 1</td><td>1</td><td>1</td></tr><tr><td>2 1 1 3</td><td>1</td><td>1</td></tr><tr><td>2 1 3 1</td><td>1</td><td>1</td></tr><tr><td>2 3 1 1</td><td>2</td><td>1</td></tr><tr><td>3 1 1 2</td><td>2</td><td>1</td></tr><tr><td>3 1 2 1</td><td>1</td><td>1</td></tr><tr><td>3 2 1 1</td><td>2</td><td>0</td></tr></tbody></table>
Nous observons que le nombre de suites $x$ telles que $\forall x = 0$ (resp. 1 et 2) est égal au nombre des suites $x$ telles que $\xi x = 0$ (resp. 1 et 2). Ce nombre est ici 1 (resp. 7 et 4).

Nous explicitons ce résultat en construisant pour un ensemble $\mathcal{X}$ totalement ordonné une permutation $\varphi$ de l'ensemble $S_n$ des suites de longueur $n$ d'éléments de $\mathcal{X}$ telles que si $\forall x = m \in \mathbb{N}$ (propriété $\mathcal{R}$) alors $\xi \varphi x = m$ (propriété $\mathcal{R}'$). En fait, nous établissons le théorème combinatoire non commutatif suivant (théorème 6.1).

Soit $x = (x_{i_1}, x_{i_2}, \dots, x_{i_n})$ une suite de $n$ ($n > 1$) éléments d'un ensemble totalement ordonné $\mathcal{X}$, $(x_{j_1}, x_{j_2}, \dots, x_{j_n})$ la suite déduite de $x$, en réarrangeant les $x_{i_k}$ en ordre non décroissant. Alors il est possible d'associer à $x$, de façon bijective, une troisième suite $(x_{v_1}, x_{v_2}, \dots, x_{v_n})$ où $(v_1, v_2, \dots, v_n)$ est une permutation de $(i_1, i_2, \dots, i_n)$, telle qu'à tout $k \in [1, n]$ pour lequel $x_{i_k} < x_{j_k}$ correspond biunivoquement un $k' \in [1, n]$ tel que

$$x_{i_k} = x_{v_{k'} - 1} < x_{v_k'} = x_{j_k}.$$

La démonstration s'appuie encore sur les méthodes développées dans le chapitre 4. Nous montrons que tout sous-ensemble $U_f$ ($f \in \mathcal{X}^*$) contient un et un seul mot d'un certain sous-ensemble $\mathcal{H}_1$ de $\mathcal{Y}^*$, lui-même en correspondance biunivoque avec $\mathcal{X}^*$.

Une autre preuve de ce théorème est donnée dans le chapitre 8 ("Application des factorisations spéciales. Un théorème combinatoire non commutatif"), à partir de factorisations du monoïde $\mathcal{X}^*$ dites spéciales. Celles-ci forment une classe importante de factorisations de monoïdes libres étudiées par Schützenberger. En voici la définition :

Une factorisation spéciale d'un monoïde libre $\mathcal{X}^*$ engendré par un ensemble totalement ordonné $\mathcal{X}$ est la donnée d'un sous-ensemble $\mathcal{H}$ de mots de $\mathcal{X}^{**}$ et d'un ordre total $\leq$ sur $\mathcal{H}$ tels que d'une part $h, h' \in \mathcal{H}$ et $h \geq h'$ entraînent que la dernière lettre de $h$ est supérieure ou égale (pour l'ordre total de $\mathcal{X}$) à la première lettre de $h'$ et d'autre part que tout $f \in \mathcal{X}^{**}$ a une et une seule factorisation de la forme $f = h_1 h_2 \dots h_s$ ($s > 0$) où

$$h_1, h_2, \dots, h_s \in \mathcal{H} \text{ et } h_1 \geq h_2 \geq \dots \geq h_s.$$

Nous consacrons tout le chapitre 7 ("Factorisations spéciales") à leur étude. Une construction algébrique en est donnée par une méthode combinatoire utilisée aussi dans l'étude des algèbres de Lie
libres. Elle nous permet d'unifier les résultats de Lyndon sur la factorisation en mots lexicographiques standards et la factorisation définie par Spitzer en théorie des fluctuations de sommes de variables aléatoires. Lorsque $X = \mathbf{R}$, nous montrons, de plus, qu'à toute fonction continue monotone croissante est attachée une telle factorisation de $X^*$.

Dans le chapitre 9 ("Statistiques d'ordre. Formule de Spitzer"), nous montrons comment ces résultats combinatoires ont une interprétation naturelle en Calcul des Probabilités. Une identité est établie, ayant la même structure formelle que l'identité de Spitzer, et qui est valable pour une nouvelle famille de fonctions caractéristiques. De façon précise, nous avons (théorèmes 9.1 et 9.5).

Soit $X_1, X_2, \dots, X_n, \dots$ une suite de variables aléatoires en dépendance symétrique ; $X_1^*, X_2^*, \dots, X_n^*$ la statistique d'ordre de $X_1, X_2, \dots, X_n$ (c'est-à-dire la suite des $X_k$ rangés en ordre non décroissant ($1 \le k \le n$)) et $b : \mathbf{R}^2 \to \mathbf{R}$ une fonction mesurable telle que $b(x, x') = 0$ si $x \ge x'$. Alors, pour $n \ge 2$, les deux variables aléatoires

$$Y_n = \sum_{k=2}^{n} b(X_k, X_k^*) \quad \text{et} \quad Z_n = \sum_{k=2}^{n} b(X_{k-1}, X_k)$$

ont même distribution.

Si, en plus, les $X_k$ ($k \ge 1$) sont indépendantes et équidistri-buées, on a en posant

$$\varphi_n(t) = E \exp(it Y_n) = E \exp(it Z_n) \quad \text{pour } n \ge 2,$$

$$\varphi_o(t) = \varphi_1(t) = \psi_1(t) = 1 \quad \text{et}$$

$$\psi_k(t) = E \exp[it(b(X_1, X_2) + b(X_2, X_3) + \dots + b(X_{k-1}, X_k) + b(X_k, X_1))]$$

pour $k > 1$, l'identité

$$\sum_{n=0}^{\infty} \varphi_n(t) u^n = \exp \left[ \sum_{k=1}^{\infty} \frac{\psi_k(t)}{k} u^k \right]$$

($|u| < 1$ et $\text{Im}(t) \ge 0$).

A titre d'application, nous donnons enfin, dans le chapitre 10 ("Applications combinatoires. Formule de Dixon"), une nouvelle démonstration de certaines identités combinatoires contenant des coefficients binomiaux, comme l'identité de Dixon
$$ \sum_{k=0}^{2p} (-1)^k \left( \binom{2p}{k} \right)^3 = (-1)^p \frac{(3p)!}{(p!)^3} \quad (p \ge 0) $$

ou celle de Fjeldstad

$$ \sum_k (-1)^k \binom{b+c}{c+k} \binom{c+a}{a+k} \binom{a+b}{b+k} = \frac{(a+b+c)!}{a! b! c!} $$
(a, b, c entiers non négatifs).

Là encore, les mêmes méthodes permettent de donner une interprétation aux coefficients binomiaux apparaissant dans ces formules : nous montrons explicitement quels sont les objets qui sont comptés.

Je voudrais exprimer toute ma reconnaissance à M. le Professeur Dugué, à qui je dois de m'être intéressé très tôt aux problèmes combinatoires et qui n'a jamais cessé de me prodiguer conseils et encouragements.

Je remercie M. le Professeur Lichnerowicz d'avoir bien voulu présenter mes Notes aux Comptes-Rendus et d'avoir accepté de présider le Jury de cette thèse.

Je remercie également M. le Professeur Fortet de s'être intéressé à mon travail durant mon séjour au C. N. R. S. et d'avoir bien voulu accepté de faire partie du Jury.

Je voudrais exprimer enfin toute ma gratitude à M. le Professeur Schützenberger pour les précieuses indications qu'il n'a cessé, si gentiment, de me donner dans la poursuite de ce travail. Il est à l'origine de cette thèse, qui s'appuie, d'ailleurs, sur certains de ses travaux personnels.

Il m'est en outre très agréable de remercier MM. les Professeurs H. B. Mann et R. C. Bose qui m'ont aidé et encouragé dans mon travail durant mon séjour aux Etats-Unis.
1. 1928

2. 1930

3. 1932

4. 1934

5. 1936

6. 1938

7. 1940

8. 1942

9. 1944

10. 1946
## 2. Notations et préliminaires algébriques

Nous rappelons dans ce chapitre quelques notions algébriques qui seront utilisées par la suite et précisons nos notations.

En particulier, si $f: X \to Y$ est une application quelconque d'un ensemble X dans un ensemble Y, l'image par $f$ de $x \in X$ sera notée $fx$ au lieu de $f(x)$ s'il n'existe aucun risque de confusion.

De même, si $h$ est la composée de deux applications $f: X \to Y$ et $g: Y \to Z$, nous écrirons $gfx$ pour

$$g(f(x)) \quad (x \in X).$$

Les notions de calcul de probabilités que nous utiliserons au chapitre 9 seront indiquées au début dudit chapitre.

### 2.1. Monoïdes libres.

$\mathcal{X}$ étant un ensemble non vide, soit $\mathcal{X}^*$ l'ensemble des suites finies non vides $f = (x_{i_k})_{k \in K}$, où $K$ est un intervalle de $\mathbb{N}$ de la forme $[1, r]$. Une suite $f = (x_{i_k})_{k \in [1, r]}$ sera identifiée au monôme ou mot $x_{i_1} x_{i_2} \dots x_{i_r}$. Sous cette forme $x_{i_1}, x_{i_2}, \dots, x_{i_r}$ seront dits les lettres du mot $f$.

L'entier positif $r$ est le degré du monôme ou la longueur du mot $f$ ; on posera $r = \lambda f$. On convient aussi que l'ensemble vide $\emptyset$ forme un mot de $\mathcal{X}^*$, qu'on notera $1$, de longueur $\lambda 1 = 0$. Nous désignerons alors par $\mathcal{X}^{**}$ l'ensemble des mots de longueur positive.

L'ensemble $\mathcal{X}^*$ est muni d'une loi associative, le produit de juxtaposition qui à deux mots $f=x_{i_1} x_{i_2} \dots x_{i_r}$ et $f'=x_{i'_1} x_{i'_2} \dots x_{i'_r}$,
de $\mathcal{X}^*$ fait correspondre le produit $f^1 = x_{i_1} x_{i_2} \dots x_{i_{r+r'}}$, tel que $x_{i''_k} = x_{i_k}$ pour $k \in [1, r]$ et $x_{i''_k} = x_{i'_{k-r}}$ pour $k \in [r+1, r+r']$.

Cette loi est associative et admet le mot vide $1$ comme élé. ment unité. $\mathcal{X}^*$ muni de cette loi a alors une structure de monoïde, et le couple formé par $\mathcal{X}^*$ et le produit de juxtaposition qu'on notera encore $\mathcal{X}^*$ est appelé *monoïde libre engendré par* $\mathcal{X}^{(1)}$. On aura par la suite l'occasion de munir $\mathcal{X}^*$ d'autres structures de monoïde, et les monoïdes formés seront notés différemment $(\mathcal{X}_1^*, \mathcal{X}_2^*)$.

Remarquons tout de suite que $\lambda$ est un homomorphisme de $\mathcal{X}^*$ dans le monoïde additif des entiers. Les éléments de $\mathcal{X}^*$ de longueur $n$ ($n \ge 0$) constituent un sous-ensemble de $\mathcal{X}^*$ noté $\mathcal{X}_n^*$, le sous-ensemble $\mathcal{X}_1^*$ sera identifié à $\mathcal{X}$ et l'on supposera ainsi $\mathcal{X} \subset \mathcal{X}^*$.

Si $U$ est un sous-ensemble de $\mathcal{X}^*$ et $f_o \in \mathcal{X}^*$, $f_o U$ dési- gnera l'ensemble des mots $f$ de $\mathcal{X}^*$ tels que $f = f_o f_1$ où $f_1 \in U$.

Si $f = f_1 f_2 \dots f_s$ ($f_1, f_2, \dots, f_s \in \mathcal{X}^*$) ($s > 0$), on dira que chacun des $f_k$ ($1 \le k \le s$) est un *facteur* de $f$ ; on dira aussi que le produit $f_1 f_2 \dots f_s$ est une *factorisation* de $f$ ou que $f$ *factorise* en les $s$ mots $f_1, f_2, \dots, f_s$. Le facteur $f_1$ est appelé *facteur initial* de la factorisation.

Dans la suite, **P** (resp. **L**) désignera l'application qui au mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ de $\mathcal{X}^{++}$ fait correspondre sa première lettre $x = x_{i_1}$ (resp. sa dernière lettre $x = x_{i_r}$) soit

$$ \mathbf{P}f = x_{i_1} \quad \text{et} \quad \mathbf{L}f = x_{i_r}. $$

Deux mots $f$ et $f'$ de $\mathcal{X}^*$ sont dits *disjoints* s'ils n'ont aucune lettre en commun et *conjugués* s'il existe $f_1, f_2 \in \mathcal{X}^*$ tels que $f = f_1 f_2$ et $f' = f_2 f_1$. Enfin, un mot $f$ de $\mathcal{X}^*$ est *primitif* si l'on ne peut avoir $f = f'^p$, $f' \in \mathcal{X}^{++}$ pour $p > 1$ et dans ce cas les mots conjugués à $f$ sont aussi primitifs. On parlera ainsi de classe primitive d'éléments conjugués.

<footnote>(1) De cette façon, nous ne définissons en fait qu'un modèle pour le monoïde libre engendré par $\mathcal{X}$ (Cf. Chevalley (C.): *Fundamental Concepts of Algebra*. Academic Press, New York (1956), pp. 18-19).</footnote>
## 2.2. Monoïdes abéliens libres.

Ici encore, nous ne définirons qu'un modèle pour le monoïde abélien libre engendré par un ensemble donné $\mathcal{X}$.

On appelle monoïde abélien libre engendré par un ensemble $\mathcal{X}$ l'ensemble des applications $h : \mathcal{X} \to \mathcal{N}$ telles que $hx = 0$ sauf pour un nombre fini de $x \in \mathcal{X}$, muni de l'addition induite par celle de $\mathcal{N}\mathcal{X}$, que nous noterons $\oplus$.

Cet ensemble est bien stable pour l'addition dans $\mathcal{N}\mathcal{X}$ et celle-ci est évidemment associative. Ce monoïde sera noté $\bar{\mathcal{X}}^*$. L'application nulle est l'élément unité de $\bar{\mathcal{X}}^*$.

Nous désignons par $\alpha$ l'homomorphisme canonique de $\mathcal{X}^*$ sur $\bar{\mathcal{X}}^*$; c'est l'homomorphisme qui fait correspondre à $f = x_{i_1} x_{i_2} \dots x_{i_r}$ de $\mathcal{X}^*$ l'application $\alpha f$ de $\bar{\mathcal{X}}^*$ définie par

$$ (\alpha f)(x) = \text{nombre d'indices } k \text{ tels que } x_{i_k} = x \quad (1 \le k \le r) \text{ pour tout } x \in \mathcal{X}; $$

et au mot unité, l'application nulle.

On posera encore $\bar{\mathcal{X}}^{**} = \alpha \mathcal{X}^{**}.$

Pour $f \in \mathcal{X}^*$, $\alpha f \in \bar{\mathcal{X}}^*$ sera appelé l'image abélienne de $f$ et pour $h \in \bar{\mathcal{X}}^*$, $\alpha^{-1}h \in \mathcal{P}(\mathcal{X}^*)$ sera la classe abélienne de $h$. Tous les mots d'une même classe abélienne $\alpha^{-1}h$ ont même longueur et on posera $\lambda h = \lambda f$ pour un $f$ quelconque de $\alpha^{-1}h$.

Un élément $h \in \bar{\mathcal{X}}^*$ sera dit multilinéaire [en abrégé $h \in \overline{\mathcal{M}}$] si $hx \le 1$ pour tout $x \in \mathcal{X}$. On posera $\overline{\mathcal{M}} = \alpha^{-1} \overline{\mathcal{M}} \in \mathcal{P}(\mathcal{X}^*)$ et si $f \in \overline{\mathcal{M}}$, on dira encore que $f$ est multilinéaire.

## 2.3. Mots non décroissants.

Lorsque $\mathcal{X}$ est muni d'une structure d'ordre total, nous sommes tout naturellement conduits à introduire la notion de mots non décroissants.

Supposons désormais que $\mathcal{X}$ est totalement ordonné ; alors un mot $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{X}^{**}$ est dit non décroissant si $x_{i_1} \le x_{i_2} \le \dots \le x_{i_r}$ pour l'ordre total $\le$ dans $\mathcal{X}$.

Pour $h \in \bar{\mathcal{X}}^{**}$ nous désignerons par $\mathcal{N}(h)$ la suite croissante $(x_{u_1}, x_{u_2}, \dots, x_{u_d})$ des $d = \dim h$ lettres $x$ de $\mathcal{X}$ pour lesquelles $hx > 0$. Posons

tel +r'].

éléïde, qu'on On es de (x*)

désiré U.

que� i que fac- appelé

qui au mière

s n'ont pas tels rimitif ce cas

non oïde algebra.
$$hx_{u_t} = n_t \quad (1 \le t \le d) \quad \text{et} \quad r = \sum_{t=1}^{d} n_t.$$

Alors le mot

$$\beta'h = x_{u_1}^{n_1} x_{u_2}^{n_2} \dots x_{u_d}^{n_d}$$

est non décroissant et est le seul mot non décroissant de la classe abélienne $\alpha^{-1}h$.

De là $\beta = \beta'\alpha$ sera une application de $\mathcal{X}^*$ sur l'ensemble de ses mots non décroissants et pour $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{X}^{**}$ on écrira le mot non décroissant $\beta f$ de la classe abélienne de $f$ sous la forme $\beta f = x_{j_1} x_{j_2} \dots x_{j_r}$.

Faisons aussi la convention $\beta 1 = 1$. Nous définirons encore pour $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \alpha^{-1}h$ et $k \in [1, r]$, $\gamma_k f = (\alpha x_{i_1} x_{i_2} \dots x_{i_k}) (x_{i_k}) \in \mathbb{N}$.

$\gamma_k f$ nous servira à indiquer les lettres égales à l'intérieur d'un même mot ; c'est le nombre de lettres égales à $x_{i_k}$ dans le facteur initial $x_{i_1} x_{i_2} \dots x_{i_k}$ de $f$.

## 2.4. Algèbre large d'un monoïde.

Nous présenterons certains résultats combinatoires sous la forme d'identités dans des algèbres larges de monoïdes libres.

Nous rappelons ici cette notion. Soit toujours $\mathcal{X}^*$ le monoïde libre engendré par un ensemble $\mathcal{X}$ et $\Omega$ un anneau commutatif (unitaire). Considérons le module produit $\Omega^{\mathcal{X}^*}$ des familles $(a_f)_{k \in \mathcal{X}^*}$ d'éléments de $\Omega$. Nous écrirons ces familles sous forme de séries formelles $\Sigma\{\text{faf} : f \in \mathcal{X}^*\}$ qu'on munit d'une opération-produit en posant

$$\Sigma \{ \text{faf} : f \in \mathcal{X}^* \}. \Sigma \{ \text{fa}'f : f \in \mathcal{X}^* \} = \Sigma \left\{ f \sum_{f_1 f_2 = f} a_{f_1} a'_{f_2} : f \in \mathcal{X}^* \right\}. (2.4.1)$$

La somme $\sum_{f_1 f_2 = f} a_{f_1} a'_{f_2}$ est une somme dans l'anneau $\Omega$ qui porte sur un nombre fini de termes puisqu'il n'y a pour tout $f \in \mathcal{X}^*$ qu'un nombre fini de couples $(f_1, f_2)$ d'éléments de $\mathcal{X}^*$ tels que $f_1 f_2 = f$. (Propriété (D) de Bourbaki (1)).

<footnote>(1) Bourbaki (N.). - Algèbre L. II, chap. 2 (Algèbre Linéaire). Hermann, Paris (1955), p. 114.</footnote>
Le module $\mathfrak{X}^*$ muni de cette multiplication devient une algèbre qu'on notera $\mathfrak{A} = \mathfrak{O}[[\mathfrak{X}^*]]$ et qui est l'algèbre large du monotde libre $\mathfrak{X}^*$. Dans la série formelle $\mathfrak{S}\{\mathrm{faf} : f \in \mathfrak{X}^*\}$, l'élément de $\mathfrak{O}$ est dit coefficient de $f$. On construit de même l'algèbre large $\bar{\mathfrak{A}} = \mathfrak{O}[[\bar{\mathfrak{X}}^*]]$ du monoïde $\bar{\mathfrak{X}}^*$ car lui aussi vérifie la propriété (D) qui s'énonce ainsi

il n'y a qu'un nombre fini de couples $(h_1, h_2)$ d'éléments de $\bar{\mathfrak{X}}^*$ tels que $h_1 \oplus h_2 = h$ pour tout $h \in \bar{\mathfrak{X}}^*$.

Nous prolongeons d'abord l'homomorphisme canonique $\alpha : \mathfrak{X}^* \to \bar{\mathfrak{X}}^*$ à un homomorphisme de $\mathfrak{A}$ sur $\bar{\mathfrak{A}}$ que nous noterons encore $\alpha$, défini pour $\mathfrak{S}\{\mathrm{faf} : f \in \mathfrak{X}^*\} \in \mathfrak{A}^*$ par

$$ \alpha \mathfrak{S}\{\mathrm{faf} : f \in \mathfrak{X}^*\} = \mathfrak{S}\{\bar{\mathrm{h}}\mathrm{a}\mathrm{h} : h \in \bar{\mathfrak{X}}^*\} \quad (2.4.2) $$

$$ \text{avec } \bar{\mathrm{a}}\mathrm{h} = \sum_{f \in \alpha^{-1}h} \mathrm{af}. $$

Vérifions, en particulier, que $\alpha$ est un homomorphisme pour la multiplication dans les deux algèbres.

Soit $\mathfrak{a}_i = \mathfrak{S}\{\mathrm{fa}_i f : f \in \mathfrak{X}^*\}$ (i = 1, 2) deux éléments de $\mathfrak{A}$. Nous allons vérifier que pour tout $h$ le coefficient de $h$ dans les séries $\alpha \mathfrak{a}_1, \alpha \mathfrak{a}_2$ et $\alpha (\mathfrak{a}_1, \mathfrak{a}_2)$ est le même et égal à

$$ \sum_{\alpha(f_1 f_2)^h = h} \alpha_1 f_1 . \alpha_2 f_2 . $$

Posons

$$ \bar{\mathfrak{a}}_i = \alpha \mathfrak{a}_i = \mathfrak{S}\{\bar{\mathrm{h}}\mathrm{a}_i h : h \in \bar{\mathfrak{X}}^*\} \quad (i = 1, 2). $$

Alors

$$ \bar{\mathrm{a}}_i h = \sum_{f \in \alpha^{-1}h} a_i f \quad (i = 1, 2). $$

Ainsi le coefficient de $h$ dans $\bar{\mathfrak{a}}_1, \bar{\mathfrak{a}}_2$ est égal à

$$ \begin{aligned} \sum_{h_1 \oplus h_2 = h} \bar{\mathfrak{a}}_1 h_1 . \bar{\mathfrak{a}}_2 h_2 &= \sum_{h_1 \oplus h_2 = h} \left( \sum_{f_1 \in \alpha^{-1}h_1} a_1 f_1 \right) \left( \sum_{f_2 \in \alpha^{-1}h_2} a_2 f_2 \right) = \\ &= \sum_{\alpha(f_1 f_2)^h = h} a_1 f_1 . a_2 f_2 \end{aligned} $$

De même le coefficient de $f$ dans $\mathfrak{a}_1, \mathfrak{a}_2$ est

<figure><img src="image_3.png" /></figure>
$$ \sum_{f_1 f_2 = f} a_1 f_1 \cdot a_2 f_2 $$

et le coefficient de h dans $\alpha(a_1 \cdot a_2)$ est alors

$$ \sum_{f \in a^{-1}h} \sum_{f_1 f_2 = f} a_1 f_1 \cdot a_2 f_2 $$

soit

$$ \sum_{\alpha(f_1 f_2) = h} a_1 f_1 \cdot a_2 f_2 \cdot $$

Lorsque $\mathcal{X}$ est fini, $\mathcal{X} = \{x_1, x_2, \dots, x_n\}$ ($n > 0$), il sera bon de considérer pour tout $k \in [1, n]$ l'application $X_k : \mathcal{X} \to \mathcal{X}$ telle que

$$ \begin{cases} X_k(x) = 1 & \text{si } x = x_k \\ = 0 & \text{si } x \neq x_k. \end{cases} $$

La base canonique de $\bar{\alpha} = \Omega[[\bar{\mathcal{X}}^*]]$ sera alors identifiée à l'ensemble formé par les produits

$$ F = X_{i_1}^{n_1} X_{i_2}^{n_2} \dots X_{i_r}^{n_r} \quad (1 \le i_1 < i_2 < \dots < i_r \le n) $$

où $n_{i_1}, n_{i_2}, \dots, n_{i_r}$ sont des entiers positifs et par l'élément unité de $\Omega$.

Si $F'$ et $F''$ sont deux tels éléments écrits sous la forme

$$ F' = X_1^{n'_1} X_2^{n'_2} \dots X_n^{n'_n} \quad \text{et} \quad F'' = X_1^{n''_1} X_2^{n''_2} \dots X_n^{n''_n} $$

où les $n'_k$ et $n''_k$ sont des entiers $\ge 0$, on posera

$$ F \oplus F' = X_1^{n'_1+n''_1} X_2^{n'_2+n''_2} \dots X_n^{n'_n+n''_n} $$

Les $X_k$ ($1 \le k \le n$) seront appelés les indéterminés de l'al. gèbre $\bar{\alpha}$.

Soit $\mathbf{a} = \sum \{ \text{faf} : f \in \mathcal{X}^* \}$ une série formelle de $\mathcal{A}$ et soit $\mathcal{U}$ un sous-ensemble de $\mathcal{X}^*$ ; on notera par $\sum \{ \text{faf} : f \in \mathcal{U} \}$ la série $\sum \{ \text{fbf} : f \in \mathcal{X}^* \}$ telle que $\text{bf} = \text{af}$ pour $f \in \mathcal{U}$ et $\text{bf} = 0$ pour $f \notin \mathcal{U}$. En particulier, $\sum \{ \text{faf} : f \in \mathcal{X}_n^* \}$ sera défini comme la com-
posante homogène de degré $n$ de $\mathbf{a}$ ($n \ge 0$) et si $\mathbf{a} \neq 0$, l'ordre de
a, noté $oa$, est défini comme le plus petit des entiers $n \ge 0$ tels que la composante homogène de degré $n$ de $a$ soit $\ne 0$. On posera aussi $\mathbf{0} = +\infty$.

Si $a$ et $a'$ sont deux séries formelles de $\mathcal{A}$, on a

$$ \mathbf{o}(a+a') \ge \min\{\mathbf{o}a, \mathbf{o}a'\} \qquad (2.4.3) $$

$$ \mathbf{o}(a a') \ge \mathbf{o}a + \mathbf{o}a'. \qquad (2.4.4) $$

Nous avons des définitions analogues pour $\bar{\mathcal{A}}$. Remarquons en plus que si $\mathbf{o}$ désigne aussi l'ordre d'une série formelle dans $\bar{\mathcal{A}}$, par définition de l'homomorphisme $\alpha$ nous avons pour tout $a \in \bar{\mathcal{A}}$

$$ \mathbf{o} \alpha a \ge \mathbf{o} a. \qquad (2.4.5) $$

## 2.5. Topologie des séries formelles.

La topologie des séries formelles est définie à partir de l'ordre (Cf. Zariski et Samuel : "Commutative Algebra" vol. 2, Van Nostrand, New York, 1960, Pages 132-134) et les résultats sur les algèbres larges de monoïde abélien s'étendent de manière naturelle aux algèbres larges de monoïde non commutatif.

Soit $\mathcal{A}_n$, l'ensemble des séries de $\mathcal{A}$ d'ordre $\ge n$. Les relations (2.4.3) et (2.4.4) entraînent alors que pour tout $n \ge 0$, $\mathcal{A}_n$ est un idéal dans $\mathcal{A}$ et que $\mathcal{A}_n \subset \mathcal{A}_m$ pour $m \le n$ ; d'où $\bigcap_{n=1}^{\infty} \mathcal{A}_n = \{0\}$.

La topologie qu'on prendra sur $\mathcal{A}$ est la topologie pour laquelle l'élément $\mathbf{o}$ a pour base de voisinages les idéaux $\mathcal{A}_n$ ($n \ge 0$) et $\mathcal{A}$ devient alors un anneau topologique. Pour cette topologie, toute série $\sum_{n=1}^{\infty} a_n$ où $\mathbf{o}a_n \longrightarrow +\infty$, converge vers un élément $\mathbf{a} \in \mathcal{A}$.

En particulier, si $\mathbf{a}$ est une série formelle de $\mathcal{A}$ de composante homogène nulle ou encore si $\mathbf{a} = \sum (\text{faf} : f \in \mathcal{X}^{*+})$ alors la série $1 + \sum \{\mathbf{a}^n : n > 0\}$ converge et est justement l'inverse de la série formelle $(1 - \mathbf{a})$.

Soit

$$ (1 - \mathbf{a})^{-1} = 1 + \sum \{\mathbf{a}^n : n > 0\} \qquad (2.5.1) $$

pour $\mathbf{a} \in \mathcal{A}_1$.
Nous avons de même

$$ (1 - \alpha \mathbf{a})^{-1} = 1 + \sum \{\alpha \mathbf{a}^n : n > 0\} \qquad (2.5.2) $$

pour $\mathbf{a} \in \mathcal{A}_1$, à cause de la relation (2.4.5) et du fait que $\alpha$ est un homomorphisme.

Pour $k > 0$, la série formelle de $\overline{\mathcal{A}}$,

$$ \alpha \sum \{\mathbf{a}^n : n > k\} - \sum \{\alpha \mathbf{a}^n : n > k\} $$

est d'ordre $> k$. Elle converge donc vers 0 lorsque $k \to +\infty$. Nous avons ainsi

$$ \alpha \sum \{\mathbf{a}^n : n > 0\} = \sum \{\alpha \mathbf{a}^n : n > 0\}. $$

Soit

$$ \alpha (1 - \mathbf{a})^{-1} = (1 - \alpha \mathbf{a})^{-1} \qquad (2.5.3) $$

pour tout $\mathbf{a} \in \mathcal{A}_1$.

Remarque.

(2.5.4)

Cette relation est encore satisfaite si l'ensemble des mots de $\mathcal{X}^*$ est muni d'une autre opération associative $\Gamma$, distincte du produit de juxtaposition, mais telle que pour tout $\mathbf{f}, \mathbf{f}' \in \mathcal{X}^*$

$$ \alpha (\Gamma \mathbf{f} \mathbf{f}') = \alpha (\mathbf{f} \mathbf{f}') . \qquad (2.5.5) $$

En effet, nous reportant à la formule (2.4.2), il nous suffit seulement de vérifier que $\alpha$ est un homomorphisme pour les multiplications de l'algèbre large $\Omega[[\mathcal{X}^*]]$ du monoïde $(\mathcal{X}^*, \Gamma)$ et de l'algèbre $\Omega[[\mathcal{X}^*]]$.

Or, nous avons montré que si $\mathbf{a}_i = \sum \{\mathbf{fa}_i \mathbf{f} : \mathbf{f} \in \mathcal{X}^*\}$ ($i = 1, 2$) sont deux éléments de $\mathcal{A}$, le coefficient de $\mathbf{h}$ ($\mathbf{h} \in \overline{\mathcal{X}^*}$) dans les séries $\alpha \mathbf{a}_1, \alpha \mathbf{a}_2$ et $\alpha(\mathbf{a}_1, \mathbf{a}_2)$ était le même et égal à

$$ \sum_{\alpha (\mathbf{f}_1 \mathbf{f}_2) = \mathbf{h}} \mathbf{a}_1 \mathbf{f}_1 . \mathbf{a}_2 \mathbf{f}_2 . $$

D'après (2.5.5) ce coefficient est aussi

$$ \sum_{\alpha (\mathbf{f}_1 \mathbf{f}_2) = \mathbf{h}} \mathbf{a}_1 \mathbf{f}_1 . \mathbf{a}_2 \mathbf{f}_2 $$

et ainsi $\alpha(\mathbf{a}_1 \cdot \mathbf{a}_2) = \alpha \mathbf{a}_1$. $\alpha \mathbf{a}_2$ où $\Gamma$ désigne la multiplication de l'algèbre $\Omega[[\mathcal{X}^*]]$.
# 3. Une identité combinatoire non commutative

## 3.1. Introduction.

Ce chapitre a un double but : d'abord de définir sur l'ensemble $\mathcal{X}^*$ des mots d'un monoïde libre engendré par un ensemble totale- ment ordonné $\mathcal{X}$ une nouvelle structure de monoïde notée $\mathcal{X}_\Gamma^*$ (proposition 3.1), puis de démontrer une identité combinatoire dans l'algèbre large $\Omega [[\mathcal{X}_\Gamma^*]]$ de ce nouveau monoïde, relative à un an- neau $\Omega$ (formule 3.3.2). Si l'on désigne par $\alpha$ l'homomorphisme canonique de cette algèbre sur l'algèbre large $\Omega [[\overline{\mathcal{X}}^*]]$ du monoïde abélien libre $\overline{\mathcal{X}}^*$, on retrouve, pour $\mathcal{X}$ fini, l'identité du "Master Theorem" de Mac Mahon en prenant l'image par $\alpha$ des deux membres de cette identité.

En outre, pour $\mathcal{X}$ infini, l'image par $\alpha$ donnera le "Master Theorem" pour une infinité de variables commutatives.

Les méthodes combinatoires développées dans ce chapitre n'utilisent la cardinalité de $\mathcal{X}$ et explicitent en particulier le ré- sultat de Mac Mahon.

Signalons enfin que la preuve de l'identité (3.3.2) dans l'algèbre non commutative $\Omega [[\mathcal{X}_\Gamma^*]]$ ne sera complétée qu'au chapitre suivant.

## 3.2. Le monoïde d'intercalement $\mathcal{X}_\Gamma^*$.

Désormais nous supposons que $\mathcal{X}$ est un ensemble totale- ment ordonné quelconque et que $\Omega$ est un anneau commutatif (uni- taire), non réduit à 0.

Nous formons d'abord le monoïde $\mathcal{X}^*$ et définissons sur l'ensemble des éléments (mots) de $\mathcal{X}^*$ une autre loi de composi- tion $\Gamma$, telle que le couple $(\mathcal{X}^*, \Gamma)$ soit un monoïde qu'on notera $\mathcal{X}_\Gamma^*$ et telle que l'on ait
$$ \alpha (f \upharpoonright f') = \alpha(ff') = \alpha f + \alpha f' \in \bar{\mathcal{X}}^* $$

pour tout $f, f' \in \mathcal{X}^*$. En effet, soit $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{X}^{**}$ et $h \in \bar{\mathcal{X}}^*$ tel que

$$ (\alpha f)(x) \leq hx \quad (x \in \mathcal{X}). \qquad (3.2.1) $$

Désignons par $x_{u_1}, x_{u_2}, \dots, x_{u_d}$ ($x_{u_1} < x_{u_2} < \dots < x_{u_d}$) les h = dim h lettres x de $\mathcal{X}^*$ pour lesquelles h(x) > 0 ; posons $K_o = 0$

$$ K_v = (\alpha f)(x_{u_1}) + (\alpha f)(x_{u_2}) + \dots + (\alpha f)(x_{u_v}) \quad (1 \le v \le d). $$

Alors $f$ factorise en $d$ mots, à savoir

$$ f = f_1 f_2 \dots f_d $$

si l'on pose

$$ \begin{aligned} f_v &= 1 \quad (\text{mot unité}) \quad \text{si} \quad (\alpha f)(x_{u_v}) = 0 \\ &= x_{i_{K_v-1}+1} x_{i_{K_v-1}+2} \dots x_{i_{K_v}} \quad \text{si} \quad (\alpha f)(x_{u_v}) > 0 \end{aligned} \quad (1 \le v \le d). $$

Nous dirons alors que $f_1 f_2 \dots f_d$ est une factorisation de $f$ suivant $h$. Lorsque $f$ est non décroissant, alors

$$ f_v = x_{u_v}^{(\alpha f)(x_{u_v})} \quad (1 \le v \le d). $$

En particulier, deux mots $f$ et $f'$ de $\mathcal{X}^{**}$ factorisent tous deux suivant $h = \alpha(ff')$ puisque

$$ \alpha(ff') = \alpha(f) + \alpha(f') $$

d'où

$$ (\alpha f)(x) (\text{resp. } (\alpha f')(x)) \le h(x) \quad (x \in \mathcal{X}). $$

Si donc $d = \dim \alpha(ff')$ et si $f = f_1 f_2 \dots f_d$ et $f' = f'_1 f'_2 \dots f'_d$ sont les deux factorisations de $f$ et $f'$ suivant $\alpha(ff')$, on pose

$$ f \upharpoonright f' = f_1 f'_1 f_2 f'_2 \dots f_d f'_d. \qquad (3.2.2) $$

On peut dire qu'on a intercalé de façon canonique les lettres de $f'$ dans les lettres de $f$, tout en conservant leur ordre. Comme on démontre ci-dessous que $\upharpoonright$ est une opération associative, $\mathcal{X}^*$ sera appelé *le monoïde d'intercalement*.
Par définition, on posera aussi

$$1 \Gamma f = f \Gamma 1 = f$$

pour tout $f \in \mathcal{X}^*$.

*Exemple* - Si $f$ = cada et $f' = bcd$ sont deux mots du monoïde libre engendré par l'ensemble ordonné $(a < b < c < d)$, alors

$f_1 = \text{ca}, f_2 = 1 \text{ (mot unité)},$

$f_3 = d, f_4 = a,$

$f'_1 = 1, f'_2 = bc$

$f'_3 = b, f'_4 = 1$

et

$$f \Gamma f' = f_1 f'_1 f_2 f'_2 f_3 f'_3 f_4 f'_4 = cabcdba$$

**PROPOSITION 3.1.** - L'ensemble $\mathcal{X}^*$ muni de la loi de composition $\Gamma$ est un monoïde non commutatif (on le note $\mathcal{X}_\Gamma^*$).

PREUVE.- Il nous faut vérifier que l'opération $\Gamma$ est associative. Soit donc $f, f'$ et $f''$ trois mots de $\mathcal{X}^*$. Posons $h = \alpha(ff'f'')$ et $N(h) = \{x_{u_1}, x_{u_2}, \dots, x_{u_d}\}$ (Cf. § 2.3).

Nous désignons par $f_1, f_2, \dots, f_d, f'_1, f'_2, \dots, f'_d$ et $f''_1, f''_2, \dots, f''_d$ les factorisations de $f, f'$ et $f''$ suivant $h$. Les factorisations de $f$ et $f'$ suivant $\alpha(ff')$ sont alors

$$f_{p_1} f_{p_2} \dots f_{p_s} \text{ et } f'_{p_1} f'_{p_2} \dots f'_{p_s}$$

où $p_1, p_2, \dots, p_s$ est une suite croissante de l'intervalle $[1, d]$. (Un entier $p$ appartient à $[1, d] - \{p_1, p_2, \dots, p_s\}$ si et seulement si $(\alpha ff')(x_{u_p}) = 0$. De là, par définition de $\Gamma$ (formule 3.3.2)), nous avons

$$f \Gamma f' = f_{p_1} f'_{p_1} f_{p_2} f'_{p_2} \dots f_{p_s} f'_{p_s}$$

Posons maintenant $f_p = f'_p = 1$ pour tout $p \in [1, d]$ tel que $(\alpha ff')(x_{u_p}) = 0$.

Nous pouvons écrire alors

$$f \Gamma f' = f_1 f'_1 f_2 f'_2 \dots f_d f'_d$$

et $(f'_1 f'_1) (f_2 f'_2) \dots (f_d f'_d)$ est justement la factorisation de $f \Gamma f'$ suivant $h$.
De là, par définition de $\Gamma$, nous avons

$$ (f \Gamma f') f'' = ((f_1 f'_1) f''_1) ((f_2 f'_2) f''_2) \dots ((f_d f'_d) f''_d) \\ = (f_1 (f'_1 f''_1)) (f_2 (f'_2 f''_2)) \dots (f_d (f'_d f''_d)) $$

et comme on montre de la même façon que

$$ f' \Gamma f'' = f'_1 f''_1 f'_2 f''_2 \dots f'_d f''_d, $$

nous avons bien

$$ (f \Gamma f') \Gamma f'' = f \Gamma (f' \Gamma f''). $$

### 3.3. Une identité combinatoire non commutative.

Le monoïde $X_\Gamma^*$ satisfait lui aussi à la propriété (D) (Cf. § 2.4) et l'on peut former son algèbre large $\Omega[[X_\Gamma^*]]$ relative à $\Omega$. Nous donnerons dans ce paragraphe une identité combinatoire dans cette algèbre. Nous verrons que la cardinalité de $X$ n'intervient pas. Il nous faut seulement supposer $X$ totalement ordonné.

Donnons d'abord quelques définitions.

Soit $f = x_{i_1} x_{i_2} \dots x_{i_r}$ un mot multilinéaire de $X^*$ ($f \in \mathfrak{M}$) et $\beta f = x_{j_1} x_{j_2} \dots x_{j_r}$ le mot non décroissant qui lui est associé.

Soit $\varepsilon_f$ l'indice de la permutation $x_{j_k} \to x_{i_k}$ ($1 \le k \le r$) de l'ensemble $\{x_{j_1}, x_{j_2}, \dots, x_{j_r}\}$.

On désigne alors par $\zeta$ l'application $\zeta : \mathfrak{M} \to \{+1, -1\}$ qui a $f$ fait correspondre $\zeta f = \varepsilon_f (-1)^{\lambda f + 1}$.

Soit d'autre part $b : X^2 \to \Omega$ une application fixe.

Posons pour chaque $f = x_{i_1} x_{i_2} \dots x_{i_r} \in X^{**}$,

$$ \forall f = b(x_{j_1}, x_{i_1}) b(x_{j_2}, x_{i_2}) \dots b(x_{j_r}, x_{i_r}) \quad (3.3.1) $$

où $x_{j_1} x_{j_2} \dots x_{j_r}$ est le mot non décroissant $\beta f$ de la classe abélienne de $f$ (Cf. § 2.3) et $\forall f = 1$ si $f = 1$ (mot unité).

Nous avons alors le résultat suivant

THEOREME 3.1. - $\forall : X_\Gamma^* \to \Omega$ est un homomorphisme de $X_\Gamma^*$ dans le monoïde multiplicatif de $\Omega$ et dans l'algèbre large $\Omega[[X_\Gamma^*]]$, on a l'identité
$$ (1 - \Sigma \{f. \zeta f. \nu f : f \in \mathfrak{m}\})^{-1} = \Sigma \{f. \nu f : f \in \mathfrak{x}^*\} \quad (3.3.2) $$

PREUVE.- Vérifions d'abord que $v$ est un homomorphisme. Pour cela, posons pour deux mots $f = x_{i_1} x_{i_2} \dots x_{i_r}$ et

$$ f' = x_{i'_1} x_{i'_2} \dots x_{i'_r} \in \mathfrak{x}^{**} $$

de même longueur $\lambda f = \lambda f' = r$,

$$ B(f', f) = b(x_{i'_1}, x_{i'_2}) b(x_{i'_2}, x_{i'_2}) \dots b(x_{i'_r}, x_{i'_r}) $$

$$ \text{et } B(f, f') = 1 $$

$$ \text{si } f = f' = 1 \quad (\text{mot unité}). $$

Nous avons ainsi pour tout $f \in \mathfrak{x}^*$,

$$ \nu f = B(\beta f, f). $$

Soit $f=f_1\dots f_d$ et $f'=f'_1\dots f'_d$ les factorisations de deux mots $f$ et $f' \in \mathfrak{x}^{**}$ suivant $\alpha(\overline{f'f})$, et de même $\beta f = \overline{f'_1}\dots\overline{f'_d}$ et $\beta f' = \overline{f'_1}\dots\overline{f'_d}$ les factorisations des mots non décroissants $\beta f$ et $\beta f'$ qui leur sont associés.

Par définition de la fonction $v$, nous avons

$$ \nu f = B(\overline{f_1}, f_1) B(\overline{f_2}, f_2) \dots B(\overline{f_d}, f_d) $$

$$ \nu f' = B(\overline{f'_1}, f'_1) B(\overline{f'_2}, f'_2) \dots B(\overline{f'_d}, f'_d). $$

Mais d'autre part

$$ \beta (f \tau f') = \overline{f_1 f'_1 f_2 f'_2} \dots \overline{f_d f'_d} = \beta f \tau \beta f' $$

et

$$ f \tau f' = f_1 f'_1 f_2 f'_2 \dots f_d f'_d. $$

D'où

$$ v(f \tau f') = B(\beta(f \tau f'), f \tau f') = $$

$$ = B(\overline{f_1}, f_1) B(\overline{f'_1}, f'_1) B(\overline{f_2}, f_2) B(\overline{f'_2}, f'_2) \dots B(\overline{f_d}, f_d) B(\overline{f'_d}, f'_d) $$

$$ = B(\overline{f_1}, f_1) B(\overline{f_2}, f_2) \dots B(\overline{f_d}, f_d) B(\overline{f'_1}, f'_1) B(\overline{f'_2}, f'_2) \dots B(\overline{f'_d}, f'_d) $$

$$ = \nu f . \nu f' . $$
lytiques à plusieurs variables complexes établi par lui également [16]. Ce théorème lui permet de donner une démonstration courte et élégante du théorème de Mac Mahon en interprétant le déterminant D comme le jacobien d'une certaine transformation. Là encore, on ne peut par ces méthodes expliciter le résultat ou encore étudier le cas d'une infinité de variables.

Nous nous proposons dans cette section de reformuler ce théorème et de montrer qu'il affirme qu'une certaine identité est valable dans une algèbre commutative (formule 3.4.2). Ceci nous permettra d'établir la transition entre les cas non commutatif et commutatif, c'est-à-dire d'indiquer comment on passe de l'identité (3.3.1) du théorème 3.1 à l'identité (3.4.2) du "Master Theorem". Nous verrons enfin que l'opération $\Gamma$ du paragraphe 3.2 s'introduit de façon naturelle et que le "Master Theorem" est encore valable pour une infinité de variables commutatives.

Reprenons les hypothèses du théorème 3.2, en supposant que les coefficients $b_{k,l}$ ($1 \le k, l \le n$) sont pris dans un anneau commutatif (unitaire) $\Omega$ non réduit à 0. $X$ étant alors un ensemble de n éléments ($n > 0$) $X = \{x_1, x_2, \dots, x_n\}$, nous désignons par $\bar{\alpha}$ et $\bar{\alpha}^*$ les algèbres larges des monoïdes libre $X^*$ et abélien libre $\bar{X}^*$ engendrés par $X$ et nous considérons que les n indéterminés $X_1, X_2, \dots, X_n$ du théorème 3.2 sont les n indéterminés de l'algèbre $\bar{\alpha}$. (Cf. § 2.4). Dans ces conditions, $a_1, a_2, \dots, a_n$ sont n éléments de $\bar{\alpha}$ et nous notons par $\overline{\nu : X \longrightarrow \Omega}$ l'application qui à $h = X_1^{c_1} X_2^{c_2} \dots X_n^{c_n} \in \bar{X}^*$ fait correspondre le coefficient de $h$ dans $a_1^{c_1} a_2^{c_2} \dots a_n^{c_n}$. Nous posons aussi $\overline{\nu 1} = 1$. Il sera enfin commode de considérer les coefficients $b_{k,l}$ comme les images des couples $(x_k, x_l)$ par une certaine application fixe $b : X^2 \longrightarrow \Omega$, soit

$$b_{k,l} = b(x_k, x_l) \quad (1 \le k, l \le n).$$

Le déterminant $D$ où $D$ est donné par la formule (3.4.1) est un certain élément de $\bar{\alpha}$ qui est inversible dans $\bar{\alpha}$. Le "Master Theorem" affirme alors

Dans l'algèbre large $\Omega$ $[[\bar{\bar{X}}^*]]$ on a l'identité

$$\Sigma \{ h. \overline{\nu} h : h \in \bar{\bar{X}}^* \} = D^{-1} \quad (3.4.2)$$

Nous allons maintenant donner une forme plus symétrique à cette identité. D'abord le déterminant $D$ de la formule (3.4.1) peut encore s'écrire

$$D = 1 + \sum_{r=1}^{n} (-1)^r \sum_{1 \le j_1 < j_2 < \dots < j_r \le n} X_{j_1} X_{j_2} \dots X_{j_r} \det (b_{j,j'} \epsilon_{\{j_1,j_2,\dots,j_r\}}) \quad (3.4.3)$$
où la somme $\sum_{1 \le j_1 < j_2 < \dots < j_r \le n}$ est étendue, pour $r$ fixé $\in [1, n]$, à toutes les suites croissantes $j_1, j_2, \dots, j_r$ de r entiers extraites de $[1, n]$. Pour toute suite croissante $(j_1, j_2, \dots, j_r)$ extraite de $[1, n]$, notons par $\sigma_{j_1 j_2 \dots j_r}$ le groupe symétrique opérant sur $\{j_1, j_2, \dots, j_r\}$. Le mot $X_{j_1} X_{j_2} \dots X_{j_r}$ étant multilinéaire, la classe abélienne $\alpha^{-1}(X_{j_1} X_{j_2} \dots X_{j_r})$ contient exactement les mots

$$ \{ x_{\sigma_{j_1}} x_{\sigma_{j_2}} \dots x_{\sigma_{j_r}} : \sigma \in \mathcal{S}_{j_1 j_2 \dots j_r} \} \quad (3.4.4) $$

On peut donc écrire l'expression

$$ X_{j_1} X_{j_2} \dots X_{j_r} \det (b_{j_1 j_2'} \varepsilon_{\{j_1, j_2, \dots, j_r\}}) $$

de la formule (3.4.3) comme

$$ \sum \{ \alpha(x_{\sigma_{j_1}} x_{\sigma_{j_2}} \dots x_{\sigma_{j_r}}), \varepsilon_{\sigma} \cdot b_{j_1 \sigma_{j_1}} b_{j_2 \sigma_{j_2}} \dots b_{j_r \sigma_{j_r}} : \sigma \in \mathcal{S}_{j_1 j_2 \dots j_r} \} \quad (3.4.5) $$

où $\varepsilon_{\sigma}$ est l'indice de la permutation $\sigma$. Posant alors

$$ b_{k,l} = b(x_k, x_l) \quad (1 \le k, l \le n) $$

et remarquant que l'indice $\varepsilon_{\sigma}$ de la permutation $\sigma$ est identique à l'indice $\varepsilon_f$ de la permutation : $x_{j_k} \to x_{i_k}$ où $i_k = \sigma j_k$ ($1 \le k \le r$) et $f = x_{i_1} x_{i_2} \dots x_{i_r}$, la formule (3.4.5) peut encore s'écrire

$$ \sum \{ \alpha f, \varepsilon_f, \nu f : f \in \alpha^{-1} (X_{j_1} X_{j_2} \dots X_{j_r}) \} \quad (3.4.6) $$

où $\nu f$ est, pour tout $f \in \mathfrak{M}$, un élément de $\Omega$, défini en (3.3.1). De là, se rappelant que $\zeta f = \varepsilon_f \cdot (-1)^{\lambda f+1}$, pour $f \in \mathfrak{M}$, nous avons

$$ D = \alpha (1 - \sum \{ f, \zeta f, \nu f : f \in \mathfrak{M} \}) \quad (3.4.7) $$

où $\mathfrak{M}$ est l'ensemble des mots multilinéaires de $\mathcal{X}^*$. D est ainsi l'image par $\alpha$ d'une série formelle (réduite ici à un polynôme puisque $\mathcal{X}$ est fini) de l'algèbre non commutative, série qui apparaît dans l'identité du théorème 3.1.

Explicitons maintenant le premier membre de (3.4.2). Nous montrons d'abord

PROPOSITION 3.2. - Pour tout $h \in \bar{\mathcal{X}}^*$, on a

$$ \bar{v}h = \sum \{ \nu f : f \in \alpha^{-1} h \} \quad (3.4.8) $$
$$ (\alpha(1 - \Sigma\{f. \zeta f. \nu f : f \in \mathfrak{m}\}))^{-1} = \alpha\Sigma\{f. \nu f : f \in \mathfrak{m}^*\}(3.4.12) $$

Cette forme est plus symétrique ; elle fait disparaître le déterminant qui nous imposait de considérer le cas $\mathfrak{X}$ fini et fait apparaître la fonction $\nu$ dans les deux membres. Il était donc naturel de chercher à définir sur $\mathfrak{X}^*$ une opération associative $\tau$ pour laquelle $\nu$ était un homomorphisme de $(\mathfrak{X}^*, \tau)$ dans le monoïde multiplicatif de $\Omega$,

$$ \nu(f \tau f') = \nu f. \nu f' \quad (f, f' \in \mathfrak{X}^*) $$

et à voir si l'identité

$$ (1 - \Sigma\{f. \zeta f. \nu f : f \in \mathfrak{m}\})^{-1} = \Sigma\{f. \nu f : f \in \mathfrak{X}^*\} \quad (3.4.13) $$

était valable dans l'algèbre large $\Omega[[\mathfrak{X}_\tau^*]]$ du monoïde $(\mathfrak{X}^*, \tau)$. C'est ce que nous avons fait dans les paragraphes 3.2 et 3.3 avec le monoïde d'intercalement $\mathfrak{X}_\tau^*$.

Nous montrons, pour terminer, que l'identité (3.4.12) qui est l'identité du "Master Theorem" pour $\mathfrak{X}$ fini, est aussi valable pour un ensemble $\mathfrak{X}$ quelconque mais totalement ordonné.

Il suffit, en effet, de considérer l'identité (3.3.2) où les deux membres sont des séries formelles de $\Omega[[\mathfrak{X}_\tau^*]]$ et de prendre l'image par $\alpha$ de ces deux membres, où $\alpha$ va désigner ici l'homomorphisme canonique de $\Omega[[\mathfrak{X}_\tau^*]]$ sur $\overline{\alpha}$. (Cf. (2.4.2) et remarque (2.5.4)). Nous avons alors

$$ \alpha((1 - \Sigma\{f. \zeta f. \nu f : f \in \mathfrak{m}\})^{-1}) = (\alpha(1 - \Sigma\{f. \zeta f. \nu f : f \in \mathfrak{m}\}))^{-1} $$

d'après (2.5.3) et la remarque (2.5.4), d'où l'identité (3.4.12) en prenant aussi l'image par $\alpha$ du second membre de (3.3.2). Nous décrivons ce résultat dans le théorème 3.3 ci-dessous après avoir rappelé les notions utilisées.

Soit $\alpha$ et $\overline{\alpha}$ les algèbres larges des monoïdes libre $\mathfrak{X}^*$ et abélien libre $\overline{\mathfrak{X}}^*$ engendrés par un ensemble totalement ordonné $\mathfrak{X}$, relatives à un anneau commutatif (unitaire) $\Omega$ ;

$b : \mathfrak{X}^2 \to \Omega$ une application ;

$v : \mathfrak{X}^* \to \Omega$ l'application qui à

$f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathfrak{X}^{*+}$ (c'est-à-dire différent du mot unité) fait correspondre la quantité
$b(x_{j_1}, x_{i_1}) b(x_{j_2}, x_{i_2}) \dots b(x_{j_r}, x_{i_r}) \text{ où } x_{j_1} x_{j_2} \dots x_{j_r} = \beta f$

(le mot non décroissant de la classe abélienne de $f$) et au mot unité 1, l'unité de $\Omega$;

$\zeta$ une application définie sur $\mathfrak{M}$, l'ensemble des mots multilinéaires de $\mathfrak{X}^*$, à valeurs $+1$ ou $-1$, qui à $f = x_{i_1} x_{i_2} \dots x_{i_r}$ de $\mathfrak{M}$ fait correspondre la quantité $\zeta f = (-1)^{\lambda f+1} \epsilon_f$ où $\epsilon_f$ est l'indice de la permutation : $x_{i_k} \mapsto x_{i_{k+1}} \dots x_{i_r}$ ($1 \le k \le r$) de l'ensemble $\{x_{j_1}, x_{j_2}, \dots, x_{j_r}\} (x_{j_1} x_{j_2} \dots x_{j_r} = \beta f)$.

Posons aussi $\overline{\mathfrak{M}} = \alpha \mathfrak{M}$ et pour $h \in \overline{\mathfrak{X}}^*$,

$\lambda h$ = longueur du mot $h$

$\bar{\mu} = \sum \{ \zeta f. \nu f : f \in \alpha^{-1} h \}$

$\bar{\nu} = \sum \{ \nu f : f \in \alpha^{-1} h \}$.

Nous avons alors

THEOREME 3.3. -

$$ (1 - \sum \{ h. \bar{\mu} h : h \in \overline{\mathfrak{M}} \})^{-1} = \sum \{ h. \bar{\nu} h : h \in \overline{\mathfrak{X}^*} \} $$

dans l'algèbre commutative $\overline{\mathfrak{A}}$.
The new system of printing, which was introduced into the city last year, gives a much better view of all the events of the day, and enables one to read the newspaper at home, without being able to hear it read in public. The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.

The new system of printing has been very much preferred of late, and it is expected that, in a few years, the old system will be superseded by the new.
# 4. La représentation en cycles du monoïde libre

## 4.1. Introduction.

Pour compléter la démonstration du théorème 3.1, nous avons vu qu'il nous restait à démontrer que $M$ était un système de générateurs de l'algèbre large $\Omega [[X_i^*]]$ et aussi à établir une identité sur la fonction $\zeta$ introduite au chapitre précédent. Ces résultats sont donnés maintenant (propositions 4.3 et 4.5 respective- ment).

Avant de les établir, nous aurons besoin d'une série de lemmes combinatoires, tous assez longs à vérifier. Ils sont repro- duits dans ce chapitre, ce qui explique sa longueur. Toutefois ils conservent un intérêt propre car ils vont aussi nous fournir des résultats combinatoires qui seront exploités dans les chapitres 6 et 10.

Ils nous permettent, en fait, d'écrire les éléments $f$ d'un monoïde $X^*$ engendré par un ensemble $X$ non plus sous la forme de mots, mais, par analogie avec la théorie du groupe des permu- tations, sous forme de produits de cycles.

D'où le titre de ce chapitre.

Pour chaque problème combinatoire considéré, tout va revenir à définir pour tout mot $f \in X^*$ une représentation en cycles, unique.

Rappelons d'abord rapidement quelques propriétés du groupe symétrique.

E étant un ensemble fini de $r$ ($r > 0$) éléments, le groupe symétrique d'ordre $r$ opérant sur $E$ est défini comme l'ensemble des permutations de $E$ muni de la loi de composition des fonctions. Si $\sigma$ est une telle permutation, elle induit une relation d'équiva-
lence $\bar{\sigma}$ sur E, en posant pour $x$ et $y \in E$, $x\bar{\sigma}y \iff$ il existe un entier n tel que $x = \sigma^ny$.

Un cycle de la permutation $\sigma$ est alors défini comme la permutation de $E$ dont la restriction à $C$ (l'une des classes d'équivalence de $\bar{\sigma}$) est égale à la restriction de $\sigma$ à $C$ et dont la restriction à $E-C$ est l'application identique. $\sigma$ est alors le produit de ses cycles pris dans un ordre quelconque. Si $C = \{x_{v_1}, x_{v_2}, \dots, x_{v_K}\}$ est une classe d'équivalence de $\sigma$ ($1 \le K \le r$), on peut supposer que les indices $v_1, v_2, \dots, v_K$ ont été choisis de façon que

$$x_{v_K} = \sigma x_{v_1}$$

et si $K > 1$, en plus

$$x_{v_1} = \sigma x_{v_2}, x_{v_2} = \sigma x_{v_3}, \dots, x_{v_{K-1}} = \sigma x_{v_K}.$$

Il est alors d'usage de noter le cycle correspondant par

$$(x_{v_1} x_{v_2} \dots x_{v_K}). \qquad (4.1.1)$$

Si tous les cycles de la permutation $\sigma$ sont

$$(x_{v_{K-p-1}+1} \ x_{v_{K-p-1}+2} \ \dots \ x_{v_{K-p}}) \quad (K_o = 1; 1 \le p \le s)$$

on écrit la permutation $\sigma$ sous la forme

$$\sigma = (x_{v_1} \ x_{v_2} \ \dots \ x_{v_{K_1}}) \ (x_{v_{K_1+1}} \ x_{v_{K_1+2}} \ \dots \ x_{v_{K_2}}) \ \dots \ (x_{v_{K_{s-1}+1}} \ x_{v_{K_{s-1}+2}} \ \dots \ x_{v_{K_s}}). \qquad (4.1.2)$$

Soit maintenant $f = x_{i_1} x_{i_2} \dots x_{i_r}$ un mot multilinéaire de $\mathcal{X}^*$ où $\mathcal{X}$ est totalement ordonné et $\beta f = x_{j_1} x_{j_2} \dots x_{j_r}$ le mot non décroissant associé.

Faisons correspondre à $f$ la permutation $\sigma$ de l'ensemble $\{x_{j_1}, x_{j_2}, \dots, x_{j_r}\}$ définie par $\sigma: x_{j_k} \to x_{i_k} \ (1 \le k \le r)$, puis interprétons les cycles de cette permutation écrits sous la forme (4.1.1) comme des éléments d'un ensemble $\mathcal{Y}$ en correspondance biunivoque avec $\mathcal{X}^*$, et la permutation $\sigma$ écrite sous la forme (4.1.2) comme un certain mot de $\mathcal{Y}^*$.

Nous dirons alors que $\sigma$ est une représentation en cycles de $f$. Le but de cette suite de lemmes va donc être de préciser cette notion et de l'étendre aux mots de $\mathcal{X}^*$ non multilinéaires.
Nous pourrons alors composer les mots de $\mathcal{Y}^*$ par le produit de juxtaposition de $\mathcal{Y}^*$ et cette opération correspondra justement à l'opération $\tau$ définie sur $\mathcal{X}^*$ (lemme 4.5).

Mentionnons enfin que ce chapitre reprend et développe certains points d'une note aux Comptes Rendus [12].

## 4.2. Quelques lemmes préliminaires.

$\mathcal{X}$ étant un ensemble quelconque, nous supposons désormais que $h$ est un élément fixe de $\mathcal{X}^{*+}$.

Soit $x_{u_1}, x_{u_2}, \dots, x_{u_d}$ les $d = \dim h$ lettres $x$ de $\mathcal{X}$ telles que $hx > 0$.

Posons

$$hx_{u_t} = n_t \quad (1 \le t \le d)$$

et

$$r = \sum_{t=1}^{d} n_t.$$

De plus, désignons par $N(h)$ l'ensemble des couples

$$\{(x_{u_t}, m_t) : 1 \le m_t \le n_t; 1 \le t \le d\}$$

et par $E(h)$ l'ensemble des applications $\psi$ de $N(h)$ sur l'ensemble $\{x_{u_1}, x_{u_2}, \dots, x_{u_d}\}$ telles que

$$\text{card} \{x : \psi^{-1} x = x_{u_t}\} = n_t \quad (1 \le t \le d).$$

(Ce sont les applications telles que tout $x_{u_t}$ est l'image par $\psi$ de $n_t$ couples exactement de $N(h)$ ($1 \le t \le d$)).

Nous nous proposons alors de définir une représentation en cycles de ces fonctions. D'abord, nous introduisons un ensemble $\mathcal{Y}$ et une bijection $\theta : \mathcal{Y} \to \mathcal{X}^*$ que nous étendons à un épimorphisme du monoïde libre $\mathcal{Y}^*$ engendré par $\mathcal{Y}$ sur $\mathcal{X}^*$, en posant pour $g = y_{l_1} y_{l_2} \dots y_{l_s}$

$$\theta g = \theta y_{l_1} \theta y_{l_2} \dots \theta y_{l_s}$$

Ensuite nous désignons par $G(h)$ le sous-ensemble des mots $g$ de $\mathcal{Y}^*$ tels que $\alpha\theta g = h$.
Pour $g = y_{l_1} y_{l_2} \dots y_{l_s} \in G(h)$, nous posons

$$ \theta g = x_{v_1} x_{v_2} \dots x_{v_r} \in \alpha^{-1}h $$

$$ K_o = 0, \quad K_p = \lambda \theta y_{l_1} + \dots + \lambda \theta y_{l_p} \quad (1 \le p \le s). $$

Alors l'ensemble $\{(x_{v_k}, \gamma_k \theta g) : 1 \le k \le r\}$ est identique à $N(h)$, puisque par définition $\theta g \in \alpha^{-1}h$.

L'application qui au couple $(x_{v_k}, \gamma_k \theta g)$ fait correspondre l'élément $x_{v_{k-1}}$ si $k \neq K_{p-1}+1$ pour tout $p \in [1, s]$ et l'élément $x_{v_{K_p}}$ si $k = K_{p-1}+1$ pour un certain $p \in [1, s]$, est alors une application de $N(h)$ dans l'ensemble $\{x_{u_1}, x_{u_2}, \dots, x_{u_d}\}$.

Soit $\mathfrak{e}$ cette application. Alors

LEMME 4.1. - $\mathfrak{e} \in E(h)$ et l'application $\mathfrak{e} : G(h) \to E(h)$ une surjection.

PREUVE. - Soit pour $1 \le t \le d$, $k_1, k_2, \dots, k_{n_t}$ les $n_t$ indices $k$ ($1 \le k \le r$) tels que $x_{u_k} = x_{u_t}$. Alors $x_{v_k}$ est l'image du couple $(x_{v_{k+1}}, \gamma_{k+1} \theta g)$ si $k \neq K_p$ pour tout $p \in [1, s]$ et du couple $(x_{v_{K_p-1}}, \gamma_{K_p-1} \theta g)$ si $k = K_p$ ($k = k_1, k_2, \dots, k_{n_t}$).

Nous avons donc bien

$$ \mathrm{card} \{x : (\mathrm{eg})^{-1} x = x_{u_t}\} = n_t \quad (1 \le t \le d) $$

Pour la seconde propriété, soit $\psi$ un élément de $E(h)$; nous allons construire un mot $g$ tel que $\mathfrak{e}g = \psi$.

Si $r=1$, $G(h)$ et $E(h)$ sont réduits à un seul élément et le résultat est évident. Pour $r>1$, posons $q_r = d$ et $f_{r+1} = 1$ (mot unité) et soit pour $2 \le k \le r$,

$$ f_k = x_{u_{q_k}} x_{u_{q_{k+1}}} \dots x_{u_{q_r}} $$

$$ m_k = n_{q_k} - (\alpha f_{k+1}) (x_{u_{q_k}}) $$

$$ w_k \text{ l'entier tel que } x_{u_{w_k}} = \psi(x_{u_{q_k}}, m_k) $$

$$ \text{et } m_k' = n_{w_k} - (\alpha f_k)(x_{u_{w_k}}). $$

Alors on pose
$$q_{k-1} = w_k \quad \text{si } m_k' > 0$$

$$\text{et} \quad = \max \{q : n_q - (\alpha f_k)(x_{u_q}) > 0\} \quad \text{si} \quad m_k' = 0.$$

Soit $s$ le nombre des indices $k$ pour lesquels $m_k' = 0$ et désignons par $K_{s-1}+1$, $K_{s-2}+1$, ..., $K_o+1$ ($K_o = 0$) la suite décroissante des $k$ pour lesquels $m_k' = 0$. Posons aussi $K_s = r$.

Formons

$$y_{l_p} = \theta^{-1} x_{u_{q_{K_p-1}}+1} x_{u_{q_{K_p-1}}+2} \dots x_{u_{q_{K_p}}} \in \mathcal{Y} \quad (1 \le p \le s)$$

et

$$g = y_{l_1} y_{l_2} \dots y_{l_s}.$$

Puisque $\gamma_k \theta g = n_{q_k} - (\alpha f_{k+1})(x_{u_{q_k}})$ on a bien $m_k = \gamma_k \theta g$ pour tout $k \in [1, r]$. D'où par définition de $w_k$, $\psi(x_{u_{q_k}}, \gamma_k \theta g) = x_{u_{q_{k-1}}}$ si $k \neq K_{p-1}+1$ pour tout $p \in [1, s]$ et on peut vérifier ensuite que $\psi(x_{u_{q_k}}, \gamma_k \theta g) = x_{u_{K_p}}$ si $k = K_{p-1}+1$.

Lorsque $eg = \psi$, nous dirons alors que $g$ est une représentation en cycles de $\psi$.

Le prochain lemme généralise les propriétés des cycles disjoints dans le cas des permutations, à savoir dans ce cas que les cycles ne sont définis qu'à une permutation circulaire près de leurs éléments et que le produit des cycles est commutatif.

LEMME 4.2. - Soit $g = y_{l_1} y_{l_2} \dots y_{l_s}$ un mot de $G(h)$ tel que $\theta y_{l_p}$ soit multilinéaire pour un certain $p \in [1, s]$ ; soit $\theta y'$ un mot de la classe des conjugués de $\theta y_{l_p}$ et $g'$ le mot de $\mathcal{Y}$ obtenu en substituant dans $g$ la lettre $y'$ à la lettre $y_{l_p}$.

$$\text{Alors } eg = eg'.$$

De même, si $g = y_{l_1} y_{l_2} \dots y_{l_s}$ ($s > 1$) est tel que les mots $\theta y_{l_p}$ et $\theta y_{l_{p+1}}$ de $\mathcal{X}^*$ sont disjoints pour $p \in [1, s-1]$ et si $g'$ est le mot de $\mathcal{Y}^*$ obtenu en permutant dans $g$ les deux lettres $y_{l_p}$ et $y_{l_{p+1}}$, alors $eg = eg'$.

PREUVE. - Posons $K_o = 0$ $K_p = \lambda\theta y_{l_1} + \dots + \lambda\theta y_{l_p}$ ($1 \le p \le s$)
$$ \theta g = x_{v_1} x_{v_2} \dots x_{v_r} $$

et

$$ \theta g' = x_{v'_1} x_{v'_2} \dots x_{v'_r} $$

Trivialement, les restrictions de $eg$ et $eg'$ aux éléments $(x_{u_t}, m_t)$ tels que

$$ (x_{u_t}, m_t) = (x_{v_k}, \gamma_k \theta g) = (x_{v'_k}, \gamma'_k \theta g') $$

$$ 1 \le k \le K_{p-1} \text{ (si } p > 1) \text{ et } K_p < k \le r \text{ (si } p < s \text{)} $$

sont égales.

Ensuite $\theta y'$ se déduisant de $\theta y_l$ par une permutation circulaire, si $x_{v_k} = x_{u_t}$ ($K_{p-1} + 1 \le k \le K_p$) il existe un et un seul $k'$ ($K_{p-1} + 1 \le k' \le K_p$) tel que $x_{v'_k} = x_{v_k} = x_{u_t}$ et si $x_{v_{k-1}}$ (resp. $x_{v_{K_p}}$) = $x_{u_t}$, si $k \ne K_p$ (resp. $k = K_{p-1} + 1$) on a aussi

$$ x_{v'_{k'-1}} \text{ (resp. } x_{v'_{K_p}} \text{)} = x_{u_t}, \text{ si } k' \ne K_p \text{ (resp. } k' = K_{p-1} + 1 \text{).} $$

Enfin, puisque $\theta y_l$ et $\theta y'$ sont multilinéaires, on a forcément $\gamma_k \theta g = \gamma_{k'} \theta g$ pour le précédent couple $(k, k')$.

D'où la première propriété.

Pour la deuxième propriété, observons que

$$ (\alpha \theta y_{l_{p+1}}) (x_{v_k}) = 0 \quad \text{pour tout} \quad k \in [K_{p-1}+1, K_p] \quad (4.2.1) $$

et de même

$$ (\alpha \theta y_{l_p}) (x_{v_k}) = 0 \quad \text{pour tout} \quad k \in [K_p+1, K_{p+1}] \quad (4.2.2) $$

Or

$$ \gamma_k \theta g = (\alpha \theta y_{l_1} \dots y_{l_{p-1}}) (x_{v_k}) + (\alpha \theta y_{l_p}) (x_{v_k}) + (\alpha x_{v_{K_p+1}} \dots x_{v_{K_p}}) (x_{v_k}) \quad \text{pour } k \in [K_p+1, K_{p+1}] $$

(le premier terme du second membre disparaissant si $p=1$).

$$ \text{Pour } k' = k - \lambda \theta y_{l_p} \quad (K_p + 1 \le k \le K_{p+1}), \text{ on a} $$

$$ \gamma_k, \theta g' = (\alpha \theta y_{l_1} \dots y_{l_{p-1}}) (x_{v'_k}) + (\alpha x_{v'_{k-1}} \dots x_{v'_{k-1}}) (x_{v'_k}) $$

et de
$$x_{v'}_{K_{p-1}+1} \dots x_{v'}_{K_p} = x_{v_{K_p+1}} \dots x_{v_K}$$

il résulte que

$$\gamma_k \theta g = \gamma_{k'} \theta g'$$

en vertu de (4.2.1).

On a pareillement

$$\gamma_k \theta g = \gamma_{k'} \theta g' \quad \text{où} \quad k \in [K_{p-1} + 1, K_p] \text{ et } k' = k + \lambda \theta y_{l_{p+1}}.$$

### 4.3. L'opérateur $\delta$.

Dans la présente section, nous introduisons un opérateur $\delta : y^* \to y^*$ qui nous permettra d'obtenir pour toute fonction $\psi$ de $E(h)$ une représentation en cycles $g = y_{l_1} y_{l_2} \dots y_{l_s}$ où tous les $\theta y_{l_p}$ ($1 \le p \le s$) sont multilinéaires ($\in \mathfrak{M}$).

Soit $y \in \mathcal{Y}$ et posons $\theta y = x_{v_1} x_{v_2} \dots x_{v_r} \in \mathcal{X}^*$. Si $y \notin \theta^{-1}\mathfrak{M}$, nous désignons par $k'$ ($1 \le k' < r$) le plus grand entier tel que

$$(\alpha x_{v_k}, x_{v_{k'+1}}, \dots, x_{v_r}) (x_{v_k'}) = 2$$

et par $k''$ l'indice tel que $x_{v_{k''}} = x_{v_{k'}}$ ($k' < k'' \le r$).

Nous posons alors

$$\begin{aligned} \delta y &= \theta^{-1} x_{v_1} \dots x_{v_k} x_{v_{k'+1}} \dots x_{v_r} \quad \text{si } k'' < r \\ &= \theta^{-1} x_{v_1} \dots x_{v_k} \quad \text{si } k'' = r \end{aligned}$$

$$\text{et } \bar{\delta} y = \theta^{-1} x_{v_{k'+1}} \dots x_{v_{k''}}.$$

Par définition même de $k'$, on a

$$(\alpha x_{v_{k'+1}} \dots x_{v_r}) (x_{v_k}) = 1$$

$$\text{pour tout } k \in [k' + 1, r].$$

D'où en particulier, le mot $x_{v_{k'+1}} \dots x_{v_{k''}} = \theta \bar{\delta} y$ est multilinéaire. ($\bar{\delta} y \in \theta^{-1} \mathfrak{M}$).

On pose alors

$$\delta y = \bar{\delta} y \cdot \delta y$$
et nous étendons cette définition au cas où $y \in \theta^{-1} \mathfrak{M}$ en posant

$$ \delta y = y = \underline{\delta} y . \bar{\delta} y = \underline{\delta} y $$

avec $\bar{\delta} y = 1$ (mot unité de $y^*$) ; enfin, pour $n > 0$ $\delta^n y$ est défini par

$$ \delta^n y = \underline{\delta^n} y . \bar{\delta} \delta^{n-1} y . \cdots . \bar{\delta} \underline{\delta} y . \delta^n y . $$

Nous avons alors

$$ 0 < \lambda \theta \underline{\delta} y \le \lambda \theta y \quad (4.3.1) $$

et

$$ \lambda \theta \underline{\delta} y < \lambda \theta y \iff \theta y \notin \mathfrak{M} . \quad (4.3.2) $$

De là, la suite des entiers

$$ \lambda \theta y, \lambda \theta \underline{\delta} y, \lambda \theta \bar{\delta}^2 y, \dots, \lambda \theta \underline{\delta}^n y, \dots $$

est non croissante et bornée inférieurement par 0 et les relations (4.3.1) et (4.3.2) entraînent alors qu'il existe un entier $n_0 \ge 0$ tel que pour $n \ge n_0$

$$ \lambda \theta \underline{\delta}^n y = \lambda \theta \bar{\delta}^{n_0} y, $$

soit alors

$$ \underline{\delta}^{n_0} y \in \theta^{-1} \mathfrak{M} . $$

Si nous choisisons $n_0$ comme le plus petit entier ayant cette propriété,

$$ \text{alors le mot } \underline{\delta}^{n_0} y . \bar{\delta} \delta^{n_0-1} y . \cdots . \bar{\delta} \underline{\delta} y . \delta^n y = \delta^{n_0} y \quad (4.3.3) $$

$$ \text{a toutes ses lettres } \in \theta^{-1} \mathfrak{M} . $$

Si donc pour $g = y_{l_1} y_{l_2} \dots y_{l_s} \in y^*$ nous posons $\delta_p g = g$ si $p > s$ ou si $y \in \theta^{-1} \mathfrak{M}$ et

$$ \delta_p g = y_{l_1} y_{l_2} \dots y_{l_{p-1}} . \delta y_{l_p} . y_{l_{p+1}} \dots y_{l_s} $$

$$ (y_{l_0} = y_{l_{s+1}} = 1 \text{ (mot unité de } y^*) ) $$

- ce que nous ferons désormais -
nous avons pour $1 \le p \le s$, en utilisant les notations ci-dessus

$$ \delta_p^n g = y_{l_1} y_{l_2} \dots y_{l_{p-1}} \cdot \delta_p^n y_{l_p} \cdot y_{l_{p+1}} \dots y_{l_s} $$

pour tout $n > 0$.

Ainsi en vertu de (4.3.3) nous obtenons

LEMME 4.3.- Pour tout $g = y_{l_1} y_{l_2} \dots y_{l_s} \in \mathcal{Y}^*$, il existe $s$ entiers $\ge 0$ $n_{o_1}, n_{o_2}, \dots, n_{o_s}$ tels que le mot $\delta_1^{n_{o_1}} \delta_2^{n_{o_2}} \dots \delta_s^{n_{o_s}} g$ a toutes les lettres $\in \Theta^{-1}\mathfrak{M}$.

Notre but maintenant va être de montrer que si $g$ est une représentation en cycles d'une application $\phi \in E(h)$ alors $\delta_p g$ est aussi une représentation en cycles de $\phi$ pour tout $p \ge 1$. Il en résultera alors, d'après le lemme précédent, que toute application admet une représentation en cycles $g = y_{l_1} y_{l_2} \dots y_{l_s}$ où tous les $\theta y_{l_p}$ ($1 \le p \le s) \in \mathfrak{M}$. Il nous suffit donc de montrer le.

LEMME 4.4.- $\text{ey} = e \delta y$ pour tout $y \in \mathcal{Y}$.

PREUVE.- En reprenant les mêmes notations que celles introduites pour la définition de $\delta$, nous avons, en posant $\theta \delta y = x_{v'_1} x_{v'_2} \dots x_{v'_r}$,

$$ f_1 = x_{v_1} \dots x_{v_k} = x_{v'_1} \dots x_{v'_k} $$

$$ f_2 = x_{v'_k+1} \dots x_{v'_k} = x_{v'_r-k+''+k'+1} \dots x_{v'_r} $$

et

$$ f_3 = 1 \quad \text{si} \quad k'' = r $$

$$ = x_{v''_k+1} \dots x_v = x_{v'_k+1} \dots x_{v'_r-k+''+k'} \quad \text{si} \quad k'' < r, $$

$$ \theta y = f_1 f_2 f_3 $$

$$ \underline{\delta} y = f_1 f_3 $$

et

$$ \bar{\delta} y = f_2 $$

Si $f_3 \ne 1$, par définition même de $k'$ et de $k''$, les deux mots $f_2$ et $f_3$ sont disjoints et multilinéaires ; on a donc

$$ (x_{v_k}, \gamma_k \theta y) = (x_{v'_k+''+k''}, \gamma_{k'+k-k''} \theta \delta y) \quad k''+1 \le k \le r. \quad (4.3.4) $$

D'autre part, on a toujours
$$ 
\begin{aligned}
(x_{v_k}, \gamma_k \theta y) &= (x_{v'_k}, \gamma_k \theta \delta y) \quad \text{pour} \quad 1 \le k \le k' \\
&= (x_{v'_{r-k''+k}}, \gamma_{r-k''+k} \theta \delta y) \quad \text{pour} \quad k' + 1 < k < k''. \quad (4.3.5)
\end{aligned}
$$

La fonction $e^{\delta y}$ appliquée au couple $(x_{v'_1}, \gamma_1 \theta \delta y)$ donne

$$ 
\begin{aligned}
(e^{\delta y}) (x_{v'_1}, \gamma_1 \theta \delta y) &= x_{v'_{r-k''+k'}} = x_{v_r} && (\text{si } k'' < r) \quad (4.3.6) \\
&= x_{v_{k''}} && (\text{si } k'' = r);
\end{aligned}
$$

mais dans ce dernier cas on a aussi

$$ = x_{v_r} \quad \text{puisque} \quad x_{v_r} = x_{v_{k''}} = x_{v_{k'}}; $$

d'autre part,

$$ (\text{eg}) (x_{v'_1}, \gamma_1 \theta y) = x_{v_r}. $$

La relation (4.3.5) pour $k=1$ donne alors

$$ (\text{eg}) (x_{v_1}, \gamma_1 \theta y) = (e^{\delta y}) (x_{v_1}, \gamma_1 \theta y). \quad (4.3.7) $$

Si $k' > 1$ la relation (4.3.5) pour $1 < k \le k'$ entraîne bien $\text{évj.}$ demment

$$ (e^{\delta y}) (x_{v'_k}, \gamma_k \theta \delta y) = x_{v'_{k-1}} = x_{v_{k-1}} = (\text{ey}) (x_{v_k}, \gamma_k \theta y); $$

d'où

$$ (e^{\delta y}) (x_{v_k}, \gamma_k \theta y) = (\text{ey}) (x_{v_k}, \gamma_k \theta y) \quad (4.3.8) $$

pour $1 < k \le k'$.

Si $k'' < r$ on a $(\text{ey}) (x_{v_{k''+1}}, \gamma_{k''+1} \theta y) = x_{v_{k''}}$ par définition de $\text{ey}$ et

$$ 
\begin{aligned}
& (e^{\delta y}) (x_{v'_{k'+1}}, \gamma_{k'+1} \theta y) \\
&= x_{v'_{k'}}.
\end{aligned}
$$

Ainsi, de l'égalité $x_{v'_k} = x_{v_k'} = x_{v_{k''}}$ et de la relation (4.3.4) pour $k = k'' + 1$, on déduit

$$ (\text{ey}) (x_{v_{k''+1}}, \gamma_{k''+1} \theta y) = (e^{\delta y}) (x_{v_{k''+1}}, \gamma_{k''+1} \theta y). \quad (4.3.9) $$

Si $k'' + 1 < r$, la relation (4.3.4) pour $k'' + 1 < k \le r$ et la définition de $\text{ey}$ et $e^{\delta y}$ entraînent
$$ (\text{ey}) (x_{v_k}, \gamma_k \theta y) = x_{v_{k-1}} = x_{v'_{k'+k-1-k''}} = (e \delta y) (x_{v'_{k'+k-k''}}, \gamma_{k'+k-k''} \theta \delta y). $$

D'où

$$ (\text{ey}) (x_{v_k}, \gamma_k \theta y) = (e \delta y) (x_{v_k}, \gamma_k \theta y) \quad k'' + 1 \le k \le r. \quad (4.3.10) $$

Reste à considérer le cas où $k \in [k' + 1, k'']$.

Tout d'abord

$$ (\text{ey}) (x_{v_{k'+1}}, \gamma_{k'+1} \theta y) = x_{v_k'} $$

et

$$ (e \delta y) (x_{v_{r-k''+k'+1}}, \gamma_{r-k''+k'+1} \theta \delta y) = x_{v_r'} $$

Dès lors, de l'égalité $x_{v_r'} = x_{v_{k''}} = x_{v_k'}$, et de la relation (4.3.5) pour $k = k' + 1$, on déduit

$$ (\text{ey}) (x_{v_{k'+1}}, \gamma_{k'+1} \theta y) = (e \delta y) (x_{v_{k'+1}}, \gamma_{k'+1} \theta y). \quad (4.3.11) $$

Si enfin $k' + 1 < k''$, la relation (4.3.5) pour $k' + 1 < k \le k''$ et la définition de $\text{ey}$ et $e \delta y$ entraînent

$$ (\text{ey}) (x_{v_k}, \gamma_k \theta y) = x_{v_{k-1}} = x_{v'_{r-k''+k'-1}} = (e \delta y) (x_{v'_{r-k''+k}}, \gamma_{r-k''+k} \theta \delta y). $$

Soit

$$ (\text{ey}) (x_{v_k}, \gamma_k \theta y) = (e \delta y) (x_{v_k}, \gamma_k \theta y) \quad (4.3.12) $$

pour $k' + 1 < k \le k''$.

Ainsi les relations (4.3.7) à (4.3.12) entraînent que les fonctions $\text{ey}$ et $e \delta y$ sont identiques.

Pour toute application $\psi$ de $E(h)$ nous pouvons ainsi construire une représentation en cycles $g = y_{l_1} y_{l_2} \dots y_{l_s}$ où tous les $\theta y_{l_p} \in \mathfrak{M}$ ($1 \le p \le s$).

Il nous suffit pour cela de construire une représentation en cycles quelconque de $\psi$, ce que nous pouvons faire d'après le lemme 4.1. - soit $g = y_{l_1} y_{l_2} \dots y_{l_s}$ - et d'y appliquer l'opérateur $\delta_1^n \delta_2^n \dots \delta_s^n$ pour n suffisamment grand, d'après le lemme 4.3.

Lorsqu'une représentation en cycles $g = y_{l_1} y_{l_2} \dots y_{l_s}$ est telle que $\theta y_{l_p} \in \mathfrak{M}$ ($1 \le p \le s$) nous dirons que $g$ est une représentation en cycles multilinéaires.
Exemple.- Soit le mot $\theta y = \text{cadbcda}$ de $\mathcal{X}^*$ où $\mathcal{X} = \{\text{a}, \text{b}, \text{c}, \text{d}\}$. Le mot $y$ de $\mathcal{Y}^*$ est une représentation en cycles de l'application $\psi$ de l'ensemble $\{(\text{a}, 1), (\text{a}, 1), (\text{b}, 1), (\text{c}, 1), (\text{c}, 2), (\text{d}, 1), (\text{d}, 2)\}$ sur $\{\text{a}, \text{b}, \text{c}, \text{d}\}$ définie par

$$ \psi(\text{c}, 1) = \text{a}; \psi(\text{a}, 1) = \text{c}; \psi(\text{d}, 1) = \text{a}; \psi(\text{b}, 1) = \text{d} $$

$$ \psi(\text{c}, 2) = \text{b}; \psi(\text{d}, 2) = \text{c}; \psi(\text{a}, 2) = \text{d} $$

Nous avons, en reprenant les notations ci-dessus

$$ f_1 = \text{cad} \quad f_2 = \text{bcd} \quad f_3 = \text{a} $$

D'où

$$ \delta y = \theta^{-1} \text{ cada. } \theta^{-1} \text{ bcd} $$

Et nous pouvons encore vérifier que $\delta y$ est aussi une représentation en cycles de $\psi$.

En appliquant $\delta_1$ à $\delta y$, on a

$$ \delta_1 \delta y = \theta^{-1} \text{ ca. } \theta^{-1} \text{ da. } \theta^{-1} \text{ bcd} $$

mot de $\mathcal{Y}^*$ qui a toutes ses lettres $\in \theta^{-1}\mathcal{M}$.

Toute fonction $\psi$ de $E(h)$ admettant (au moins) une représentation en cycles multilinéaires, le prochain résultat montre comment on peut passer de l'une d'elles à une autre.

### 4.4. Les opérateurs $\tau$.

Soit $\tau''$ l'application qui au mot $f = x_{v_1} x_{v_2} \dots x_{v_r}$ de $\mathcal{M}$ associe le mot $f' = x_{v_2} x_{v_3} \dots x_{v_r} x_{v_1}$ si $r > 1$ et $f$ si $r = 1$.

Désignons par $\tau' = \theta^{-1} \tau'' \theta$ l'opérateur de $\theta^{-1} \mathcal{M}$ sur lui-même et posons pour $g = y_{l_1} y_{l_2} \dots y_{l_s} \in (\theta^{-1} \mathcal{M})^*$, $(\theta^{-1} \mathcal{M})^*$ étant le sous-monoïde de $\mathcal{Y}^*$ engendré par $\theta^{-1} \mathcal{M}$,

$$ \tau'_p g = g \quad \text{si} \quad p > s; $$

$$ \tau'_p g = y_{l_1} \dots y_{l_{p-1}} \cdot \tau' y_{l_p} \cdot y_{l_{p+1}} \dots y_{l_s} \quad \text{si} \quad 1 \le p \le s $$

et

$$ \tau_p g = g \quad \text{si} \quad p \ge s $$
ou pour $1 \le p \le s-1$ si les deux mots $\theta y_{l_p}$ et $\theta y_{l_{p+1}}$ sont non disjoints ; enfin

$$ \tau_p g = y_{l_1} \cdots y_{l_{p-1}} y_{l_{p+1}} y_{l_p} y_{l_{p+2}} \cdots y_{l_s} $$

si $1 \le p \le s-1$ et $\theta y_{l_p}$ et $\theta y_{l_{p+1}}$ disjoints.

Les $\tau'_p$ et $\tau_p$ engendrent de façon naturelle un monoïde d'opérateurs $T = \{\tau_p, \tau'_p\}$ de $(\theta^{-1}\mathfrak{M})^*$ sur lui-même.

D'après le lemme 4.2. nous avons

$$ e \tau g = e g \quad \text{pour tout} \quad \tau \in T. $$

Réciproquement, si $g$ est une représentation en cycles multi-linéaires de $\psi \in E(h)$, alors toutes ses autres représentations en cycles multilinéaires sont données par $\{\tau g : \tau \in T\}$ ou encore

**PROPOSITION 4.1.** - Si $g$ et $g'$ sont deux mots de $(\theta^{-1}\mathfrak{M})^*$ alors $eg = eg'$ si et seulement s'il existe un opérateur $\tau$ de $T$ tel que

$$ g' = \tau g. $$

**PREUVE.-** La condition est suffisante d'après le lemme 4.2. Montrons qu'elle est aussi nécessaire. Soit donc

$$ g = y_{l_1} y_{l_2} \cdots y_{l_s} \quad \text{et} \quad g = y_{l'_1} y_{l'_2} \cdots y_{l'_s}, $$

deux mots de $(\theta^{-1}\mathfrak{M})^*$ tels que $eg = eg'$.

Posons

$$ K_o = 0 \qquad K_p = \lambda \theta y_{l_1} + \dots + \lambda \theta y_{l_p} \qquad 1 \le p \le s $$

$$ K'_o = 0 \qquad K'_p = \lambda \theta y'_{l'_1} + \dots + \lambda \theta y'_{l'_p} \qquad 1 \le p \le s' $$

$$ \theta g = x_{v_1} x_{v_2} \cdots x_{v_r} $$

et

$$ \theta g' = x_{v'_1} x_{v'_2} \cdots x_{v'_r} $$

Soit alors $q$ le plus petit entier tel que $\theta y_{l_1}$ et $\theta y_{l'_q}$ ne soient pas disjoints.

$q$ est bien défini puisque $g$ et $g'$ ont en particulier même image abélienne.
Nous allons montrer que si $t$ et $t'$ sont deux entiers $1 \le t \le \lambda\theta y_{l_1}$ et $1 \le t' \le \lambda\theta y_{l'_q}$ tels que

$$x_{v_t} = x_{v'_{t'+K_{q-1}}} \quad (4.4.1)$$

(il en existe d'après la définition même de $q$), alors

$$x_{v_{t-1}} \quad (\text{ou} \quad x_{v_{K_1}} \quad \text{si} \quad t=1) = x_{v'_{K_{q-1}+t'-1}} \quad (4.4.2)$$

(ou $x_{v'_{K_q}}$ si $t' = 1$).

Il s'ensuivra que $\theta y_{l_1}$ et $\theta y_{l'_q}$ seront conjugués puisque $\theta y_{l_1}$ et $\theta y_{l'_q}$ sont multilinéaires donc primitifs.

Soit donc deux entiers $t$ et $t'$ ayant la propriété (4.4.1). Tout d'abord

$$\gamma_k \theta g = 1 \quad \text{pour tout} \quad k \in [1, K_1] \quad \text{puisque} \quad \theta y_{l_1}$$

est multilinéaire, et d'autre part

$$\gamma_{t'+K_{q-1}} \quad \theta g' = 1$$

puisque $\theta y_{l'_q} \in \mathfrak{M}$ et si $q > 1$, $\theta y_{l_1}$ et $\theta y_{l'_p}$ sont disjoints pour tout $p \in [1, q-1]$.

Mais puisque $eg = eg'$, on a

$$\begin{align*}
x_{v_{t-1}} \quad (\text{ou} \quad x_{v_{K_1}} \quad \text{si} \quad t=1) &= (\text{eg}) \quad (x_{v_t}, \gamma_t \theta g) = (\text{eg}) \quad (x_{v_t}, 1) \\
&= (\text{eg'}) \quad (x_{v'_{K_{q-1}+t'}} \quad , \quad 1) = (\text{eg'}) \quad (x_{v'_{K_{q-1}+t'}} \quad , \quad \gamma_{K_{q-1}+t'} \theta g') \\
&= x_{v'_{t-1}} \quad (\text{ou} \quad x_{v'_{K_q}} \quad \text{si} \quad t'=1).
\end{align*}$$

D'où la propriété (4.4.2).

Les mots $\theta y_{l_1}$ et $\theta y_{l'_q}$ sont donc conjugués ou encore

$$\tau'^n y_{l'_q} = y_{l_1}$$

pour un certain $n > 0$.

Si $q > 1$, $\theta y_{l_1}$ et $\theta y_{l'_p}$ sont disjoints pour tout $p \in [1, q-1]$; les deux mots
$g$ et $g'' = \tau_1'^n \tau_1 \tau_2 \dots \tau_{q-1} g'$ (ou $\tau_1'^n g'$ si $q = 1$)

ont alors leurs premières lettres égales.

Si $s = 1$, $\theta g$ est alors lui-même multilinéaire et on a nécessairement

$$q = s' = 1.$$

D'où

$$g = y_{l_1} = \tau'^n y_{l_1'} = \tau_1'^n g'$$

Il suffit donc de montrer le résultat par récurrence sur $s$ en supposant $1 < s \le s'$.

Avec les notations ci-dessus, les mots

$g = y_{l_1} y_{l_2} \dots y_{l_s}$ et $g'' = y_{l_1} y_{l'_1} \dots y_{l'_{q-1}} y_{l'_{q+1}} \dots y_{l'_s}$,

ou $y_{l_1} y_{l_2'} \dots y_{l'_s}$ si $q = 1$,

ont leurs premières lettres égales ; soit

$$g = y_{l_1} g''' \quad \text{et} \quad g'' = y_{l_1} g^{\prime\prime}.$$

$$\text{d'où } eg''' = eg^{\prime\prime\prime}.$$

Comme $\lambda g''' = s - 1$, on applique la récurrence au couple $(g''', g^{\prime\prime\prime})$ et le résultat suit.

### 4.5. Le monoïde $\mathcal{C}$.

Nous supposons désormais que $\mathcal{X}$ est totalement ordonné. La classe abélienne $\alpha^{-1}h$ ($h \in \mathcal{X}^{\alpha+1}$) contient alors un élément non décroissant $\beta'h$. En reprenant les mêmes notations qu'au début du paragraphe 4.2 et en supposant $x_{u_1} < x_{u_2} < \dots < x_{u_d}$ nous avons

$$ \begin{aligned} \beta' h &= x_{u_1}^{n_1} x_{u_2}^{n_2} \dots x_{u_d}^{n_d} && \text{que nous posons égal aussi à} \\ &= x_{j_1} x_{j_2} \dots x_{j_r}. \end{aligned} $$

Tout mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ de $\alpha^{-1}h$ induit alors une application $\pi f$ de $E(h)$ si l'on pose
$$ (\pi f)(x_{j_k}, \gamma_k \beta^l h) = x_{i_k} \quad (1 \le k \le r). \quad (4.5.1) $$

Réciproquement, à toute application $\psi$ de $E(h)$ correspond un et un seul mot $f$ de $\alpha^{-1}h$ tel que $\pi f = \psi$ ; ce mot $f$ est le seul mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ tel que

$$ x_{i_k} = \psi(x_{u_t}, m_t) $$

où $t$ et $m_t$ sont définis comme les entiers satisfaisant à

$$ n_1 + \dots + n_{t-1} < k \le n_1 + \dots + n_t $$

et

$$ m_t = k - (n_1 + \dots + n_{t-1}) $$

(on posera $n_o = 0$).

$\pi$ est alors une bijection de $\alpha^{-1}h$ sur $E(h)$. Posons

$$ \rho = \pi^{-1} e : G(h) \longrightarrow \alpha^{-1}h. $$

Alors, d'après le lemme 4.1, $\rho$ est une surjection. De plus, d'après le lemme 4.3, pour tout $f \in \alpha^{-1}h$, $\rho^{-1}f \cap (\theta^{-1}\mathfrak{m})^* = \emptyset$ n'est pas vide et si $g$ est un élément quelconque de cet ensemble, alors

$$ \rho^{-1} f \cap (\theta^{-1} \mathfrak{m})^* = \{g' : g' = \tau g, \tau \in T\} $$

d'après la proposition 4.1.

Nous allons réunir tous ces résultats dans une proposition.

**PROPOSITION 4.2.** - A tout mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ de $\mathcal{X}^{*+}$ on peut associer un sous-ensemble $U_f = \rho^{-1} f \cap (\theta^{-1} \mathfrak{m})^*$ de $\mathcal{Y}^*$ tel que $\forall g = y_{l_1} y_{l_2} \dots y_{l_s} \in U_f$, alors

$$ (i) \quad \alpha\theta g = \alpha f $$

$$ (ii) \quad \theta y_{l_p} \in \mathfrak{m} \quad (1 < p < s) $$

$$ (iii) \quad \text{si l'on pose } \beta f = x_{j_1} x_{j_2} \dots x_{j_r} \text{ et} $$

$$ \theta y_{l_p} = x_{v_{K_{p-1}}+1} x_{v_{K_{p-1}}+2} \dots x_{v_{K_p}} \quad (1 \le p \le s; K_o = 0), $$

il correspond à tout $k \in [1, r]$ un et un seul $k' \in [1, r]$ tel que

$$ (x_{j_k}, \gamma_k \beta f) = (x_{v_k}, \gamma_k \theta g) \quad (4.5.2) $$
5.1)

et

$$x_{i_k} = x_{v_{k'-1}} \quad \text{si} \quad k' \neq K_{p-1} + 1$$

pour tout $p \in [1, s]$

$$= x_{v_{K_p}} \quad \text{si} \quad k' = K_{p-1} + 1.$$

De plus, si $g = y_{l_1} y_{l_2} \dots y_{l_s}$ et

$$g' = y_{l'_1} y_{l'_2} \dots y_{l'_s}, \in U_f,$$

alors

(iv) $s = s'$

(v) il existe un mot $g'' = y_{l_1''} y_{l_2''} \dots y_{l_s''} \in U_f$ tel que $\theta y_{l_1''}$ et $\theta y_{l_p''}$ sont conjugués ($1 \le p \le s$) et tel qu'on peut passer de la suite $(\theta y_{l_1}, \theta y_{l_2}, \dots, \theta y_{l_s})$ à la suite $(\theta y_{l_1''}, \theta y_{l_2''}, \dots, \theta y_{l_s''})$ par une suite d'opérations $\tau$ consistant à permuter deux mots consécutifs de la suite disjoints.

Notre but va être maintenant de choisir canoniquement dans chaque sous ensemble $U_f$ un élément privilégié, ce qui nous amènera plus loin à définir le monoïde $\mathcal{C}$.

Mais établissons tout d'abord comment l'opération $\tau$ introduite au chapitre 3 correspond au produit de juxtaposition dans $\mathcal{Y}^*$.

LEMME 4.5. - Soit $f'$ et $f''$ deux mots de $\mathcal{X}^{**}$ et $g'$ et $g''$ respectivement deux éléments quelconques de $\rho^{-1} f'$ et $\rho^{-1} f''$ alors

$$f' \tau f'' = \rho (g' g''). \quad (4.5.4)$$

PREUVE.- Comme $\rho = \pi^{-1}e$, nous allons montrer

$$\pi(f' \tau f'') = e (g' g'').$$

Posons

$$f' = x_{i_1'} \dots x_{i_r'}, \quad f'' = x_{i_1''} \dots x_{i_r''}, \quad f = f' \tau f'' = x_{i_1} \dots x_{i_r}$$

$$(r = r' + r'')$$

$$\beta f' = x_{j_1'} \dots x_{j_r'}, \quad f'' = x_{j_1''} \dots x_{j_r''}, \quad f = x_{j_1} \dots x_{j_r}$$

$$g' = y_{l_1'} \dots y_{l_s'}, \quad g'' = y_{l_1''} \dots y_{l_s''}, \quad g = g' g'' = y_{l_1} \dots y_{l_s} \quad (s = s' + s'')$$
$$ \theta g' = x_{v_1'} \dots x_{v_{r'}}' $$

$$ \theta g'' = x_{v_1''} \dots x_{v_{r''}}'' $$

$$ \text{et} \quad \theta g = x_{v_1} \dots x_{v_r} $$

$$ h = \alpha(f'f''). $$

Soit aussi $x_{u_1}, x_{u_2}, \dots, x_{u_d}$ les $d = \dim h$ lettres $x$ de $X$ pour lesquelles $hx > 0$. et posons

$$ h x_{u_t} = n_t \quad (\alpha f') (x_{u_t}) = n'_t \quad (\alpha f'') (x_{u_t}) = n''_t \quad (1 \le t \le d). $$

Il nous faut prouver

$$ (e(g'g'')) (x_{u_t}, m_t) = (\pi(f' \upharpoonright f'')) (x_{u_t}, m_t) $$

$$ \text{pour tout } (x_{u_t}, m_t) \in \mathbb{N}(h). $$

Soit donc $(x_{u_t}, m_t)$ un couple de $\mathbb{N}(h)$. Faisons-lui correspondre l'entier $q$ ($1 \le q \le r$) défini par

$$ x_{v_q} = x_{u_t} \quad \text{et} \quad \gamma_q \theta g = m_t. $$

Si $q$ satisfait $1 \le q \le r'$ (resp. $r' + 1 \le q \le r' + r''$) faisons correspondre à l'entier $q$ l'entier $q'$ ($1 \le q' \le r'$) (resp. $q''$ ($1 \le q'' \le r''$)) défini par

$$ x_{v'_q}, (\text{resp. } x_{v''_q}) = x_{v_q} $$

et

$$ \gamma_q, \theta g' \text{ (resp. } \gamma_{q''} \theta g'') = \gamma_q \theta g $$

$$ \text{c'est-à-dire } q' = q \text{ et } q'' = q - r'. $$

Faisons alors correspondre à $q'$ (resp. $q''$) l'entier $w'$ (resp. $w''$) défini par

$$ x_{j'_w} = x_{v'_q}, \quad (\text{resp. } x_{j''_w} = x_{v''_q}) $$

et

$$ \gamma_w, f' = \gamma_q, \theta g' \text{ (resp. } \gamma_{w''} f'' = \gamma_{q''} \theta g'') ; $$

puis à $w'$ (resp. $w''$) l'entier $w$

$$ w = n_1'' + \dots + n_{w-1}'' + w' \quad (\text{resp. } n_1' + \dots + n_w' + w'') $$

où $W$ est le plus petit entier ($1 \le W \le d$) satisfaisant

$$ w' \le n_1' + \dots + n_W' \quad (\text{resp. } w'' \le n_1'' + \dots + n_W'') $$
L'application $q \rightarrow w$ est une permutation de $[1, r]$ et l'on a

$$ 
\begin{aligned}
(x_{v_t}, m_t) &= (x_{v_q}, \gamma_q \theta g) = (x_{v'_q}, \gamma_q' \theta g') \quad (\text{resp. } (x_{v''_q}, \gamma_q'' \theta g'')) \\
&= (x_{j'_w}, \gamma_w' f') \quad (\text{resp. } (x_{j''_w}, \gamma_w'' f'')) = (x_{j_w}, \gamma_w f).
\end{aligned} 
\quad (4.5.5) $$

La dernière égalité provenant de la définition même de l'opération $\Gamma$ appliquée au couple $(f, f')$.

Or

$$ x_{v_{q'-1}} = x_{v'_q, -1} \quad \text{ou} \quad x_{v_{K_p}} = x_{v'_{K_p},} \quad \text{si} \quad 1 \le q \le r \\ p' = p $$

et

$$ = x_{v''_{q''}-1} \quad \text{ou} \quad x_{v_{K_p}} = x_{v'_{K_p},} \quad \text{si} \quad r' + 1 \le q \le r' + r'' \\ p'' = p - s'. $$

D'autre part, puisque

$$ \rho g' = f' \quad \text{et} \quad \rho g'' = f'' $$

on a

$$ x_{v_{q'-1}} = x_{v'_q, w'} \quad \text{si} \quad q' \neq K'_{p',-1} + 1 $$

et

$$ x_{v'_{K_p}} = \quad \text{si} \quad q' = K'_{p',-1} + 1 $$

et des identités analogues pour le couple $(q'', w'')$.

Enfin, par définition de l'opération $\Gamma$ et de l'entier $w$

$$ x_{i_w} \quad (\text{resp. } x_{i_w''}) = x_{i_w} $$

Soit en vertu des égalités (4.5.5)
$$e (g' g'') (x_{u_t}, m_t)$$

$$= X_{v_{q-1}}$$

$$= X_{v_{K_p}}$$

$$(\text{si } q = K_{p-1} + 1)$$

$$= = = =$$

$$= X_{v'_{q'-1}} = X_{v''_{q''-1}}$$

$$= X_{v'_{K_p''}} = X_{v''_{K_p''}}$$

$$(\text{si } 1 \le q \le r')$$

$$(\text{si } r' + 1 \le q \le r' + r'')$$

$$(\text{si } 1 \le q \le r')$$

$$= X_{i_w^*} = X_{i_w''} = X_{i_w''}$$

$$= X_{i_w^*}$$

$$= X_{i_w} = (\pi(f' \upharpoonright f'')) (x_{u_t}, m_t).$$

Nous sommes déjà en mesure de compléter la première partie de la démonstration du théorème 3.2 à savoir

**PROPOSITION 4.3.** - $\mathcal{M}$ forme un système de générateurs de l'algèbre large $\Omega [[X_\tau^*]]$ ou encore à tout $f \in X^*$ on peut associer une suite $(f_1, f_2, \dots, f_s)$ d'éléments de $\mathcal{M}$ tels que

$$f = f_1 \tau f_2 \tau \dots \tau f_s .$$

**PREUVE.-** D'après la proposition 4.2, on peut toujours associer à $f \in X^*$ un élément $g = y_{l_1} y_{l_2} \dots y_{l_s}$ tel que

$$\theta y_{l_p} \in \mathcal{M} \quad (1 \le p \le s)$$

et tel que

$$\rho g = \rho y_{l_1} y_{l_2} \dots y_{l_s} = f .$$

Posons

$$\rho y_{l_p} = f_p \quad (1 \le p \le s).$$

Alors on a

$$f_1 \tau f_2 \tau \dots \tau f_s = f$$

en vertu du lemme 4.5 et de l'associativité de l'opération $\tau$.

Supposons maintenant qu'il existe un sous-ensemble totalement ordonné $\mathfrak{S}_0$ de $\mathcal{M}$ tel que toute classe de mots conjugués multi-linéaires de $X^*$ a une intersection avec $\mathfrak{S}_0$ réduite à un seul
élément. Nous notons $S_o f$ le mot de $\mathfrak{S}_o$ conjugué à $f \in \mathfrak{M}$ et
posons $\mathfrak{S} = \theta^{-1} \mathfrak{S}_o$.

En fait, nous prendrons plus bas sur $\mathfrak{X}^*$ l'ordre lexicographique induit soit par l'ordre de $\mathfrak{X}$ soit par l'ordre inverse de $\mathfrak{X}$ et pour ces ordres $\mathfrak{S}_o$ sera l'ensemble des mots multilinéaires minimum dans leurs classes de conjugués.

Prenons sur $\mathfrak{S}$ l'ordre induit par celui de $\mathfrak{S}_o$ :

$g < g'$ (dans $\mathfrak{S}$) $\Longleftrightarrow$ $\theta g < \theta g'$ (dans $\mathfrak{S}_o$).

D'après la proposition 4.1, $\rho^{-1}f \cap \mathfrak{S}^*$ est non vide pour tout $f \in \mathfrak{S}^*$ et tous ses éléments ont même image abélienne (dans $\overline{\mathfrak{y}^*}$). On peut donc donner la

**Définition 4.1.** - Le mot $g = y_{l_1} y_{l_2} \dots y_{l_s}$ de $\rho^{-1} f \cap \mathfrak{S}^*$ est canonique si $s=1$ ou si $s>1$ et

$$ 
\begin{align*}
y_{l_1} &= \max \{ \mathbf{P} g : g \in \rho^{-1} f \cap \mathfrak{S}^* \} \\
y_{l_2} &= \max \{ \mathbf{P} g : g \in \rho^{-1} \rho y_{l_2} \dots y_{l_s} \cap \mathfrak{S}^* \} \quad (4.5.6) \\
\vdots & \\
y_{l_{s-1}} &= \max \{ \mathbf{P} g : g \in \rho^{-1} \rho y_{l_{s-1}} y_{l_s} \cap \mathfrak{S}^* \}.
\end{align*}
$$

La proposition 4.1. entraîne qu'il y a et un seul élément canonique dans chaque classe $\rho^{-1} f \cap \mathfrak{S}^*$ et si $g = y_{l_1} y_{l_2} \dots y_{l_s}$ est un tel élément

$y_{l_k} < y_{l_{k+1}} \implies \theta y_{l_k}$ et $\theta y_{l_{k+1}}$ sont non disjoints.

L'élément canonique de $\rho^{-1} f \cap \mathfrak{S}^*$ sera noté $C f$ et $f \mapsto Cf$ est ainsi une bijection de $\mathfrak{X}^*$ sur l'ensemble des mots canoniques $\{C f : f \in \mathfrak{X}^*\}$.

Nous définissons alors sur cet ensemble une opération notée $\circ$, en posant pour deux éléments canoniques

$$ C f \text{ et } C f' \quad (f \text{ et } f' \in \mathfrak{X}^*), \tag{4.5.7} $$

$$ C f \circ C f' = C \rho (Cf \cdot Cf') $$

Soit $\mathfrak{C}$ le couple formé par l'ensemble $\{C f : f \in \mathfrak{X}^*\}$ et l'opération $\circ$. C'est alors un monoïde, propriété qui se déduit
immédiatement de l'associativité du produit de juxtaposition dans
et de la définition de $C$ et $\rho$, et l'on a

PROPOSITION 4.4. - $C : \mathcal{X}_1^* \to \mathcal{C}$ est un isomorphisme.

PREUVE.- Que $C$ soit une bijection est une conséquence du fait
que l'application $\rho$ est surjective et que toute classe $\rho^{-1}f \cap g'$
ne contient qu'un seul élément canonique.

Reste à vérifier $C(f \tau f') = C f \circ C f'$.

En effet, dans le lemme 4.5 on a montré $f \tau f' = \rho(gg')$ pour deux éléments quelconques $g$ et $g'$ respectivement $\in \rho^{-1}f$ et $\in \rho^{-1}g'$.

D'où en particulier

$$
f \tau f' = \rho(Cf. Cf')
$$

et en appliquant $C$ aux deux membres, on a

$$
C (f \tau f') = C \rho (Cf. Cf') = Cf \circ Cf'.
$$

4.6. L'identité sur les ζ.

Dans cette section, nous complétons la démonstration du théorème 3.2 en prouvant l'identité (4.6.2) ci-dessous sur les ζ.

Montrons d'abord

LEMME 4.6. -

$$
\zeta f = (-1)^{\lambda_{Cf+1}} \quad \text{pour tout } f \in \mathcal{M}. \qquad (4.6.1)
$$

PREUVE.- Soit

$$
f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{M}
$$

et $\beta f = x_{j_1} x_{j_2} \dots x_{j_r}$ le mot non décroissant qui lui est associé.

Posons

$$
C f = y_{l_1} y_{l_2} \dots y_{l_s}.
$$
Cf est une représentation en cycles multilinéaires de l'application $(x_{j_k}, 1) \to x_{i_k}$ ($1 \le k \le r$).

De là, la permutation $i_k \to j_k$ ($1 \le k \le r$) est le produit de s cycles disjoints d'ordre $\lambda_\theta y_{l_1}, \lambda_\theta y_{l_2}, \dots, \lambda_\theta y_{l_s}$ respectivement.

Comme une permutation est paire ou impaire suivant que le nombre de ses cycles d'ordre pair est pair ou impair on a

$$ \epsilon_f = (-1)^{n_f} $$

où $n_f$ est le nombre d'indices $p$ ($1 \le p \le r$) tels que $\lambda_\theta y_{l_p}$ est pair.

Mais d'autre part,

$$ \lambda f \equiv s - n_f \pmod{2} $$

puisque la somme des longueurs des mots $\theta y_{l_p}$ tels que $\lambda_\theta y_{l_p}$ est pair est forcément paire.

D'où

$$ n_f + \lambda f \equiv s \pmod{2} $$

et

$$ \zeta f = \epsilon_f (-1)^{\lambda f + 1} = (-1)^{n_f + \lambda f + 1} = (-1)^{s+1} = (-1)^{\lambda c_f + 1} $$

Nous poserons pour $f \in \mathfrak{M}$, $\eta C_f = (-1)^{\lambda c_f + 1} = \zeta f$.

Nous montrons enfin

**PROPOSITION 4.5.** - Pour tout $f \in \mathcal{X}^{*+}$

$$ \sum \zeta f_{m_1} \zeta f_{m_2} \dots \zeta f_{m_t} = 1 $$

où la somme est étendue à toutes les suites $f_{m_1}, f_{m_2}, \dots, f_{m_t}$ de $\mathfrak{M}$ telles que $f = f_{m_1} \tau f_{m_2} \dots \tau f_{m_t}$.

**PREUVE.** - Un sous-ensemble $\mathfrak{S}_0$ de $\mathfrak{M}$ ayant été choisi pour la définition des mots canoniques $C_f$ ($f \in \mathcal{X}^*$) (voir définition 4.1) et posant $\mathfrak{S} = \Theta^{-1} \mathfrak{S}_0$, nous avons, d'après la proposition 4.4
$$f = f_{m_1} \circ f_{m_2} \circ \dots \circ f_{m_t}$$

si et seulement si

$$C f = C f_{m_1} \circ C f_{m_2} \circ \dots \circ C f_{m_t}$$

dans le monoïde $\mathcal{C}$.

D'autre part, d'après le lemme 4.6, pour $f \in \mathcal{M}$, on a

$$\eta C f = \zeta f.$$

Désignons par $\mathcal{C}$ le sous-ensemble $C\mathcal{M}$ de $\mathcal{C}$.

Il est donc équivalent de montrer que pour tout $f \in \mathcal{X}^*$

$$\Sigma \eta C f_{m_1} \cdot \eta C f_{m_2} \cdot \dots \cdot \eta C f_{m_t} = 1 \quad (4.6.3)$$

où la somme est étendue à toutes les suites $C f_{m_1}, C f_{m_2}, \dots, C f_{m_t}$ d'éléments de $\mathcal{C}$ telles que

$$C f = C f_{m_1} \circ C f_{m_2} \circ \dots \circ C f_{m_t}.$$

$\mathcal{C}$ est encore le sous-ensemble de $\mathcal{S}^*$ contenant $\mathcal{S}$ et les mots $g = y_{l_1} y_{l_2} \dots y_{l_s}$ ($s > 1$) de $\mathcal{Y}^*$ tels que $(\theta y_{l_1}, \theta y_{l_2}, \dots, \theta y_{l_s})$ forme une suite décroissante de mots de $\mathcal{S}_0$ disjoints deux à deux, et pour $g \in \mathcal{C}$ on a

$$\eta g = (-1)^{\lambda} g^{+1}.$$

Par définition de $C$, on a pour toute suite $(g_{m_1}, g_{m_2}, \dots, g_{m_t})$ d'éléments de $\mathcal{C}$,

$$g_{m_1} \cdot g_{m_2} \cdot \dots \cdot g_{m_t} = C \rho(g_{m_1} g_{m_2} \dots g_{m_t}) = C f$$

si et seulement si le mot $g_{m_1} g_{m_2} \dots g_{m_t} \in \rho^{-1} f$.

Pour tout $f \in \mathcal{X}^*$, nous désignons alors par $Rf$ l'ensemble des suites $(g_{m_1}, g_{m_2}, \dots, g_{m_t})$ d'éléments de $\mathcal{C}$ tels que $g_{m_1} g_{m_2} \dots g_{m_t} \in \rho^{-1} f$ et nous allons montrer l'identité

$$\sum_{(g_{m_1}, g_{m_2}, \dots, g_{m_t}) \in Rf} \eta g_{m_1} \cdot \eta g_{m_2} \cdot \dots \cdot \eta g_{m_t} = 1 \quad (4.6.4)$$

pour tout $f \in \mathcal{X}^*$.
Nous désignons par $R\{f/g_0\}$ l'ensemble des suites $(g_{m_2}, \dots, g_{m_t})$ de mots de $\mathfrak{C}$ tels que $g_0 g_{m_2} \dots g_{m_t} \in Rf$ pour un mot $g_0$ fixé $\in \mathfrak{C}$.

Si $R\{f/g_0\}$ n'est pas vide, alors $R\{f/g_0\} = Rf'$ pour un certain $f'$ de $\mathcal{X}^*$ et l'on a $\lambda Cf' < \lambda Cf$.

En effet

$$ \rho(g_0 g_{m_2} \dots g_{m_t}) = f \iff f = f'' \tau f' $$

avec $f'' = \rho g_0$ et $f' = \rho(g_{m_2} \dots g_{m_t})$ d'après la proposition 4.4.

D'où $g_{m_2} \dots g_{m_t} \in R f'$ et $f'$ ne dépend pas de la suite $(g_{m_2}, \dots, g_{m_t})$ choisie puisque si $g_{m_2'} \dots g_{m_t'} \in R\{f/g_0\}$ on a en-core $\rho(g_0 g_{m_2'} \dots g_{m_t'}) = f$

d'où

$$ \text{si } f''' = \rho(g_{m_2'} \dots g_{m_t'}), $$

$$ f = f'' \tau f' = f'' \tau f''' \implies f' = f'''. $$

Réciproquement, pour tout $(g_{m_2}, \dots, g_{m_t}) \in R f'$ et $g_0 \in \mathfrak{C}$, en posant $\rho g_0 = f''$,

$$ f'' \tau f' = \rho(g_0 g_{m_2} \dots g_{m_t}); $$

d'où

$$ (g_0, g_{m_2}, \dots, g_{m_t}) \in Rf \quad \text{pour} \quad f = f'' \tau f' $$

Pour $f \in \mathcal{X}^*$ nous définissons enfin l'ensemble

$$ \mathcal{R}f = \{y : y \in \mathfrak{S} ; y \mathcal{Y}^* \cap \rho^{-1}f \cap \mathfrak{S}^* \neq \emptyset\} $$

c'est-à-dire l'ensemble des $y \in \mathfrak{S}$ qui apparaissent comme première lettre d'une représentation en cycles $g \in \rho^{-1}f \cap \mathfrak{S}^*$.

Soit $p = \text{card } \mathcal{R}f$ et soit $y_1, y_2, \dots, y_p$ ses p éléments rangés en ordre décroissant $(y_1 > y_2 > \dots > y_p)$ pour l'ordre dans $\mathfrak{S}$. Il résulte alors de la proposition 4.1 que si $p > 1$, tous les mots $\theta y_1, \theta y_2, \dots, \theta y_p$ sont disjoints deux à deux.

D'autre part, si $(g_{m_1}, g_{m_2}, \dots, g_{m_t}) \in R f$ avec

$$ g_{m_1} = y_{q_1} y_{q_2} \dots y_{q_n} \quad (n > 1), $$

6.3

et les
$\theta y_1$,
$\theta y_2$,
$\dots$
deux,

, $g_{m_t}$

semble
s que
alors les mots $\theta y_{q_1}, \theta y_{q_2}, \dots, \theta y_{q_n}$ sont disjoints deux à deux puisque $g_{m_1} \in \mathfrak{C}$. Par suite, tout mot $g = y_{q_1 l_1} y_{q_2 l_2} \dots y_{q_n l_n} g_{m_2} \dots g_{m_t}$ où $l_1, l_2, \dots, l_n$ est une permutation quelconque de $[1, n]$, est encore un élément de $\mathfrak{P}^{-1} f \cap \mathfrak{S}^*$ d'après la proposition 4.1.

Donc, en particulier, tous les $y_{q_1}, y_{q_2}, \dots, y_{q_n}$ apparaissent comme première lettre d'une représentation en cycles $g \in \mathfrak{P}^{-1} f \cap \mathfrak{S}^*$.

Ou encore $y_{q_1}, y_{q_2}, \dots, y_{q_n} \in \mathfrak{R} f$.

Ainsi, l'ensemble de tous les premiers élément $g_{m_1}$ des suites $(g_{m_1}, g_{m_2}, \dots, g_{m_t})$ de $Rf$ n'est autre que l'ensemble $R'$f des mots décroissants $g$ du sous-monoïde libre engendré par $\mathfrak{R} f$.

Nous avons alors

$$ \sum_{(g_{m_1}, g_{m_2}, \dots, g_{m_t}) \in Rf} \eta g_{m_1} \eta g_{m_2} \dots \eta g_{m_t} = \sum_{g_o \in R'f} \eta g_o \sum_{(g_{m_2}, \dots, g_m) \in R \{f/g_o\}} \eta g_{m_2} \dots \eta g_{m_t} $$

Or, pour $g_o$ fixé $\in R'f$, $R\{f/g_o\} = Rf'$ où $\lambda C f' < \lambda C f = g_o$, d'après ce qui a été montré plus haut.

Ainsi, par récurrence sur $s$, on a

$$ \sum_{(g_{m_1}, g_{m_2}, \dots, g_{m_t}) \in Rf} \eta g_{m_1} \eta g_{m_2} \dots \eta g_{m_t} = \sum_{g_o \in R'f} \eta g_o = \sum_{g_o \in R'f} (-1)^{\lambda g_o + 1} = \sum_{n=1}^{p} (-1)^{n+1} Rf' \quad \text{où } R'_n \text{ est le nombre de mots de } R'f \text{ de longueur égale à } n. $$

Or, pour tout sous-ensemble $\{y_{q_1}, y_{q_2}, \dots, y_{q_n}\}$ de mots de $\mathfrak{R}f$, il n'y a qu'un et qu'un seul mot décroissant,

$$ g = y_{q_1 l_1} y_{q_2 l_2} \dots y_{q_n l_n} $$

ayant même image abélienne que

$$ y_{q_1} y_{q_2} \dots y_{q_n} \quad (1 \le n \le p). $$

Ainsi $R'_n$ est égal au nombre de combinaisons de $n$ éléments qu'on peut extraire de l'ensemble $\{y_1, y_2, \dots, y_p\}$ soit $\binom{p}{n}$.

D'où
$$ \sum_{n=1}^{p} (-1)^{n+1} R_n = - \sum_{n=1}^{p} (-1)^n \left(\binom{p}{n}\right) = -(1-1)^n + (-1)^0 \left(\binom{p}{0}\right) = 1 $$

ce qui complète la preuve de la proposition 4.5.

Enfin, les propositions 4.3 et 4.5 complètent définitivement la démonstration du théorème 3.1.
# 5. Les factorisations de monoïdes libres

## 5.1. Introduction.

Nous rappelons dans ce chapitre le théorème de factorisation de Schützenberger et en donnons quelques applications.

Nous mentionnons aussi la factorisation en mots lexicographiques standards (introduite par Lyndon [25] puis Chen, Fox et Lyndon [8] et Širšov [37]) et en déduisons une factorisation (proposition 5.2) que nous utiliserons au chapitre suivant.

## 5.2. Le théorème de factorisation de Schützenberger.

Soit toujours $X^*$ le monoïde libre engendré par un ensemble $X$.

Nous avons donné au paragraphe 2.1 la notion de mots conjugués de $X^*$. Si $X'$ est un sous-monoïde de $X^*$ nous dirons encore que les mots $f f'$ et $f' f$ de $X^*$ sont $X' - \text{conjuagués}$ si $f$ et $f'$ appartiennent tous deux à $X'$.

Soit maintenant $\{Y_j : j \in J\}$ une famille de sous-ensembles de $X^*$ où $J$ est un ensemble totalement ordonné. Pour une telle famille, Schützenberger [34] considère les conditions (I), (I') et (II) suivantes.

(I) (resp. (I')) Chaque $f \in X^{*+}$ a au plus (resp. au moins) une factorisation de la forme $f = f_1 f_2 \dots f_s$ ($s > 0$) où chaque $f_i \in Y_{j_i}$ et $j_1 \ge j_2 \ge \dots \ge j_s$ (pour l'ordre total dans $J$).

(II) Chaque classe $C$ de mots conjugués a une intersection non vide avec le sous-monoïde $Y_j^*$ engendré par $Y_j$ pour un et un seul $j \in J$ ; de plus $C \cap Y_j^*$ est une classe de mots $Y_j^* - \text{conjuagués}$. Il montre alors le théorème suivant.
THEOREME 5.1. (Schützenberger [34]). - Deux quelconques des conditions (I), (I') et (II) entraînent la troisième.

Son résultat lui permet en outre de donner dans l'algèbre large $\mathbb{R}[[\mathcal{X}^*]]$ une expression pour $\log(1 - \mathbb{X})^{-1}$ où $\mathbb{X}$ est la série formelle $\Sigma^*\{f : f \in \mathcal{X}^*\}$ ; à savoir

$$ \text{Log} (1 - \mathbb{X})^{-1} = \sum \left\{ \frac{1}{\text{card } C} \mid \Sigma \{ \log (1 - f)^{-1} : f \in C \} : \text{toutes les classes } C \text{ d'éléments primitifs} \right\}. $$

Dans le même article, il montre qu'on peut construire pour un ensemble $\mathcal{X}$ non vide une infinité de familles $\{Y_j : j \in J\}$ satisfaisant les conditions (I) et (I').

Nous y reviendrons au début du chapitre 7.

Dans le prochain paragraphe, nous donnons simplement quelques conséquences de ce résultat.

### 5.3. Quelques applications et définitions.

Nous dirons que la donnée de la famille $\{Y_j : j \in J\}$ de sous-ensembles de $\mathcal{X}^*$(J totalement ordonné) est une factorisation de Schützenberger (factorisation (S)) si les deux consitions (I) et (I') sont remplies. La notion de factorisation (S) est donc la transposition au cas des monoïdes libres de la notion de factorisation des groupes (Cf. par exemple Szép [40]). Si un mot $f$ de $\mathcal{X}^*$ est de longueur 1, il est forcément contenu dans un et un seul $Y_j$ ($j \in J$). Réciproquement, nous dirons que la factorisation (S) est de type $a$, si chaque $Y_j$ contient au plus un mot de $\mathcal{X}^*$ de longueur 1. Nous dirons aussi qu'une factorisation (S) est de type $b$, si chaque ensemble $Y_j$ ne contient qu'un seul élément de $\mathcal{X}^*$. La donnée d'une telle factorisation est alors équivalente à la donnée d'un sous-ensemble $\mathcal{H}$ de mots de $\mathcal{X}^{**}$ et d'un ordre total sur $\mathcal{H}$ que l'on notera $\not\leq$, tels que chaque élément $f \in \mathcal{X}^{**}$ a une et une seule factorisation de la forme $f_1 f_2 \dots f_s$ ($s > 0$) où

$$ (S') \qquad f_1, f_2, \dots, f_s \in \mathcal{H} \qquad (1) $$

$$ f_1 \geq f_2 \geq \dots \geq f_s \qquad (2) $$

Nous pouvons tout de suite donner une application du théorème 5.1 sous la forme d'un
COROLLAIRE 5.1. - Pour une factorisation de type b, toute classe de mots conjugués, contient une puissance d'un et d'un seul mot de $\mathcal{H}$, et tous les éléments de $\mathcal{H}$ sont primitifs.

PREUVE. - En effet, le sous-monoïde $Y_j^*$ engendré par $Y_j$ est à un seul générateur et la première propriété découle immédiate-ment de la condition (II). Pour la deuxième propriété, observons que si l'on a $f \in \mathcal{H}$ et $f = f^{1p}$ (p entier $> 0$ maximal), alors soit $f''$ le mot (primitif) conjugué à $f'$ qui soit élément de $\mathcal{H}$. Alors les mots $f''^p$ et $f^{1p}$ sont conjugués ; soit C leur classe. Nous avons alors $C \cap \{f\}^* \neq \emptyset$ et $C \cap \{f''\}^* \neq \emptyset$. Mais d'après la conditions (II) cela ne peut arriver que si $f = f''$ ; donc f est primitif.

CONSEQUENCE 5.1. - *Pour une factorisation de type b, toute classe primitive contient un et un seul mot de $\mathcal{H}$.*

Cette remarque est suffisante pour démontrer la formule dite de Witt pour toutes les factorisations de type b. Cette formule a été démontrée par plusieurs auteurs et sa démonstration combina-toire s'appuie sur un résultat combinatoire dû au Colonel Moreau (cité dans Lucas [24]).

LEMME 5.1. (Lucas [24] p. 501-503). - *Le nombre de classes conju-guées de mots primitifs de longueur n dans un monoïde libre engendré par un ensemble de q éléments est donné par $(1/n) \sum_{d|n} \mu(n/d) q^d$ où $\mu$ désigne la fonction de Möbius (définie sur $\mathbb{N}$ et telle que pour $a \in \mathbb{N}$, $\mu(a) = 0$ (resp. $(-1)^a$) si a est divisible (resp. n'est pas divisible) par un carré $\neq 1$, k désignant le nombre de diviseurs premiers de a).*

Supposons donc donnée une factorisation (S) de type b, c'est-à-dire un sous-ensemble $\mathcal{H}$ de mots (primitifs) de $\mathcal{X}^*$ et un ordre total $\leq$ sur $\mathcal{H}$, tel que chaque mot $f \in \mathcal{X}^{*+}$ a une et une seule factorisation $f_1, f_2, ... f_s$ ($s > 0$) ayant les propriétés (1) et (2) de (S').

Si $\mathcal{Q}$ est un sous-ensemble de $\mathcal{X}$ de q éléments $\{x_1, x_2, ..., x_q\}$ ($q > 0$) et n un entier positif, nous désignons par $Q_n$, l'ensemble des mots du sous-monoïde $Q^*$ de $\mathcal{X}^*$ en-gendré par $\mathcal{Q}$, de longueur n. Nous désignons aussi par $\mathcal{Q}(n_1, n_2, ..., n_q)$ l'ensemble des mots f de $Q^*$ tels que
$$ (\alpha f)(x_1) = n_1, \dots, (\alpha f)(x_q) = n_q, $$

où $n_1, n_2, \dots, n_q$ sont q entiers positifs tels que

$$ n_1 + n_2 + \dots + n_q = n. $$

Nous avons alors

PROPOSITION 5.1. -

$$ \mathrm{card} (Q_n \cap \mathcal{H}) = 1/n \sum_{d|n} \mu(n/d) q^d \quad (5.3.1) $$

$$ \mathrm{card} (Q(n_1, n_2, \dots, n_q) \cap \mathcal{H}) = 1/n \sum_{d|n_1, \dots, n_q} \mu(d) \left(\frac{n}{d}\right)! \left(\frac{n_1}{d}\right)! \dots \left(\frac{n_q}{d}\right)! \quad (5.3.2) $$

où $\mu$ désigne la fonction de Möbius.

PREUVE. - (5.3.1) se déduit immédiatement du lemme de Moreau et de la conséquence 5.1. Pour la seconde formule, nous observerons que la classe abélienne $Q(n_1, n_2, \dots, n_q)$ contient $\frac{n!}{n_1! \dots n_q!}$ éléments. D'où la formule

$$ \frac{n!}{n_1! \dots n_q!} = \sum_{d|n_1, n_2, \dots, n_q} \mathrm{card} \ Q \left( \frac{n_1}{d}, \frac{n_2}{d}, \dots, \frac{n_q}{d} \right) $$

et la formule (5.3.2) en appliquant la formule d'inversion de Möbius.

Notons que ces formules ont aussi été données par Širšov [37], Chen, Fox et Lyndon [8] et Hall [19] pour chacune de leurs factorisations.

Donnons maintenant quelques indications sur la factorisation en mots lexicographiques standards, factorisation qu'on utilisera dans le chapitre suivant pour donner une première démonstration d'un théorème combinatoire.

Soit $\mathcal{X}$ un ensemble totalement ordonné et soit $\leq$ l'ordre lexicographique sur $\mathcal{X}^*$ induit par l'ordre de $\mathcal{X}$. Soit $\mathcal{H}$ le sous-ensemble de $\mathcal{X}^{**}$ défini par la condition (5.3.3)

$$ f \in \mathcal{H} \iff (f = f'f'' ; f' , f'' \in \mathcal{X}^{**} \Rightarrow f < f'') \quad (5.3.3) $$
Alors

THEOREME 5.2. (Sirsov [37], Lyndon [25]). - *Tout mot* $f \in \mathcal{X}^{**}$ a une et une seule factorisation $f = f_1 f_2 \dots f_s$ où tous les éléments $f_k$ appartiennent à $\mathcal{H}$ et satisfont $f_1 \succeq f_2 \succeq \dots \succeq f_s$.

Nous ne donnons pas ici la démonstration, car cette factorisation sera de nouveau explicitée au chapitre 7 et donnée comme un exemple d'une famille plus générale de factorisations. La définition (5.3.3) est aussi (Cf. [8]) équivalente à la définition

$f \in \mathcal{H} \iff f$ est minimum dans sa classe de conjugués. (5.3.4)

$\mathcal{H}$ est encore désigné comme l'ensemble des mots standards de $\mathcal{X}^*$.

En vue de démontrer le résultat combinatoire du chapitre suivant, nous donnons maintenant une nouvelle factorisation (S) déduite de celle-ci :

La première lettre $\mathbf{P}f$ d'un mot standard $f \in \mathcal{H}$ est forcément une lettre minimale du mot, d'après la définition (5.3.3) et les propriétés de l'ordre lexicographique. Désignons par $\mathcal{K}_0$ l'ensemble des mots standards $f$ de $\mathcal{H}$ tels que $(\alpha f)(\mathbf{P}f) = 1$ (les mots minimum dans leurs classes de conjugués et dont la première lettre est aussi minimum parmi les autres lettres du mot). Alors tout mot standard $f$ a une factorisation unique $f = f_1 f_2 \dots f_m$ où $f_1, f_2, \dots, f_m \in \mathcal{K}_0$ et où $\mathbf{P}f_1 = \mathbf{P}f_2 = \dots = \mathbf{P}f_m$.

Ou encore, si $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{H}$, soit

$$ \Lambda_1(=1), \Lambda_2, \dots, \Lambda_m (\le r) $$

la suite croissante des indices tels que

$$ \mathbf{P}f = x_{i_{\Lambda_1}} = x_{i_{\Lambda_2}} = \dots = x_{i_{\Lambda_m}} $$

et $x_{i_1} > \mathbf{P}f$ si

$$ l \notin \Lambda_1, \Lambda_2, \dots, \Lambda_m $$

alors le mot

$$ x_{i_{\Lambda_t}} x_{i_{\Lambda_{t+1}}} \dots x_{i_{\Lambda_{t+1}^{-1}}} (\Lambda_{m+1} = r+1) $$
a seulement sa première lettre égale à $\mathbf{P}f$, et comme celle-ci est minimale parmi les lettres de $f$, il appartient à $\mathcal{K}_0$.

Il résulte alors du théorème 5.2.

**PROPOSITION 5.2.** - *Tout mot* $f \in \mathcal{X}^{*+}$ *a une et une seule factorisation* $f_1 = f_1 f_2 \dots f_s$ *où* $f_1, f_2, \dots, f_s \in \mathcal{K}_0$ *et où*

$$ \mathbf{P}f_1 \ge \mathbf{P}f_2 \ge \dots \ge \mathbf{P}f_s. $$

Dans la terminologie du théorème 5.1, $J$ est identique à l'ensemble totalement ordonné $\mathcal{X}$ et $Y_j$ est le sous-ensemble des mots $f$ de $\mathcal{K}_0$ tels que $\mathbf{P}f = j \ (\in J)$.
# 6. Une application de la représentation en cycles du monoïde libre

## 6.1. Introduction.

Nous donnons dans ce chapitre la démonstration d'un théorème combinatoire non commutatif (théorème 6.1 ci-dessous). Une autre démonstration en sera donnée au chapitre 8 lorsque nous aurons introduit la notion de factorisation spéciale d'un monoïde libre. Ce résultat aura une interprétation naturelle en termes de calcul des probabilités qui sera donnée au chapitre 9.

Avant de démontrer ce résultat combinatoire, nous donnerons la définition d'un opérateur $\delta'$ (paragraphe 6.2) qui nous permettra de construire pour tout mot $f$ d'un monoïde libre $\mathcal{X}^*$ une et une seule représentation en cycles de $f$ ayant la propriété d'appartenir à $\mathcal{K}_1$ (ensemble défini ci-dessous par (6.2.8) et (6.2.9)). Nous en déduirons alors la construction d'une permutation $\Phi$ de $\mathcal{X}^*$ qui va complètement expliciter le résultat combinatoire du théorème 6.1'.

La construction que nous allons donner s'appuie sur les résultats du chapitre 4 et il nous semble bon de rappeler ici ceux que nous utiliserons, ainsi que quelques notations.

$\mathcal{X}^*$ est le monoïde libre engendré par un ensemble totalement ordonné $\mathcal{X}$ ; $\theta : \mathcal{Y} \to \mathcal{X}^*$ une bijection et $\rho : \mathcal{Y}^* \to \mathcal{X}^*$ une surjection ayant les propriétés suivantes (Cf. proposition 4.2) :

si $g = y_{l_1} y_{l_2} \dots y_{l_s} \in \mathcal{Y}^*$ et si l'on pose :

$$ \theta y_{l_p} = x_{v_{K_{p-1}+1}} x_{v_{K_{p-1}+2}} \dots x_{v_{K_p}} \quad (K_o = 0 ; 1 \le p \le s), $$

$\rho$ fait correspondre au mot $g$ un mot $\rho g = f = x_{i_1} x_{i_2} \dots x_{i_r}$ de $\mathcal{X}^*$ tel qu'en posant $\beta f = x_{j_1} x_{j_2} \dots x_{j_r}$, il correspond à tout $k \in [1, r]$ un et un seul $k' \in [1, r]$ tel que
$$ (x_{j_k}, \gamma_k \beta f) = (x_{v_k}, \gamma_k, \theta g) \qquad (6.1.1) $$

et

$$ \begin{align*} x_{i_k} &= x_{v_{k'-1}} \quad \text{si} \quad k' \neq K_{p-1} + 1 \quad \text{pour tout } p \in [1, s] \tag{6.1.2} \\ &= x_{v_{K_p}} \quad \text{si} \quad k' = K_{p-1} + 1. \end{align*} $$

En particulier, on a

$$ \alpha \theta g = \alpha f. $$

(Nous rappelons que le nombre $\gamma_k f$ où $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathfrak{S}$ est défini pour $1 \le k \le r$ et n'est autre que le nombre de lettres égales à $x_{i_k}$ dans le facteur initial $x_{i_1} x_{i_2} \dots x_{i_k}$ de $f$).

De plus, $\mathfrak{S}_0$ est un sous-ensemble de $\mathfrak{M}$ (l'ensemble des mots multilinéaires de $\mathfrak{S}^*$) ayant la propriété d'avoir une intersection non vide avec toute classe de mots conjugués de $\mathfrak{M}$. Ensuite $\mathfrak{S} = \theta^{-1} \mathfrak{S}_0$.

Nous prendrons sur $\mathfrak{S}^*$ l'ordre lexicographique induit soit par l'ordre de $\mathfrak{S}$, soit par l'ordre inverse de $\mathfrak{S}$ et $\mathfrak{S}_0$ désigne l'ensemble des mots multilinéaires minimum dans leurs classes de conjugués pour l'ordre choisi.

D'autre part, dans toute classe $\rho^{-1}f$, on distingue (définition 4.1) un et seul élément, dit *canonique*, noté $Cf$, tel que si (6.1.3)

$$ Cf = y_{l_1} y_{l_2} \dots y_{l_s} $$

alors

$$ y_{l_1}, y_{l_2}, \dots, y_{l_s} \in \mathfrak{S} \quad \text{et} \quad s = 1 \quad \text{ou} \quad s > 1 $$

et

$$ y_{l_1} = \max \{ \mathbf{P} g : g \in \rho^{-1} f \cap \mathfrak{S}^* \} $$

$$ y_{l_2} = \max \{ \mathbf{P} g : g \in \rho^{-1} \rho y_{l_2} \dots y_{l_s} \cap \mathfrak{S}^* \} $$

$$ y_{l_{s-1}} = \max \{ \mathbf{P} g : g \in \rho^{-1} \rho y_{l_{s-1}} y_{l_s} \cap \mathfrak{S}^* \} $$

(les "max" ci-dessus se rapportent à l'ordre induit sur $\mathfrak{S}$ par
1.1)

l'ordre choisi sur $\mathcal{X}^*$ et $\mathfrak{S}^*$ désigne le monoïde engendré par l'ensemble $\mathfrak{S}$).

1.2)

L'ensemble des mots canoniques munis de l'opération o ($g, g'$ canoniques, $g \circ g' = C \circ (gg')$) est un monoïde libre noté $\mathfrak{C}$. (6.1.4)

Enfin, nous désignons par $\mathcal{K}_o$ l'ensemble des mots $f \in \mathcal{X}^*$ minimum (par rapport à l'ordre choisi dans $\mathcal{X}^*$) dans leurs classes de conjugués et tels que $(\alpha f)(Pf) = 1$.

Nous posons aussi $\mathcal{K} = \theta^{-1} \mathcal{K}_o$. En particulier $\mathfrak{S}_o \subset \mathcal{K}_o$.

## 6.2. L'opérateur $\delta'$.

L'opérateur $\delta'$ que nous définissons maintenant peut être interprété comme l'inverse de l'opérateur $\delta$ introduit au paragraphe 4.3.

Plus précisément soit $\mathcal{X}^*$ le monoïde libre engendré par un ensemble totalement ordonné $\mathcal{X}$, $\theta: \mathcal{Y} \to \mathcal{X}^*$ une bijection. Alors pour un élément $(y', y'')$ du produit cartésien $\mathcal{Y} \times \theta^{-1} \mathcal{M}$, tel que $\theta y'$ et $\theta y''$ sont non disjoints, nous posons

$$ \delta'(y', y'') = y \qquad (6.2.1) $$

si et seulement si

$$ (i) \quad y' = \delta y \qquad (6.2.2) $$

(ii) $\theta y''$ et $\theta \overline{\delta} y$ sont conjugués.

$\delta'$ est donc une application de $\mathcal{Y} \times \theta^{-1} \mathcal{M}$ dans $\mathcal{Y}^*$. Les opérateurs $\delta$ et $\overline{\delta}$ ont été définis au paragraphe 4.3, mais nous allons expliciter cette définition.

Si

$$ \theta y' = x_{v_1} x_{v_2} \dots x_{v_r} $$

et

$$ \theta y'' = x_{w_1} x_{w_2} \dots x_{w_r} $$

soit $k'$ le plus grand entier $(1 \le k' \le r')$ tel que

$$ (\alpha \theta y'') (x_{v_k'}) > 0 \quad (= 1 \text{ puisque } \theta y'' \in \mathcal{M}) $$

et $k''$ l'indice tel que $x_{w_{k''}} = x_{v_{k'}}$, $(1 \le k'' \le r'')$.
Posons

$$f_1 = x_{v_1} \dots x_{v_k}$$

$$I_2 = \tau^{\prime\prime k''} \theta y'' = x_{w_k''+1} \dots x_{w_r''} \ x_{w_1} \dots x_{w_k''}$$

si $k'' > 1$ et égal à $\theta y''$ si $k'' = 1$

$$f_3 = x_{v_{k'}+1} \dots x_{v_r} \quad \text{si} \quad k' < r'$$

$$= 1 \quad \text{si} \quad k' = r'$$

Alors $\delta'(y', y'') = y = \theta^{-1}(f_1 f_2 f_3)$. Illustrons cette définition par un exemple.

*Exemple.* - Soit dans le monoïde libre $X^*$ engendré par les entiers les mots $f' = 23421$ et $f'' = 643$.

Désignons par $[x_{i_1} x_{i_2} \dots x_{i_r}]$ l'élément $\theta^{-1} f$ de $Y$ où $f = x_{i_1} x_{i_2} \dots x_{i_r} \in X^*$ et posons $y' = [23421]$ et $y'' = [643]$.

Avec les notations précédentes nous avons

$$f_1 = 234$$

$$f_2 = \tau^{\prime\prime 2} f'' = 364$$

$$f_3 = 21$$

D'où

$$\delta'(y', y'') = [f_1 f_2 f_3] = [23436421].$$

Examinons maintenant quelques conséquences immédiates de cette définition.

Tout d'abord, les mots $\theta\delta'(y', y'')$ et $\theta y'$ ont même première lettre ($x_{v_1}$ dans nos notations précédentes) d'où

$$\mathbf{P} \theta \delta'(y', y'') = \mathbf{P} \theta y'. \qquad (6.2.3)$$

D'autre part, d'après le lemme 4.4, on a

$$ey = e\delta y \quad \text{pour tout} \quad y \in Y \qquad (6.2.4)$$

soit encore
$$e \delta'(y', y'') = e(y' y'') \qquad (6.2.5)$$

puisque

$$e(y' y'') = e(\delta y. y'') \qquad \text{d'après } (6.2.2)$$

$$e(\delta\bar{y}.y'') = e(\delta\bar{y}.\delta y) \qquad \text{d'après } (6.2.2)$$

et le lemme 4.2 puisque $\theta y''$ est multilinéaire.

Enfin,

$$e(\delta y. \delta\bar{y}) = e\delta y = ey = e \delta'(y' y'')$$

d'après la définition de $\delta$, (6.2.4) et (6.2.1).

Nous allons maintenant étendre la classe des opérateurs $\delta'$ et définir une famille d'opérateurs $\delta'_p$ de la manière suivante.

Pour $g = y_{l_1} \ y_{l_2} \ \dots \ y_{l_s} \in \mathcal{Y}^*$ nous posons

$$\delta'_p g = y_{l_1} y_{l_2} \dots y_{l_{p-1}} \delta'(y_{l_p}, y_{l_{p+1}}) y_{l_{p+2}} \dots y_{l_s}$$

si les 3 conditions suivantes sont vérifiées :

$$(1) \quad 1 \le p \le s - 1$$

$$(2) \quad \theta y_{l_{p+1}} \in \mathcal{M} \qquad (6.2.6)$$

$$(3) \quad \theta y_{l_p} \text{ et } \theta y_{l_{p+1}} \text{ non dis joints ;}$$

et $\delta'_p g = g$ si au moins une de ces trois conditions n'est pas satisfaite.

Les $\delta'_p$ engendrent un monoïde d'opérateurs $\Delta'$ de $\mathcal{Y}^*$ dans $\mathcal{Y}^*$. Il résulte alors de (6.2.5) et de la définition de l'application $e$ (lemme 4.1) que pour tout opérateur $\chi' \in \Delta'$

$$e \chi' g = eg \quad (e \in \mathcal{Y}^*). \qquad (6.2.7)$$

Puisque $\pi^{-1}e = \rho$ (voir début du § 4.5), nous obtenons

$$\rho \chi' g = \rho g \qquad (6.2.7')$$

en appliquant $\pi^{-1}$ aux deux membres de (6.2.7).
Cette dernière relation peut, pour tout $\chi' \in \Delta'$ être vérifiée directement.

Désignons par $\mathcal{K}_1$ l'ensemble des mots $g = y_{m_1} y_{m_2} \cdots y_{m_t}$ de $\mathcal{Y}^*$ tels que les conditions

$$ y_{m_1}, y_{m_2}, \dots, y_{m_t} \in \mathcal{K} \qquad (6.2.8) $$

$$ \mathbf{P} \theta y_{m_1} \ge \mathbf{P} \theta y_{m_2} \ge \dots \ge \mathbf{P} \theta y_{m_t} \qquad (6.2.9) $$

(pour l'ordre choisi sur $\mathcal{X}^*$)

soient satisfaites.

La proposition 5.2 entraîne qu'à tout $f \in \mathcal{X}^{**}$ on peut faire correspondre de façon bijective une suite $(f_1, f_2, \dots, f_t)$ de mots de $\mathcal{K}_0$ tels que $\mathbf{P}f_1 \ge \mathbf{P}f_2 \ge \dots \ge \mathbf{P}f_t$. et $f = f_1 f_2 \dots f_t$. Nous désignons alors par $\phi: \mathcal{X}^* \to \mathcal{K}_1$ la bijection qui à $f$ fait correspondre l'élément $\psi f = \theta^{-1} f_1 \theta^{-1} f_2 \dots \theta^{-1} f_t$ de $\mathcal{K}_1$.

Il en résulte en particulier que

$$ \mathrm{card} \, \mathcal{K}_1 \cap G(h) = \mathrm{card} \, \alpha^{-1} h \quad (h \in \bar{\mathcal{X}}^*) \qquad (6.2.10) $$

(Nous rappelons que $G(h)$ désigne l'ensemble des mots $g \in \mathcal{Y}^*$ tels que $\theta g \in \alpha^{-1} h$).

Nous montrons alors la

**PROPOSITION 6.1.** - Toute classe $\wp^{-1}f$ ($f \in \mathcal{X}^*$) contient un et un seul élément de $\mathcal{K}_1$ ou encore

A tout mot $g = y_{l_1} y_{l_2} \cdots y_{l_t}$ de $\mathcal{C}$ correspond biunivoque. ment un mot $\chi g = y_{m_1} y_{m_2} \cdots y_{m_t}$ ($t > 0$) de $\mathcal{Y}^*$ tel que

$$ y_{m_1}, y_{m_2}, \dots, y_{m_t} \in \mathcal{K} $$

$$ \mathbf{P} \theta y_{m_1} \ge \mathbf{P} \theta y_{m_2} \ge \dots \ge \mathbf{P} \theta y_{m_t} $$

(pour l'ordre choisi dans $\mathcal{X}^*$) et

$$ \wp \chi g = \wp g. $$

Ce mot $\chi g$ est identique à $g$ si $s=1$, et pour $s > 1$ peut être obtenu en appliquant à $g$ l'opérateur
$$ \delta_t^{s-s_t} \dots \delta_2^{s_3-s_2} \dots \delta_1^{s_2-s_1} $$

où $s_1 = 1$ et $s_2, \dots, s_t (\le s)$ est la suite croissante des entiers $s_k$ tels que

$$ P \theta y_{l_{s_k}} \le P \theta y_{l_p} \quad \text{pour tout } p < s_k. $$

PREUVE. - Dans toute la démonstration, quand on comparera deux lettres de $\mathcal{X}$, il s'agira de l'ordre induit sur $\mathcal{X}$ par l'ordre choisi sur $\mathcal{X}^*$, donc de l'ordre initial de $\mathcal{X}$ si on a pris l'ordre lexicographique ordinaire sur $\mathcal{X}^*$ ou de l'ordre inverse de $\mathcal{X}$ si on a choisi sur $\mathcal{X}^*$ l'ordre lexicographique induit par l'ordre inverse de $\mathcal{X}$.

Nous allons montrer que toute classe $\rho^{-1}f (f \in \mathcal{X}^*)$ contient un élément de $\mathcal{K}_1$, en construisant explicitement un tel élément. Il en résultera qu'il est unique d'après la relation (6.2.10), la relation

$$ \mathrm{card} \, \mathcal{C} \cap G(h) = \mathrm{card} \, \alpha^{-1} h \quad (h \in \bar{\mathcal{X}}^*) $$

(qui exprime que toute classe $\rho^{-1}f (f \in \alpha^{-1}h)$ contient un et un seul élément canonique) et le fait que $\{ \rho^{-1}f : f \in \mathcal{X}^* \}$ est une partition de $\mathcal{Y}^*$.

Soit donc $g = y_{l_1} y_{l_2} \dots y_{l_s} \ (s > 0)$ un mot de $\mathcal{C}$ : posons $s_1 = 1$ et si $s > 1$, déterminons la suite de tous les indices $s_k > 1$ tels que

$$ P \theta y_{l_{s_k}} \le P \theta y_{l_p} \quad \text{pour tout } p < s_k. \quad (6.2.12) $$

Nous obtenons une suite $s_1 (= 1), s_2, \dots, s_t (\le s)$ d'entiers tels que

$$ P \theta y_{l_{s_1}} \ge P \theta y_{l_{s_2}} \ge \dots \ge P \theta y_{l_{s_t}}. \quad (6.2.13) $$

Par commodité, posons aussi $s_{t+1} = s+1$.

Si $s_{k+1} - s_k > 1$ pour $k \in [1, t]$, nous avons

$$ P \theta y_{l_{s_k}} < x \quad (6.2.14) $$

pour toute lettre $x$ du mot $\theta y_{l_p} (s_k < p < s_{k+1})$ et pour toute lettre $x$ du mot $\theta y_{l_{s_k}}$ à l'exclusion de la première. Cette relation est une conséquence immédiate de la définition des $s_k$ et du

ifiée

2.8)

2.9)

cor-

2.10)

mots

et un

que-

peut
fait que les mots $\theta y_{l_p}$ sont multilinéaires et minimum dans leurs classes de conjugués.

D'autre part, si $s_{k+1} - s_k > 1$, les mots

$$ \theta y_{l_{s_k}} y_{l_{s_k+1}} \dots y_{l_{p-1}} \text{ et } \theta y_{l_p} \quad (6.2.15) $$

$(s_k < p < s_{k+1})$ sont non disjoints.

En effet, s'ils étaient disjoints, les mots

$$ g_1 = y_{l_p} y_{l_{s_k}} y_{l_{s_k+1}} \dots y_{l_{p-1}} y_{l_{p+1}} \dots y_{l_s} $$

et

$$ g_2 = y_{l_{s_k}} y_{l_{s_k+1}} \dots y_{l_p} y_{l_{p+1}} \dots y_{l_s} $$

vérifieraient $eg_1 = eg_2$ d'après la proposition 4.1 et l'on n'aurait pas

$$ y_{l_{s_k}} = \max\{ \mathbf{P} g' : g' \in \rho^{-1} \rho y_{l_{s_k}} y_{l_{s_k+1}} \dots y_{l_s} \cap \mathcal{S}^* \} $$

puisque, d'après les formules (4.5.6) ou (6.1.3), la relation $\mathbf{P} \theta y_{l_{s_k}} < \mathbf{P} \theta y_{l_p}$ entraîne en particulier

$$ y_{l_{s_k}} < y_{l_p} \quad (\text{pour l'ordre dans } \mathcal{S}). $$

Toujours dans l'hypothèse $s_{k+1} - s_k > 1$, nous pouvons appliquer l'opérateur $\delta'$ au couple $(y_{l_{s_k}}, y_{l_{s_k+1}})$.

D'après (6.2.3), nous avons

$$ \mathbf{P} \theta \delta'(y_{l_{s_k}}, y_{l_{s_k+1}}) = \mathbf{P} \theta y_{l_{s_k}} \quad (6.2.16) $$

et il résulte alors de (6.2.14) que

$$ \delta'(y_{l_{s_k}}, y_{l_{s_k+1}}) \in \mathcal{K}. \quad (6.2.17) $$

De même, lorsque $s_{k+1} - s_k > 2$, nous pouvons appliquer, d'après (6.2.15), l'opérateur $\delta'$ successivement aux couples

$$ \begin{gathered} (y_{l_{s_k}}, y_{l_{s_k+1}}), (\delta'(y_{l_{s_k}}, y_{l_{s_k+1}}), y_{l_{s_k+2}}), \dots, \\ (\delta'(\dots \delta'(y_{l_{s_k}}, y_{l_{s_k+1}}), \dots, y_{l_{s_k+1-2}}), y_{l_{s_k+1-1}}). \end{gathered} $$

Nous obtenons, en posant $y_{m_k} = \delta'(\dots \delta'(y_{l_{s_k}}, y_{l_{s_k+1}}), \dots, y_{l_{s_k+1-1}})$,
$$ \mathbf{P} \theta y_{m_k} = \mathbf{P} \theta y_{l_{s_k}} \quad (6.2.18) $$
### 6.3. Un théorème combinatoire non commutatif.

La proposition 6.1 nous permet de donner une première démonstration du théorème combinatoire suivant.

**THEOREME 6.1.** - Soit $x = (x_{i_1}, x_{i_2}, \dots, x_{i_r})$ une suite de (r > 1) éléments d'un ensemble totalement ordonné $\mathcal{X}$, $(x_{j_1}, x_{j_2}, \dots, x_{j_r})$ la suite déduite de x en réarrangeant les $x_{i_k}$ en ordre non décroissant. Alors il est possible d'associer à x, de façon bijective, une troisième suite $(x_{v_1}, x_{v_2}, \dots, x_{v_r})$ d'éléments de $\mathcal{X}$ où

$$ (v_1, v_2, \dots, v_r) $$

est une permutation de $(i_1, i_2, \dots, i_r)$, telle qu'à tout $k \in [1, r]$ pour lequel $x_{i_k} < x_{j_k}$ correspond biunivoquement un $k'$ tel que $x_{v_k'} = x_{j_k}$ et $x_{v_{k'-1}} = x_{i_k}$. Il est aussi possible d'associer à x, toujours de façon bijective, une autre suite $(x_{w_1}, x_{w_2}, \dots, x_{w_r})$ d'éléments de $\mathcal{X}$ où encore $(w_1, w_2, \dots, w_r)$ est une permutation de $(i_1, i_2, \dots, i_r)$ telle qu'à tout $k \in [1, r]$ pour lequel $x_{i_k} > x_{j_k}$ correspond un indice $k''$ tel que $x_{w_k''} = x_{j_k}$ et $x_{w_{k'-1}} = x_{i_k}$.

Ce théorème se déduira immédiatement du théorème 6.1' que nous donnerons ci-après.

Rappelons tout de suite le résultat de Mac Mahon ([27] P.186) qui va apparaître comme une simple conséquence du théorème précédent. Mais introduisons d'abord quelques notations.

Soit $x = (x_{i_1}, x_{i_2}, \dots, x_{i_r})$ une suite de r éléments (r > 1) de $\mathcal{X}$ (totalement ordonné) et $(x_{j_1}, x_{j_2}, \dots, x_{j_r})$ la suite déduite de x en réarrangeant les $x_{i_k}$ en ordre non décroissant. Assemblons à x les nombres entiers $\mathcal{V}x$ et $\xi x$ définis par

$$ \mathcal{V}x = \text{nombre d'indices } k \text{ tels que } x_{i_k} > x_{j_k} \qquad (6.3.1) $$

$$ \xi x = \text{nombre d'indices } k \text{ tels que } x_{i_k} > x_{i_k+1} $$

(1 ≤ k ≤ r-1). Nous avons alors

**COROLLAIRE 6.1.** (Mac Mahon). - *Etant donné une suite croissante $(x_{u_1}, x_{u_2}, \dots, x_{u_d})$ (d > 0) d'éléments de $\mathcal{X}$ (totalement ordonné) et $n_1, n_2, \dots, n_d$ entiers positifs, nous désignons par h l'ensemble de toutes les suites ordonnées contenant exactement $n_1$ fois l'élément $x_{u_1}, \dots, n_d$ fois l'élément $x_{u_d}$ et par $(x_{j_1}, x_{j_2}, \dots, x_{j_r})$ la suite*
$$ \underbrace{(x_{u_1}, \dots, x_{u_l})}_{n_1 \text{ fois}} , \dots , \underbrace{(x_{u_d}, \dots, x_{u_d})}_{n_d \text{ fois}} $$

$$ \text{où } r = n_1 + n_2 + \dots + n_d . $$

Alors, pour tout entier $m \ge 0$, il y a dans h autant de suites x telles que $\xi x = m$ que de suites x telles que $\vee x = m$.

C'est une conséquence du théorème 6.1 puisque si

$$ x = (x_{i_1}, x_{i_2}, \dots, x_{i_r}) $$

est une suite de h, on peut trouver dans h de façon bijective une suite $\Phi'x = (x_{w_1}, x_{w_2}, \dots, x_{w_r})$ telle qu'à tout $k \in [1, r]$ pour lequel $x_{i_k} > x_{j_k}$, correspond biunivoquement un indice $k''$ tel que

$$ x_{w_k''} = x_{j_k} \quad \text{et} \quad w_{k''-1} = x_{i_k}, \quad \text{donc} \quad x_{w_k''-1} > x_{w_k''} $$

$$ \text{D'où } \vee x = \xi \Phi' x, \text{ par définition des fonctions } \vee \text{ et } \xi. $$

Mac Mahon obtenait ce résultat par des manipulations algé-briques sur les fonctions génératrices, d'où l'on ne peut déduire de procédé constructif permettant d'expliciter le résultat.

Nous donnons maintenant le résultat du théorème 6.1'. Dans le chapitre 8, nous construirons une autre permutation $\varphi$ de $X^*$ ayant les mêmes propriétés que $\Phi_1$ et $\Phi_2$ définis à la fin du paragraphe 6.2.

Nous définissons sur $X^*$ deux familles de fonctions à valeurs entières $(v_x, x')$ et $(\xi_x, x')_{(x', x') \in X^2}$, en posant pour $f = x_{i_1} x_{i_2} \dots x_{i_r}$ et $\beta f = x_{j_1} x_{j_2} \dots x_{j_r}$, $v_x, x', f$ = nombre d'indices k tels que $x_{i_k} = x$ et $x_{j_k} = x'$ ($1 \le k \le r$)

$$ \begin{align*} \xi_{x,x'} \quad f = 0 \quad \text{si} \quad \lambda f = 1 \\ = \text{nombre d'indices } k \text{ tels que } x_{i_k} = x \text{ et} \end{align*} $$

$$ x_{i_{k+1}} = x' \quad (1 \le k \le r-1) \quad \text{si} \quad \lambda f > 1. $$

On posera aussi $v_{x,x'}$, $f = \xi_{x,x'}$, $f = 0$ si $f = 1$ (mot unité).
THEOREME 6.1'. - Les permutations $\Phi_1$ et $\Phi_2$ de $X^*$ vérifient

$$ \alpha\Phi f = \alpha f \quad (f \in X^*; \Phi = \Phi_1 \text{ ou } \Phi_2); \quad (6.3.2) $$

et l'on a pour tout $f \in X^*$

$$ v_{x,x'} f = \xi_{x,x'} \Phi_1 f \quad (6.3.3) $$

pour tout couple $(x, x') \in X^2$ tel que $x < x'$,

et

$$ v_{x,x'} f = \xi_{x,x'} \Phi_2 f \quad (6.3.4) $$

pour tout couple $(x, x') \in X^2$ tel que $x > x'$.

PREUVE. - Prenons sur $X^*$ l'ordre lexicographique induit par l'ordre de $X$ ou l'ordre inverse de $X$.

Soit $f = x_{i_1} x_{i_2} \dots x_{i_r}$ un mot de $X^{*+}$.

La bijection $\chi C$ fait correspondre à $f$ un mot unique $\chi C f = y_{l_1} y_{l_2} \dots y_{l_s} \in \mathcal{K}_1$, d'après la proposition 6.1.

Posons

$$ \theta y_{l_p} = x_{v_{K_p-1}+1} x_{v_{K_p-1}+2} \dots x_{v_{K_p}} \quad (1 \le p \le s, K_o = 0). $$

De là, $\psi^{-1} \chi C f = \Phi f = x_{v_1} x_{v_2} \dots x_{v_r}$, par définition de $\psi$.

Puisque $\rho \chi C f = f$, il résulte de (6.1.1) qu'à tout $k \in [1, r]$ correspond biunivoquement un $k' \in [1, r]$ tel que

$$ (x_{j_k}, \gamma_k, \beta f) = (x_{v_k}, \gamma_k, \Phi f) $$

et

$$ x_{i_k} = x_{v_{k'-1}} \quad \text{si } k' \neq K_{p-1} + 1 $$

pour tout $p \in [1, s]$

$$ = x_{v_{K_p}} \quad \text{si } k' = K_{p-1} + 1. $$

Or, si $f'' \in \mathcal{K}_o$ et est de longueur $> 1$, sa dernière lettre est toujours plus grande que sa première (pour l'ordre choisi). Nous pouvons donc toujours écrire

$$ x_{v_{K_{p-1}}+1} \le x_{v_{K_p}} \quad (6.3.5) $$
De même, si $f''$ et $f'''$ sont deux mots de $\mathcal{K}$ tels que
$\mathbf{P}f'' \ge \mathbf{P}f'''$ on a, a fortiori

$$
\mathbf{L} f'' \geq \mathbf{P} f'' \geq \mathbf{P} f''' .
$$

D'où, dans le cas présent, si $s > 1$

$$
x_{v_{k'} + 1} \le x_{v_{k'}} \qquad (6.3.6)
$$

Si donc on ne s'intéresse qu'aux indices $k \in [1, r]$ pour les-  
quels $x_{j_k} > x_{i_k}$, alors l'indice $k'$ correspond à $k$ est différent  
de $K_{p-1} + 1$ pour tout $p \in [1, s]$.

Et ainsi, à tout $k \in [1, r]$ tel que $x_{j_k} > x_{i_k}$ correspond biunivoquement un indice $k'$ tel que

$$
x_{v_k} = x_{j_k} \quad \text{et} \quad x_{v_{k'} - 1} = x_{i_k}.
$$

Si on a pris l'ordre lexicographique ordinaire sur $\mathcal{X}^*$ alors
$\Phi = \Phi_1$ et si pour un couple $(x, x') \in \mathcal{X}^2$ tel que $x < x'$;

$(k_1, k_2, \dots, k_n)$

sont tous les indices k pour lesquels $x_{i_k} = x < x' = x_{j_k}$, alors
nous avons exactement n indices distincts $k'$ ($k'_1, k'_2, \dots, k'_n$)
pour lesquels $x_{v_{k'}-1} = x < x' = x_{v_k}$, parmi les lettres du mot
$\Phi_1 f = x_{v_1} x_{v_2} \dots x_{v_r}$.

D'où

$$
v_{x,x'}, f = \xi_{x,x'}, \Phi_1 f.
$$

Si on a pris l'ordre lexicographique induit par l'ordre inverse de $\mathcal{X}$, nous devons inverser les relations d'ordre (6.3.5) et (6.3.6) et à tout $k \in [1, r]$ pour lequel $x_{i_k} > x_{j_k}$ correspond biunivoquement un indice $k'$ tel que

$$
x_{v_{k'} - 1} = x_{i_k} > x_{j_k} = x_{v_{k'}}.
$$

D'où encore

$$
v_{x,x'}, f = \xi_{x,x'}, \Phi_2 f \quad \text{pour tout couple}
$$

$$
(x, x') \in \mathcal{X}^2 \text{ tel que } x > x'.
$$

Ce qui achève la démonstration du théorème 6.1'.
Le théorème 6.1 se déduit alors immédiatement si l'on associe à toute suite $(x_{i_1}, x_{i_2}, \dots, x_{i_r})$ d'éléments de $\mathcal{X}$ le mot $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{X}^*$.

Les suites $(x_{v_1}, x_{v_2}, \dots, x_{v_r})$ et $(x_{w_1}, x_{w_2}, \dots, x_{w_r})$ de l'énoncé sont les suites d'éléments de $\mathcal{X}$ telles que

$$ \Phi_1 f = x_{v_1} x_{v_2} \dots x_{v_r} \quad \text{et} \quad \Phi_2 f = x_{w_1} x_{w_2} \dots x_{w_r}. $$
# 7. Les factorisations spéciales

## 7.1. Introduction.

Une autre preuve du théorème combinatoire 6.1 sera donnée au chapitre 8 (théorème 8.1). A toute factorisation de Schützenberger nous associerons une certaine permutation $\varphi$ de $X^*$ (le monoïde libre engendré par $X$ totalement ordonné). Il sera alors démontré que cette permutation $\varphi$ a les mêmes propriétés que la permutation $\Phi_1$ du théorème 6.1', c'est-à-dire

$$ \alpha \varphi f = \alpha f \quad (f \in X^*) $$

et

$$ v_{x, x'} f = \xi_{x, x'} \varphi f \quad (f \in X^*) $$

pour tout $(x, x') \in X^2$ tel que $x < x'$ quand et seulement quand la factorisation (S) considérée appartient à une certaine classe de factorisation (Sp) dites spéciales. Donnons-en tout de suite la définition.

Etant donnée une factorisation (S) d'un monoïde $X^*$ (Cf. § 5.3) engendré par un ensemble totalement ordonné $X$, c'est-à-dire une famille $\{Y_j : j \in J\}$ de sous-ensembles de $X^+$ (J totalement ordonné) telle que chaque $f \in X^+$ a une et une seule factorisation $f = f_1 f_2 \dots f_s$ ($s > 0$) ayant les propriétés

$$ f_k \in Y_{j_k} \quad \text{et} \quad j_1 \ge j_2 \ge \dots \ge j_s, $$

nous dirons que *l'ordre de J* est spécial si les conditions

$$ f \in Y_j, f' \in Y_{j'} \quad \text{et} \quad j \ge j' \quad (7.1.1) $$

(pour l'ordre dans J) entraînent $Lf \ge Pf'$ (pour l'ordre dans $X$), et d'autre part que
La factorisation (S) est spéciale si l'ordre de J est spé-
cial et si elle est de type b. (7.1.2)

D'après § 5.3, cette dernière condition (7.1.2) est alors équivalente à la donnée d'un sous-ensemble $\mathcal{H}$ de mots de $\mathcal{X}^{*+}$ et d'un ordre total $\leq$ sur $\mathcal{H}$ tels que $f \in \mathcal{X}^{*+}$ a une et une seule factorisation $f = f_1 f_2 \dots f_s$ ($s > 0$) telle que

$f_1, f_2, \dots, f_s \in \mathcal{H}$

$f_1 \succeq f_2 > \dots > \succeq f_s$

et $f, f' \in \mathcal{H}, f \succeq f'$ entraînent $Lf \geq Pf'$.

Nous donnons, dans ce chapitre, la construction de toute une classe de factorisations (Sp) par la méthode des crochets, utilisée aussi dans l'étude des algèbres de Lie libres (Voir dans [10] une construction analogue en théorie des codes).

De façon précise, soit $D = D(\mathcal{X})$ le système algébrique libre à une seule opération binaire sur $\mathcal{X}$. (Cf. [22] et [35]). Nous posons $D = D^+ \cup \mathcal{X}$ où $D^+$ est construit par induction comme l'ensemble des symboles $d = [d', d'']$ avec $d', d'' \in D$. $D^*$ désigne en outre le monoïde libre engendré par $D$.

Si $g = d_1 d_2 \dots d_i \dots d_s \in D^*$ et $d_i = [d', d'']$, nous disons que le mot $g' = d_1 d_2 \dots d_{i-1} d'^{\prime} d''$ est une décomposition de $g$ et alors que toute décomposition de $g'$ est aussi une décomposition de $g$. Tout $g \in D^*$ a alors une décomposition unique $\delta^* g \in \mathcal{X}^*$.

Pour obtenir une base de l'algèbre de Lie libre engendrée par $\mathcal{X}$, une méthode consiste (Meier-Wunderli [28], Hall [19], Schützenberger [35]) à associer à une application $\sigma: D \to J$, où $J$ est un ensemble totalement ordonné, un sous-ensemble $H_0 \subset D^*$ et à déterminer des conditions suffisantes sur $\sigma$ pour que $\delta^*: H_0 \to \mathcal{X}^*$ soit bijectif. La condition de Meier-Wunderli est une condition suffisante pour qu'il en soit ainsi (nous le rappelons dans le théorème 7.1).

Dans le paragraphe 7.2, nous définissons pour tout $\sigma$ un tel sous-ensemble $H_0 \subset D^*$ et montrons d'abord que $\delta^*: H_0 \to \mathcal{X}^*$ est surjectif (proposition 7.1) ; ce qui entraîne l'existence d'une famille $\{Y_j : j \in J\}$ de sous-ensembles de $\mathcal{X}^{**}$ satisfaisant à la condition (I') de Schützenberger. Lorsqu'en plus $\delta^*: H_0 \to \mathcal{X}^*$ est bijectif, alors cette famille $\{Y_j : j \in J\}$ détermine une factorisation (S) (proposition 7.2).
Nous donnons ensuite une nouvelle condition suffisante sur $\sigma$, dite condition (B), pour que $\delta^* : H_0 \to \mathcal{X}^*$ soit bijectif (proposition 7.3).

Une condition plus stricte avait déjà été introduite par Brunk [7] pour les seuls mots $d \in D$ tels que $\delta^*d$ est multilinéaire.

Nous montrons ensuite que si $\mathcal{X}$ est totalement ordonné et si pour $x, x' \in \mathcal{X}$

$$ (\text{dans } \mathcal{X}) \qquad (\text{dans } \mathcal{J}) $$

alors la condition (B) entraîne que l'ordre de J est spécial et moyennant une autre condition sur $\sigma$ (proposition 7.4), l'existence d'une factorisation spéciale.

La factorisation en mots lexicographiques standards est de ce type, nous le montrons dans le paragraphe 7.4.

De même que la factorisation de Spitzer (Cf. § 7.5 Cependant, celle-ci n'est pas de type b bien que l'ordre sur l'ensemble J correspondant soit spécial. Nous montrons dans ce paragraphe comment on peut en déduire cependant une factorisation spéciale que nous utiliserons au chapitre 9 pour donner une démonstration complètement combinatoire de la formule de Spitzer.

Enfin, dans le paragraphe 7.6, nous indiquons lorsque $\mathcal{X} = \mathbf{R}$ comment on peut introduire d'autres factorisations spéciales associées à toute fonction continue strictement monotone.

## 7.2. Préliminaires algébriques.

Nous utiliserons la méthode des crochets déjà utilisée par Meyer-Wunderli [28] et Hall [19] pour la détermination de certaines bases dans les algèbres de Lie libres. Nous reprenons aussi, dans ce qui suit, les notations de Schützenberger [35].

Soit $D = D(\mathcal{X})$ le système algébrique libre à une seule opération (ne satisfaisant à aucune identité) sur $\mathcal{X}$. Par définition, $D = D' \cup \mathcal{X}$ où $D'$ est construit par induction comme l'ensemble des symboles $d = [d', d'']$ avec $d', d'' \in D$. Notons par $D^*$ le monoïde libre engendré par $D$.

Tout $g \in D^*$ possède une décomposition unique notée $\delta^*g$ qui est un élément de $\mathcal{X}^*$ (Cf. § 7.1).
Supposons-nous maintenant donnés un ensemble totalement or-
donné J et une application $\sigma : D \to J$. Nous définissons alors
par induction un sous-ensemble H de D par les règles suivantes :

$\mathcal{X} \subset H$ et si $d = [d', d''] \in D^+$, $d \in H$ si et si seulement si

$$
(H1) \quad d', d'' \in H
$$

$$
(H2) \quad \sigma d' < \sigma d''
$$

$$
(H3) \text{ ou bien } d'' \in \mathcal{X} \text{ ou bien si } d'' = [d''' , d'^{\nu}]
$$

alors \qquad $\sigma d' \geq \sigma d''' .$

Soit maintenant $H_0$ le sous-ensemble des éléments

$$
g = d_1 d_2 \dots d_s \quad \text{de} \quad D^*
$$

tels que

$$
(H_0 1) \quad d_1, d_2, \dots, d_s \in H,
$$

et si $s > 1$, tels que

$$
(H_0 2) \quad \sigma d_1 \ge \sigma d_2 \ge \dots \ge \sigma d_s .
$$

L'application $\delta^*$ envoie tous les éléments de $H_0$ sur $\mathcal{X}'$.
Nous nous proposons donc de voir dans quelles conditions la restriction de $\delta^*$ à $H_0$ est une bijection de $H_0$ sur $\mathcal{X}^*$. Nous montrerons plus loin que de telles conditions entraînent l'existence d'une factorisation (S). Montrons tout d'abord la

PROPOSITION 7.1. - *Pour tout couple $(\sigma, J)$, l'application* $\delta^* : H_0 \to \mathcal{X}^*$ *est une surjection.*

PREUVE. - Nous introduisons d'abord un sous-ensemble $H_1$ de $D^+$ contenant $H_0$ et les éléments $g = d_1 d_2 \dots d_s$ de $D^* (s > 1)$ tels que pour un entier $k$ ($1 \le k < s$), l'élément $d_1 d_2 \dots d_k$ appartient à $H_0$ et tels que

$$
(H_1 1) \quad d_{k+1}, d_{k+2}, \dots, d_s \in \mathcal{X}
$$

et

$$
(H_1 2) \quad \sigma d_k < \sigma d_{k+1} .
$$
Le sous-ensemble $H_1$ contient en particulier $\mathcal{X}^*$. Pour démontrer la proposition, il suffit donc de définir une application $\psi: H_1 \to H_1$ telle que si $g \in H_1 \setminus H_0$, alors

$$ \lambda\psi g < \lambda g \quad \text{et si} \quad g \in H_0, $$

alors

$$ \lambda\psi g = \lambda g. $$

En fait, la définition de l'application $\psi$ que nous donnons ci-après nous permet, pour tout $f \in \mathcal{X}^*$, de construire un élément $g \in H_0$ tel que $\delta^* g = f$.

Soit donc $g = d_1 d_2 \dots d_s$ un élément de $H_1$.

Nous envisageons plusieurs cas.

D'abord, on pose $\psi g = g$ si $k=s$ ou si $s=1$ (c'est-à-dire $g \in H_0$).

D'autre part, lorsque $1 \le k < s$ puisque $d_{k+1} \in \mathcal{X}$ les conditions (H1), (H2) et (H3) sont satisfaites pour le couple $(d_k, d_{k+1})$.

On a ainsi

$$ [d_k, d_{k+1}] \in H. \quad (7.2.1) $$

Lorsque $1 = k < s$, nous posons $\psi g = [d_1, d_2] d_3 \dots d_s$ et alors $\psi g \in H_1$ et pour $1 < k < s$ si

$$ \sigma d_{k-1} \ge \sigma [d_k, d_{k+1}], \quad (7.2.2) $$

nous posons

$$ \psi g = d_1 d_2 \dots d_{k-1} [d_k, d_{k+1}] d_{k+2} \dots d_s. $$

Dans ce cas, les relations $(H_0^2)$ et (7.2.2) entraînent alors que $\psi g \in H_1$.

Pour ces deux cas, nous posons aussi $l=k$.

Lorsque $1 < k < s$, si la relation (7.2.2) n'est pas satisfaite, soit $l$ le plus petit entier $(1 \le l < k)$ tel que l'on ait

$$ \sigma d_m < \sigma [d_{m+1}, \dots, [d_k, d_{k+1}] \dots] \quad (7.2.3) $$

pour $l \le m \le k-1$.
Si $l = 1$, on pose

$$ \psi g = [d_1, [d_2, \dots, [d_k, d_{k+1}] \dots]] d_{k+2} \dots d_s $$

et si $l > 1$

$$ g = d_1 d_2 \dots d_{l-1} [d_l, [d_{l+1}, \dots, [d_k, d_{k+1}] \dots]] d_{k+2} \dots d_s $$

Nous avons encore $\psi g \in H_1$.

En effet, d'abord si $l = k-1$, c'est vrai puisque les relations $(H_0)$, $(7.2.2)$ pour $m=k-1$ et $(7.2.1)$ entraînent que les relations $(H1)$, $(H2)$ et $(H3)$ sont vérifiées pour le couple $(d', d'')$ tel que

$$ d' = d_{k-1} \quad \text{et} \quad d'' = [d_k, d_{k+1}] $$

et ainsi

$$ [d_{k-1}, [d_k, d_{k+1}]] \in H. $$

D'où la propriété suit par définition de $l$ (égal, dans ce cas, à $k-1$).

Pour $1 \le l < k-1$, le résultat suit par récurrence sur $m$, puisque si l'on suppose

$$ [d_{m'}, \dots, [d_k, d_{k+1}] \dots] \in H \quad (7.2.4) $$

pour un certain $m'$ ($l < m' \le k-1$), alors les relations (7.2.4), $(H_0)$, $(7.2.3)$ pour $m=m'-1$ et $(H_0)$ entraînent que les relations $(H1)$, $(H2)$ et $(H3)$ sont vérifiées pour le couple $(d', d'')$ où

$$ d' = d_{m'-1} \quad \text{et} \quad d'' = [d_{m'}, \dots, [d_k, d_{k+1}] \dots]. $$

D'où

$$ [d_{m'-1}, [d_{m'}, \dots, [d_k, d_{k+1}] \dots]] \in H. $$

On a ainsi successivement

$$ [d_k, d_{k+1}] \in H $$

$$ [d_{k-1}, [d_k, d_{k+1}]] \in H $$

$$ [d_l, [d_{l+1}, \dots, [d_k, d_{k+1}] \dots]] \in H. $$
Si $l = 1$, la propriété est alors démontrée et si $l > 1$ la définition de $l$ entraîne

$$ \sigma d_{l-1} \ge \sigma[d_l, [d_{l+1}, \dots, [d_k, d_{k+1}] \dots]] $$

et encore $\psi g \in H_1$, puisque $g \in H_1$ et $l < k$.

Dans tous les cas où $1 \le k < s$, c'est-à-dire lorsque $g \in H_1 - H_o$, pour définir $\psi g$, on fait toujours l'opération $(d_k, d_{k+1}) \to [d_k, d_{k+1}]$ on a ainsi

$$ \lambda \psi g < \lambda g. $$

D'où la proposition 7.1 est démontrée.

Soit $\mathcal{H}$ le sous-ensemble de $\mathcal{X}^*$ défini par

$$ \mathcal{H} = \{ \delta^* d : d \in H \} $$

et pour tout $j \in J$ le sous-ensemble

$$ Y_j = \mathcal{H} \cap \delta^* \sigma^{-1} j. $$

Les sous-ensembles $\{Y_j : j \in J\}$ de $\mathcal{X}^*$ forment alors une famille totalement ordonnée par $J$.

La proposition précédente entraîne qu'à tout $f \in \mathcal{X}^{*+}$ on peut associer au moins une suite $(d_1, d_2, \dots, d_s)$ d'éléments de $D$ telle que les conditions $(H_01)$ et $(H_02)$ soient remplies ; d'où encore si l'on pose

$$ \sigma d_1 = j_1, \dots, \sigma d_s = j_s $$

et

$$ \delta^* d_1 = f_1, \dots, \delta^* d_s = f_s, $$

f admet au moins une factorisation de la forme $f = f_1 f_2 \dots f_s$ où $f_k \in Y_{j_k}$ et $j_1 \ge j_2 \ge \dots \ge j_s$.

Ainsi la famille $\{Y_j : j \in J\}$ satisfait à la condition (I'). Si, en plus, l'application $\delta^* : H_o \to \mathcal{X}^*$ est bijective, alors à tout $f$ correspond un et un seul mot $d_1 d_2 \dots d_s$ de $H_o$, d'où $f$ admet une et une seule factorisation $f_1 f_2 \dots f_s$ telle que $f_k \in Y_{j_k}$ et $j_1 \ge j_2 \ge \dots \ge j_s$.

D'où l'existence d'une factorisation (S). Résumons ces résultats dans une proposition.
**PROPOSITION 7.2.** - Pour tout couple $(\sigma, J)$, la famille $\{Y_j : j \in J\}$ où $Y_j = \{\delta^* d : d \in H \text{ et } \sigma d = j\}$ satisfait à la condition (1') et si $\delta^* : H_o \to \mathcal{X}^*$ est bijectif, alors les $\{Y_j : j \in J\}$ déter mines une factorisation (S).

### 7.3. Les factorisations spéciales.

Dans cette section, nous donnons une condition suffisante pour que $\delta^* : H_o \to \mathcal{X}^*$ soit bijectif.

D'après la proposition 7.2, nous pouvons donc en déduire une factorisation (S). En fait, cette condition nous permet directement de montrer l'existence d'une factorisation (S) (lemme 7.1) et nous en déduisons ensuite seulement que $\delta^* : H_o \to \mathcal{X}^*$ est bijectif (lemme 7.2).

Enfin, on montre comment cette condition entraîne l'existence de factorisations spéciales.

A titre d'exemple, nous rappelons d'abord le résultat de Meier-Wunderli qui donne une première condition suffisante pour que $\delta^* : H_o \to \mathcal{X}^*$ soit bijectif.

**THEOREME 7.1.** (Meier-Wunderli [28]). - Si $\sigma$ est une injection de D dans J tel que (HO) si $d = [d', d''] \in D$, on ait $\sigma d' < \sigma d$ et $\sigma d' < \sigma d$, alors $\delta^*$ établit une application bijective de $H_o$ sur $\mathcal{X}^*$.

Pour la démonstration, nous renvoyons à l'article de Schützenberger [35] où une preuve originale est donnée dans le cas plus général des partitions de Širšov. Nous obtenons ainsi un nouvel exemple de factorisation (S) déjà signalé dans [34]. Dans cet article, Schützenberger donne deux autres exemples introduits par Spitzer [38] d'une part et par Chen, Fox & Lyndon [8] et Širšov [37] d'autre part.

Nous montrerons que ces deux exemples sont deux cas particuliers de factorisations spéciales construites ci-après.

Nous donnons maintenant une autre condition sur $\sigma$ qui va entraîner d'abord que $\delta^* : H_o \to \mathcal{X}^*$ est bijectif et ensuite nous permettre de déterminer pour chaque couple $(\sigma, J)$ une factorisation spéciale.

Cette condition sur $\sigma$ généralise une condition introduite par Brunk [7] sur les mots multilinéaires.
Soit $\theta : \mathcal{X}^{*+} \to J$ une surjection satisfaisant la condition
(B) pour $f, f' \in \mathcal{X}^{*+}$, on a $\theta f > \theta f'f' > \theta f'$ ou

$$ \theta f = \theta f'f' = \theta f' \quad \text{ou} \quad \theta f < \theta f'f' < \theta f'f' $$

L'application $\sigma = \theta\delta^*$ est alors une surjection de $D$ sur $J$. Formons le sous-ensemble $H_0$ de $D^*$ (Cf. § 7.2). Nous avons alors

PROPOSITION 7.3. - $\delta^*$ établit une application bijective de $H_0$ sur $\mathcal{X}^*$.

Nous pouvons étendre $\sigma : D \to J$ à une surjection de $D^*$ sur $J$ en posant pour $g \in D^*$, $\sigma g = \theta \delta^* g$. D'après la condition (B), $\sigma$ satisfait aux conditions (i) et (ii) suivantes. Soit $g$ et $g' \in D^*$, on a les relations

$$ (i) \quad \sigma g = \sigma g' \quad \text{si} \quad \delta^* g = \delta^* g' \quad \text{et} $$

(ii) l'une des trois conditions suivantes satisfaite

$$ \sigma g > \sigma gg' > \sigma g' ; \sigma g = \sigma gg' = \sigma g' ; \sigma g < \sigma gg' < \sigma g' $$

Formons le sous-ensemble $\mathcal{B}$ de $\mathcal{X}^*$ défini par

$$ \mathcal{B} = \{ f \in \mathcal{X}^{*+} : \theta f' < \theta f \text{ pour toute factorisation } f = f'f'' (f' = 1, f) \} $$

et pour tout $j \in J$, le sous-ensemble $Y_j = \mathcal{B} \cap \theta^{-1}j$. Nous démontrons d'abord le lemme 7.1 déjà donné par Brunk [7] pour les mots multilinéaires.

LEMME 7.1. - La famille des sous-ensembles $\{Y_j : j \in J\}$ satisfait aux conditions (I) et (I') (ou encore détermine une factorisation (S)).

PREUVE. - Soit $f = x_{i_1} x_{i_2} \dots x_{i_r}$ un mot de $\mathcal{X}^{*+}$. Nous pouvons définir l'entier $t_1$ comme le plus petit entier tel que

$$ \theta x_{i_1} x_{i_2} \dots x_{i_k} \le \theta x_{i_1} x_{i_2} \dots x_{i_{t_1}} $$
pour tout $k$ ($1 \le k \le r$). Si $t_1 < r$, nous définissons $t_2$ comme le plus petit entier tel que

$$ \theta x_{i_{t_1+1}} x_{i_{t_1+2}} \dots x_{i_k} \stackrel{<}{=} \theta x_{i_{t_1+1}} x_{i_{t_1+2}} \dots x_{i_{t_2}} $$

pour tout $k$ ($t_1 + 1 \le k \le r$) et ainsi de suite...

Nous obtenons ainsi une suite d'entiers

$$ O = t_0 < t_1 < t_2 < \dots < t_s = r. $$

Posons

$$ f_p = x_{i_{t_{p-1}+1}} x_{i_{t_{p-1}+2}} \dots x_{i_{t_p}} \quad (p = 1, 2, \dots, s) $$

Nous avons alors

$$ f = f_1 f_2 \dots f_s; $$

ensuite

$$ \theta f_1 \ge \theta f_2 \ge \dots \ge \theta f_s \quad \text{car} \quad \theta f_1 \ge \theta f_1 f_2 $$

par définition de $t_1$, d'où

$$ \theta f_1 \ge \theta f_1 f_2 \ge \theta f_2 $$

en vertu de la condition (B).

De même, la définition de $t_2$ donne $\theta f_2 \ge \theta f_2 f_3$ ; d'où en-core $\theta f_2 \ge \theta f_2 f_3 \ge \theta f_3$ et ainsi de suite...

Enfin, par définition des $t_p$ ($1 \le p \le s$), nous avons encore $f_p \in Y_{j_p}$ si $\theta f_p = j_p$.

La condition (I') est donc satisfaite.

Il nous reste à voir que la condition (I) est aussi satisfaite ou encore que la factorisation est unique. En effet, soit $f = f_1 f_2 \dots f_p$ une factorisation de $f$ telle que $\theta f_1 \ge \theta f_2 \ge \dots \ge \theta f_s$ et $f_1, f_2, \dots, f_s \in \mathbb{R}$.

Posons

$$ t_p = \lambda f_1 + \dots + \lambda f_p \quad (1 \le p \le s) $$
et soit $k$ un entier $\in [t_{p-1} + 1, r]$. Il existe alors un et un seul indice $p'$ ($p \le p' \le s$) tel que $t_{p'-1} < k \le t_p$. Comme $f_p \in \mathcal{B}$, on a

$$ \theta f_p \ge \theta x_{i_{t_p'-1}+1} x_{i_{t_p'-1}+2} \dots x_{i_k} $$

(on a l'égalité si et seulement si $k = t_p$).

Comme d'autre part $\theta f_p \ge \dots \ge \theta f_p$, il résulte de la condition (B) que $t_p$ est bien le plus petit entier tel que

$$ \theta x_{i_{t_p-1}+1} x_{i_{t_p-1}+2} \dots x_{i_k} \le \theta x_{i_{t_p-1}+1} x_{i_{t_p-1}+2} \dots x_{i_{t_p}} = \theta f_p \\ (t_{p-1} + 1 \le k \le r) $$

Ce qui achève la démonstration du lemme 7.1.

Ainsi la donnée d'une surjection $\theta: \mathcal{X}^* \to J$ où $J$ est totalement ordonné entraîne l'existence d'une factorisation (S) donnée par la famille $Y_j = \mathcal{R} \cap \theta^{-1} j$ ($j \in J$).

Nous dirons que la factorisation (S) obtenue est induite par le couple $(\theta, J)$.

Formons le système algébrique libre $D$ associé à $(\sigma, J)$ (Cf. la section 7.2), puis le sous-ensemble $H$ de $D^*$. Alors

LEMME 7.2. - $\delta^*$ établit une bijection de $H$ sur $\mathcal{B}$.

PREUVE. - Nous montrons d'abord la propriété suivante.

Si $d \in H$, on a alors $\delta^*d \in \mathcal{B}$ et en posant $\delta^*d = x_{i_1} x_{i_2} \dots x_{i_r}$, on a de plus

$$ \text{ou } r = 1 $$

$$ \text{ou } d = [d_1, d_1'] \in D^+ \text{ et } t = \lambda \delta^* d_1 \text{ est le plus petit entier } (1 \le t < r) \text{ tel que} \quad (7.3.1) $$

$$ \theta x_{i_1} x_{i_2} \dots x_{i_k} \le \theta x_{i_1} x_{i_2} \dots x_{i_r} $$

pour tout $k$ ($1 \le k < r$).

Tout d'abord, la propriété est trivialment vraie pour les $d \in H$ tels que $\lambda \delta^* d = 1$, puisqu'alors $\delta^*d = d \in \mathcal{X})$. Supposons
donc la propriété vraie pour les d tels que $\lambda \delta^* d < r$ et procédons par induction sur $r$. Si $d \in H$ et $\lambda \delta^* d > 1$, posons $\delta^* d = f = x_{i_1} x_{i_2} \dots x_{i_r} \quad (r > 1)$. Alors par définition de l'ensemble H et en vertu de la condition (ii) sur $\sigma$, il existe un entier $p \ge 1$ et une suite $d_1, d_2, \dots, d_p, d'_p$ d'éléments de H tels que

$$d = [d_1, [d_2, [\dots [d_p, d'_p] \dots ]]] \\ d'_p \in \mathcal{X} \quad \text{et} \\ \sigma d > \sigma d_1 \ge \sigma d_2 \ge \dots \ge \sigma d_p < \sigma d'_p. \tag{7.3.2}$$

Posons

$$\lambda_o = \Lambda_c = 0, \quad \lambda_q = \lambda \delta^* d_q \quad (1 \le q \le p)$$

et

$$\Lambda_q = \lambda_1 + \dots + \lambda_q \quad (1 \le q \le p).$$

Ainsi

$$r = \lambda_1 + \dots + \lambda_p + 1 = \Lambda_p + 1.$$

Soit $k \in [1, r-1]$ ; il existe alors un entier $q$ ($1 \le q \le p$) tel que l'on ait

$$\Lambda_{q-1} < k \le \Lambda_q.$$

Puisque $\lambda_q < r$ et que $d_q \in H$, on a alors par récurrence $\delta^* d_q \in \mathcal{R}$ ; donc en particulier

$$\theta x_{i_{\Lambda_{q-1}+1}} \dots x_{i_k} \le \theta x_{i_{\Lambda_{q-1}+1}} \dots x_{i_{\Lambda_q}} \tag{7.3.3}$$

(l'égalité étant satisfaite dans le seul cas où $k = \Lambda_q$). Si $q = 1$, les relations (7.3.2) donnent

$$\sigma d > \sigma d_1$$

et nous avons

$$\theta f = \sigma d > \sigma d_1 = \theta x_{i_1} \dots x_{i_{\Lambda_1}} \ge \theta x_{i_1} \dots x_{i_k} \tag{7.3.3'}$$

en vertu de la relation (7.3.3) pour $q = 1$, l'égalité étant satisfaite dans le seul cas où $k = \Lambda_1$. On a donc en particulier si $t = \lambda_1 = \lambda \delta^* d_1 > 1$,
$$ \theta x_{i_1} x_{i_2} \dots x_{i_k} < \theta x_{i_1} x_{i_2} \dots x_{i_t}. \quad (7.3.3'') $$

Si $q > 1$, il résulte alors de la condition (ii) sur $\sigma$, des relations (7.3.2) et (7.3.3) que

$$ \sigma d > \sigma d_1 \ge \sigma d_1 d_2 \dots d_{q-1} = \theta x_{i_1} x_{i_2} \dots x_{i_{\Lambda_{q-1}}} \ge \sigma d_{q-1} \ge \sigma d_q \ge \theta x_{i_{\Lambda_{q-1}+1}} \dots x_{i_k}; $$

d'où l'on tire, à cause de la propriété (B) (ou des conditions (i) et (ii) sur $\sigma$)

$$ \begin{aligned} \sigma d = \theta f > \sigma d_1 = \theta x_{i_1} x_{i_2} \dots x_{i_t} &\ge \theta x_{i_1} \dots x_{i_{\Lambda_{q-1}+1}} \ge \theta x_{i_1} x_{i_2} \dots x_{i_k} \\ &\ge \theta x_{i_{\Lambda_{q-1}+1}} \dots x_k. \end{aligned} $$

Soit

$$ \theta f > \theta x_{i_1} \dots x_{i_k} \quad \text{et} \quad (7.3.4) $$

$$ \theta x_{i_1} x_{i_2} \dots x_{i_t} \ge \theta x_{i_1} x_{i_2} \dots x_{i_k}. \quad (7.3.4') $$

Il résulte donc de (7.3.3') et (7.3.4) que

$$ \delta^* d = f \in \mathcal{B}, $$

et de (7.3.3'') et (7.3.4') que la condition sur $t$ de la propriété (7.3.1) est bien satisfaite. Ceci achève la démonstration de la propriété (7.3.1).

Réciproquement, nous montrons maintenant que pour tout $f \in \mathcal{B}$, il existe un et un seul $d \in H$ tel que $\delta^* d = f$. C'est triviallement vrai pour les mots $f$ de longueur 1, puisqu'on a alors $d = f(\in X)$. Supposons le résultat établi pour tous les mots $f \in \mathcal{B}$ de longueur $< r$ et procédons par récurrence sur $r$. Soit $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{B}$ ($r > 1$). D'après la propriété (7.3.1), s'il existe $d = [d_1, d_1']$ appartenant à $H$ tel que $\delta^* d = f$, alors $t = \lambda \delta^* d_1$ est le plus petit entier tel que

$$ \theta x_{i_1} \dots x_{i_k} \le \theta x_{i_1} \dots x_{i_t} \quad \text{pour tout } k \in [1, r-1]. \quad (7.3.5) $$

Pour démontrer la propriété, il nous suffit alors de montrer qu'il existe un et un seul couple $(d_1, d_1')$ d'éléments de $H$ tels que

$$ \delta^* d_1 = x_{i_1} \dots x_{i_t} $$

et

$$ \delta^* d_1' = x_{i_{t+1}} \dots x_{i_r} $$
et que $[d_1, d_1'] \in \mathbb{H}$. Soit donc $t$ le plus petit entier véri-
fiant (7.3.5). Si $t > 1$, nous avons ainsi

$$
\theta x_{i_1} x_{i_2} \dots x_{i_k} < \theta x_{i_1} x_{i_2} \dots x_{i_t}
$$

pour tout $k$ ($1 \le k \le t-1$), c'est-à-dire $x_{i_1} x_{i_2} \dots x_{i_t} \in \mathfrak{B}$ et la même conclusion si $t=1$. Puisque $t<r$, par récurrence il existe donc un élément $d_1 \in \mathbb{H}$ et un seul tel que

$$
\delta^* d_1 = x_{i_1} x_{i_2} \dots x_{i_t}.
$$

De même, si $t=r-1$, il existe bien $d_1' \in \mathbb{H}$ tel que $\delta^* d_1' = x_{i_{t+1}} = x_{i_r}$.
Enfin, si $t<r-1$, nous avons $x_{i_{t+1}} \dots x_{i_r} \in \mathfrak{B}$; car si on avait

$$
\theta x_{i_1} \dots x_{i_t} \ge \theta x_{i_{t+1}} \dots x_{i_r}
$$

pour un certain $t'$ ($t+1 \le t' \le r$), les relations (B) entraîneraient

$$
\theta x_{i_1} \dots x_{i_t} < \theta x_{i_1} \dots x_{i_r} < \theta x_{i_{t+1}} \dots x_{i_r} \le \theta x_{i_{t+1}} \dots x_{i_r}, \quad (7.3.6)
$$

soit

$$
\theta x_{i_1} \dots x_{i_t} < \theta x_{i_1} \dots x_{i_{t'}} < \theta x_{i_{t+1}} \dots x_{i_t},
$$

ce qui contredirait la définition de $t$. Puisque $r-t<r$, par récurrence il existe encore un et un seul élément $d_1' \in \mathbb{H}$ tel que $\delta^* d_1' = x_{i_{t+1}} \dots x_{i_t}$. D'où la condition (H1) est satisfaite pour la paire $(d_1, d_1')$. Ensuite, la relation (7.3.6) entraîne que l'on a $\sigma d_1 < \sigma d_1'$ d'où la condition (H2) est satisfaite. Enfin, si $r-t>1$, on a alors $d_1' = [d_1^{11}, d_1^{12}] \in D^+$. D'où il existe un entier $t''$ ($t+1 \le t'' < r$) tel que $\delta^* d_1' = x_{i_{t+1}} \dots x_{i_t''}$. Mais la relation (7.3.5) entraîne pour $k=t''$

$$
\theta x_{i_1} \dots x_{i_t} \ge \theta x_{i_1} \dots x_{i_{t''}} \ge \theta x_{i_{t+1}} \dots x_{i_{t''}}
$$

soit $\sigma d_1 \ge \sigma d_1'$. D'où la propriété (H3) satisfaite. Ainsi $[d_1, d_1'] \in \mathbb{H}$ et $\delta^*[d_1, d_1'] = f$. Ce qui achève la démonstration du lemme 7.2.

A tout mot $g = d_1 d_2 \dots d_s$ de $H_o$, on peut donc faire correspondre de façon bijective une suite $f_1, f_2, \dots, f_s$ de mots de $\mathfrak{B}$ tels que $\theta f_1 \ge \theta f_2 \ge \dots \ge \theta f_s$. Il suffit de prendre $f_1 = \delta^* d_1, \dots, f_s = \delta^* d_s$ d'après le lemme 7.2. Ensuite, par le lemme 7.1, il correspond à cette suite un et un seul mot $f$ de $\mathcal{X}^*$ ($f = f_1 f_2 \dots f_s$).

La proposition 7.3 est ainsi démontrée.
Une conséquence de la proposition 7.3 est que tout mot $f \in \mathfrak{B} (\equiv \mathfrak{R})$, de longueur $\lambda f \ge 2$, admet toujours une factorisation $f_1 f_2$ où $f_1$ et $f_2 \in \mathfrak{B}$ et $\theta f_1 < \theta f_2$.

D'autre part, pour obtenir la factorisation unique d'un mot quelconque de $f$ en mots de $\mathfrak{B}$ soit $f_1 f_2 \dots f_s$ où

$$ \theta f_1 \ge \theta f_2 \ge \dots \ge \theta f_s, $$

on peut déterminer par la méthode de la proposition 7.1 l'élément unique $g$ de $H_0$ tel que $\delta^* g = f$.

Cette méthode sera illustrée dans les exemples que nous donnerons au paragraphe suivant.

Donnons enfin une condition suffisante pour qu'un couple $(\theta, J)$ satisfaisant (B) induise une factorisation spéciale.

**PROPOSITION 7.4.** - Si $\mathcal{X}$ est totalement ordonné, si l'application $\theta: \mathcal{X}^* \to J$ satisfait la condition (B) et que l'on a pour $x, x' \in \mathcal{X}$

$$ x < x' \iff \begin{array}{l} \theta x < \theta x' \\ \text{(dans } \mathcal{X}) \quad \text{(dans } J \end{array} \qquad (7.3.7) $$

alors l'ordre induit par $\theta^{-1}$ sur les éléments de $\mathfrak{B}$ est spécial. Si, de plus, la restriction de $\theta$ à l'ensemble $\mathcal{R}$ des mots primitifs est injective et que l'on a

$$ \theta f = \theta f^p \qquad (7.3.8) $$

pour tout $f \in \mathcal{R}$ et tout entier $p > 0$, alors la factorisation (S) induite par $(\theta, J)$ est spéciale.

**PREUVE.** - Il nous faut vérifier d'abord

$$ f, f' \in \mathfrak{B}, \theta f \ge \theta f' \implies \mathbf{L}f \ge \mathbf{P}f \quad \text{(dans } \mathcal{X}) $$

En effet, soit

$$ f = x_{i_1} x_{i_2} \dots x_{i_r} \quad \text{et} \quad f' = x_{i'_1} x_{i'_2} \dots x_{i'_r}, $$

En vertu des conditions (B), on a

$$ \theta f \ge \theta x_{i_r} \quad \text{et} \quad \theta x_{i_1} \le \theta f' $$
dans les deux cas, l'égalité n'étant satisfaite que si

$$ \lambda f \text{ ou } \lambda f' = 1, $$

d'où

$$ \mathbf{L} f = x_i \geq x_i' = \mathbf{P} f'. $$

Pour la seconde propriété, notons que si l'on avait $f = f^*$ et $f' \in \mathcal{R}$ et $p$ entier $> 1$, alors on aurait $\theta f = \theta f'$ d'après (7.3.8) et $f$ ne pourrait appartenir à $\mathcal{B}$.

Donc $\mathcal{B}$ ne contient que des éléments primitifs et puisque $Y_j = \mathcal{B} \cap \theta^{-1} j$ et que la restriction de $\theta$ à $\mathcal{R}$ est injective, tout $Y_j$ ne contient qu'un seul élément. La factorisation induite est donc de type $b$, donc spéciale d'après la première partie.

Dans les prochains paragraphes, nous allons montrer comment certaines factorisations déjà connues peuvent être induites par des couples $(\theta, J)$ ayant les propriétés ci-dessus.

### 7.4. Factorisation en mots lexicographiques standards.

Nous avons déjà rappelé au paragraphe 5.3 la factorisation en mots lexicographiques standards.

Nous voulons maintenant démontrer qu'en prenant de façon appropriée un ensemble totalement ordonné $J$ et une application $\theta: \mathcal{X}^* \to J$ satisfaisant la condition (B), la factorisation $(\theta, J)$ est justement la factorisation en mots lexicographiques standards.

Soit donc $\mathcal{X}$ un ensemble totalement ordonné. Prenons pour ensemble $J$, l'ensemble $\mathcal{R}$ des mots primitifs de $\mathcal{X}^*$, que nous munissons de l'ordre total suivant (que nous appellerons *ordre lexicographique circulaire et que nous noterons par $\leq$) :

$$ \text{si } j, j' \in J, \text{ alors } j \leq j' \iff j^{\lambda j'} \leq j^{\lambda j} \quad (7.4.1) $$

(pour l'ordre lexicographique noté $\leq$).

Nous avons bien défini là un ordre. En effet,

$$ j \leq j' \text{ et } j' \leq j $$

entraînent

$$ j^{\lambda j'} = j'^{\lambda j}, $$
d'où $j = j'$ puisque $j$ et $j'$ sont primitifs.

Ensuite, si $j \leq j'$ et $j' \leq j''$, nous avons

$$j^{\lambda j'} \cdot \lambda j'' \leq j'^{\lambda j} \cdot \lambda j'' \leq j''^{\lambda j} \cdot \lambda j'$$

soit

$$j^{\lambda j''} \leq j''^{\lambda j} \quad j \leq j''$$

Tout mot $f \in \mathcal{X}^{**}$ peut s'écrire univoquement $f = (j)^q$ où $j \in J$ et où $q$ est un entier positif. Nous posons alors $\theta f = j$.

**PROPOSITION 7.5.** - Si $j$ et $j'$ sont deux éléments distincts de $J$, alors

$$m < \theta(mM) < \theta(Mm) < M \quad (7.4.2)$$

où $m = \min(j, j')$ et $M = \max(j, j')$ et si de plus, $j$ et $j'$ sont standards pour l'ordre lexicographique ordinaire et tels que $j$ est un facteur initial de $j'$, alors $j < j'$.

**PREUVE.** - En vertu des propriétés de l'ordre lexicographique, les relations (7.4.2) sont évidentes pour un couple $(j, j')$ tel que $\lambda j = \lambda j'$.

Supposons donc

$$\lambda j < \lambda j'$$

Si $j$ est un facteur initial de $j'$, nous posons

$$j' = j^q j'' \text{ avec } q \text{ maximal } (q > 0) \text{ et } j'' \in \mathcal{X}^{**}$$

et si $j$ n'est pas un facteur initial de $j'$, nous posons encore

$$j' = j^q j'' \text{ avec } q = 0 \text{ et } j'' = j'$$

Ecrivons

$$j = x_1 x_2 \dots x_r \quad j' = x'_1 x'_2 \dots x'_r \quad \text{et} \quad j'' = x''_1 x''_2 \dots x''_r$$

Deux cas sont alors à considérer :
(i) ou il existe un entier k ($1 \le k \le \min(r, r'')$) tel que

$$x_k \neq x'_k, = x''_k \quad \text{où} \quad k' = qr + k$$

(ce qui est toujours le cas si $r'' \ge r$ car $q$ est maximal)

(ii) où alors $r'' < r, q > 0$ et $j''$ est un facteur initial de $j$ et nous pouvons poser

$$j = j'' j''' (j''' \in \mathcal{X}^{**}).$$

Dans le cas (i), en prenant pour $k$ le plus petit entier ($1 \le k \le \min(r, r'')$) tel que $x_k \neq x_k'$, nous pouvons écrire

$$j^{q+2} = j^q x_1 x_2 \dots x_k \dots x_r x_1 x_2 \dots x_k \dots x_r$$

$$j j' = j^{q+1} j'' = j^q x_1 x_2 \dots x_k \dots x_r x_1'' x_2'' \dots x_k'' \dots x_r''$$

$$(j'j)^2 = j^q j'' j^q j'' j' = j^q x_1'' x_2'' \dots x_k'' \dots x_r'' j^q x_1 x_2 \dots x_k \dots x_r j'' j'$$

$$j'^2 = j^q j'' j^q j'' = j^q x_1'' x_2'' \dots x_k'' \dots x_r'' j^q x_1'' x_2'' \dots x_k'' \dots x_r''$$

D'où, en comparant ces mots par rapport à l'ordre lexicographique

$$j < j j' < j' j < j' \quad \text{si} \quad x_k < x_k'' \quad (\text{dans } \mathcal{X})$$

et

$$j > j j' > j' j > j' \quad \text{si} \quad x_k > x_k'' \quad (\text{dans } \mathcal{X}).$$

Dans le cas (ii), on a posé $j = j'' j'''$ et $q$ étant positif, nous pouvons écrire

$$j^{q+3} = j^q j'' j''' j'' (j''' j'') j'''$$

$$(jj')^2 = j^q j''(j''' j'') (j'' j''') j'$$

$$(j'j)^2 = j^q j''(j'' j''') j^{q-1} j''(j''' j'') j$$

$$(j')^3 = j^q j'' j'' j''' j^{q-1} j''(j'' j''') j^{q-1} j''$$

Puisque $j$ est primitif et que $j''' \in \mathcal{X}^{**}$ on ne peut avoir

$$j = j'' j''' = j''' j''.$$

(Cf. Lemmes 3 et 4 de [26]). D'où, en comparant les mots
$j^{q+3}, (j j')^2, (j' j)^2 \text{ et } (j')^3,$

nous avons

$j < j \ j' < j' \ j < j'$ si $j''' \prec j'' \ j'''$

et

$j > j \ j' > j' \ j > j'$ si $j''' \succ j'' \ j'''$.

Maintenant, si $j$ et $j'$ sont des mots standards tels que $j$ est un facteur initial de $j'$, alors $j' = j^q j''$ avec $q$ entier positif maximal et $j'' \in \mathcal{X}^{*+}$.

Si l'on avait $j > j^q j''$, dans le cas (i) on aurait alors

$x_k > x_k'' \implies j > j'' \implies j^q j'' > j''$

et par suite $j' = j^q j''$ ne serait pas standard ; dans le cas (ii), on aurait

$j''' \succ j'' \ j''' = j$

et là enCORE j ne serait pas standard.

Ce qui achève la démonstration de la proposition.

$\theta : \mathcal{X}^* \to J$ est une surjection satisfaisant, d'après la proposition précédente, la condition (B) et trivialement sa restriction à $\mathcal{R}$ est bijective et les conditions (7.3.7) et (7.3.8) sont remplies.

Il résulte alors de la proposition 7.4 que la factorisation indirecte par $(\theta, J)$ est une factorisation spéciale. Elle est, de plus, identique à la factorisation de Širšov en mots lexicographiques standards. En effet, si $f$ est standard, alors $f \prec f''$ pour toute factorisation $f = f' f''$ $(f', f'' \in \mathcal{X}^{*+})$.

D'autre part, puisque $\lambda f > \lambda f''$, on a $f \prec f''$ si et si seulement $\theta f < \theta f''$ ou encore d'après la condition (B) si et seulement si $\theta f' < \theta f$, c'est-à-dire

$f \in \mathcal{B} = \{f \in \mathcal{X}^{*+} : \theta f' < \theta f \text{ pour } f = f' f'' (f' \neq 1, f)\}$.

Ensuite, si $f$ et $f' \in \mathcal{B}$, alors $f \prec f'$ si et seulement si $\theta f = f < f' = \theta f'$.
C'est évidemment vrai si $\lambda f \ge \lambda f'$ et dans le cas $\lambda f < \lambda f'$ lorsque $f$ n'est pas un facteur initial de $f'$.

Enfin, lorsque $f$ est un facteur initial de $f'$, soit $f' = f^q f'$ avec $q > 0$ et $f'' \in \mathcal{X}^{*+}$, on a toujours $f < f'$ d'après la seconde partie de la proposition 7.5 ; donc encore dans ce cas,

$$f < f^q f'' \iff f < f^q f'' .$$

### 7.5. La factorisation de Spitzer.

Spitzer [38] a introduit une factorisation d'un sous-ensemble du monoïde libre $\mathcal{X}^*$ engendré par $\mathcal{X} = \mathbf{R}$ (la droite réelle). Schützenberger [34] a montré, en l'étendant à tous les mots de $\mathcal{X}^*$, que cette factorisation était un exemple de factorisation (S).

Dans ce paragraphe, nous démontrons comment cette factorisation peut être induite par un couple $(\theta, J)$ et comment on peut en déduire une factorisation spéciale.

Cette factorisation spéciale nous permettra, au chapitre 9, de donner une démonstration complètement combinatoire de l'identité de Spitzer.

Prenons $\mathcal{X} = \mathbf{R}$ (la droite réelle) et munissons le sous-ensemble $\mathcal{R}$ des mots primitifs du monoïde libre $\mathcal{X}^*$ de l'ordre lexicographique circulaire induit par l'ordre total de $\mathbf{R}$. Dénotons par $J$ le produit cartésien $J = \mathbf{R} \times \mathcal{R}$. $J$ est alors muni d'un ordre total si l'on pose pour

$$(r, f) \quad \text{et} \quad (r', f') \in \mathbf{R} \times \mathcal{R}, \\ (r, f) < (r', f') \iff r < r' \quad (\text{dans } \mathbf{R}) \qquad (7.5.1)$$

ou si $r = r'$ et $f < f'$ pour l'ordre lexicographique circulaire de $\mathcal{R}$.

Nous désignons maintenant par $\tau$ l'application $\tau: \mathcal{X}^* \to \mathbf{R}$ qui fait correspondre au mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ de $\mathcal{X}^*$ le nombre réel

$$\tau f = \sum_{k=1}^{r} x_{i_k} / \lambda f.$$

Il est immédiat que
$$ \tau f < \tau f' \implies \tau f < \tau f' f' = \tau f' f < \tau f' \quad (7.5.2) $$

et

$$ \tau f = \tau f' \implies \tau f = \tau f' f' = \tau f' f = \tau f' . $$

En effet, il suffit de remarquer que si $a, a', b$ et $b'$ sont quatre nombres réels tels que $b$ et $b' \neq 0$, alors l'inégalité

$$ \frac{a}{a'} < \frac{b}{b'} \implies \frac{a}{b} < \frac{a+a'}{b+b'} < \frac{a'}{b'} $$

et évidemment

$$ \frac{a}{a'} = \frac{b}{b'} \implies \frac{a}{b} = \frac{a+a'}{b+b'} = \frac{a'}{b'} $$

Tout $f \in \mathcal{X}^*$ peut s'écrire univoquement $f = f'^q$ où $f' \in \mathcal{R}$ et $q$ est un entier positif. Nous posons $\pi f = f'$. ($\pi$ est la fonction $\theta$ du paragraphe précédent).

Alors l'application $\theta: \mathcal{X}^* \to J$ qui au mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ associe le couple $(\tau f, \pi f)$ de $J$ satisfait la condition (B). En effet, si $\theta f < \theta f'$ (dans $J$) alors

$$ \begin{gather*} \text{- ou } \tau f < \tau f' \text{ (dans } \mathbb{R} \text{) et l'on a } \tau f < \tau f' f' = \tau f' f < \tau f' \\ \theta f < \theta f f' < \theta f' \text{ et } \theta f < \theta f' f < \theta f' \end{gather*} $$

- ou $\tau f = \tau f'$ mais alors $\pi f < \pi f'$ (dans $\mathcal{R}$) et d'après la proposition 7.5, nous avons

$$ \pi f < \pi f' f' < \pi f' \quad \text{et} \quad \pi f < \pi f' f' < \pi f' $$

et

$$ \tau f = \tau f' f' = \tau f' f = \tau f' . $$

D'où

$$ \theta f < \theta f f' < \theta f' \quad \text{et} \quad \theta f < \theta f' f' < \theta f' \quad \text{(dans } J \text{)} $$

D'autre part, la condition (7.3.7) est triviallement satisfaite.

Ensuite, la restriction de $\theta$ à $\mathcal{R}$ est une injection car si $f$ et $f'$ sont deux mots distincts $\in \mathcal{R}$ et $\tau f = \tau f'$ alors
$\pi f \neq \pi f'$ d'où $\theta f \neq \theta f'$.

Enfin, si $f = f'^q$ avec $f' \in \mathcal{R}$ et $q > 1$, on a évidemment
$\tau f = \tau f'$ et $\pi f = \pi f'$ d'après les résultats du paragraphe précédent.

D'où $\theta f = \theta f'$ et la condition (7.3.8) est ainsi satisfaite.

Il résulte alors de la proposition (7.4) que la factorisation
induite par $(\theta, J)$ est une factorisation spéciale, que nous dési-
gnerons par factorisation spéciale de Spitzer.

Chaque $Y_j = \mathfrak{R} \cap \theta^{-1} j$ est réduit à un seul élément, et si

$$
f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathfrak{R},
$$

alors la ligne polygonale joignant dans le plan, muni d'un système
d'axes de coordonnées, les points

$$
(0, 0), (1, x_{i_1}), (2, x_{i_1} + x_{i_2}), \dots, (r, x_{i_1} + \dots + x_{i_r})
$$

est située au-dessous ou sur la corde joignant les points (0,0) et
(r, x_{i_1} + ... + x_{i_r}).

S'il existe des entiers $r'$ ($1 \le r' < r$) tels que les points $(r', x_{i_1} + \dots + x_{i_r})$ se trouvent sur cette corde, nous pouvons caractériser ces entiers $r'$.

Soit $\eta : \mathcal{Y} \to \mathcal{R}$ une bijection ; l'ordre lexicographique sur $\mathcal{R}$ induit un ordre total sur $\mathcal{Y}$. On peut donc munir $\mathcal{Y}^*$ de l'ordre lexicographique induit par l'ordre de $\mathcal{Y}$.

Soit alors $r_1, r_2, \ldots, r_s$ la suite de tous les entiers tels
que les points $(r_1, x_{i_1} + \ldots + x_{i_{r_1}}), \ldots, (r_s, x_{i_1} + \ldots + x_{i_{r_s}})$
sont sur la corde joignant

$$
(0, 0) \text{ et } (r, x_{i_1} + \dots + x_{i_r})
$$

$(1 \le r_1 < r_2 < \dots < r_s < r)$ et posons

$$
\eta g_1 = x_{i_1} \dots x_{i_{r_1}}, \quad \eta g_2 = x_{i_{r_1+1}} \dots x_{i_{r_2}}, \dots, \quad \eta g_s = x_{i_{r_s+1}} \dots x_{i_{r_s}}
$$

Alors le mot $g_1 g_2 \dots g_s$ est un mot lexicographique standard dans
le monoïde libre $\mathcal{Y}^*$.
*Exemple.* - Considérons dans le monoïde libre $\mathcal{X}^*$ engendré par $\mathcal{X} = \mathbb{R}$ le mot correspondant à la suite

$$S = (-1, 2, 0, 1, -4, 2, 2, -2, 3, -4, 2, 2, -2, 0, 1, 1, -1, 0)$$

c'est-à-dire le mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ où $r = 20$ et où

$$(x_{i_1}, x_{i_2}, \dots, x_{i_r})$$

est identique à la suite S.

Dans le plan, considérons un système d'axes rectangulaires et traçons la ligne polygonale joignant les points $(0, 0)$, $(1, x_{i_1})$, $(2, x_{i_1} + x_{i_2})$, ..., $(20, x_{i_1} + x_{i_2} + \dots + x_{i_{20}})$. Nous obtenons

<figure><img src="image_4.png" /></figure>

Par la méthode des crochets, décrite dans le paragraphe 7.2, nous construisons l'élément unique de $H_0$ correspondant à $f$ et nous obtenons

$$\text{[[-1 2][0 1]}}{{\text{[[-4 2] 2] 2}[-2 3]}}{{\text{[[-4 2] 2] 2} \text{[[-2 0] 1] 1}[-1 0]}$$

D'où la factorisation de $f$ correspondant aux suites
$(-1, 2, 0, 1) \ (-4, 2, 2, -2, 3) \ (-4, 2, 2, 2) \ (-2, 0, 1, 1) \ (-1, 0).$

Observons que les trois premiers mots correspondent à des lignes polygonales dont les cordes ont même pente, que si l'on pose
$$ \eta g_1 = -1, 2 $$

$$ \eta g_2 = 0, 1 $$

$$ \eta g_3 = -4, 2, 2, 2 $$

$$ \eta g_4 = -2, 3 $$

$$ \eta g_5 = -4, 2, 2, 2, \text{ alors} $$

$(g_1, g_2), (g_3, g_4), (g_5)$ est justement la factorisation en mots lexicographiques standards.

Observons enfin sur cet exemple que les mots $f$ de $\mathfrak{B}$ vé. rifient

$$ P f \leq L f. $$

### 7.6. Factorisation spéciale induite par une fonction continue strictement monotone.

DEFINITION (Hardy, Polya, Littlewood 20 p. 65.). - Soit $\psi$ une fonction continue strictement monotone définie dans un intervalle $I \subset \mathbb{R}$ et $(x_{i_k})_{1 \leq k \leq r}$ une famille de $r$ points de $I$. On ap- pelle moyenne de cette famille relativement à $\psi$ le nombre

$$ \mathfrak{M}_{\psi}((x_{i_k})_{1 \leq k \leq r}) = \psi^{-1} \left( \frac{\sum \psi(x_{i_k})}{r} \right). $$

Pour une famille $(x_{i_k})_{1 \leq k \leq r}$ donnée, le nombre $\mathfrak{M}_{\psi}((x_{i_k})_{1 \leq k \leq r})$ est unique et l'on a

$$ \min (x_{i_k}) \leq \mathfrak{M}_{\psi}((x_{i_k})_{1 \leq k \leq r}) \leq \max (x_{i_k}) $$

et nous avons l'égalité de ces trois membres dans le seul cas où tous les $x_{i_k}$ sont égaux.

La factorisation spéciale induite se définit comme suit. J est encore l'ensemble totalement ordonné défini au paragraphe précédent.

Soit $\mathcal{X}^*$ le monoïde libre engendré par $I$ et nous désignons par $\tau_{\psi}$ l'application $\mathcal{X}^* \to \mathbb{R}$ qui fait correspondre au mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ le nombre réel

$$ \tau_{\psi} f = \mathfrak{M}_{\psi}((x_{i_k})_{1 \leq k \leq r}) = \psi^{-1} \left( \frac{\sum \psi(x_{i_k})}{r} \right) $$

et par $\theta_{\psi}: \mathcal{X}^* \to J$ l'application qui au mot $f = x_{i_1} x_{i_2} \dots x_{i_r}$ de $\mathcal{X}^*$ associe le couple $(\tau_{\psi} f, \pi f)$ de $J$.
L'application $\theta_{\psi}$ satisfait la condition (B).

Supposons, en effet, que pour $f = x_{i_1} x_{i_2} \dots x_{i_r}$ et

$$f' = x_{i_1}' x_{i_2}' \dots x_{i_r}'$$

on ait

$$\tau_{\psi} f < \tau_{\psi} f'$$

Alors, puisque $\phi$ est continu et strictement monotone

$$\frac{\Sigma \psi(x_{i_k})}{r} < \frac{\Sigma \psi(x_{i_k}')}{r'}$$

D'où

$$\frac{\Sigma \psi(x_{i_k})}{r} < \frac{\Sigma \psi(x_{i_k}) + \Sigma \psi(x_{i_k}')}{r + r'} < \frac{\Sigma \psi(x_{i_k}')}{r'}$$

Soit

$$\tau_{\psi} f < \tau_{\psi} f' f = \tau_{\psi} f' f < \tau_{\psi} f'$$

Enfin, il est bien évident que si

$$\tau_{\psi} f = \tau_{\psi} f' \quad \text{alors} \quad \tau_{\psi} f = \tau_{\psi} f f' = \tau_{\psi} f' f = \tau_{\psi} f' f'$$

Comme d'autre part, la fonction $\pi$ satisfait la condition (B), ceci est suffisant pour montrer que $\theta_{\psi}$ satisfait la condition (B). Les mêmes autres remarques que pour la factorisation de Spitzer s'appliqueraient ici pour montrer qu'on obtient encore une factorisation spéciale.

Lorsque $\phi$ est une application affine, on retrouve la factorisation de Spitzer.

Lorsque

$$I = \{x \in \mathbb{R} : x > 0\} \text{ et } \phi : x \rightarrow \log x$$

$\pi_{\psi}((x_{i_k})_{(1 \le k \le r)})$ est la moyenne géométrique de $x_{i_k}$.

Lorsque
$$I = \{x \in \mathbb{R} : x > 0\} \text{ et } \psi : x \to \frac{1}{x}$$

$\mathcal{M}_{\psi}((x_{i_k})_{(1 \le k \le r)})$ est la moyenne harmonique des $x_{i_k}$.

Toutes ces fonctions induisent donc une factorisation spéciale de $\mathcal{X}^*$ où $\mathcal{X}$ est un intervalle de la droite réelle.
8. Applications des factorisations spéciales
Un théorème combinatoire non commutatif

8.1. Introduction.

Nous nous proposons dans ce chapitre de donner une nouvelle
démonstration du théorème combinatoire 6.1. Il va s'agir en fait
de construire une certaine permutation $\varphi$ de $X^*$, où $X^*$ est le
monoidre libre engendré par un ensemble totalement ordonné $X$,
associée à toute factorisation spéciale de $X^*$.

La méthode employée va consister, comme dans le chapitre 4,
à faire correspondre à tout mot $f \in X^*$ une permutation $\Pi f$ d'un
ensemble fini qu'on écrira comme produit de cycles disjoints sous
une forme dite standard que l'on définira.

Lorsque $X = \mathbb{R}$, une telle correspondance $f \to \Pi f$ a déjà
été introduite, au moins de façon implicite, par Foster & Stuart
[14], Barton & Mallows [3] et Rényi [31].

Mais dans tous ces articles, seul le cas des mots multi-
linéaires $f$ est étudié.

En d'autres termes, si $x_{i_1}, x_{i_2}, \ldots, x_{i_r}$ est une suite de r
nombres réels qu'on considère comme une réalisation de r va-
riables aléatoires $X_1, X_2, \ldots, X_r$, disons indépendantes et équi-
distribuées, il est supposé dans ces articles que la fonction de ré-
partition des $X_k$ est continue. Les $x_{i_k} (1 \le k \le r)$ sont donc
tous distincts deux à deux et le mot $f = x_{i_1} x_{i_2} \ldots x_{i_r}$ corres-
pondant, multilinéaire.

Une factorisation unique d'un tel mot $f$ est alors définie à
partir des "lower records" chez Foster ou des "éléments saillants"
chez Rényi qui sont les $x_{i_k}$ tels que

$$
x_{i_k} = \min \{ x_{i_k}, : 1 \le k' \le k \}.
$$
Si $k_1, k_2, \dots, k_s$ sont les p indices des éléments sailants, alors

$$ f_1 f_2 \dots f_s \quad \text{où} \quad f_p = x_{i_{k_{p-1}+1}} \dots x_{i_{k_p}} \\ (k_o = 0; 1 \le p \le s) $$

est justement la factorisation du mot f multilinéaire en mots lexicographiques standards.

La permutation $\varphi$ que nous allons construire va, au contraire, être définie pour tous les mots f de $\mathcal{X}^*$ non nécessairement multilinéaires.

Sa construction exige cependant que l'on démontre d'abord quelques lemmes afin de définir $\Pi f$ sans ambiguïté.

Nous avons cru bon de terminer ce chapitre par un exemple qui permet de suivre toutes les transformations définies au cours de ces lemmes.

Signalons enfin que les résultats de ce chapitre ont déjà été donnés dans une note aux Comptes-Rendus [13].

## 8.2. Rappel de définitions.

$\mathcal{X}^*$ étant le monoïde libre engendré par un ensemble $\mathcal{X}$, nous avons introduit au § 6.3 deux familles de fonctions $(v_x, x')$ et $(\xi_{x, x'}, l_{(x, x')} \in \mathcal{X}^2)$ définies sur $\mathcal{X}^*$ à valeurs entières en posant pour

$$ f = x_{i_1} x_{i_2} \dots x_{i_r} \quad \text{et} \quad \beta f = x_{j_1} x_{j_2} \dots x_{j_r} $$

$$ v_{x, x'} \quad f = \text{nombre d'indices } k \text{ tels que } x_{i_k} = x \qquad (8.2.1) $$

$$ \text{et } x_{j_k} = x' \quad (1 \le k \le r). $$

$$ \xi_{x, x'} \quad f = 0 \quad \text{si} \quad \lambda f = 1 \qquad (8.2.2) $$

$$ = \text{nombre d'indices } k \text{ tels que } x_{i_k} = x $$

$$ \text{et } x_{i_{k+1}} = x' \quad (1 \le k \le r-1) \quad \text{si} \quad \lambda f > 1. $$
Supposons-nous maintenant donnée une factorisation de Schützenberger de type b, c'est-à-dire un sous-ensemble $\mathcal{H}$ fixe de mots primitifs et $\mathfrak{a}$ un ordre total sur $\mathcal{H}$ tel que chaque élément $f \in \mathcal{X}^{**}$ a une et une seule factorisation de la forme $f_1 f_2 \dots f_s$ ($s > 0$) où

(i) $f_1, f_2, \dots, f_s \in \mathcal{H}$

(ii) $f_1 \preceq f_2 \preceq \dots \preceq f_s$.

Posons

$$f_p = x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1} \quad (\lambda f_p = \lambda_p : 1 \le p \le s)$$

et convenons aussi, dans ce qui suit, que le deuxième indice $l$ des variables $x_{p,l}$ est un entier modulo $\lambda_p$ ($1 \le p \le s$).

Nous pouvons alors définir sur $\mathcal{X}^*$ une famille de fonctions à valeurs entières $(\mu_{x,x'})_{((x,x') \in \mathcal{X}^2)}$, associée à cette factorisation en posant

$$\mu_{x,x'} : f = \text{nombre de couples } (p, l)$$

tels que

$$x_{p,l} = x \quad \text{et} \quad x_{p,l+1} = x' \\ (1 \le p \le s, \ 0 \le l \le \lambda_p - 1).$$

Notre but est d'abord de construire, associée à une telle factorisation, une permutation $\varphi$ de $\mathcal{X}^*$ telle que

$$(1) \qquad \alpha \varphi f = \alpha f \qquad (8.2.3)$$

$$(2) \qquad \nu_{x,x'} : f = \mu_{x,x'} \quad \varphi f \quad (f \in \mathcal{X}^*)$$

pour tout couple $(x, x') \in \mathcal{X}^2$.

Lorsque, en plus, le couple $(\mathcal{H}, \preceq)$ satisfait la condition (Sp) suivante

(Sp) Il existe un sous-ensemble $\mathcal{X}_o \subset \mathcal{X}^2$ tel que pour tout couple $f, f'$ de mots de $\mathcal{H}$ tels que $f \preceq f'$, on a

$$(Lf, Pf) \notin \mathcal{X}_o,$$

nous disons que $(\mathcal{H}, \preceq, \mathcal{X}_o)$ est spécial.
Lorsque $\mathcal{X}$ est un ensemble totalement ordonné ($\leq$ son ordre) nous disons simplement que $(\mathcal{X}, \leq)$ est *spécial* ou que la factorisation (S) associée est *spéciale* si

$$ \mathcal{X}_0 = \{(x, x') \in \mathcal{X}^2 : x \leq x'\}. \text{ (Cf. (7.1.1) et (7.1.2)).} $$

Dans le chapitre précédent, nous avons vu comment construire des factorisations spéciales à partir de couples $(\theta, J)$ où $J$ est un ensemble totalement ordonné et où $\theta: \mathcal{X}^* \to J$ vérifie la condition (B)

$$ f, f' \in \mathcal{X}^* \Rightarrow \theta f > \theta f' > \theta f' \text{ ou } \theta f = \theta f' = \theta f' \text{ ou } \theta f < \theta f' < \theta f' $$

La factorisation en mots lexicographiques standards (Cf. § 7.4) était de ce type, de même que la factorisation de Spitzer (Cf. § 7.5) et aussi les factorisations sur le monoïde libre engendré par un intervalle I de la droite réelle, induites par une fonction continue strictement monotone (§ 7.6).

Etant donnés un sous-ensemble fixe $\mathcal{X}_0$ de $\mathcal{X}^2$ et $(\mathcal{X}, \leq)$ une factorisation (S) de type b, alors nous montrerons (théorème 8.1 ci-dessous) que la permutation $\varphi$ associée à $(\mathcal{X}, \leq)$ vérifie

$$ v_{x,x'} \cdot f = \xi_{x,x'} \cdot \varphi f \quad (8.2.4) $$

identiquement pour tout couple $(x, x') \in \mathcal{X}_0$ si et seulement si $(\mathcal{X}, \leq, \mathcal{X}_0)$ est spécial.

Remarquons tout de suite que si la définition de la famille $(\mu_{x,x'}), (\nu_{x,x'}), \in \mathcal{X}^2$ dépend du couple $(\mathcal{X}, \leq)$ considéré, les définitions de $v_{x,x'}$ et $\xi_{x,x'}$ ne dépendent que du couple $(x, x') \in \mathcal{X}^2$ choisi. De plus, si $f = x_i$ ($\lambda f = 1$), alors card $\alpha f = 1$ et la restriction de $\varphi$ à $\alpha^{-1}\alpha f$ est triviallement l'application identique. Or, $v_{x_i,x_i} f = 0$ et $\xi_{x_i,x_i} f = 1$. (8.2.4) n'est donc pas satisfait. Ce qui montre que lorsque $(\mathcal{X}, \leq, \mathcal{X}_0)$ est spécial, alors $\mathcal{X}_0$ ne contient aucun élément de la diagonale de $\mathcal{X}^2$.

### 8.3. Construction de la permutation $\varphi$.

La permutation $\varphi$ aura la propriété (1) de (8.2.3) et nous pourrons donc supposer que $h$ est un élément fixe de $\mathcal{X}^*$ et construire la restriction de $\varphi$ à la classe abélienne $\alpha^{-1} h$.

Nous reprenons les mêmes notations qu'au paragraphe 4.2, c'est-à-dire que nous désignons encore par $x_{u_1}, x_{u_2}, \dots, x_{u_d}$ les lettres $x$ de $\mathcal{X}$ telles que $h x >^1 0$, et posons
$$h x_{u_t} = n_t \quad (1 \le t \le d)$$

$$r = \sum_{t=1}^{d} n_t \quad \text{et}$$

$$\beta'h = x_{u_1}^{n_1} x_{u_2}^{n_2} \dots x_{u_d}^{n_d} = x_{j_1} x_{j_2} \dots x_{j_r}$$

(le mot non décroissant de la classe abélienne $\alpha^{-1}h$) et désignons par $N(h)$ l'ensemble des couples $\{(x_{u_t}, m_t) : 1 \le m_t \le n_t, 1 \le t \le d\}$.

Soit $f = x_{i_1} x_{i_2} \dots x_{i_r}$ un mot de $\alpha^{-1}h$. Alors l'application

$$\Pi f : (x_{i_k}, \gamma_k f) \longrightarrow (x_{j_k}, \gamma_k \beta' h)$$

est une permutation de l'ensemble $N(h)$. Ecrivons-la comme produit de cycles disjoints (Cf. 4.1)

$$\Pi f = (B_1) (B_2) \dots (B_s) \quad (s > 0)$$

où

$$B_p = ((x_{p,0}, \epsilon_{p,0}) (x_{p,1}, \epsilon_{p,1}) \dots (x_{p,\lambda_{p-1}}, \epsilon_{p,\lambda_{p-1}}))$$

avec

$$x_{p,0}, x_{p,1}, \dots, x_{p,\lambda_{p-1}} \in \mathcal{X}$$

$$\epsilon_{p,0}, \epsilon_{p,1}, \dots, \epsilon_{p,\lambda_{p-1}} \in \mathbb{N}$$

$$(1 \le p \le s) \quad \text{et} \quad \{(x_{p,l}, \epsilon_{p,l}) : 1 \le p \le s \quad 0 \le l \le \lambda_{p-1}\} = N(h).$$

Dans ce qui suit, convenons aussi que le deuxième indice $l$ des variables $x_{p,l}, \epsilon_{p,l}, \dots$ est un entier modulo $\lambda_p$.

Avec cette convention, et par définition même de la permutation $\Pi f$, à tout $k \in [1, r]$, correspond un et un seul couple $(p, l)$ ($1 \le p \le s$ ; $0 \le l \le \lambda_{p-1}$) tel que

$$(x_{p,l}, \epsilon_{p,l}) = (x_{i_k}, \gamma_k f); \quad (8.3.1)$$

et l'on a (1)

$$(x_{i_k}, \gamma_k \beta' h) = (\Pi f)(x_{i_k}, \gamma_k f) = (\Pi f)(x_{p,l}, \epsilon_{p,l}) = (x_{p,l+1}, \epsilon_{p,l+1}) \quad (8.3.2)$$

(1) Nous faisons ici la convention de noter par $(a_{i_1} a_{i_2} \dots a_{i_k})$ un cycle d'une permutation $\sigma$ de n objets $(a_1, a_2, \dots, a_n)$ si l'on a $0 < k \le n$ et $\sigma a_{i_1} = a_{i_2}, \sigma a_{i_2} = a_{i_3}, \dots, \sigma a_{i_{k-1}} = a_{i_k}, \sigma a_{i_k} = a_{i_1}$.
Nous vérifions d'abord le

LEMME 8.1. - Soit $p$ et $p'$ deux entiers $\in [1, s]$ et $l$ et $l'$ deux entiers pris modulo $\lambda_p$ et $\lambda_{p'}$ respectivement tels que

$$x_{p,l} = x_{p',l'} \quad \text{et} \quad \varepsilon_{p,l} < \varepsilon_{p',l'}$$

alors on a

$$\text{ou} \quad x_{p,l+1} < x_{p',l'+1}$$

$$\text{ou} \quad x_{p,l+1} = x_{p',l'+1} \quad \text{et} \quad \varepsilon_{p,l+1} < \varepsilon_{p',l'+1}.$$

PREUVE. - En effet, désignons par $k$ et $k' \in [1, r]$ les entiers tels que l'on ait respectivement

$$(x_{i_k}, \gamma_k f) = (x_{p,l}, \varepsilon_{p,l})$$

et

$$(x_{i_k}, \gamma_k f) = (x_{p',l'}, \varepsilon_{p',l'}).$$

Alors, l'hypothèse $\varepsilon_{p,l} < \varepsilon_{p',l'}$ entraîne évidemment $\gamma_k f < \gamma_{k'} f$. Mais comme $x_{i_k} = x_{p,l} = x_{p',l'} = x_{i_k'}$, on a $k < k'$ par définition même de $\gamma_k$ et $\gamma_{k'}$.

D'autre part, la définition de $\Pi f$ donne

$$(x_{j_k}, \gamma_k \beta' h) = (\Pi f)(x_{i_k}, \gamma_k f) = (\Pi f)(x_{p,l}, \varepsilon_{p,l}) = (x_{p,l+1}, \varepsilon_{p,l+1})$$

et de même

$$(x_{j_k}, \gamma_k, \beta' h) = (x_{p',l'}, \varepsilon_{p',l'+1}).$$

Ainsi $k < k'$ entraîne $x_{j_k} < x_{j_k'}$, c'est-à-dire

$$x_{p,l+1} < x_{p',l'+1}$$

$$\text{ou si } x_j = x_{j'}$$

$$\gamma_k \beta' h < \gamma_{k'} \beta' h$$

soit

$$\varepsilon_{p,l+1} < \varepsilon_{p',l'+1}$$
Appliquons ce résultat dans le lemme suivant

LEMME 8.2. - Le mot $x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1}$ est primitif (1 ≤ p ≤ s) et si les deux mots $x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1}$ et $x_{p',0} x_{p',1} \dots x_{p',\lambda_p-1}$ sont conjugués, alors

$$ \varepsilon_{p,l} < \varepsilon_{p',l+l_0} \quad \text{ou} \quad \varepsilon_{p,l} > \varepsilon_{p',l+l_0} $$

pour tout $l \in [0, \lambda_p - 1]$, $l_0$ étant l'entier modulo $\lambda_p$ tel que

$$ x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1} = x_{p',l_0} x_{p',l_0+1} \dots x_{p',\lambda_p+l_0-1} \quad (1 \le p < p' \le s) $$

PREUVE. - Supposons donc que $x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1}$ n'est pas primitif.

Alors $x_{p,1} x_{p,2} \dots x_{p,\lambda_p} = f'^q (q > 1)$ où $f' \in \mathcal{X}^{*+}$ et où l'entier q est maximal ; en posant $\lambda f' = m$, nous avons

$$ x_{p,0} = x_{p,m} = \dots = x_{p,(q-1)m} $$

..................

$$ x_{p,m-1} = x_{p,2m-1} = \dots = x_{p,qm-1} $$

Supposons que

$$ \varepsilon_{p,0} = \min \{ \varepsilon_{p,0}, \varepsilon_{p,m}, \dots, \varepsilon_{p,(q-1)m} \} $$

(on peut toujours permuter circulairement le cycle $B_p$ pour qu'il en soit ainsi).

En appliquant le précédent lemme pour $p = p'$ et

$$ (l, l') = (0, (q-1)m) $$

on a

$$ \varepsilon_{p,1} < \varepsilon_{p,0} \quad \text{si} \quad m = 1. $$

D'où une contradiction.

Si $m > 1$, on a

$$ \varepsilon_{p,1} < \varepsilon_{p,(q-1)m+1} $$

D'où, en appliquant le lemme successivement à
$(l, l') = (1, (q-1)m+1), (2, (q-1)m+2) \dots (m-1, qm-1)$, et $p = p'$, on a les inégalités

$$ \varepsilon_{p,1} < \varepsilon_{p,(q-1)m+1} ; \varepsilon_{p,2} < \varepsilon_{p,(q-1)m+2} ; \dots ; \varepsilon_{p,m} < \varepsilon_{p,qm} $$

Soit, en particulier, puisque $qm \equiv 0 \mod \lambda_p$

$$ \varepsilon_{p,m} < \varepsilon_{p,0} $$

D'où une contradiction.

Ce qui démontre que le mot $x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1}$ est bien primitif.

Pour la seconde partie du lemme, supposons par exemple que $\varepsilon_{p,0} < \varepsilon_{p'}, l_0$.

Puisque les deux mots

$x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1}$ et $x_{p',l_0} x_{p',l_0+1} \dots x_{p',\lambda_p+l_0-1}$

sont identiques, nous avons, en appliquant le lemme précédent,

$$ \varepsilon_{p,1} < \varepsilon_{p',l_0+1} $$

d'où par itération

$$ \varepsilon_{p,2} < \varepsilon_{p',l_0+2} , \dots , \varepsilon_{p,\lambda_p-1} < \varepsilon_{p,\lambda_p+l_0-1} $$

Ce qui achève la démonstration du lemme.

Ces deux lemmes vont nous permettre d'écrire la permutation $\Pi$ sous une forme dite *standard*. Plus précisément, d'après le lemme 8.2, tout mot $x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1}$ est primitif. Le théorème 5.1 entraîne alors qu'il n'y a qu'un et qu'un seul mot de $\mathfrak{H}$ conjugué à $x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1}$. Comme chacun des cycles $(B_p)$ n'est défini qu'à une seule permutation circulaire près de ses éléments, on peut supposer désormais que

$$ x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1} \in \mathfrak{H} \quad (1 \le p \le s). $$

Sous cette hypothèse, toute relation

$$ x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1} = x_{p',0} x_{p',1} \dots x_{p',\lambda_p-1} $$
(p f p') entraîne alors, d'après la deuxième partie du lemme 8.2, que

$$ \epsilon_{p,l} < \epsilon_{p',l} \quad \text{pour tout} \quad l \in [0, \lambda_p - 1] $$

ou

$$ \epsilon_{p',l} < \epsilon_{p,l} \quad \text{pour tout} \quad l \in [0, \lambda_p - 1]. $$

De même $\Pi f$ n'étant défini qu'à une permutation près de ses cycles, on peut supposer désormais que $\Pi f$ est sous forme standard, c'est-à-dire que

$$ (1) \qquad x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1} \in \mathcal{H} \quad (1 \le p \le s) \qquad (8.3.3) $$

$$ (2) \quad \text{si} \quad 1 \le p < p' \le s, \quad \text{alors} $$

$$ \text{ou} \quad x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1} \succ x_{p',0} x_{p',1} \dots x_{p',\lambda_p-1} $$

$$ \text{ou} \quad x_{p,0} x_{p,1} \dots x_{p,\lambda_p-1} = x_{p',0} x_{p',1} \dots x_{p',\lambda_p-1} $$

mais $\epsilon_{p,l} < \epsilon_{p',l}$ pour tout $l \in [0, \lambda_p - 1]$. Ainsi, chaque $\Pi f$ a une et une seule forme standard

$$ \Pi f = ((x_{1,0}, \epsilon_{1,0}) \dots (x_{1,\lambda_1-1}, \epsilon_{1,\lambda_1-1})) \dots ((x_{s,0}, \epsilon_{s,0}) \dots (x_{s,\lambda_s-1}, \epsilon_{s,\lambda_s-1})). $$

Nous posons

$$ \wp f = x_{1,0} \dots x_{1,\lambda_1-1} x_{2,0} \dots x_{2,\lambda_2-1} \dots x_{s,0} \dots x_{s,\lambda_s-1}. \quad (8.3.4) $$

Puisque $\Pi f$ est une permutation de l'ensemble $N(h)$, nous avons bien $\wp f \in \alpha^{-1}h$.

Il résulte alors des identités (8.3.1) et (8.3.2) qu'à tout entier $k \in [1, r]$ correspond biunivoquement un couple $(p, l)$ ($1 \le p \le s$ ; $0 \le l \le \lambda_p - 1$) tel que

$$ x_{i_k} = x_{p,l} \quad \text{et} \quad x_{j_k} = x_{p,l+1}. $$

Pour tout couple $(x, x') \in \mathcal{X}^2$ il y a ainsi autant d'indices $k$ tels que $x_{i_k} = x$ et $x_{j_k} = x'$ ($1 \le k \le r$) que de couples $(p, l)$ tels que $x_{p,l} = x$ et $x_{p,l+1} = x'$ ($1 \le p \le s$ ; $0 \le l \le \lambda_p - 1$).

La condition (2) de (8.2.3) est ainsi satisfaite, soit
$$v_{x,x'} f = \mu_{x,x'} \varphi f \quad (x, x') \in \mathcal{X}^2.$$

Nous allons montrer ensuite que l'application $\varphi$ ainsi définie est bien une permutation de $\alpha^{-1} h$.

Le prochain lemme va nous permettre de déterminer, lorsque $\Pi f$ est sous forme standard, la valeur des entiers $\epsilon_{p,l}$ en fonction seulement des lettres du mot $\varphi f$.

D'abord, à tout couple $(p, l)$ ($1 \le p \le s$ ; $0 \le l \le \lambda_p - 1$), nous faisons correspondre le mot

$$c_{p,l} = x_{p,l} x_{p,l+1} \dots x_{p,l+\Lambda-1} \quad \text{où} \quad \Lambda = r'!.$$

Avec notre convention sur le second indice $l'$ de $x_{p,l'}$ nous aurons ainsi $x_{p,l'} = x_{p,l''}$ si $l' \equiv l'' \bmod \lambda_p$.

Nous avons

LEMME 8.3. - L'entier $\epsilon_{p,l}$ est égal au nombre des couples $(p', l')$ tels que

$$(1) \qquad x_{p',l'} = x_{p,l}$$

$$(2) \qquad \text{soit } c_{p',l'}.$$

(8.3.6)

précède $c_{p,l}$ dans l'ordre lexicographique

$$(0 \le l' \le \lambda_p, -1 ; 1 \le p' \le s)$$

soit $c_{p',l'} = c_{p,l}$

$$(0 \le l' \le \lambda_p, -1 ; 1 \le p' \le p).$$

PREUVE. - Soit deux couples $(p, l)$ et $(p', l')$

$$(p, p' \in [1, s] ; 0 \le l \le \lambda_p - 1 ; 0 \le l' \le \lambda_p - 1)$$

tels que

$$x_{p,l} = x_{p',l'} \quad \text{et} \quad \epsilon_{p,l} < \epsilon_{p',l'}$$

et considérons les deux mots associés $c_{p,l}$ et $c_{p',l'}$. Si

$$c_{p,l} \neq c_{p',l'}.$$
alors il existe un entier $l_o \ge 0$ tel que

$$x_{p,l} = x_{p',l'} \quad x_{p,l+1} = x_{p',l'+1} \dots, x_{p,l+l_o} = x_{p',l'+l_o}$$

et

$$x_{p,l+l_o+1} \neq x_{p',l'+l_o+1}$$

Comme $\varepsilon_{p,l} < \varepsilon_{p',l'}$, on a, par application du lemme 8.1

$$\varepsilon_{p,l} < \varepsilon_{p',l'} \implies \varepsilon_{p',l+1} < \varepsilon_{p',l'+1} \implies \dots \implies \varepsilon_{p,l+l_o} < \varepsilon_{p',l'+l_o}$$

et cette dernière inégalité entraîne encore

$$x_{p,l+l_o+1} < x_{p',l'+l_o+1}$$

$$\text{D'où } c_{p,l} < c_{p',l'} \qquad (8.3.7)$$

Si les deux couples $(p, l)$ et $(p', l')$ sont distincts et si $c_{p,l} = c_{p',l'}$, alors, puisque d'après le lemme 8.2 les mots $x_{p,0} x_{p,1} \dots x_{p,\lambda_{p-1}}$ et $x_{p',0} x_{p',1} \dots x_{p',\lambda_{p'-1}}$ sont primitifs, $p \neq p'$ ; et $\Pi$ f'étant sous forme standard, la condition (2) de (8.3.3) entraîne $p < p'$.

Ainsi, si $\varepsilon_{p,l} = m$, il y a m couples $(p', l')$ en comptant le couple $(p, l)$, tels que

$$x_{p',l'} = x_{p,l} \quad \text{et} \quad \varepsilon_{p',l'} \le m$$

et pour chacun de ces couples, ou $c_{p',l'}$ précède $c_{p,l}$ dans l'ordre lexicographique d'après (8.3.7), ou $c_{p',l'} = c_{p,l}$ mais $p \le p'$.

Le lemme 8.3 est ainsi démontré.

Nous dirons maintenant qu'une permutation $\Pi_o$ de $N(h)$ est standard si elle peut s'écrire comme produit des cycles disjoints,

$$\Pi_o = (B_1) (B_2) \dots (B_s)$$

où

$$(B_p) = ((x_{p,0}, \varepsilon_{p,0}) (x_{p,1}, \varepsilon_{p,1}) \dots (x_{p,\lambda_{p-1}}, \varepsilon_{p,\lambda_{p-1}})) \quad (1 \le p \le s)$$

et où

$$(1) \quad x_{p,0} x_{p,1} \dots x_{p,\lambda_{p-1}} \in \mathcal{H} \quad (1 \le p \le s) \quad \text{et si } s > 1,$$

$$(2) \quad x_{p,0} x_{p,1} \dots x_{p,\lambda_{p-1}} \stackrel{\gamma}{=} x_{p+1,0} x_{p+1,1} \dots x_{p+1,\lambda_{p+1}-1} \quad (1 \le p \le s-1) \quad (8.3.8)$$