# La correspondance de robinson

Marcel-Paul Schützenberger

► To cite this version:

Marcel-Paul Schützenberger. La correspondance de robinson. [Rapport de recherche] IRIA-RR-180, IRIA. 1976, pp.49. hal-04716368

HAL Id: hal-04716368

https://inria.hal.science/hal-04716368v1

Submitted on 1 Oct 2024

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>
RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B.P. 5 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

LA CORRESPONDANCE
DE ROBINSON

Marc Paul SCHÜTZENBERGER

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

Rapport de Recherche N° 180

Juillet 1976
LA CORRESPONDANCE DE ROBINSON

M.P. Schützenberger

Résumé :

On rassemble de façon systématique l'ensemble des énoncés connus sur la théorie combinatoire des tableaux de Young et la correspondance de G. de B. Robinson.

Abstract :

The main results in the combinatorial theory of Young tableaux are developed in a systematic fashion.
# 1. Introduction.

1.1. La correspondance R entre permutations et tableaux standards de Young introduite en 1938 par G. de B. Robinson [12] dans la théorie des représentations du groupe symétrique a été depuis étudiée en elle-même par divers auteurs qui lui ont découvert une série de propriétés combinatoires curieuses, ou utiles pour l'étude des fonctions symétriques. Dans le présent travail nous nous proposons de donner un exposé systématique des principaux résultats basé sur la théorie de C. Green ([5], [6], [7]) grâce à laquelle il devient possible de montrer que la correspondance R est *naturelle* sur l'ensemble de tous les tableaux gauches ("skew" de Young (appelés ici *tableaux*) muni d'une structure convenable.

J'ai utilisé de nombreuses idées de G. Thomas et de A. Lascoux pour simplifier ces preuves et organiser les énoncés de façon à réduire autant que j'ai pu la partie combinatoire.
La technique est la suivante. On considère le plan entier $P = Z \times Z$ muni de son ordre naturel $\leq (x, y) \leq (x', y')$ ssi $x \leq x'$ et $y \leq y'$) et on identifie chaque tableau (gauche, "shew") de Young à un morphisme (de structure d'ordre) bijec-tif d'un intervalle du plan sur une chaîne standard $[n] = \{1 < 2 < ... < n\}$. On associe une certaine relation d'ordre $C_{\phi}$ sur $[n]$ à chaque tableau $\phi$ d'image $[n]$ et pour $j \geq 0, k \geq 1$ on définit $L_j(\phi; k)$ comme le maximum du nombre des éléments parmi les parties de $[n-j]$ qui sont unions de $k C_{\phi^{-1}}$-chaînes.

La fonction $L$ induit une équivalence $\equiv$ sur l'ensemble des tableaux $(\phi \equiv \psi \text{ ssi } L(\phi) = L(\psi))$ dont chaque classe contient un et un seul élément qui soit un tableau standard (c'est-à-dire dont la forme soit celle d'un diagramme de Ferrers) : c'est la correspondance de Robinson et on peut caractériser les trans-formations entre tableaux (les "glissements") qui commutent avec $\equiv$.

La famille des tableaux peut être munie d'un produit associatif pour lequel $\equiv$ est une congruence. De ce point de vue les permutations peuvent être considérées comme des produits $\sigma$ dont chaque terme a pour domaine un point. Il se trouve que les ordres $C_{\sigma}$ et $C_{\sigma^{-1}}$ sont isomorphes et on en déduit aisément le théorème fondamental de G. de B. Robinson que la correspondance $\sigma \to (\sigma R, \sigma^{-1}R)$ est une bijection des permutations sur les paires de tableaux standards de même forme.

Cet énoncé fournit le substrat combinatoire aux résultats classiques connus sous le nom de "règle de Littlewood-Richardson" et "théorème d'Aitken". Le lien avec la théorie des fonctions de Schur s'effectue en vérifiant que les manipulations précédentes équivalent au calcul dans le quotient de l'anneau des polynômes en $n$ variables $x_i$ par la congruence $x_i^2 \equiv 0 (i = 1, 2, ..., n)$.

Nous ferons référence aux travaux de G. Thomas ([18], [19]) qui montrent de façon plus précise, que le relèvement de la structure multilinéaire seule considérée ici peut être réalisé au moyen des opérateurs de Baxter introduits en algèbre par G. -C. Rota.
Une partie importante des propriétés que nous venons de résumer résulte de ce que la congrence $\equiv$ commute avec les involutions naturelles induite par la structure d'ordre sur le plan $\tilde{P}$. Pour profiter au maximum des simplifications que procurent ces opérations nous avons rassemblé dans la seconde partie de cette introduction l'ensemble des définitions et des notions géométriques, au demeurant parfaitement triviales, qui seront utilisées par la suite. Le chapitre 2 contient la définition des glissements. Le chapitre 3 montre d'après C. Green que ces opérations entre tableaux préservent la fonction L et quelles peuvent être obtenues en composant des transformations encore plus simples dues à D. E. Knuth [8]. La correspondance de Robinson est définie dans le même chapitre et le théorème fondamental sur les permutations est établi dans le chapitre 4. Le dernier chapitre établit la connexion avec les fonctions de Schur.

Les lecteurs de ce mémoire devront remercier le Professeur D. Foata qui a consacré beaucoup d'efforts à son amélioration et sans lequel je n'aurais pu le terminer.

## 1.2. NOTATIONS.

**Intervalles.** Dans tout ce travail nous désignerons par $J$ la famille des parties finies $F$ du plan entier $\tilde{P} = Z \times Z$ qui sont des **intervalles** par rapport à l'ordre naturel $\le$ c'est-à-dire qui satisfont la condition

$$ (1) \qquad p, p' \in F, p'' \in \tilde{P}, p \le p'' \le p' \Rightarrow p'' \in F. $$

Un interval $F$ sera dit **principal** ($F \in \tilde{J}$) ssi il possède un point minimum (par rapport à l'ordre naturel) **unique** c'est-à-dire ssi il a la forme d'un diagramme de Ferrers. Chaque intervalle $F$ est contenu dans un plus petit intervalle principal $\tilde{F}$ que l'on peut définir comme la plus petite partie $F'$ du plan qui contienne $F$ et qui soit telle que

$$ (2) \qquad p, p' \in F' \Rightarrow \text{Min}\{p, p'\} \in F'. $$
Il sera commode de désigner par $\tilde{J}^1$ la sous-famille des intervalles $F$ dont $(1, 1)$ est le point minimum de $\tilde{F}$, c'est-à-dire de disposer d'une cross section de $J$ par rapport aux translations.

**Ordre croisé.** Concurremment avec l'ordre naturel $\leq$, nous utiliserons un second ordre sur le plan $P$, dit *ordre croisé* dont le graphe $C \subset P \times P$ sera défini par l'identité :

$$ (3) \qquad ((x, y), (x', y')) \in C \quad \text{ssi} \ x \leq x' \ \text{et} \ y \geq y'. $$

Autrement dit, l'involution $(x, y) \to (x, -y)$ sur le plan établit un isomorphisme entre les ordres naturels et croisés. La transposition $p = (x, y) \to p^T = (y, x)$ est un anti-isomorphisme entre $C$ et l'ordre opposé $\bar{C}$. Il en est de même de la symétrie par rapport à l'origine $p = (x, y) \to -p = (-x, -y)$ c'est-à-dire que pour toute paire $(p, p')$ de points les relations :

$$ (4) \qquad (p, p') \in C; \ (p', p) \in \bar{C}; \ (p'^T, p'^T) \in C; \ (-p', -p) \in C; \ (-p'^T, -p'^T) \in C; $$
sont équivalentes.

Nous dirons qu'une partition ordonnée $(F_1, F_2, \dots, F_n)$ d'une partie $F$ du plan est une *C-partition* ssi, d'une part deux points de $F$ sont incomparables pour l'ordre naturel quand ils appartiennent à deux composantes *distinctes* et, d'autre part, $(p, q) \in C$ pour tout $p \in F_i, q \in F_j$ quand $i < j$. Par exemple la suite ordonnée des points $\{(n, 1)\}, \{(n-1, 2)\}, \dots \{(n-i, i+1)\}, \dots \{(1, n)\}$ forme une C-partition de leur union $F$.

On voit facilement qu'une condition nécessaire et suffisante pour que $(F_1, \dots, F_r)$ soit une C-partition est qu'il existe des points $(x_i, y_i)$ $(i = 2, \dots, r)$ tels que pour chaque $j = 1, \dots, r$ et $(x, y) \in F_j$ on ait :
x ≤ xᵢ, y ≥ yᵢ si j ≤ i et xᵢ \{x, yᵢ\} y si j > i.

Manifestement chaque composante $F_i$ d'une C-partition d'un intervalle F est elle-même un intervalle.

**Morphisme.** Dans tout ce travail un **morphisme** sera une application partielle $\varphi$ du plan P dans une chaîne dont la restriction à son domaine est un morphisme de structure d'ordre, c'est-à-dire qui est telle que $p\varphi \le p'\varphi$ pour toute paire ordonnée $p \le p'$ de points de son domaine. Pour l'essentiel nous n'aurons à faire qu'à une famille plus restreinte, à savoir la famille $\mathcal{M}$ des morphismes qui satisfont les deux conditions supplémentaires suivantes :

(1) leur domaine $F$ est un **intervalle** fini du plan ;

(2) leur restriction à celui-ci est une **bijection** sur leur image $A$.

Si besoin est, on précisera le domaine ou l'image par des écritures telles que $\eta_A$, $M(F)$ ou $\eta_A(F)$.

Comme les morphismes de $\mathcal{M}$ sont des bijections, il n'y aura pas d'inconvénient à désigner par la même notation $\varphi|F'$ ou $\varphi|A'$ leur restriction à une partie $F'$ de leur domaine ou $A'$ de leur image.

Nous ferons un usage constant de la remarque triviale que si le domaine $F$ d'un morphisme $\varphi$ (non nécessairement bijectif) est un intervalle (resp. un intervalle principal) et si $B$ est un intervalle (resp. un intervalle initial) de son image, le domaine de la restriction $\varphi|B$ est encore un intervalle (resp. un intervalle principal).

Nous supposerons en général que la chaîne $A = \{a_1 < a_2 < \dots < a_n\}$ est fixée. Ses éléments seront appelés **pièces**. Enfin on notera $a \to -a$ l'anti-isomorphisme de $A$ sur la chaîne opposée $-A = \{-a_n < \dots < -a_2 < -a_1\}$.
La transposition et la symétrie par rapport à l'origine permettent d'associer à chaque application $\varphi : F \to A$ trois autres applications $\varphi^T : F^T \to A$, $\bar{\varphi} : -F \to -A$ et $\overline{\varphi^T} = \varphi^{-T} : -F^T \to -A$ en posant

$$ (5) \qquad p^{T} \varphi^{T} = p\varphi; \ (-p)\bar{\varphi} = -(p\varphi) \quad \text{et} \quad (-p)^{T} \varphi^{-T} = -(p\bar{\varphi}) $$

pour chaque point $p$ de $F$.

Il est clair que ces opérations sont des involutions sur $\mathfrak{m}$ et que si $\varphi$ principal (c'est-à-dire si son domaine est principal) il en est de même de son transposé $\varphi^T$.

**DEFINITION.** Etant donnée une bijection $\varphi : F \to A$ la relation d'ordre $C_{\varphi}$ sur $A$ est définie par la condition que pour toute paire de pièces $a, b$ de $A$ on ait :

$$ (6) \qquad (a, b) \in C_{\varphi} \text{ ssi } a \leq b \text{ et } (a\varphi^{-1}, b\varphi^{-1}) \in C. $$

On définit de même $\bar{C}_{\varphi}$ en remplaçant $C$ par l'ordre opposé $\bar{C}$.

En raison de son importance pour la suite nous isolons la remarque suivante :

**1.1.** On a $\bar{C}_{\varphi} = C_{\varphi^T}$ et la bijection $a \to -a$ de $A$ sur $-A$ établit un anti-isomorphisme entre les ordres $C_{\varphi}$ sur $A$ et $C_{\bar{\varphi}}$ sur $-A$.

**Preuve.** L'isomorphisme entre $\bar{C}_{\varphi}$ et $C_{\varphi^T}$ résulte de ce que $(p, q) \in \bar{C}$ équivaut à $(q^T, p^T) \in C$. L'anti-isomorphisme entre $C_{\varphi}$ et $\bar{C}_{\bar{\varphi}}$ de ce que si $a\varphi^{-1} = p$, $b\varphi^{-1} = q$ la double condition $a \leq b$, $(p, q) \in C$ équivaut à $-b \leq -a$, $(-q, -p) \in C$.

Q.E.D.
L'exemple suivant peut aider le lecteur à visualiser ces notations. (Conformément à l'usage courant dans le reste des mathématiques les coordonnées X (resp. Y) vont en croissant de gauche à droite (resp. de bas en haut)). La bijection $\varphi$ n'est pas un morphisme (à cause de la paire (3, 2)) et son domaine n'est pas un intervalle.

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

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

On a :

$$C_{\varphi} = \{(1, 2), (1, 3), (1, 4), (3, 4)\};$$

$$\bar{C}_{\varphi} = C_{\varphi}^{\top} = \{(1, 5), (2, 3), (2, 5), (3, 5), (4, 5)\};$$

$$C_{\bar{\varphi}} = \{(-2, -1), (3, -1), (-4, -1), (-4, -3)\};$$

$$C_{\bar{\varphi}}^{\top} = \{(-5, -1), (-3, -2), (-5, -3), (-5, -4)\}.$$

Par contre la bijection

$$\psi = \begin{pmatrix} 2 & 5 & \cdot & \cdot \\ \cdot & 1 & 4 & \cdot \\ \cdot & \cdot & \cdot & 3 \end{pmatrix}$$

est un *morphisme* dont le domaine est un intervalle qui, d'ailleurs, admet la C-partition $(F_1, F_2)$ où $F_1$ a la forme $\cdot \cdot \cdot$ et où $F_2$ est réduit au point portant la pièce 3. On a

$$C_{\psi} = \{(1, 3), (1, 4), (2, 3), (2, 4), (2, 5)\}.$$
**Produit.** Deux applications $\psi: F \to A$ et $\psi': F' \to A$ ne diffèrent que par une
**translation** ssi leurs domaines $F$ et $F'$ ont le même nombre de points et si il
existe $(u, v) \in Z \times Z$ tel que $(x+u, y+v)\psi' = (x, y)\psi$ pour chaque point $(x, y)$ de
$F$.

Considérons maintenant une suite $(\varphi_1, \dots, \varphi_r)$ de morphismes
$\varphi_i \in \mathfrak{M}_{A_i}(F_i)$. Nous écrirons $\varphi_1\varphi_2 \dots \varphi_r = 0$ pour les $A_i$ ne forment pas une
partition de leur union $B$. Dans le cas contraire nous dirons qu'une application
$F \to B$ est un **produit** des $\varphi_i$ (et nous écrirons $\varphi \in \varphi_1\varphi_2 \dots \varphi_r$) ssi $F$ admet
une C-partition $(F'_1, \dots, F'_r)$ telle que chaque restriction $\varphi'_i = \varphi|_{F'_i}$ ne diffère
de $\varphi_i$ que par une translation $(i = 1, 2, \dots, r)$.

Pour illustrer ceci considérons par exemple les trois morphismes principaux $\varphi_1 = \begin{smallmatrix} 3 \\ 1 \end{smallmatrix}; \varphi_2 = 5; \varphi_3 = 34$. Un produit $\varphi \in \varphi_1\varphi_2\varphi_3$ serait par exemple :

$$ \begin{array}{l@{\qquad}l} \varphi = \begin{smallmatrix} 3 & \cdot & \cdot & \cdot \\ 1 & \cdot & \cdot & \cdot \\ \cdot & \cdot & 5 & \cdot \\ \cdot & \cdot & \cdot & 34 \end{smallmatrix} & \text{ou aussi bien } \varphi' = \begin{smallmatrix} 3 & \cdot & \cdot & \cdot \\ 1 & \cdot & \cdot & \cdot \\ \cdot & \cdot & 5 & \cdot \\ \cdot & \cdot & \cdot & 34 \end{smallmatrix} \\ \text{Soit } F \text{ le domaine d'un produit } \varphi \in \varphi_1 \dots \varphi_r, \text{ où chaque } \varphi_i \text{ appartient} \\ \text{à } \mathfrak{M}. \text{ Par hypothèse } F \text{ est un intervalle, } \varphi \text{ est bijectif et enfin } \varphi \text{ est un mor-} \\ \text{phisme puisque deux points de } F \text{ sont incomparables pour l'ordre naturel quand} \\ \text{ils appartiennent à deux composantes distinctes. Donc } \varphi \in \mathfrak{M}. \end{array} $$

Posant $0\psi = \psi0 = 00 = 0$, $(\psi \in \mathfrak{M})$ il en résulte immédiatement que la notion de produit que nous venons de définir munit $\mathfrak{M} \cup \{0\}$ d'une structure de semi-groupe. De fait, c'est même une structure de monoïde puisque $\mathfrak{M}$ contient le morphisme de domaine vide (à ne pas confondre avec le zéro $0$) qui est élément neutre du produit.
Il est clair que les relations $\varphi \in \varphi_1\varphi_2 ; \varphi^T \in \varphi_2^T\varphi_1^T ; \bar{\varphi} \in \bar{\varphi_2}\bar{\varphi_1}$ ;
$-\varphi^T \in \varphi_1^-\varphi_2$ sont identiquement équivalentes. Nous soulignons la remarque suivante :

1.2. **Soit $\varphi \in \varphi_1 \cdots \varphi_r$ un produit. L'ordre $C_\varphi$ ne dépend que de la suite $(C_{\varphi_1}, \cdots, C_{\varphi_r})$.**

**Preuve.** Comme chaque point du domaine de $\varphi_i$ est en relation $C$ avec tous les points de celui de $\varphi_j$ pour $i < j$, le graphe $C_\varphi$ est l'union des graphes $C_{\varphi_i}$ et des paires $(a_i, a_j)$ où $a_i$ (resp. $a_j$) appartient à l'image de $\varphi_i$ (resp. de $\varphi_j$) et $i < j$ $(i, j = 1, 2, \dots, r)$.

Q.E.D.

**Permutations.** Une bijection $\sigma$ d'image $A$ sera dite une **permutation** de $A$ ($\sigma \in S_A^1$) ssi son domaine est constitué des points $(n+1-i, i)$ ($1 \le i \le n = \text{Card } A$), ce qui entraîne qu'il soit un intervalle et que $\sigma \in \mathcal{M}$; nous la représenterons le plus souvent par la suite $(1\sigma) (2\sigma) \cdots (n\sigma)$ des pièces de $A$ lues dans l'ordre $C$.

L'énoncé suivant sera utilisé plusieurs fois par la suite.

1.3. **A chaque morphisme bijectif $\varphi$ d'image $A$ correspond une et une seule permutation $\sigma = \sigma(\varphi)$ telle que $C_\sigma = C_\varphi$. Une condition suffisante pour qu'un autre morphisme bijectif $\psi$ de même image $A$ satisfasse $C_\varphi = C_\psi$ est que chaque pièce de $A$ se trouve dans la même ligne dans $\varphi$ et dans $\psi$.$$

**Preuve.** Nous définissons un ordre total $C^L$ contenant l'ordre croisé $C$ par l'identité

$$((x, y), (x', y')) \in C^L \quad \text{ssi} \quad (x \le x' \text{ et } y = y') \text{ ou } (y > y')$$
et à chaque morphisme bijectif $\circ$ d'image A nous associons l'ordre $C_{\phi}^{L}$ contenant $C_{\phi}$ par la condition que $(a, b) \in C_{\phi}^{L}$ ssi $a \le b$ et $(a\phi^{-1}, b\phi^{-1}) \in C^{L}$.

Puisque $C^{L}$ est un ordre total il correspond à $\phi$ une et une seule permutation $\sigma = \sigma(\phi)$ de $S_{A}^{1}$ pour laquelle $C_{\phi}^{L} = C_{\sigma}^{L}$, à savoir celle représentée par la suite $s_{k}s_{k-1}\cdots s_{1}$ où chaque $s_{i}$ est la suite des pièces (lues dans l'ordre naturel) sur la ligne $y_{i}$ de $\phi$ et où $y_{k} > y_{k-1} > \cdots > y_{1}$. Par conséquent $\sigma(\phi) = \sigma(\psi)$ dans les conditions de l'énoncé. De plus $C_{\sigma}^{L} = C_{\phi}^{L}$ puisque les deux ordres $C^{L}$ et $C$ coincident sur le domaine de toute permutation.

Supposons $(a, b) \in C_{\phi}^{L} \setminus C_{\phi}$. On a $a \le b$ et les points $p = (x, y) = a\phi^{-1}$ et $p' = (x', y') = b\phi^{-1}$ sont tels que d'une part $x \le x'$ et $y = y'$ ou $y > y'$ et d'autre part on n'ait pas $x \le y'$. On a donc $x \ge x'$ et $y \ge y'$, c'est-à-dire $b\phi = (x', y') \le a\phi = (x, y)$ ce qui montre que $\phi$ n'est pas un morphisme.

Par conséquent sous l'hypothèse contraire, on a $C_{\phi} = C_{\phi}^{L}$ (puisque $C_{\phi} \subset C_{\phi}^{L}$ par construction) ce qui achève la preuve.

Q.E.D.

Pour des raisons évidentes on peut appeler *connexe* toute partie du plan qui n'admet pas de C-partition non triviale. Nous laissons au lecteur de vérifier l'observation (que nous n'utiliserons pas) qu'à chaque morphisme $\phi \in \mathcal{M}$ correspond un morphisme $\psi$ de $\mathcal{M}$, unique à une translation prise dans le plan, dont le domaine est connexe et pour lequel $C_{\phi} = C_{\psi}$ et $C_{\phi}^{T} = C_{\psi}^{T}$.
## 2. Les Glissements.

Disons qu'une partie $F$ et un point $p$ du plan sont **quasi-intervalle** et un **complément** de celui-ci si $F \cup p$ est un intervalle et $p \notin F$, ce qui n'exclut pas la possibilité que $F$ soit déjà lui-même un intervalle.

Soient maintenant $\varphi \in \mathcal{M}$ un morphisme bijectif sur $A$ dont le domaine est l'intervalle $F$ et $p = (x, y)$ un complément de $F$ tel que $F$ contienne au moins un des deux points $p^X = (x+1, y)$, $p^Y = (x, y+1)$. Nous construisons une suite $(\varphi_1, \rho_0) = (\varphi, p), \dots, (\varphi_k, \rho_k)$ de paires dans lesquelles chaque $\varphi_i$ est une bijection sur $A$ dont le domaine $F_i$ est un quasi-intervalle de complément $\rho_i$ par les trois conditions suivantes :

$$ (1) \quad k \text{ est le premier indice pour lequel } F_i \cap \{p_i^X, p_i^Y\} = \emptyset; $$

$$ (2) \quad F_{i+1} = (F_i \setminus p_{i+1}) \cup p_i \quad \text{où } p_{i+1} \in \{p_i^X, p_i^Y\} \text{ est défini par la condition que} \\ p_{i+1} \varphi_i = \text{Min} \{p_i^X \varphi_i, p_i^Y \varphi_i\}; $$

$$ (3) \quad p_i \varphi_{i+1} = p_{i+1} \varphi_i \text{ et } p' \varphi_{i+1} = p' \varphi_i \text{ pour tous les autres points } p'. $$

Autrement dit, $\varphi_{i+1}$ se déduit de $\varphi_i$ en amenant au point $p_i$ la plus petite des pièces $p_i^X \varphi_i$ et $p_i^Y \varphi_i$ si $F_i$ contient les deux points $p_i^X$ et $p_i^Y$ et sinon la seule de ces pièces qui existe. Comme les points $p_i$ forment une suite strictement croissante, le processus s'arrête puisqu'il finit par donner un point $\rho_k$ qui se trouve être un point maximal du domaine $F_k$.

Nous poserons $\varphi_k = \varphi_{\Gamma_p}$ (ou pour préciser s'il le faut $(\varphi_k, \rho_k) = (\varphi_{\Gamma_p})$) et nous appelerons $\varphi_k$ le **glissement de $\varphi$ de sommet** $p$.

L'exemple suivant où $k=3$, $q=p_k$ illustre cette construction :
$p_{i-1}$ par la condition duale que $p_{i-1} \varphi_i = \max \{p_i^{-X} \varphi_i, p_i^{-Y} \varphi_i\}$, ce qui est clair car si $p_{i-1} = p_i^{-X} = (x-1, y)$ (resp. $p_i^{-Y}$) on a $p_{i-1} \varphi_i = p_i \varphi_{i-1} \ge (x, y-1)\varphi_{i-1}$ (resp. $\ge p_i^{-X} \varphi_{i-1}$) puisque $\varphi_{i-1}$ est un morphisme.

(5) Comme $\varphi | B \in \mathcal{M}$ ceci résulte immédiatement du caractère local de la construction.

Q.E.D.

D'après (4), la paire finale $(\psi, q) := (\varphi_k, p_k)$ détermine de façon unique la paire initiale $(\varphi, p)$ que nous appelerons le *glissement inverse* $\varphi = \psi \bar{\Gamma}_q$ de sommet $q$ de $\psi$. Les glissements et les glissements inverses constituent donc une famille de bijections sur l'ensemble $\mathcal{M}_A$, contenant l'inverse de chacun de ses membres [15]. La semi-orbite $\varphi^{\Gamma_*}$ d'un morphisme $\varphi$ sera le plus petit ensemble fermé par glissement qui le contienne ; son *orbite* sera la plus petite union de semi-orbites fermée par glissements inverses qui contienne $\varphi^{\Gamma_*}$.

Disons pour abréger que $\varphi$ est un *morphisme principal* de point minimum $(x, y)$ ssi son domaine est un intervalle principal ayant cette propriété (cf. introduction).

## 2.2. *Chaque semi-orbite $\varphi^{\Gamma_*}$ contient un morphisme principal de point minimum* $(x, y)$ *pour tous* $x, y \in Z$ *assez petits*.

**Preuve.** Soient $F$ le domaine de $\varphi$ et $\tilde{F}$ le plus petit intervalle principal contenant $F$. Si $F$ lui-même n'est pas principal, $\tilde{F} \setminus F$ contient au moins un point maximal. On vérifie facilement que $p \cup F$ est un intervalle et que si $G$ est le domaine du glissement $\varphi^{\Gamma_p}$, l'ensemble $\tilde{G} \setminus G$ est contenu dans $F \setminus (F \cup p)$. Donc, par induction sur Card $\tilde{F} \setminus F$, la semi-orbite de $\varphi$ contient un morphisme principal $\psi$ dont le point minimum $(x, y)$ est contenu dans $\tilde{F}$.

Pour achever la preuve il suffit de montrer que la semi-orbite de $\psi$
contient des morphismes principaux de point minimum (x-1, y) et (x, y-1). En raison de la symétrie par rapport à la transposition, il suffit de vérifier ceci pour (x-1, y). Soit H le domaine de $\psi$. Il contient un point maximum de la forme (x, y) avec $y' \ge y$. L'union de H et du point $p' = (x-1, y')$ est un intervalle. Appliquant la construction précédente au glissement $\psi - \phi_{p'}^t$, on obtient un morphisme principal de point minimum (x-1, y) appartenant à la semi-orbite de $\psi'$, donc de $\phi$.

Q.E.D.

Soient $a < b < c$ trois pièces. Le glissement de sommet (1, 1) fait passer du morphisme $\varphi_1 = \begin{smallmatrix} b & c \\ & a \end{smallmatrix}$ au morphisme $\varphi_1 K = \begin{smallmatrix} b & c \\ & a \end{smallmatrix}$ et du morphisme $\varphi_2 = \begin{smallmatrix} a & c \\ & b \end{smallmatrix}$ au morphisme $\varphi_2 K = \begin{smallmatrix} c & \\ & a \end{smallmatrix}$. Nous appellerons $\varphi_1$ et $\varphi_2$ **tableaux élémentaires** et l'opération $\varphi_i \to \varphi_i K$ **transformation** (élémentaire) de Knuth. Cet auteur a montré que ces transformations et leurs inverses engendrent pour l'essentiel toutes les opérations entre tableaux qui nous intéressent. Nous nous proposons de donner une forme un peu plus stricte de ce résultat (en évitant les inverses). Plus précisément, nous appellerons **semi-orbite de Knuth** $\chi K^*$ d'un morphisme $\chi$ le plus petit ensemble de morphismes $X$ contenant $\chi$ qui satisfasse les deux conditions suivantes :

$$ (1) \quad \varphi \in X, C_{\varphi} = C_4 = \{ \psi \in X \}; $$

$$ (2) \quad \text{Si } \varphi \in X \text{ est un produit de la forme } \varphi'\varphi_i\varphi'' \text{ où } \varphi_i \text{ est un des deux morphismes } \varphi_1 \text{ ou } \varphi_2 \text{ ci-dessus on a } \varphi'(\varphi_i K)\varphi'' \in X. $$

Rappelons la notation $\sigma(\varphi)$ pour désigner la permutation associée à un morphisme $\varphi$ ainsi qu'il a été expliqué dans l'énoncé 1.3. La permutation $\sigma(\varphi_1)$ (resp. $\sigma(\varphi_2)$) est bca (resp. acb) et $\sigma(\varphi_1 K) = bac$ (resp. $\sigma(\varphi_2 K) = cab$).

Il est immédiat que la semi-orbite $\chi K^*$ est caractérisée par la condition que $\varphi \in \chi K^*$ implique $\psi \in \chi K^*$ quand il existe deux permutations $\sigma'$ et $\sigma''$ et
trois pièces. $a < b < c$ telles que

$$ (3) \quad \text{Soit } \sigma(\varphi) = \sigma'\text{bca}\sigma'' \text{ et } \sigma(\psi) = \sigma'\text{bac}\sigma''; $$

$$ \text{Soit } \sigma(\varphi) = \sigma'\text{acb}\sigma'' \text{ et } \sigma(\psi) = \sigma'\text{cab}\sigma'' . $$

D'après la définition de $\chi K^*$ chaque morphisme de cet semi-orbite peut être obtenu par une suite de glissements à partir de $\chi$. Il est un peu plus difficile de vérifier le théorème de Knuth qui affirme la réciproque de cette propriété. Nous commençons par examiner en détail le cas où $\chi$ est un produit $(\lambda)(b)$ où $\lambda$ est un morphisme dont le domaine est une ligne $\lambda = b_1b_2\dots b_m$ ($b_1, \dots, b_m \in A$) et où $b$ est une pièce unique.

Si $b_m < b$ le morphisme $\varphi$ formé de la ligne $b_1 \dots b_m b$ peut être obtenu par glissement à partir de $\chi$ et il appartient à $\chi K^*$ puisque $\varphi$ et $\chi$ correspondent à la même permutation $b_1 \dots b_m b$.

Supposons donc $b_m > b$. Soit $b_r$ la plus petite des pièces de l'image de $\lambda$ qui soit plus grande que $b$.

**2.3.** *Le produit* $\varphi = (b_r)(\lambda')$ où $\lambda'$ est le morphisme obtenu en remplacant $b_r$ par $b$ dans $\lambda$ appartient à $\chi K^*$ et peut être obtenu par glissements à partir de $\chi$.*

**Preuve.** On peut supposer que dans $\chi$ chaque $b_i$ se trouve au point $(i, 1)$ $(1 \le i \le m)$ et $b$ au point $(m+1, 0)$. On passe par glissement au morphisme $\varphi_m$ qui ne diffère de $\chi$ que par le fait que $b$ se trouve au point $(m, 0)$. Définissons $\varphi_i = \varphi_{i+1} \Gamma_{(i, 1)}$ $(i = m-1, \dots, 1)$. Chaque glissement $\varphi_{i+1} \to \varphi_i$ consiste quand $i > r$ (resp. $i \le r$) à déplacer $b$ (resp. $b_r$) d'un pas vers la gauche et à abaisser la pièce $b_{i+1}$ (resp. $b_i$). Chacun d'eux est une opération K ce qui établit le résultat puisque $\varphi_1 = \varphi$ a bien la forme indiquée.

Q.E.D.
EXEMPLE. Soient $\lambda = 12356$ ; $b=4$. On a $b_r = 5$ et

$$ \varphi_5 = \begin{matrix} 1 & 2 & 3 & 5 & 6 \\ \cdot & \cdot & \cdot & \cdot & 4 \end{matrix}; \quad \varphi_4 = \begin{matrix} 1 & 2 & 3 & 5 & \cdot \\ \cdot & \cdot & \cdot & 4 & 6 \end{matrix}; \quad \varphi_3 = \begin{matrix} 1 & 2 & 5 & \cdot & \cdot \\ \cdot & \cdot & 3 & 4 & 6 \end{matrix}; $$

$$ \varphi_2 = \begin{matrix} 1 & 5 & \cdot & \cdot & \cdot \\ 1 & 2 & 3 & 4 & 6 \end{matrix}; \quad \varphi_1 = \begin{matrix} 5 & \cdot & \cdot & \cdot & \cdot \\ 1 & 2 & 3 & 4 & 6 \end{matrix}. $$

Nous considérons maintenant un cas plus compliqué. Soient $\varphi_i$ et $\varphi_{i+1}$ deux des morphismes consécutifs construits dans un glissement et supposons que l'un se trouve dans le cas où $\varphi_{i+1}$ diffère de $\varphi_i$ par le déplacement de la pièce c du point (x, y) au point adjacent en dessous (x, y-1). On peut représenter la ligne y de $\varphi_i$ par un produit $s_3cs_4$ où $s_3$ et $s_4$ sont des suites croissantes de pièces ; de la même manière la ligne y-1 de $\varphi_{i+1}$ peut être notée $s_1cs_2$. Par hypothèse, les longueurs de ces suites satisfont $|s_1| \le |s_3|$ ; $|s_2| \ge |s_4|$. De plus si $s_2 = a_1a_2... a_m$ et $s_4 = b_1... b_p$ où les $a_j, b_j$ sont des pièces, on a par hypothèse $c < a_1$ et $a_i < b_i$ pour $i = 1, 2, ..., p \le m$ ; des relations similaires valent pour $s_1$ et $s_3$. Un exemple avec $c = 6$ est fourni par $s_1 = 13, s_2 = 78, s_3 = 245, s_4 = 9$ ce qui correspond aux lignes y et y-1 de $\varphi_i$ et de $\varphi_{i+1}$ représentées par

$$ \begin{array}{l@{\quad}l@{\quad}l} 2 & 4 & 5 \\ \cdot & 1 & 3 \end{array} \begin{array}{c} 6 \\ \times \\ 7 & 8 \end{array} \quad \text{et} \quad \begin{array}{l} 2 \\ 4 \\ 5 \\ \cdot \\ 1 & 3 & 6 & 7 & 8 \end{array} \begin{array}{c} 9 \\ \times \\ 8 \end{array} $$

2.3. bis On a $\psi \in \varphi K^*$ où $\varphi$ est le produit des deux lignes $s_3cs_4$ et $s_1s_2$, et $\psi$ celui des deux lignes $s_3s_4$ et $s_1cs_2$.

**Preuve.** Par induction sur le nombre des pièces, le cas initial étant trivial. Si $|s_3| > |s_1|$ on peut écrire $s_3 = s_3's''_3$ où $|s_3''| = |s_1|$ et l'on a que $\varphi$ et $\psi$ sont le produit de $s_3'$ par $\varphi'$ et par $\psi'$ obtenus en remplaçant $s_3$ par $s_3''$. Le résultat découle alors de l'hypothèse d'induction sauf si $|s_3'| = 0$, c'est-à-dire auf si $|s_1| = |s_3|$ comme nous le supposons désormais. On distingue deux cas :
$$ (1) \qquad |s_1| = |s_3| = 0 $$

Soient $s_2 = a_1 \dots a_m$ et $s_4 = b_1 \dots b_p$ comme ci-dessus. On peut considérer $\varphi$ comme le produit de $c_{s_4}$ par les singolets $a_1, a_2, \dots, a_m$, ce que nous écrirons

$$ \varphi = (c_{s_n})(a_1)(a_2)\dots(a_m). $$

D'après $c < a_1 < b_1$ et 2.3, on a que la semi-orbite de Knuth du produit $(c_{s_n})(a_1)$ contient le morphisme $\varphi_1 = ca_1b_2 \cdots b_p$. Donc $\varphi_1 \in \varphi K^*$ où

$$ \varphi_1 = (b_1)(ca_1b_2 \cdots b_p)(a_2) \cdots (a_m). $$

On obtient de même $\varphi_2 \in \varphi_1 K^* \subset \varphi K^*$ où :

$$ \varphi_2 = (b_1)(b_2)(ca_1a_2b_3 \cdots b_p)(a_3) \cdots (a_m) $$

et où on peut aussi bien écrire $(b_1b_2)$ que $(b_1)(b_2)$. Répétant la même opération on obtient enfin que $\varphi_m \in \varphi K^*$ où :

$$ \varphi_m = (b_1 \cdots b_m)(c_1a_1 \cdots a_m b_{m+1} \cdots a_p) = \psi. $$

Ce qui achève la vérification dans ce cas.

$$ (2) \qquad |s_1| = |s_3| \ge 1 $$

On peut poser $s_1 = s'_1$ et $s_3 = b s'_3$ où $a < b$ sont deux pièces. Considérant $\varphi$ comme le produit $(b s'_3 c_{s_n})(a)(s'_1 s_2)$ et appliquant 2.3 aux deux premiers facteurs, on trouve que $\varphi K^*$ contient le produit $(b)(a s'_3 c_{s_4})(s'_1 s_2)$. Donc, appliquant l'hypothèse d'induction aux deux derniers facteurs de ce produit, on obtient que $\varphi K^*$ contient le produit $(b)(a s'_3 s_4)(s'_1 c_{s_2}) = \varphi'$. Maintenant comme $a$ est la plus petite de toutes les pièces, le morphisme formé par les deux dernières lignes de $\varphi'$ a la forme $(\overline{c s_3})_{n-2}$ avec $\overline{c} = a$, $\overline{s_3} = s'_3 s_4$ et $\overline{s_2} = s'_1 c_{s_2}$. On
peut donc lui appliquer la même opération que dans le cas 1 ci-dessus. On obtient que le produit de $b, \bar{s}_3$ et $\overline{cs}_2$ est dans $\phi K^*$, donc dans $\phi K^*$, c'est-à-dire que l'on a :

$$ \phi'' = (b)(s'_3 s_4)(a s'_1 c s_2) \in \phi K^* . $$

Ceci conclut la preuve car comme $b$ est plus petit que toutes les pièces de $s'_3 s_4$, la permutation de $\phi''$ est la même que celle du produit des deux lignes $(b s'_3 s_n)(a s'_1 c s_2) = (s_3 s_4)(s_1 c s_2) = \psi$.

Q.E.D.

**THEOREME 2.4 (D. E. Knuth [8])**. *Chaque semi-orbite de glissement est une semi-orbite de Knuth.*

*Preuve.* D'après nos définitions, il suffit de montrer que $\chi' \in \chi K^*$ quand $\chi'$ est obtenu par un seul glissement à partir du morphisme $\chi$.

Considérons la suite $\chi_1 = \chi, \chi_2, \dots, \chi_h = \chi'$ des morphismes construits pour définir ce glissement. Il suffit d'établir $\chi_{i+1} \in \chi_i K^*$ pour tout $i$. La per-mutation $\sigma(\chi_i)$ est la même que la permutation associée au produit des lignes de $\chi_i$. Donc si $\chi_{i+1}$ ne diffère de $\chi_i$ que par le déplacement de la pièce c du point $(x, y)$ au point $(x-1, y)$, on a $\sigma(\chi_i) = \sigma(\chi_{i+1})$ et le résultat est établi pour cette paire. Si au contraire $\chi_{i+1}$ est obtenu en faisant passer c de $(x, y)$ en $(x, y-1)$, on peut se borner à considérer le produit des lignes y et $y-1$ de $\chi_i$ et $\chi_{i+1}$ et le résultat découle de l'énoncé 2.3 bis.

Q.E.D.
### 3. Le théorème de C. Green.

Etant donnés $k \ge 1$ et $\varphi \in \mathfrak{M}_A$, soit $\mathcal{E}(\varphi; k)$ l'ensemble des parties de $A$ qui sont unions de $k$ $C_\varphi$-chaînes et, comme indiqué dans l'introduction :

$$L_j(\varphi, k) = \max \{\text{Card } E : E \in \mathcal{E}(\varphi|A_j; k)\}$$

où $A_j$ est l'intervalle initial de $A$ obtenu en lui enlevant ses $j$ plus grandes pièces ($j \ge 0$) (et où, par conséquent, $A_0 = A$ ; $A_m = \emptyset$ pour $m \ge \text{Card } A$). Par exemple, si $\varphi = 1 \ 4 \ \cdot \ \cdot \ \cdot \ 3 \ 6 \ 7$ , le graphe de $C_\varphi$ est représenté par

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

et la partie significative de la fonction $L(\varphi)$ est fournie par la Table :

$$ \begin{array}{l@{\hspace{2em}}c} j = & 0 \ 1 \ 2 \ 3 \ 4 \ 5 \ 6 \ 7 \ \cdot \ \cdot \ \cdot \\ k = 1 & 4 \ 3 \ 2 \ 2 \ 2 \ 1 \ 1 \ 0 \ \cdot \ \cdot \ \cdot \\ k = 2 & 6 \ 5 \ 4 \ 4 \ 3 \ 2 \ 1 \ 0 \ \cdot \ \cdot \ \cdot \\ k = 3 & 7 \ 6 \ 5 \ 4 \ 3 \ 2 \ 1 \ 0 \ \cdot \ \cdot \ \cdot \\ \dots & \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \ \cdot \end{array} $$

**THEOREME 3.1** (C. Green [ ]). On a $L(\varphi) = L(\psi)$ pour chaque $\psi$ de l'orbite de $\varphi$.

**Preuve.** Puisque les orbites sont définies par itération de glissements et de glissements inverses il suffit de considérer le cas où $\psi$ est un glissement de $\varphi$. D'après 2.1. (5) on a alors que chaque $\psi|A_j$ est égal à un glissement de $\varphi|A_j$ ou à $\varphi|A_j$ lui-même. Par conséquent, il suffit d'établir $L_0(\varphi) = L_0(\psi)$ ce qui a
été démontré par C. Green dont nous reproduisons le raisonnement pour la com-
modité du lecteur.

D'après le théorème 2.4. de D. E. Knuth et le fait que $\mathcal{E}(\varphi; k)$ ne dépend
que de l'ordre $C_{\varphi}$, on peut se limiter au cas où $\varphi$ et $\psi$ sont respectivement des
produits de la forme $\varphi_1\varphi_2\varphi_3$ et $\varphi_1(\varphi_2 K)\varphi_3$ ainsi qu'on l'a dit pour définir $K^*$.

Supposons d'abord $\varphi_2 = \begin{smallmatrix} a & c \\ b & \end{smallmatrix}$ et $\varphi_2 K = \begin{smallmatrix} c \\ a & b \end{smallmatrix}$ où, on le rappelle, $a < b < c$. On a $C_{\psi} \subset C_{\varphi}$ et $C_{\varphi} \setminus C_{\psi} = \{(a, c)\}$. Par conséquent, pour chaque $k \ge 1$, l'ensemble $\mathcal{E}(\psi, k)$ est contenu dans $\mathcal{E}(\varphi, k)$ (d'où $L_0(\psi; k) \le L_0(\varphi; k)$) et la partie E ne peut appartenir au second mais non au premier que si elle contient une chaîne de la forme sacs¹. Si b n'appartient pas à une autre chaîne de E, le fait que $a < b < c$ entraîne que sabs¹ soit une $C_{\psi}$-chaîne, donc que $E' = (E \setminus \text{sacs}^1) \cup \text{sabs}^1$ soit une union de k $C_{\psi}$-chaîne disjointes. Si au contraire E contient une chaîne tbt¹, on voit de même que sabt¹ et tcs¹ sont deux $C_{\psi}$-chaîne. Donc $E' = (E \setminus \text{sacs}^1, \text{tbt}^1) \cup \text{sabt}^1, \text{tcs}^1$ appartient à $\mathcal{E}(\psi; k)$. Dans les deux hypothèses Card E = Card E' et l'on a donc vérifié $L_0(\psi) = L_0(\varphi)$, dans le premier cas de Knuth.

Le second cas où $\varphi_2 = \begin{smallmatrix} b & c \\ a & \end{smallmatrix}$ et $\varphi_2 K = \begin{smallmatrix} b \\ a & c \end{smallmatrix}$ est traité de façon symétrique puisque l'on a alors $C_{\varphi} \subset C_{\psi} \setminus C_{\varphi} = \{a, c\}$. Le résultat est donc prouvé dans tous les cas.

Q.E.D.

Par exemple, faisant subir au morphisme $\varphi$ ci-dessus le glissement de
sommet (1, 1) on obtient

$$
\begin{array}{c}
\psi = 5 \\
2 \ 4 \\
1 \ 3 \ 6 \ 7
\end{array}
$$
pour lequel

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

Le lecteur pourra vérifier l'invariance de la fonction L associée.

On observera qu'un résultat légèrement plus fort a été établi, à savoir que si $\psi$ appartient à la semi-orbite de $\varphi$, il correspond à chaque $E \in \mathcal{E}(\varphi, k)$ un $E' \in \mathcal{E}(\psi, k)$ ayant la propriété qu'il existe une bijection $a \to a'$ de $E$ sur $E'$ telle que $a' \le a$, identiquement. J'ignore si cette propriété suffit pour caractériser les morphismes de l'orbite de $\varphi$ qui appartiennent à sa semi-orbite. Elle montre en tout cas que $a \xrightarrow{c} b$ n'appartient pas à la semi-orbite de $a \xrightarrow{c} b$ ($a < b < c$), ce qui présente un certain intérêt en raison du fait (établi plus bas) que ceci reste vrai pour tout morphisme contenant ces configurations.

Dans la suite de ce travail nous désignerons par $\mathcal{L} = \bigcup_{0 \le n} \mathcal{L}_n$ la famille des fonctions $L(\varphi)$ ($\varphi \in \mathcal{M}$), $\mathcal{L}_n$ étant la sous-famille de celles qui, de façon équivalente, satisfont $L_0(k) = n$ pour tout $k \ge n$ ou $L_j(k) = 0$ pour tout $j \ge n$, $k \in \mathbb{N}$, c'est-à-dire qui correspondent à des morphismes dont le domaine a n points.

Introduisons la notation $\rho_A$ pour désigner les morphismes de $\mathcal{M}$ d'image A dont le domaine est un intervalle principal de point minimum (1, 1). Soit $n = \text{Card } A$.

3.2. *A chaque* $L \in \mathcal{L}_n$ *correspond un et un seul morphisme principal* $\psi$ *de* $\rho_A$ *pour lequel* $L = L(\psi)$. *Son domaine est déterminé par* $L_0$ *et la position de la pièce* $\text{Max } A$ *est déterminée par* $L_0$ *et* $L_1$.

**Preuve.** Par hypothèse $L = L(\varphi)$ où $\varphi \in \mathcal{M}_A$. D'après 2.2., la semi-orbite de $\varphi$ contient au moins un morphisme principal $\psi$ et d'après le théorème précédent on
a L(Ψ) = L(φ).

Nous pouvons supposer que $\psi \in \wp_A$ et il ne reste plus qu'à montrer que $\psi$ est déterminé de façon unique par sa fonction $L$. Tout d'abord, puisque $\psi$ est un morphisme, toutes les pièces d'une $C_\psi$-chaîne doivent se trouver dans des colonnes différentes. Donc $L_0(\psi; k)$ est au moins égal à la somme des longueurs de k lignes de $\psi$ ($k \ge 1$). De fait $L_0(\psi; k)$ est exactement égal à la somme des longueurs des k plus longues lignes de $\psi$ puisque chaque ligne est une $C_\psi$-chaîne. Comme par hypothèse le domaine $F$ de $\psi$ a la forme d'un diagramme de Ferrers ceci montre qu'il est entièrement déterminé par la fonction $L_0$.

Soit maintenant $A_1 = A \setminus a$ où $a = \max A$. Le point $p = a_\psi^{-1}$ est un point maximum de $F$. Donc le domaine $F' = F \setminus p$ de $\psi|_{A_1}$ est aussi principal. D'après la première partie de la preuve, il est déterminé par $L_1(\psi) = L_0(\psi|_{A_1})$ et l'on a donc $a_\psi^{-1} = F \setminus F'$, le résultat s'en déduit par induction sur Card A.

Q.E.D.

Par exemple tous les morphismes $\varphi$ dont le domaine est l'intervalle principal $x \times x$ satisfont $x \times x \times x$

$$L_0(\varphi; 1) = 4 ; L_0(\varphi; 2) = 4 + 2 = 6 ; L_0(\varphi; k \ge 3) = 4 + 2 + 1 = 7 .$$

Selon que la pièce Max A se trouve dans la première, deuxième ou troisième ligne, on a

$$L_1(\varphi, 1) = 3 \text{ ou } 4 \text{ ou } 4 ; L_1(\varphi, 2) = 5 \text{ ou } 5 \text{ ou } 6 \text{ et } L(\varphi_1, k \ge 3) = 6 \text{ dans les trois cas.}$$

Notons $\equiv$ l'équivalence sur $\mathfrak{M}$ telle que $\varphi \equiv \psi$ ssi $L(\varphi) = L(\psi)$ et si ces deux morphismes ont même image. Le corollaire suivant résume les propriétés
dont nous aurons besoin. Nous faisons référence à l'introduction pour la définition des involutions $\varphi \to \varphi^T$ et $\varphi \to \bar{\varphi}$.

### 3.3. Les classes de l'équivalence ≡ sont les orbites. Supposant $\varphi \equiv \psi$ on a :

(1) $\varphi$ et $\psi$ ne diffèrent que par une translation si leurs domaines sont principaux ;

(2) $\varphi^T \equiv \psi^T$ ; $\bar{\varphi}$ et $\varphi$|$B \equiv \psi$|$B$ pour tout intervalle $B$ de leur image ;

(3) $\varphi\varphi' \equiv \psi\psi'$ quels que soient $\varphi'$ et $\psi'$ tels que $\varphi' \equiv \psi'$.

**Preuve.** Le théorème de C. Green montre que $\varphi \equiv \psi$ quand ces deux morphismes appartiennent à la même orbite et 3.2. montre que cette équivalence satisfait (1).

Réciproquement, d'après 2.2. on peut trouver dans les semi-orbites de deux morphismes quelconques $\varphi$ et $\psi$ des morphismes principaux ayant même point minimum de leur domaine. Si de plus $L(\varphi) = L(\psi)$, ces morphismes principaux sont égaux d'après (1) et par conséquent $\varphi$ et $\psi$ sont dans une même orbite.

Les relations (2) découlent directement des assertions (3), (4) et (5) de 2.1. puisque les classes de $\equiv$ sont les orbites.

Pour vérifier (3) nous pouvons supposer que les domaines $F$ et $F'$ de $\varphi$ et de $\varphi'$ forment une C-partition de leur union. Il existe alors des morphismes principaux $\rho \equiv \varphi$ et $\rho' \equiv \varphi'$ dont un produit $\rho\rho'$ est contenu dans la semi-orbite de $\varphi\varphi'$ et satisfait $\rho\rho' \equiv \varphi\varphi'$. Ceci permet de supposer désormais que $\varphi = \rho$, $\varphi' = \rho'$ et que $\psi$ et $\psi'$ eux aussi sont principaux. D'après (1), $\varphi$ et $\psi$ sont égaux à des translations près et il en est de même de $\varphi'$ et $\psi'$. On a donc $C_\varphi = C_{\psi'}$, $C_{\varphi'} = C_{\psi'}$ d'où enfin $C_{\varphi\varphi'} = C_{\psi\psi'}$ d'après 1.2. ce qui implique l'équivalence cherchée.

Q.E.D.
Rappelons la notation $\mathfrak{P}$ pour désigner la sous-famille des morphismes principaux de $\mathfrak{M}$ dont $(1, 1)$ est le point minimum de domaine. L'énoncé précédent justifie la

**DEFINITION.** La *correspondance de Robinson* est la projection $\mathcal{R}$ de $\mathfrak{M}$ sur $\mathfrak{P}$ envoyant chaque morphisme sur l'unique morphisme de son orbite qui appartienne à $\mathfrak{P}$.

### 3.4. On a les formules :

$$ (1) \quad \varphi^T \mathcal{R} = (\varphi \mathcal{R})^T ; \quad \bar{\varphi} \mathcal{R} = (\overline{\varphi \mathcal{R}}) \mathcal{R} ; \quad (\varphi |_{A'}) \mathcal{R} = \varphi \mathcal{R} |_{A'} \text{ pour chaque intervalle initial } A' \text{ de l'image de } \varphi ; $$

$$ (2) \quad (\varphi\psi)\mathcal{R} = (\varphi\mathcal{R}.\psi\mathcal{R})\mathcal{R} \text{ où le domaine de } (\varphi\psi)\mathcal{R} \text{ contient celui de } \varphi\mathcal{R} \text{ et de } \psi\mathcal{R}. $$

**Preuve.** Par définition les relations $\varphi \equiv \psi$ et $\varphi\mathcal{R} = \psi\mathcal{R}$ sont équivalentes. Donc (1) et la première assertion de (2) sont seulement une reformulation de l'énoncé précédent. La seconde assertion de (2) résulte de 3.2. et du fait évident que quelques soient les morphismes $\varphi$ et $\psi$ (d'images disjointes) on a $L_0(\varphi\psi) \ge L_0(\varphi)$, $L_0(\psi)$.

O. E. D.

On observera que le théorème de Green montre directement à travers son corollaire 3.4. que le sous-ensemble $\mathfrak{P}$ de $\mathfrak{M}$ peut être muni d'une structure de monoïde en définissant le produit $\pi$ de deux morphismes $\varphi, \psi$ de $\mathfrak{M}$ par $\pi = (\varphi\psi)\mathcal{R}$ (avec la convention $\mathcal{OR} = \mathcal{O}$). Il serait convenable de nommer ce résultat théorème de Schensted puisque l'associativité de ce produit peut être facilement établie en établissant le cas particulier $((a\varphi)\mathcal{R}b)\mathcal{R} = (a((\varphi b)\mathcal{R}))\mathcal{R}$ ($a, b \in A, \varphi \in \mathfrak{P}$) ce qui a été effectué directement par cet auteur [13].

Nous complétons cette section par quelques remarques.
3.5. **Soient $\varphi, \psi \in \mathfrak{m}_A$. Une condition nécessaire et suffisante pour que $\varphi \equiv \psi$ est que $L_0(\varphi|B_j) = L_0(\psi|B_j)$ pour tous les termes $B_j$ d'une suite strictement décroissante maximale $B_0 = A \supset B_1 \supset \dots \supset B_n = \emptyset$ d'intervalles de $A$**.

**Preuve.** D'après (2) de 3.3. cette condition est nécessaire. Réciproquement, chaque $B_i$ est par hypothèse un intervalle de $B_j$ pour $j \le i$. On peut donc procéder par induction sur $n = \text{Card } A$ et supposer que $\varphi|B_1 \equiv \psi|B_1$. Si $A \setminus B_1 = a$ est la plus grande pièce de $A$, l'énoncé résulte directement de 3.2. Sinon, comme $B_1$ est un intervalle de $A$, la pièce $a$ doit être la plus petite de celui-ci. Toujours d'après 2.3. on peut supposer que $\varphi, \psi, \varphi|B_1$ et $\psi|B_1$ ont des domaines principaux de point minimum (1, 1). Donc $\varphi|B_1 = \psi|B_1$ a pour domaine $F'$ et comme $\varphi = \varphi|B_0$, $\psi = \psi|B_0$, on déduit de $L_0(\varphi|B_0) = L_0(\psi|B_0)$ et de 2.2. que $\varphi$ et $\psi$ ont le même domaine principal $F$. On a évidemment $L_0(\varphi|B) = L_0(\varphi)$ et par conséquent $F \setminus F'$ est un point maximum $p$ de $F$. Par définition, $\varphi|B_1$ est déduit de $\varphi$ en enlevant la pièce $a = \text{Min } A$ du point (1, 1) et en effectuant le glissement de sommet (1, 1'). Comme cette opération est invertible on retrouve $\varphi = \psi$ en appliquant à $\varphi|B_1 = \psi|B_1'$ le glissement inverse de sommet $p$.

Q.E.D.

Une partie substantielle des preuves des résultats des chapitres suivants utilise la transformation envoyant chaque morphisme $\varphi$ de $\mathcal{P}$ (c'est-à-dire tel que $\varphi = \varphi\mathcal{R}$, $\varphi \in \mathfrak{m}_A$) sur le morphisme $\bar{\varphi}\mathcal{R}$ qui appartient évidemment aussi à $\mathcal{P}$. Cette opération change en $-A$ l'image $A$ de $\varphi$ ce qui peut être incommode et pour y remédier nous définirons $\varphi^J$ comme l'image de $\bar{\varphi}\mathcal{R}$ par l'isomorphisme $\Omega$ de la chaîne $-A$ sur la chaîne $A$. Autrement dit $a \mapsto (-a) \Omega (= \bar{a})$ est l'anti-isomorphisme $a \mapsto \bar{a}$ de la chaîne $A$ sur elle-même.

Par exemple si $\varphi = \begin{array}{c@{\;}c@{\;}c} & & 2 \\ & 4 \\ & 3 \\ \hline 5 \end{array}$ on a $\bar{\varphi} = \begin{array}{c@{\;}c@{\;}c} -5 & -3 & -1 \\ & -4 & -2 \end{array}$ et par conséquent
$\varphi^J = \begin{array}{c@{\;}c@{\;}c} 1 & 3 & 5 \\ & 2 & 4 \end{array}$ puisqu'ici $-i\Omega = 6-i$ ($1 \le i \le 5$).
Dans l'énoncé suivant on note $A^{(m)}$ (resp. $A_m$) l'intervalle final (resp. initial) formé des n-m plus grandes (resp. plus petites) pièces de A et on emploie le même symbole $\Omega$ pour désigner l'isomorphisme de $A_m$ sur $A^{(m)}$ ($m = 0, 1, ..., n = \text{Card } A$). En application des formules de 3.4. on a :

### 3.6. L'opération $\varphi \xrightarrow{J} A_m$ est une involution sur chaque $P_A(F)$ qui commute avec la transposition et qui satisfait identiquement les relations

$$ \varphi^J |_{A_m} = (\varphi |_{A^{(m)}} R \Omega)^J \quad \text{équivalentes à} \quad \bar{\varphi} R |_{-A^{(m)}} = (\overline{\varphi |_{A^{(m)}}} R)_{(0 \le m \le n)}. $$

**Preuve.** Soient $\varphi$ un morphisme de $P_A(F)$ et $\psi = \bar{\varphi}R$. On sait (1.1.) que l'involution $a \mapsto -a$ établit un anti-isomorphisme entre l'ordre $C_\varphi$ (sur A) et l'ordre $C_\psi$ (sur -A). Donc $L_0(\varphi) = L_0(\bar{\varphi}) = L_0(\psi)$ et comme le domaine F de $\varphi$ est principal par hypothèse on conclut en vertu de 3.2. que F est aussi le domaine de $\psi$. Donc $\varphi^J$ appartient à $P_A(F)$.

Comme l'application $\chi \mapsto \bar{\chi}$ ($\chi \in \mathfrak{M}$) est une involution sur la famille des orbites et qu'elle commute avec la transposition, on a immédiatement que
$$ \varphi = \bar{\psi}R \text{ d'où } \varphi^{JJ} = \varphi \text{ et que } \bar{\varphi}T_R = \psi^T \text{ d'où } \varphi^J = \varphi^T. $$

Maintenant comme $-A^{(m)}$ est un intervalle initial de l'image $-A$ de $\psi$ et que $\psi = \bar{\psi}R$, on a $\psi|-A^{(m)} \in \rho$, c'est-à-dire que $\psi|-A^{(m)}$ est l'image par $R$ de la restriction à $-A^{(m)}$ d'un morphisme quelconque de l'orbite de $\psi$ (en raison de 3.2.) donc en particulier de $\bar{\varphi}$.

Comme $\bar{\varphi}|-A^{(m)}$ est triviallement égal à $\overline{\varphi|A^{(m)}}$, on a par conséquent $\psi|-A^{(m)} = (\bar{\varphi}|-A^{(m)})R = (\overline{\varphi|A^{(m)}})R$ ce qui est la seconde des identités énoncées. La première s'en déduit facilement en observant que $\varphi^J|_{A_m}$ ne diffère de $\bar{\varphi}R|-A^{(m)}$ que par un isomorphisme entre les images et qu'il en est de même des membres de droites des deux relations de par la définition même de l'isomorphisme.
me Ω.

Q.E.D.

Cet énoncé fournit une justification directe de l'algorithme suivant de calcul de $\varphi^J$ (cf. [9] p. 57-59). Soient $A = \{a_1 < a_2 < \dots < a_n\}$ et $\varphi_0 = \varphi$. Pour chaque $m = 1, \dots, n$, on calcule $\varphi_m$ en enlevant la pièce $a_m$ du point minimum (1, 1) du domaine de $\varphi_{m-1}$ et en effectuant ensuite le glissement de $\varphi_{m-1}$ de sommét (1, 1), ce qui libère un point maximum $q_m$ du domaine de $\varphi_{m-1}$. On pose alors $q_m \varphi^J = \bar{a}_m = a_{n+1-m}$.

Par exemple si $\varphi = \begin{pmatrix} 3 & 4 & \cdot \\ 1 & 2 & 5 \end{pmatrix} = \varphi_0$ on obtient $\varphi^J = \begin{pmatrix} 3 & 4 \\ 1 & 2 & 5 \end{pmatrix}$ à la suite des opérations suivantes :

$\varphi_1 = \begin{pmatrix} 3 & 4 & \cdot \\ 2 & 3 & \ast \end{pmatrix}$ ; $\varphi_2 = \begin{pmatrix} 4 & \ast \\ 3 & 5 \end{pmatrix}$ ; $\varphi_3 = \begin{pmatrix} \ast \\ 4 & 5 \end{pmatrix}$ ; $\varphi_4 = \begin{pmatrix} \cdot \\ 5 & \ast \end{pmatrix}$ .

Le lecteur pourra vérifier que le morphisme $\bar{\varphi_R}$ est (à une translation près) l'unique morphisme de l'orbite de $\varphi$ dont le domaine est co principal (c'est-à-dire possède un point **maximum** unique) ce qui est une autre manière de formuler la dualité $\varphi \to \varphi^J$.

La structure de celle-ci est loin d'être entièrement éclaircie. Ainsi j'ai observé (sans pouvoir le démontrer) que si deux morphismes $\varphi$ et $\psi$ de $\mathcal{P}$ ne diffèrent que par la transposition de deux pièces consécutives (dans leur image) des morphismes $\varphi^J$ et $\psi^J$ ne diffèrent que par une permutation de leurs pièces consistant en un cycle de longueur paire et des points fixes. Par exemple :

$\varphi = \begin{pmatrix} 6 & \cdot & \cdot & \cdot \\ 4 & 5 & 7 & \cdot \\ 1 & 2 & 3 & 8 \end{pmatrix}$ et $\psi = \begin{pmatrix} 6 & \cdot & \cdot & \cdot \\ 4 & 5 & 8 & \cdot \\ 1 & 2 & 3 & 7 \end{pmatrix}$.

diffèrent par la transposition (7, 8) cependant que
$$ \varphi^J = \begin{array}{c} 6 \\ 4 \\ 7 \\ 8 \\ 1 \\ 2 \\ 3 \\ 5 \end{array} . . . . . . . $$

et

$$ \tilde{\varphi}^J = \begin{array}{c} 6 \\ 2 \\ 4 \\ 7 \\ 1 \\ 3 \\ 5 \\ 8 \end{array} . . . . . . . $$

se déduisent l'un de l'autre par la permutation circulaire (2, 3, 5, 8, 7, 4).

Le dernier énoncé de cette section utilise la dualité $\varphi \to \varphi^J$ pour établir un résultat combinatoire servant de base au théorème d'Aitken. Nous rappelons que $\tilde{\mathcal{J}}^1$ désigne la famille des domaines principaux de point minimum (1, 1). Une écriture telle que $\lambda \in \mathcal{P}_m(F)$ signifiera que le domaine de $\lambda$ est l'intervalle principal F de la famille $\tilde{\mathcal{J}}^1$ et que $m = \text{Card } F$.

3.7. *Soient F, G et H trois intervalles de $\tilde{\mathcal{J}}$, $\lambda_1 \in \mathcal{P}_m(F)$ et $\rho_1 \in \mathcal{P}_p(G)$. On suppose que H contient F et G. Il existe une bijection entre les ensembles $V(\lambda_1; G; H) = \lambda_1 R^{-1} \cap \eta_m(H\setminus G)$ et $V(\rho_1; F; H) = \rho_1 R^{-1} \cap \eta_p(H\setminus F)$.*

*Preuve.* Par définition on a $m = \text{Card } F$, $p = \text{Card } G$ et les ensembles considérés sont vides sauf si $\text{Card } H = m+p (= n)$ ainsi que nous le supposerons désormais. Soit $A = [n]$. Soit $U(\lambda_1, \rho_1)$ l'ensemble des morphismes $\varphi \in \mathcal{P}_A(H)$ tels que $\varphi|_G = \rho_1^J$ et $(\varphi|_H\setminus G)R\Omega = \lambda_1$ où $\Omega$ est l'isomorphisme de l'intervalle $A^{(m)} = A\setminus[p]$ sur $A_m = [m]$ dans les notations de 3.6. L'ensemble $U(\rho_1, \lambda_1)$ est défini de façon symétrique.

Il y a bijection entre $V(\lambda_1, G, H) = v$ et $U(\lambda_1, \rho_1)$ puisque nous pouvons associer à chaque $\lambda \in V$ l'unique $\varphi \in U(\lambda_1, \rho_1)$ tel que $\varphi|_G = \rho_1^J$ et $\varphi|_{H\setminus G} = \varphi\Omega^{-1}$ et réciproquement. Il en est de même pour $V(\rho_1, F, H)$ et $U(\rho_1, \lambda_1)$ et il suffit de montrer $\varphi^J \in U(\rho_1, \lambda_1)$ pour chaque $\varphi \in U(\lambda_1, \rho_1)$ pour obtenir la bijection cherchée puisque J est une involution et que les ensembles sont définis de façon symétrique.

Soit donc $\varphi$ comme ci-dessus. D'après 3.6., la restriction de $\varphi^J$ à $A_m$ est égale à $((\varphi|_{A^{(m)}})R\Omega)^J$ donc à $\lambda_1^J$ puisque par construction
$$ \varphi|A^{(m)} = \varphi|H\G = \lambda\Omega^{-1} \text{ où } \lambda R = \lambda_1. $$

On en déduit que $\varphi^J|A_m = \varphi|F$ donc que $\varphi|A^{(p)} = \varphi|H\F$ puisque $A^{(p)} = [n]\G[m] = A\G A_m$. Appliquons le même énoncé à $\varphi^J$ et p au lieu de $\varphi$ et $m$.

Comme $\varphi^{JJ} = \varphi$ on obtient que $\varphi^{JJ}|A^{(p)} = ((\varphi^J|A^{(p)})R\Omega)^J$ (avec ici $\Omega: A^{(p)} \to A_p = [p]$). Dans cette relation on a $\varphi^{JJ} = \varphi$ et, par construction, $\varphi|A_p = \rho_1^J$. En outre, comme on vient de le voir, $\varphi^J|A^{(p)} = \varphi^J|H\F$. Comme $J$ est une involution on a la conclusion désirée $\rho_1 = (\varphi^J|H\F)R\Omega$.

Q.E.D.

Comme les deux ensembles $V$ ont le même nombre d'éléments et que le premier (resp. le second) ne dépend pas du choix du morphisme $\rho_1$ (resp. $\lambda_1$), ce nombre que nous désignerons par $g(F, G; H)$ ne dépend que des intervalles $F, G$ et $H$ et ceci de façon symétrique en $F$ et $G$. Comme de plus $R$ commute avec la transposition on peut résumer l'énoncé précédent par l'identité suivante, dans laquelle on suppose $g(F, G; H) = 0$ si les conditions de 3.7. ne sont pas satisfaites.

### 3.7. bis

$$ g(F, G; H) = g(G, F; H) = g(F^T, G^T; H^T). $$

Nous verrons plus loin que les $g$ sont les paramètres de structure de la multiplication des fonctions de Schur.

Je mentionne enfin une construction dont le seul intérêt est le manifester une propriété de continuité curieuse de l'opération $R$.

Considérons un intervalle $F$ du plan, un morphisme bijectif $\varphi: F \to [n]$, deux entiers positifs $p$ et $q$ et un système $(\rho)$ de $n$ morphismes bijectifs
ρᵢ,ⱼ ((i, j) ∈ F) dont les domaines sont l'intervalle rectangulaire du plan [p] × [q] et les images de la chaîne [pa].

Soit G l'intervalle du plan formé des points de la forme (ip+k, jq+k') où (i, j) ∈ F et (k, k') ∈ [p] × [q]. On définit le **produit en couronne** de (p) dans φ comme le morphisme bijectif ψ de domaine G tel que on ait identiquement :

$$(ip+k, jq+k')\psi = (i, j)\varphi \cdot n + (k, k')\varphi_{i,j}$$

Ceci fait on a la remarque suivante dont la preuve ne fait pas intervenir d'idées nouvelles et est omise :

3.8. Si $\psi$ est le produit en couronne de $(\rho)$ dans $\varphi$, alors $\psi R$ est le produit en couronne de $(\rho)$ dans $\varphi R$.

4. Le théorème de Robinson.

Nous commençons par un calcul dû initialement à G. de B. Robinson qui l'a présenté dans [12] au moyen du formalisme des "lattice permutations" (dont la possibilité de la traduction immédiate en termes de tableaux ne semble pas toujours avoir été perçue). La formulation ci-dessous est celle de Schensted [13] avec une simplification due à Knuth [8]. Nous rappelons que $\mathcal{P}$ est l'ensemble des morphismes $\varphi$ de $\mathcal{M}$ tels que $\varphi = \varphi R$, c'est-à-dire dont le domaine est un intervalle principal de point minimum (1, 1).

4.1. (1) Si $b \in A$ et $\varphi \in \mathcal{P}_A \setminus b$, le domaine de $(\varphi b) R$ est l'union de celui de $\varphi$ et d'un point ;

(2) Réciproquement, si $\psi \in \mathcal{P}_A(F)$ il correspond à chaque point maximum p de son domaine une et une seule paire $b \in A$, où $\psi \in \mathcal{P}(F \setminus p)$ telle que $\psi = (\varphi b)R$.

Preuve. Supposons que b et $\varphi$ satisfont les conditions de (1).
Si $b$ est plus grande que toutes les pièces de la première ligne $\varphi_1$ de $\varphi$
on a $C_{\varphi b} = C_{\varphi} \text{ où } \varphi = \psi R$ est obtenu en mettant $b$ à la fin de $\varphi_1$. Donc
$\psi = (\varphi b)R$ et le résultat est établi dans ce cas.

Dans le cas contraire on construit une suite $b_0 = b, b_1, \dots, b_k$ par la
condition que chaque $b_{i+1}$ soit la plus petite pièce $> b_i$ de la ligne $i$ de $\varphi$ et
que $b_k$ soit le premier terme pour lequel la pièce obtenue soit plus grande que
toutes les pièces de la ligne supérieure. Ceci fait, on définit $\psi$ en remplaçant dans
$\varphi$ chaque $b_{i+1}$ par $b_i$ et en plaçant $b_k$ à la fin de la ligne $k+1$. On vérifie que
$\psi = \psi R \in \mathcal{M}$. Le fait que $\psi = (\varphi b)R$ est établi par induction en observant que
$\varphi = \varphi'\varphi_1$ où $\varphi'$ est la restriction de $\varphi$ aux lignes 2, 3, \dots et en faisant appel
à 2.3 qui montre que $\sigma_1 b \equiv b_1 \psi_1 \text{ d'où } \varphi b \equiv \varphi' b_1 \psi_1$.

(2) Réciproquement si le point $p$ se trouve à l'extrémité de la ligne $k+1$
de $\psi$ on construit la suite $b_k = p_\psi^{-1}, b_{k-1}, \dots, b_0 = b$ où chaque $b_i$ est la
plus grande pièce $< b_{i+1}$ de la ligne $i$ de $\psi$. Effectuant la substitution inverse
de celle faite dans (1) on trouve un morphisme $\varphi = \varphi R$ et on vérifie que l'on a
bien $\psi = (\varphi b_0)R$ par le même argument que ci-dessus.

Q.E.D.

EXEMPLE.

$$
\varphi = \begin{array}{cccccc}
      & 7 & \cdot & \cdot & \cdot & \cdot \\
    1 & 2 & 4 & 6 & 9 &
\end{array}
$$

$$
(\varphi 5) R = \begin{array}{cccccc}
      & 7 & 8 & \cdot & \cdot & \cdot \\
    3 & 6 & \cdot & \cdot & \cdot & \cdot \\
    1 & 2 & 4 & 5 & 9 &
\end{array}
$$

Nous avons défini dans le chapitre des notations à la fin de l'introduction le
sous-ensemble $S_A^1 \subset \mathcal{M}$ des *permutations* d'image $A$ comme l'ensemble des
$\sigma \in \mathcal{M}$ dont le domaine est formé des points $p_i = (n+1-i, i) \ (1 \le i \le n = \text{Card } A)$.
Chaque permutation est donc un produit $(p_1\sigma) (p_2\sigma) \dots (p_n\sigma)$. Nous définissons
son *inverse* $\sigma^{-1}$ comme le produit $\tau = c_1c_2\dots c_n \in S_n^1$ où pour chaque
$r=1, 2, \dots, n$, on a $c_r = j \text{ ssi } p_j\sigma$ est la r-ième pièce de $A$ (par ordre
croissant). C'est donc l'inverse habituel quand A est la chaîne standard [n].
On a la formule importante :

4.2. Les ordres $C_σ$ sur A et $C_{σ-1}$ sur [n] sont isomorphes.

**Preuve.** Soit $b = p_iσ$ et $b' = p_jσ$ respectivement la r-ième et la s-ième pièce de A. Par définition on a $(b, b') \in C_σ$ssi d'une part $b \le b'$, c'est-à-dire $r \le s$, et d'autre part $(p_i, p_j) \in C$, c'est-à-dire $i \le j$ et ces deux conditions équivalent donc à $(c_r, c_s) \in C_{σ-1}$.

Q.E.D.

L'énoncé 4.2. est donc une simple reformulation du fait connu que $σ^{-1}σ$ induit une bijection sur les inversions.

Nous établissons maintenant le résultat le plus important de la théorie.
Dans son énoncé $\mathcal{L}_n^{(2)}$ désigne l'ensemble des paires de fonctions $(L, L') \in L_n \times L_n$ telles que $L_0 = L_0^1$. Comme d'habitude $\text{Card } A = n$.

**THEOREME 4.3** (G. de B. Robinson). *L'application $\sigma \to (L(\sigma), L(\sigma^{-1}))$ est une bijection de $S_A^1$ sur $\mathcal{L}_n^{(2)}$.*

**Preuve.** On vient de voir que les ordres $C_σ$ et $C_{σ-1}$ sont isomorphes ce qui entraîne immédiatement $L_0(\sigma) = L_0(\sigma^{-1})$ et l'application est donc une application de $S_A^1$ dans $\mathcal{L}_n^{(2)}$.

Réciproquement, considérons une paire $(M, N) \in \mathcal{L}_n^{(2)}$ et montrons qu'il lui correspond une et une seule permutation $\sigma \in S_A^1$ telle que $M = L(\sigma)$, $N = L(\sigma^{-1})$.

Ceci est trivial pour $n=1$ et nous procédons par induction sur $n \ge 2$.
D'après 3.3. il existe une et une seule paire $\varphi = \varphi R, \psi = \psi R$ d'image $[n]$ telle que $M = L(\varphi), N = L(\psi)$. Puisque $M_0 = L_0$, les morphismes $\varphi$ et $\psi$ ont même domaine $F$. De plus, d'après 3.2., la fonction $M_1$ détermine le point maximum p de $F$ où se tourve la pièce n dans $\psi$. D'après 4.1., il existe une et une seule paire $(\varphi', b)$ où $\varphi' = \varphi'R$ a pour domaine $F \setminus p$ et $b \in [n]$ telle que $(\varphi'b)R = \varphi$. Par construction la paire de fonctions $(L(\varphi'), L(\psi|[n-1]))$ appartient à $\Sigma_{n-1}^{(2)}$. D'après la définition des fonctions $L$, la fonction $L(\psi|[n-1])$ est déterminée par $M$ puisque c'est simplement la fonction $M^+$ telle que $M_j^+ = M_{j+1}$ ($j = 0, 1, ...$).

D'après l'hypothèse d'induction il existe une et une seule permutation $\tau' = b'_1 \dots b'_{n-1}$ de $S_{n-1}^1$ qui soit telle que

$$L(\tau') = L(\varphi') \text{ et } L(\tau'^{-1}) = M^+.$$

Nous définissons maintenant la permutation $\tau = b_1 \dots b_n$ de $S_n^1$ en posant, $b_n = b$ (où b est la pièce obtenue plus haut) et pour chaque $i \le n-1$, $b_i = b'_i$ où $1+b'_i$ selon que $b_i < b$ ou $b_i > b$. Comme $b'_i \to b_i$ est un isomorphisme on a bien $\varphi = \tau R$, donc $N = L(\tau)$ et comme $b_n = b$ est le dernier élément du produit $\tau$ on a $M = L(\tau^{-1})$.

L'unicité de cette permutation $\tau$ est une conséquence immédiate du caractère biunivoque de chacune des étapes de sa construction. On obtient enfin $\sigma \in S'_A$ en posant $\sigma = \tau\Omega^{-1}$ où $\Omega$ est l'isomorphisme de $[n]$ sur $A$.

Q.E.D.

Une formulation équivalente de ce théorème est l'assertion que l'application $RR: \sigma \to (\sigma R, \sigma^{-1}R)$ est une bijection de $S_n^1$ sur l'ensemble des paires de morphismes de $\rho_n$ ayant même domaine. Un algorithme particulièrement rapide pour calculer $\sigma RR$ a été trouvé par G. Viennot ([19]).
Nous signalons maintenant quelques propriétés de cette correspondance en
employant les notations $J$ et $\Omega$ définies à la fin de la section 3. On pose
$\bar{b} = (-b)\Omega'$ ($b \in [n]$ où $\Omega'$ est ici l'isomorphisme de $-[n]$ sur $[n]$. Par consé-
quent $b \to \bar{b}$ est simplement l'anti-isomorphisme de la chaîne $[n]$ sur elle-même.
Les relations de (1) ci-dessous dans lesquelles $J$ n'intervient pas sont dues à
Schensted [13].

4.3. **Soient $\sigma = b_1 b_2 \dots b_n \in S_A^1$ une permutation et $(\varphi, \psi) = \sigma RR$. On a :**

$$
\begin{align*}
(1) \quad (\bar{b}_n \bar{b}_{n-1} \dots \bar{b}_1)_{RR} &= (\varphi^J, \psi^J) \\
& (b_n b_{n-1} \dots b_1)_{RR} = (\varphi^T, \psi^{J_T}) \\
& (\bar{b}_1 \bar{b}_2 \dots \bar{b}_n)_{RR} = (\varphi^{J_T}, \psi^T).
\end{align*}
$$

$$
(2) \quad \underline{\text{Si } \beta = b_1 \dots b_p \text{ et } \gamma = b_{p+1} \dots b_n \text{ sont une factorisation de } \sigma, \text{ on a}} \\
\underline{[\beta^{-1}R = \psi|[p] \text{ et } \gamma^{-1}R = (\psi|[n]\setminus[p])R\Omega] \text{ où } \Omega: [n]\setminus[p] \to [n-p].}}
$$

**Preuve.** Comme $b_n \dots b_1 = \sigma^T$ et comme la transposition commute avec $R$ on a $(b_n \dots b_1)R = \varphi^T$. D'autre part, d'après les définitions de l'involution $\chi \to \bar{\chi}$ ($\chi \in \mathfrak{M}$) et de l'isomorphisme $\Omega: -[n] \to [n]$ on a $\bar{\sigma}\Omega = \bar{b}_n \dots \bar{b}_2 \bar{b}_1$, donc $(\bar{b}_n \dots \bar{b}_2 \bar{b}_1)R = \varphi^J$ en raison de la définition de $J$ et de l'identité $\bar{\chi}R = (\bar{\chi}\bar{R})R$. La troisième formule $(\bar{b}_1 \dots \bar{b}_n)R = \varphi^{J_T}$ résulte des deux précédentes puisque $J \cup T$ commutent.

Pour établir les formules concernant $\psi$ il suffit de vérifier l'une d'elle et
d'utiliser la dualité $\sigma \to \sigma^{-1}$. Le plus simple est de noter que si $\sigma' = b_n \cdots b_2 b_1$
on a de façon équivalente, $\sigma'^{-1} = (\sigma^{-1})^T$ d'où $(b_n \cdots b_2 b_1)RR = (\varphi^{J_T}, \psi^T)$.

La deuxième partie de l'énoncé résulte de ce que $\beta^{-1}$ est la restriction de
$\sigma^{-1}$ à l'intervalle initial $[p]$ de son image et que, de même, $\gamma^{-1}$ est la restric-
tion de $\sigma^{-1}$ au complément de $[p]$.
4.4. La correspondance $\sigma \to \sigma R$ établit une bijection entre les involutions sur $[n]$ et $\wp$ telle que le nombre des points fixes de $\sigma$ est égal au nombre des colonnes de longueur impaire de $\sigma R$.

**Preuve.** La permutation $\sigma$ est une involution ssi $\sigma = \sigma^{-1}$, donc d'après le théorème de Robinson, ssi $\sigma R = \sigma^{-1}R$ ce qui établit la première partie de l'énoncé.

En ce qui concerne la seconde nous procédons par induction sur $[n]$ et nous considérons une involution $\sigma = b_1b_2\dots b_n$. Si $b_n = n$, $\sigma$ a un point fixe de plus que l'involution $\sigma' = b_1\dots b_{n-1}$ et le morphisme $\sigma R$ a une colonne impaire de plus que $\sigma'R$ puisque d'après 4.1., $\sigma R = (\sigma'n)R$ est obtenu en ajoutant la pièce $n$ à la fin de la première ligne de $\sigma'R$, ce qui crée une nouvelle colonne de longueur 1.

Soit maintenant $b_n = m \neq n$. Nous considérons $\sigma'$ comme ci-dessus et l'involution $\tau$ sur $A = [n]\setminus\{n, m\}$ obtenue en supprimant $b_m = n$ et $b_n = m$ dans le produit $\sigma$. Comme $n$ est une pièce maximale, $\tau R$ est la restriction de $\sigma'R$ à $A$ ; c'est-à-dire que $\tau R$ se déduit de $\sigma'R$ en retranchant la pièce $n = b_m$ qui se trouve au point $q$ du domaine $F$ de $\sigma'$.

D'autre part, toujours d'après 4.1., $\sigma R = (\sigma'm)R$ a pour domaine l'union de $F$ et d'un point $p$. Comme $\sigma R = \sigma^{-1}R$ ce point $p$ porte la pièce maximale $n$ de l'image $[n]$ de $\sigma^{-1}$. Autrement dit, l'opération $\sigma'R \to (\sigma'm)R$ déplace la pièce $n$ du point $q$ au point $p$ qui se trouve donc dans la ligne immédiatement supérieure à celle de $q$. Si $p$ et $q$ sont dans la même colonne, les domaines $F \cup p$ de $\sigma$ et $F \setminus q$ de $\tau$ ont le même nombre de colonnes impaires, d'où le résultat par induction puisque $\tau$ a par construction le même nombre de points fixes que $\sigma$.

Si au contraire $p = (i, j)$ et $q = (i', j')$ sont dans deux colonnes distinctes, c'est-à-dire si $k \neq i'$, ces deux points sont des points maximaux de $F \cup p$ et les
longueurs de ces colonnes sont $j$ et $j' = j-1$, donc de parités différentes. Par conséquent le domaine $F\setminus q$ de $\tau$ a encore le même nombre de colonnes impaires que celui de $\sigma$.

Q.E.D.

En particulier $R$ établit une bijection entre les involutions sans points fixés et les morphismes $\phi$ de $P$ dont toutes les colonnes du domaine ont une longueur paire. Une autre bijection a été découverte par W. H. Burge ([3]) entre ces involutions et les morphismes $\phi$ de $P$ dont le domaine a la forme $\{\sigma\}$ de Littlewood (cf. [3]). Je n'ai pas réussi à trouver le cadre dans lequel la construction de Burge est naturelle.

L'énoncé suivant est associé à 3.7.

4.5. **Soient $F, G$ deux domaines principaux de $\hat{J}^1$, $X \in \mathcal{P}_n(H)$ et $\lambda_1 \in \mathcal{P}_m(F)$. L'ensemble $W(F, G; X) = \{(\rho, \lambda) \in P(G) \times P(F) : (\rho\lambda)R = X\}$ est non vide ssi $n = m+p$ et $F, G \subset H$. S'il en est ainsi, il est en bijection avec l'ensemble $\lambda_1 R^{-1} \cup \pi_m(H\setminus G)$**.

**Preuve.** Supposons $(\rho, \lambda) \in W$. La condition $(\rho\lambda)R = X \in \mathcal{P}_n(H)$ implique évidemment que les images $B$ et $C$ de $\rho$ et de $\lambda$ forment une partition de $A = [n]$, donc que $n = m+p$. Le fait que $H$ contient $F$ et $G$ résulte de 3.4 (2).

Choisissons arbitrairement un morphisme $\rho_1 \in \mathcal{P}_p(G)$. D'après le théorème de Robinson il existe une et une seule permutation $\beta$ d'image $B$ telle que $\beta RR = (\rho, \rho_1)$ (resp. $\gamma$ d'image $C$ telle que $\gamma RR = (\lambda, \lambda_1)$). Soit $\sigma$ un produit $\beta\gamma$. Par construction on a $\sigma R = (\beta R \cdot \gamma R)R = (\rho\lambda)R = X$. Considérons $\psi = \sigma^{-1}R$. D'après 4.3. $(\psi|[p])R = \beta^{-1}R = \rho_1$ et $(\psi|[n]\![p])R = \gamma^{-1}R = \lambda_1$. Par conséquent pour chaque $\rho_1$ arbitrairement choisi la correspondance $(\rho, \lambda) \to (\psi|[n]\![p])\sigma$ est une application de $W$ dans $\lambda_1 R^{-1} \subseteq \mathfrak{M}(H\setminus G)$.
Réciproquement, supposant donné $\lambda$ dans ce dernier ensemble on définit
$\psi \in \rho_n(H)$ par ses restrictions $\psi|_{[p]} = \rho_i$ ; $\psi|_{[n]\setminus[p]} = \lambda\Omega^{-1}$ et on obtient $\sigma$
comme l'unique permutation telle que $\sigma RR = (\varphi, \psi)$. La factorisation $\sigma = \beta\gamma$ est
déterminée sans ambiguïté par les longueurs $p$ et $n-p=m$ de $\rho$ et de $\gamma$ et on
obtient la paire $(\beta R ; \gamma R)$ de $W(F, G, \chi)$.

Q.E.D.

Il résulte de l'existence de cette bijection que W est indépendant du choix
de $\chi$ dans H et on écrira plutôt $W(F, G; H)$. Il existe une bijection évidente
avec $W(F^T, G^T; H^T)$. L'énoncé 3.7 permet d'en établir une autre avec
$W(G, F; H)$. Enfin 4.5 lui-même signifie que $g(F, G; H) = \text{Card } W(F, G; H)$.

Nous indiquerons dans la section suivante comment ces diverses relations
équivalent à des identités connues de l'algèbre des fonctions de Schur. Leur théorie
motive le dernier énoncé de cette section qui fournit la base combinatoire à la
"règle de Littlewood-Richardson!" Il requiert quelques notions supplémentaires
qui réapparaîtront dans la section 5.

Soit $v = (n_1 \ge n_2 \ge \dots \ge n_k > 0)$ une partition de l'entier $n = n_1 + \dots + n_h$.
Elle définit un morphisme $\omega = \omega_v$ de la chaîne $[n]$ sur la chaîne $[k]$ tel que
l'image inverse $j_w^{-1}$ de chaque $j \in [k]$ soit l'intervalle de $[n]$ formé des $n_j$
éléments consécutifs $\overline{n}_{j-1}+1, \overline{n}_{j-1}+2, \dots, \overline{n}_{j-1}+n_j = \overline{n}_j$ où
$\overline{n}_{j-1} = n_1 + n_2 + \dots + n_{j-1} (= 0 pour j = 1)$.

Si $\sigma$ est une permutation des éléments de $[n]$, nous considérons $\sigma w$
comme un mot du monoïde libre $[k]^*$ engendré par $[k]$. On rappelle que $|s|_j$
désigne le nombre d'occurrences d'une lettre $j$ dans un mot $s$ et par conséquent
le _multidegré_ ($|\sigma w|_1, \dots, |\sigma w|_k$) de $\sigma w$ est précisément $v = (n_1, \dots, n_k)$.
Nous désignons par $Y$ le sous-ensemble des mots $s$ de $[k]^*$ teis que :
(Y) Pour chaque facteur gauche $s'$, le s et chaque $j \in [k-1]$ on a
$$ |s'|_j \ge |s'|_{j+1} . $$

Les mots de Y de multidegré $v$ sont les "lattice permutations" de MacMahon et G. de B. Robinson, aussi appelés "symboles de Yamanouchi" par les physiciens. Il est clair qu'un mot de $[k]^*$ ne peut appartenir au sous-ensemble Y que si son multidegré est une suite non croissante d'entiers, c'est-à-dire une partition de sa longueur. Par exemple Y comprend 5 mots de multidegré (3,2), à savoir 11122, 11212, 11221, 12112, 12121.

A la même partition $v = (n_1, \dots, n_k)$ nous associons l'intervalle principal du plan $F_v$ dont les longueurs successives des colonnes sont les $n_j$ et le morphisme $\varphi_v$ de domaine $F_v$ et d'image $[n]$ obtenu en mettant dans la colonne $j$ les éléments de l'intervalle $B_j = j\omega^{-1}$ pour $j = 1, 2, \dots, k$. Nous appellerons $\varphi_v$ le **tableau naturel** de la partition $v$. Par exemple $v = (3, 2, 1, 1)$ a pour tableau naturel le morphisme représenté par

3 . . .
2 5 .
1 4 6 7

**THEOREME 4.6 (Littlewood-Richardson).** Soit $\varphi_v$ le tableau naturel d'une partition $v$ de $[n]$. Un morphisme $\psi$ appartient à $\varphi_v R^{-1}$ si l'image $\sigma_\psi$ de la permutation $\sigma = \sigma_\psi$ qui lui est associée appartient à Y et a pour multidegré $v$.

**Preuve** (A. Lascoux). Il suffit d'appliquer le théorème 4.3. de Robinson pour établir une bijection entre le sous-ensemble $Y_v$ des mots de Y de multidegré $v$ et l'ensemble des paires de morphismes $(\varphi_v, \rho)$ de même domaine principal $F_v$.

Soit d'abord $s \in Y_v$. Parmi les permutations de $s^{-1}$, il en existe une et une seule, notée $\bar{s}_\omega$, telle que pour chaque $j \in [k]$, les éléments de l'intervalle $B_j = j\omega^{-1}$ s'y rencontrent dans l'ordre décroissant, quand elle est lue de gauche à
droite. L'hypothèse que s appartient à Y entraîne qu'il existe un morphisme $\rho_s$ de domaine $F_v$ contenant les éléments de $B_j(s\bar{\omega})^{-1}$ pour $j = 1, \dots, k$.

Comme Y contient les facteurs gauches de ses membres, on peut procéder par induction sur $[n]$ et la construction décrite au début de cette section montre facilement que

$$ (\varphi_v, \rho_s) = (s\bar{\omega}R, (s\bar{\omega})^{-1}R) . $$

Réciproquement, si $\rho$ est un morphisme de domaine $F_v$, la même technique montre que la permutation $\sigma$ telle que $(\sigma R, \sigma^{-1}R) = (\varphi_v, \rho)$ est bien de la forme $\sigma = s\bar{\omega}$ pour un mot $s$ de $Y_v$.

Q.E.D.

EXEMPLE. Soit $v = (3, 2, 1, 1)$. Le tableau naturel $\varphi_v$ a été donné plus haut. Si $\rho: \begin{array}{cccc} 3 & 5 & \cdot & \cdot \\ 1 & 2 & 4 & 6 \end{array}$ est un autre morphisme de même domaine $F_v$, la permutation $\sigma$ pour laquelle $(\sigma R, \sigma^{-1}R) = (\varphi_v, \rho)$ est $(3, 5, 2, 6, 4, 7, 1)$ et son image par $\omega$ est le mot $1213241$ de $Y_v$. Le mécanisme de l'induction est évident si l'on considère le segment initial $\sigma' = (3, 5, 2, 6, 4, 7)$ de $\sigma$ pour lequel on a

$$ \sigma'R = \begin{array}{c} 3 \ 5 \ \cdot \ \cdot \\ 2 \ 4 \ 6 \ 7 \end{array} \quad \text{et} \quad \sigma'^{-1} = \begin{array}{c} 3 \ 5 \ \cdot \ \cdot \\ 1 \ 2 \ 4 \ 6 \ \cdot \end{array} $$

Le lecteur notera que l'énoncé 4.3. permet de donner une série de formulations équivalentes de ce résultat. Celle utilisée par la "règle de Littlewood-Richardson" pour le calcul des nombres Card $W(F, G; H)$ (mentionnés à la fin de 4.5.) utilise le transposé du tableau naturel et a un rapport évident avec la notion de "file" développée dans la section suivante.
### 5. Connexion avec les fonctions de Schur.

Nous commençons par compléter l'outillage combinatoire. Si $\varphi$ est un morphisme de $\eta$, une *file* de $\varphi$ est un intervalle *maximal* B de son image qui est une $C_{\varphi}$-chaîne. Par exemple les files de

$$ \varphi = \begin{array}{r@{\;}c@{\;}l@{\quad}l@{\quad}l} & 10 & \cdot & \cdot & \cdot & \cdot \\ & 5 & 9 & 12 & \cdot & \cdot \\ & \cdot & 1 & 4 & 7 & 8 \end{array} \quad \text{sont} $$

$$ B_1 = (1, 4), B_2 = (5, 7, 8), B_3 = (9), B_4 = (10, 12). $$

Il est clair que les files de $\varphi$ constituent une partition ordonnée (de façon naturelle) de son image A et qu'elles sont déterminées sans ambiguïté par la donnée de A et de la suite (dite *suite de files*) $N=(\varphi) = (n_1, n_2, \dots, n_k)$ du nombre de leurs éléments ($N(\varphi) = (2, 3, 1, 2)$ dans l'exemple ci-dessus).

$$ \text{5.1. Soit } N(\varphi) = (n_1, \dots, n_k) \text{ la suite de files d'un morphisme } \varphi \text{ de } \eta_n $$

$$ (1) \quad N(\varphi) = N(\varphi R); $$

$$ (2) \quad N(\bar{\varphi}) = (n_k, \dots, n_1) \text{ et } N(\varphi^T) \text{ sont déterminées par } N(\varphi); $$

$$ (3) \quad \text{Quand } \varphi \text{ est une permutation } \sigma, \text{ les longueurs des facteurs croissants maximaux de } \sigma^{-1} \text{ sont } n_1, \dots, n_k. $$

**Preuve.** (1) Soit B un intervalle de l'image $[n]$ de $\varphi$. Il est contenu dans une file de $\varphi$ ssi il est contenu dans une $C_{\varphi}$-chaîne, c'est-à-dire, de façon équivalente ssi $(\varphi|B)R$ se réduit à une seule ligne d'où le résultat d'après la formule $(\varphi R|B)R = (\varphi|B)R$ établie dans le chapitre 3.

(2) La première assertion résulte immédiatement de l'anti-isomorphisme entre les ordres $C_{\varphi}$ et $C_{\bar{\varphi}}$. La seconde utilise une observation qui présente un intérêt plus général.
Soient $a < b$ deux pièces de $A$ qui n'appartiennent ni à une file de $\varphi$ ni à une file du morphisme transposé $\varphi^T$. Posant $p = a\varphi^{-1} = (x, y)$ et $q = b\varphi^{-1} = (x', y')$, ceci équivaut à $(p, q) \notin C$ et $(p^T, q^T) \notin C$, c'est-à-dire à :

NON ($x \le x' \text{ et } y \ge y'$) et NON ($y \le y' \text{ et } x \ge x'$) c'est-à-dire encore à :

($x > x'$ ou $y < y'$) et ($x < x'$ ou $y > y'$) soit enfin à :

($x > x'$ et $y > y'$) ou ($x < x'$ et $y < y'$).

La première alternative est exclue puisque $\varphi$ est un morphisme et puisque $a := (x, y)\varphi < b := (x', y')\varphi$. On a donc $x < x'$ et $y < y'$ et comme le domaine de $\varphi$ est un intervalle ce dernier contient deux points $r = (x, y')$ et $s = (x', y)$ satisfaisant $p < r, s < q$. Utilisant de nouveau le fait que $\varphi$ est un morphisme, on en déduit enfin qu'il existe deux pièces $c = r\varphi$ et $d = s\varphi$ telles que $a < c, d < b$.

Par conséquent deux pièces **consécutives** de la chaîne $A$ appartiennent à une file de $\varphi$ ou à une file de $\varphi^T$. Comme de plus les ordres $C_\varphi$ et $C_{\varphi^T}$ ont une intersection triviale on obtient le résultat que les files de $\varphi^T$ sont les intervalles maximaux de $A$ dans lesquelles toutes les pièces appartiennent à des files de $\varphi$ différentes, et vice versa.

(3) Ceci résulte immédiatement de l'isomorphisme entre $C_\sigma$ et $C_{\sigma^{-1}}$ et du fait que les **intervalles** initiaux de longueur $m$ ($m \le n$) de l'image de $\sigma$ correspondent aux **facteurs** gauches de même longueur de la permutation inverse $\sigma^{-1}$.

Q.E.D.

Etant donnés une chaîne **quelconque** $A$ et une suite $N = (n_1, n_2, \dots, n_k)$
d'entiers positifs, nous noterons $N^A$ la famille des morphismes $\omega$ de $[n]$
($n = n_1 + \dots + n_k$) dans $A$ qui sont compatibles avec $N$ en ce sens que deux
éléments $m$ et $m'$ de $n$ ont des images $m_\omega$ et $m_\omega'$ distinctes quand ils appartien-
nent à deux intervalles différents de la partition ordonnée $(B_1, \dots, B_k)$ de $[n]$
en intervalles successifs de longueur $n_i$ ($1 \le i \le k$). Ainsi, par exemple $N^A$ est
l'ensemble des morphismes injectifs (resp. de tous les morphismes) de $[n]$ dans
$A$ quand $N = (1, 1, \dots, 1)$ (resp. $N = (n)$).

Considérons maintenant la famille $\tilde{\mathfrak{M}}$ des morphismes dont le domaine est un intervalle du plan et l'image une chaîne et qui satisfont la condition que leur restriction à chaque colonne est injective c'est-à-dire qui sont tels qu'une même pièce ne figure jamais plusieurs fois dans une même colonne.

La notion de produit finie dans l'introduction se généralise de façon évidente à $\tilde{\mathfrak{M}}$. Elle y est même un peu plus simple car si $(F_1, \dots, F_r)$ est une C-partition de l'intervalle $F$, les points de deux composantes distinctes sont nécessairement dans des colonnes différentes ce qui fait qu'un morphisme de $F$ dans une chaîne $A$ appartient à $\tilde{\mathfrak{M}}$ ssi chacune de ses restrictions $\alpha|_{F_i}$ appartient à $\tilde{\mathfrak{M}}$.

Il est clair que d'une part la famille $\tilde{\mathfrak{M}}$ considérée jusqu'ici est un sous-ensemble de cette nouvelle famille $\tilde{\mathfrak{M}}$ et que d'autre part, le semi-groupe $\tilde{\mathfrak{M}} \cup \{0\}$ est le quotient du semi-groupe $\tilde{\mathfrak{M}}$ par le morphisme naturel dont le noyau est $\tilde{\mathfrak{M}} \setminus \tilde{\mathfrak{M}}$ (et la restriction à $\tilde{\mathfrak{M}}$ l'application identique). Une connexion remarquable entre ces deux semi-groupes et les opérateurs de Baxter a été découverte par G. Thomas ([17], [18]). Nous ne prouvons ici que le minimum nécessaire pour raccorder les chapitres précédents à la théorie classique des fonctions symétriques.

Comme aucune condition de surjectivité n'est impliquée dans la définition
$\tilde{\mathfrak{M}}$ il est naturel de noter $\tilde{\mathfrak{M}}_A$ la sous-famille des $\alpha$ de $\tilde{\mathfrak{M}}$ dont l'image est conte-
nue dans la chaîne $A$, le *multidegré* de $\alpha$ est le nombre de fois où chaque élément
de $A$ apparaît dans $\alpha$.
5.2. Pour chaque chaîne A il existe une projection P = P_A de $\tilde{\mathfrak{M}}_A$ sur $\mathfrak{M}$ ayant les propriétés suivantes :

(1) Pour chaque intervalle H, l'image de $\tilde{\mathfrak{M}}_A(H)$ est $\mathfrak{M}_n(H)$ ($n = \text{Card } H$);

(2) Pour chaque $\varphi \in \mathfrak{M}_n(H)$ il existe une bijection $\tilde{\mathcal{R}}$ de $\varphi P^{-1}$ sur $(\varphi R)P^{-1}$ qui conserve les multidegrés;

(3) Si H admet une C-partition $\{F, G\}$ et si $\lambda \in \mathfrak{M}(F)$, $\rho \in \mathfrak{M}(G)$ et $\lambda\rho \in \mathfrak{M}_n(H)$, on a $(\lambda'P^{-1})(\rho'P^{-1}) = (\lambda\rho)P^{-1}$ où $\lambda' = \lambda\Omega$, $\rho' = \lambda\Omega'$ pour des morphismes d'images $\Omega$ et $\Omega'$ convenables.

**Preuve.** Soit $\alpha : H \to A$ un morphisme quelconque. Il existe un et un seul morphisme bijectif $\varphi = \alpha P$ de $\varphi = \alpha P$ de $\mathfrak{M}_n(H)$ qui satisfasse les deux conditions suivantes :

(i) Il existe un morphisme $\omega$ de $[n] \to A$ tel que $\alpha = \varphi\omega$;

(ii) On a identiquement $(x, y)\varphi < (x', y')\varphi$ quand $(x, y)\alpha = (x', y')\alpha$ et $x < x'$.

Ceci revient à numéroter successivement les diverses occurrences des pièces de A de gauche à droite et de bas en haut. Il est clair que $\omega$ est uniquement déterminé par $\alpha$ et $\alpha P = \varphi$.

Supposons maintenant que $\alpha \in \tilde{\mathfrak{M}}$, c'est-à-dire que la même pièce ne figure jamais deux fois dans une colonne. Le raisonnement fait dans la preuve de 5.1 (2) montre que les points de $a\alpha^{-1}$ sont une C-chaîne pour chaque pièce a de A. Donc $a\alpha^{-1}$ est un intervalle d'une file de $\varphi$ ce qui établit que $\omega$ est compatible avec $N(\varphi)$. De plus, si $m = p\varphi^{-1}$ est le dernier élément d'une file de $\varphi$, et $m+1 = q\varphi^{-1}$ est le premier élément de la file suivante et l'on a $(q, p) \in C$ avec : $p = \text{l'occurrence la plus à droite d'une pièce a}$ et $q\alpha$ l'occurrence la plus à gauche de la pièce consécutive à a dans l'image de $\alpha$.

Réciproquement soient donnés $\varphi \in \mathfrak{M}_n(H)$ et $\omega : [n] \to A$ compatible avec
N(c). Leur produit $\alpha = \phi\omega : H \to [n]$ est un morphisme (en tant que produit de morphismes) et appartient à $\mathfrak{m}_A(H)$ puisque deux pièces d'une $C_\phi$-chaîne, donc d'une file de $\phi$, sont toujours dans des colonnes différentes. La dernière remarque faite ci-dessus montre que de fait $\phi = \alpha P$. On a donc établi que P satisfait identiquement

$$ \phi P^{-1} = \{ \phi\omega : \omega \in (N(\phi))^A \}. $$

L'assertion (2) résulte immédiatement de la précédente et de 5.1. (1). On pourrait aussi l'obtenir en numérotant dans l'ordre C les occurrences successives de chaque pièce dans $\phi$ et en effectuant directement les glissements.

L'assertion (3) est aussi une conséquence immédiate de (1).

Q.E.D.

La combinatoire est achevée. Nous considérons le Z-module libre $Z(\tilde{\mathfrak{m}})$ de base $\tilde{\mathfrak{m}}$. La structure de semi-groupe de $\tilde{\mathfrak{m}}$ induit par linéarité une structure d'algèbre sur $Z(\tilde{\mathfrak{m}})$. Il en est de même pour $\mathfrak{m}$ et $Z(\mathfrak{m})$ qui est donc une algèbre quotient de $Z(\tilde{\mathfrak{m}})$.

Dans l'énoncé suivant nous employons la convention usuelle de désigner par la même lettre $\mathfrak{m}'$ une partie de $\tilde{\mathfrak{m}}$ (ou $\mathfrak{m}$) et la somme correspondante $\Sigma \{\alpha : \alpha \in \mathfrak{m}'\}$ du module associé. Les coefficients $g$ sont ceux de 3.7. et, comme toujours $\tilde{\mathfrak{J}}^1$ est la famille des intervalles principaux de point minimum (1, 1).

5.3. Soient $F, G$ et $H$ trois intervalles principaux de $\tilde{\mathfrak{J}}^1$ où $G \subset H$. Pour chaque chaîne $A$ on a :

$$ (1) \qquad (\tilde{\mathfrak{m}}_A(H \backslash G))_R = \Sigma \{g(F'), G; H\} \cdot \tilde{\mathfrak{m}}_A(F') : F' \in \tilde{\mathfrak{J}}^1 \} $$
$$
(2) \quad (\tilde{\mathfrak{m}}_A(F) \mathfrak{m}_A(G))R = \sum \{g(F, G; H') \cdot \tilde{\mathfrak{m}}_A(H') : H' \in \tilde{J}^1\} .
$$

Preuve.
(1) Soit $m = \text{Card}(H\G)$. Par passage au quotient $Z(\mathfrak{m})$ de $Z(\tilde{\mathfrak{m}})$
l'identité (1) devient :

$$
(1 \text{ bis}) \quad (\mathfrak{m}_m(H\G))R = \sum \{g(F', G; H) \mathfrak{m}_m(F') : F' \in \tilde{J}^1\} .
$$

On vient de voir que R commute avec P, donc avec P⁻¹. Par consé-
quent (1 bis) redonne (1) en appliquant P⁻¹ aux deux membres et il suffit de
vérifier l-bis, ce qui est une simple traduction de 3.7.

Soit $\Lambda$ l'ensemble des morphismes de la forme $\lambda R$ où $\lambda \in \mathfrak{m}_m(H\G)$ et $F'_{\lambda_1}$ le domaine de chaque $\lambda_1 \in \Lambda$. Rappelant la notation $V(\lambda_1; G; H) = \lambda_1 R^{-1} \cap \mathfrak{m}_m(H\G)$, $(\lambda_1 \in \Lambda)$, le membre de gauche de (1 bis) est égal à

$$
\sum \{ V(\lambda_1 ; G ; H)R : \lambda_1 \in \Lambda \} .
$$

D'après 3.7. on sait que chaque ensemble $V(\lambda_1, G; H)$ contient un nom-
bre d'éléments $g(G_{\lambda_1}; G; H)$ qui ne dépend que du domaine de $\lambda_1$. Puisque par
définition l'image par $R$ de chacun de ses éléments est $\lambda_1$, on a que la somme
précédente est égale à

$$
\sum \{ F_{\lambda_1}, G; H \}_{\lambda_1 : \lambda_1 \in \Lambda} = \sum \{ g(F, G; H) \cdot \mathfrak{m}_m(F) : F \in \tilde{J} \}
$$

puisqu', de plus $g(F, G, H)$ est nul quand $F$ n'est pas le domaine de la même
manière de (3) de l'énoncé précédent et des ensembles $W$ de 4.5.

Q.E.D.

Considérons un ensemble de variables commutatives $\{x_a : a \in A\}$
indexées par les éléments de $A$ et associons à chaque $\alpha$ de $\tilde{\mathfrak{m}}_A$ le monôme
$\alpha X = x_a^m a x_b^{m_b} b \dots x_c^{m_c} c$ où chaque $m_b$ est le nombre d'occurrences de $b$ dans
$\alpha$ ($b \in A$). L'application $X$ s'étend à un morphisme de $Z(\tilde{\mathfrak{m}}_A)$ dans l'anneau des
polynômes en les $x_a$ (resp. de $Z(\mathfrak{m}_A)$ dans le quotient de ce dernier par la con-
gruence $x_a^2 \equiv x_b^2 \dots \equiv x_c^2 \equiv 0$). Une des définitions classiques de la fonction de
Schur $e_A(F)$ sur les variables $x_a$ ($a \in A$) associée à la forme $F$ d'un
"skew-tableau" de Young, c'est-à-dire à un intervalle de $J^1$, consiste à poser

$$
e_A(F) = \mathfrak{m}_A(F)X := \sum \{\alpha X : \alpha \in \mathfrak{m}_A(F)\}.
$$

Comme $R$ préserve les multidegrés, c'est-à-dire commute avec $X$, la
formule (1) de l'énoncé précédent équivaut à la formule VIII de Littlewood
([11] p. 110) qui exprime $e(H\G)$ en terme de fonctions de Schur associées à des
intervalles principaux c'est-à-dire à des diagrammes de Ferrers comme coeffi-
cients de structure de l'algèbre $Z(\mathfrak{m})$. L'un des résultats de 4.7 bis montre que
cette multiplication est commutative et l'autre équivaut comme on l'a dit à un
théorème d'Aitken (IX, p. 110 de [11]).
[5] C. Green, An extension of Schensted's theorem, *Advances in Math.* 14 (1974), 254-265.

[6] C. Green, Some partitions associated with a partially ordered set, *J. Combinatorial Theory* 20 (1976), 69-79.

[7] C. Green and D. J. Kleitman, The structure of Sperner k-families, *J. Combinatorial Theory* 20 (1976), 41-68.

[8] D. E. Knuth, Permutation matrices and generalised Young Tableaux, *Pacific J. Math.* 34 (1970), 709-727.

[9] D. E. Knuth, *The art of computer programming*, Vol. 3, Addison Wesley, 1973.

[10] A. Lascoux, Calcul de fonctions de Schur en géométrie algébrique, ce volume.

[11] D. E. Littlewood, *The theory of group characters* 2nd Edition, Oxford, 1950.

[12] G. de B. Robinson, On the representations of the symmetric group, *American J. Math.* 60 (1938), 746-760.

[13] C. Schensted, Longest increasing and decreasing subsequences, *Canadian J. Math.* 13 (1961), 179-191.

[14] M.-P. Schützenberger, Quelques remarques sur une construction de Schensted, *Math. Scand.* 12 (1963), 117-128.

[15] M.-P. Schützenberger, Sur un théorème de G. de B. Robinson, *Acad. Sci. Paris* 272 (1971), 420-421.

[16] R. P. Stanley, Theory and application of plane partition, *Studies in Applied Math.* 1 (1971), 167-188 and 259-279.

[17] G. P. Thomas, Baxter algebras and Schur functions. Ph. D. Thesis, Univ. of Wales, Swansea, 1974.

[18] G. P. Thomas, Frames, Young Tableaux, and Baxter Sequences, *Advances in mathematics* (to appear).
[19] G. Viennot, Une forme géométrique de la correspondance de Robinson-Schensted, ce volume.

M.-P. Schützenberger
97, rue du Ranelagh
75016 Paris, France