Séminaire Lotharingien de Combinatoire, B31a(1994), 15pp. Publ. I.R.M.A. Strasbourg, 1994/021, p. 71-85.

Une version géométrique de la construction de

Kerov-Kirillov-Reshetikhin

PAR

GUO-NIU HAN(^{∗})

1. Introduction

Les tableaux de Young, standard ou généraux, sont des objets combinatoires classiques, riches, mais difficiles à étudier. Beaucoup de problèmes les concernant sont encore ouverts. Par exemple, pour trouver le nombre de tableaux de forme et d’évaluation données, ou plus généralement, pour calculer les polynômes de Kostka, on n’a pas de méthode efficace comme des formules de récurrence : on en est réduit à énumérer tous les tableaux d’un type donné. On est alors confronté au problème de trouver une méthode pour engendrer tous les tableaux. Si l’on travaille sur le monoïde plaxique [LS1], qui est un objet équivalent à l’algèbre des tableaux, il est difficile d’énumérer tous les mots non congrus par rapport à la relation plaxique [Kn]. Force est donc de rester attentif à toute nouvelle approche qui rendrait cette algèbre de tableaux plus accessible.

Par une démarche totalement différente des méthodes utilisées jusqu’ici, S. V. Kerov, A.-N. Kirillov et N. Yu. Reshetikhin ont introduit des nouveaux objets (rigged configurations en anglais) qui sont en bijection avec les tableaux de Young (cf. [KKR], [KR], [Ki]). Les sources physiques qui ont conduit les trois auteurs précédents à introduire ces objets restent bien mystérieuses. Par contre, on peut donner une version très combinatoire de ceux-ci et rendre plus compréhensible l’approche de ces auteurs en utilisant des modèles géométriques, essentiellement des chemins polygonaux. Le résultat fondamental de KKR se traduit de la façon suivante

2  \underline{G.-N. HAN}

(^{∗}) Avec le concours du programme des Communautés Européennes en Combinatoire Algébrique. dans le modèle combinatoire que nous allons décrire ici : Les tableaux de Young sont en bijection avec les matrices dont tous les coefficients sont des chemins.

L’intérêt du modèle KKR est qu’il permet de traiter plusieurs problèmes. D’abord, on peut énumérer les tableaux de Young par bloc, ce qui permet de calculer les polynômes de Kostka très rapidement. D’autre part, certaines opérations fondamentales sur les tableaux ou sur le monoïde plaxique, comme la standardisation introduite par Lascoux et Schützenberger [LS2], qui semblent peu naturelles (sauf pour leurs inventeurs !) deviennent très explicites avec ces nouveaux objets. A l’aide de ceux-ci, il semble que de nouvelles propriétés sur les tableaux de Young pourront être étudiées.

L’objet de ce mémoire est d’expliciter le résultat fondammental de KKR (section 2), de décrire ensuite deux algorithmes sur les matrices de chemins, enfin de redémontrer le théorème fondamental de KKR, dans le cas q = 1, en établissant une bijection entre les matrices de chemins et les tableaux de Young (section 4).

2. Le théorème de KKR

Définissons d’abord trois opérations de différence sur l’ensemble des matrices des entiers, indexées Est, Sud, Ouest et notées respectivement D_{E}, D_{S} et D_{O}. Soient m = (m_{ij})_{1≤i≤l, 1≤j≤c} et n = (n_{ij})_{1≤i≤l, 1≤j≤c} deux matrices de l lignes et de c colonnes. On définit :

(i)  n = D_{E}(m) ⇔ \{ \begin{matrix}n_{ij} = m_{ij} & si j = c, \\ n_{ij} = m_{ij} − m_{i,j+1} & si j < c; \end{matrix}

(ii)  n = D_{S}(m) ⇔ \{ \begin{matrix}n_{ij} = m_{ij} & si i = l, \\ n_{ij} = m_{ij} − m_{i+1,j} & si i < l; \end{matrix}

(iii)  n = D_{O}(m) ⇔ \{ \begin{matrix}n_{ij} = m_{ij} & si j = 1, \\ n_{ij} = m_{ij} − m_{i,j−1} & si j > 1 ; \end{matrix}

Il est clair que D_{O}D_{S} = D_{S}D_{O} et que D_{O}D_{E} = D_{E}D_{O} . Soit m une matrice de taille l × c. On introduit cinq autres matrices de même taille e, E, V, F, f définies par les relations décrites dans le schéma suivant(^{∗}) :

e ⟵^{D_{E}} E ⟵^{D_{O}} m
↓D_{S}  ↓D_{S}
V ⟵^{D_{O}} F
↓D_{S}
f

Puisque l’inverse des opérations de différence existe, l’une quelconque de ces six matrices permet de calculer les cinq autres de façon unique. Les matrices e = (e_{ij}), E = (E_{ij}), m = (m_{ij}), F = (F_{ij}), f = (f_{ij}) et V = (V_{ij}) sont appelées, respectivement, escalier d’évaluation, matrice d’évaluation, matrice centrale, matrice de forme, escalier de forme et matrice de charge.

Une matrice centrale m est dite admissible, si les deux escaliers associés e et f sont des matrices à coefficients positifs (ceci implique que les trois autres matrices E, m, F sont toutes positives, mais V ne l’est pas nécessairement). Évidemment, la combinaison linéaire de deux matrices admissibles (centrales) à coefficients positifs est encore une matrice admissible. On désigne M(l, c) l’ensemble de toutes les matrices centrales admissibles de taille l × c. Soit m une matrice admissible. La dernière colonne de la matrice de forme associée F, lue de haut en bas, est forcément une suite décroissante. On identifie cette suite à une partition d’entier, qu’on appelle forme de m. De la même façon, la première ligne de la matrice d’évaluation associée E, lue de gauche à droite, est décroissante et peut aussi être identifiée à une partition d’entier. La transposée de cette partition est appelée évaluation de m. Le poids de m est défini comme le poids de sa forme. On vérifie immédiatement que c’est aussi le poids de son évaluation, ou encore le plus grand coefficient de m. Le nombre de Kostka associé à m est défini par :

K_{m} = ∏_{i=1}^{l−1} ∏_{j=1}^{c} \binom{e_{i+1,j} + f_{i,j}}{e_{i+1,j}}.

(^{∗}) Cette forme planaire est suggérée par les professeurs A. Lascoux et M.-P. Schützenberger.

Rappelons que le polynôme q-binomial est défini par

\left[{x + y \atop x}\right] = \{ \begin{matrix}0, & si x < 0 ou y < 0 ; \\ \frac{[x + y]!}{[x]! [y]!}, & sinon ; \end{matrix}

où [x]! = 1 + q + q^{2} + q^{3} + ⋯ + q^{x−1} si x ≥ 1 et [0]! = 1.

On définit plus généralement le polynôme de Kostka associé à m comme étant

K_{m}(q) = q^{c(V)} ∏_{i=1}^{l−1} ∏_{j=1}^{c} \left[{e_{i+1,j} + f_{ij} \atop e_{i+1,j}}\right].

où V est la matrice de charge associée à m et où l’on a posé c(V) = ∑_{i=1}^{l} ∑_{j=1}^{c} V_{ij}(V_{ij} − 1)/2.

Considérons, par exemple, les six matrices données par

e = ( \begin{matrix}9 & 2 & 0 \\ 2 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} ) E = ( \begin{matrix}11 & 2 & 0 \\ 3 & 1 & 1 \\ 1 & 1 & 0 \end{matrix} ) m = ( \begin{matrix}11 & 13 & 13 \\ 3 & 4 & 5 \\ 1 & 2 & 2 \end{matrix} )

V = ( \begin{matrix}8 & 1 & −1 \\ 2 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} ) F = ( \begin{matrix}8 & 9 & 8 \\ 2 & 2 & 3 \\ 1 & 2 & 2 \end{matrix} )

f = ( \begin{matrix}6 & 7 & 5 \\ 1 & 0 & 1 \\ 1 & 2 & 2 \end{matrix} )

La forme de m est la partition 8, 3, 2 ; et l’évaluation est la transposée de la partition 11, 2, 0, c’est-à-dire la partition 2^{2}1^{9}. Le nombre de Kostka est donc :

K_{m} = \binom{2 + 6}{2}\binom{0 + 7}{0}\binom{1 + 5}{1}\binom{0 + 1}{0}\binom{1 + 0}{1}\binom{0 + 1}{0} = 168.

Le polynôme de Kostka est

K_{m}(q) = q^{30}\left[{2 + 6 \atop 2}\right]\left[{0 + 7 \atop 0}\right]\left[{1 + 5 \atop 1}\right]\left[{0 + 1 \atop 0}\right]\left[{1 + 0 \atop 1}\right]\left[{0 + 1 \atop 0}\right] = q^{30}\left[{8 \atop 2}\right]\left[{6 \atop 1}\right].

Prenons un escalier d’évaluation e de taille l×c, et ajoutons lui quelques lignes et quelques colonnes ne contenant que des zéros. Nous obtenons un nouvel escalier d’évaluation e^{∗}, de taille l^{∗} × c^{∗} où l ≤ l^{∗} et c ≤ c^{∗}. Autrement dit, on pose e_{ij}^{∗} = e_{ij} pour 1 ≤ i ≤ l et 1 ≤ j ≤ c; et e_{ij}^{∗} = 0 pour les autres indices i, j. La traduction de cette opération sur les matrices centrales est obtenue par le diagramme commutatif suivant :

\begin{matrix}m & ⟶ & m^{∗} \\ ↓ & & ↓ \\ e & ⟶ & e^{∗} \end{matrix}

On vérifie facilement que si m est admissible, alors m^{∗} est aussi admissible. L’application m ↦ m^{∗} définit ainsi une injection de M(l, c) dans M(l^{∗}, c^{∗}). Nous constatons que m et m^{∗} admettent la même forme, la même évaluation, le même poids et le même nombre de Kostka. On forme donc la limite inverse en définissant :

M = lim_{\overleftarrow{l,c}} M(l, c).

Les éléments m ∈ M sont appelés encore matrices (centrales) admissibles. On parle aussi de la forme, de l’évaluation, du nombre de Kostka associés à m de façon canonique.

Soient λ, μ deux partitions. On note K_{λ,μ} le nombre de Kostka usuel et M_{λ,μ} l’ensemble des matrices admissibles de forme λ et d’évaluation μ (cf. [M]). Le résultat fondamental de KKR est consigné dans le théorème suivant.

TH^{}ÉOR^{}ÈME 1 (KKR). — On a :

K_{λ,μ} = ∑_{m∈M_{λ,μ}} K_{m}.

Le q-analogue de ce résultat est aussi obtenu par ces mêmes auteurs et s’énonce ainsi.

TH^{}ÉOR^{}ÈME q-1 (KKR). — On a :

K_{λ,μ}(q) = ∑_{m∈M_{λ,μ}} K_{m}(q).

Par exemple, pour la forme λ = 321 et l’évaluation μ = 1^{6}, les deux matrices admissibles possibles sont (\begin{matrix}6 & 6 \\ 2 & 3 \\ 1 & 1 \end{matrix}) et (\begin{matrix}6 \\ 3 \\ 1 \end{matrix}); et les nombres de Kostka

correspondant sont respectivement \binom{2}{1}\binom{4}{1} et \binom{2}{1}\binom{4}{1}, d’où le nombre de Kostka K_{321,1^{6}} = 16. Les polynômes de Kostka correspondants aux deux matrices admissibles sont respectivement q^{7}\left[{2 \atop 1}\right]\left[{4 \atop 1}\right] et q^{4}\left[{2 \atop 1}\right]\left[{4 \atop 1}\right], d’où le polynôme de Kostka

K_{321,1^{6}}(q) = q^{4}(1 + q)(1 + q^{3})(1 + q + q^{2} + q^{3}).

La démonstration du théorème 1 est reproduite à la fin de la section 4. Quant à la démonstration du théorème q-1, il faudra insister auprès des auteurs pour obtenir la démonstration de quelques lemmes !

3. Matrices de chemins

Un chemin w est un mot dont les lettres sont a et b, qui représentent respectivement les pas horizontal “—” (vers l’Est) et vertical “|” (vers le Sud) ; leurs nombres d’occurrences dans w sont notés respectivement |w|_{a} et |w|_{b}. La longueur d’un chemin w est donc |w| = |w|_{a} + |w|_{b} (cf. [Lo]). La direction de w est indiquée par sa dernière lettre ; autrement dit, si la dernière lettre de w est a (resp. b), on dit que la direction de w est vers l’Est (resp. vers le Sud). Un chemin vide n’a pas de direction. Ainsi, le mot w = abbaaba représente le chemin vers l’Est suivant :

Une matrice dont tous les coefficients sont des chemins et dont tous les coefficients de la première ligne sont des chemins sans pas horizontal est dite matrice de chemins. Voici une matrice de chemins W de taille 5 × 4 :

W = \begin{matrix}bb & bb & . & bbb \\ aaa & aaab & aaa & abba \\ b & a & ab & aaa \\ b & a & aa & aa \\ a & a & a & a \end{matrix}

Sur une matrice de chemins, dont la première ligne contient au moins un chemin non vide, on définit deux algorithmes fondamentaux : “marcher” et “déplacer”.

“Marcher”. — Imaginons que la matrice de chemins représente une ville et que ses coefficients sont des bâtiments rectangulaires séparés par des rues se coupant en angle droit, comme le montre la figure ci-après. Chaque intersection de rues — à l’exclusion de celles se trouvant le plus à droite ou tout en bas — est munie d’un panneau de signalisation. On reproduit sur ce panneau le chemin affecté au bâtiment situé au Sud-Est de cette intersection. Si le chemin est vide, rien n’est reporté sur le panneau : l’intersection ne comporte aucune direction à suivre. Dans le cas contraire, on convient que la direction à suivre est celle du chemin reproduit sur le panneau. On fait une promenade dans cette ville suivant les directions indiquées par les panneaux.

Le point d’entrée est l’intersection la plus à gauche dans la première ligne comportant une direction à suivre. Partant de ce point initial, on parcourt les rues de la ville en respectant chaque fois les directions à suivre. On s’arrête dès qu’on atteint une intersection sans direction. On dit que la ville est bien faite, si on s’arrête à une intersection de la colonne la plus à droite (sortie de la ville) ; et qu’elle est mal faite, dans le cas de contraire. Le parcours ainsi réalisé est appelé trace (le grand chemin dans la figure ci-après), qui peut être identifié à la suite des directions lues sur chaque panneau. Dans l’exemple suivant la trace est identifiée au mot bababaa.

On définit enfin deux entiers associés à la matrice des chemins W : le rang R(W) est le nombre de pas verticaux dans la trace, et la lettre L(W) le nombre de pas verticaux dans les chemins de la première ligne de W.

Pour l’exemple précédent, on a R(W) = 3 et L(W) = 7. La ville et la trace associée sont dessinées comme suit :

(W, trace)=

“Déplacer”. — Cet algorithme consiste à construire une autre matrice de chemins U, à partir de W, en déplaçant certains pas d’un chemin sur un autre. La règle générale est la suivante :

Quand on marche dans une rue horizontale vers l’Est, le chemin audessous de cette rue a toujours la direction “—”(le règle de “marcher”), on déplace ce pas vers le chemin au-dessus. Autrement dit, soient \underline{w} = x_{1}x_{2} ⋯ x_{i} et \overline{w} = y_{1}y_{2} ⋯ y_{j}a le chemin du haut et celui du bas de la rue dans laquelle on marche horizontalement dans W (voir le dessin ci-après), On définit les chemins correspondants \underline{u} et \overline{u} de la matrice des chemins U par : \underline{u} = x_{1}x_{2} ⋯ x_{i}a et \overline{u} = y_{1}y_{2} ⋯ y_{j}. De la même façon, si on marche verticalement vers le Sud, on déplace la direction “|” du chemin à droite vers le chemin à gauche de cette rue. Les dessins suivants illustrent ces mouvements :

W  U
pas horizontal : ⟶_{y_{1}y_{2}···y_{j}a}^{x_{1}x_{2}···x_{i}}  ⟹  ⟶_{y_{1}y_{2}···y_{j}}^{x_{1}x_{2}···x_{i}a}

pas vertical : x_{1}x_{2}···x_{i}↓y_{1}y_{2}···y_{j}b ⟹  x_{1}x_{2}···x_{i}b↓y_{1}y_{2}···y_{j}

Remarques. — Si on marche verticalement dans la rue de la première colonne, le chemin à gauche n’existe pas, on supprime donc seulement la direction du chemin à droite ; de la même façon, puisqu’on étudie seulement les matrices dont la première ligne ne contient pas de pas “—”, si on marche dans la rue de la deuxième ligne, on supprime simplement la direction du chemin du bas.

En résumé, on obtient une application φ : W ↦ U définie sur l’ensemble des matrices de chemins bien faites, à valeurs dans l’ensemble des matrices de chemins quelconques.

Si on reprend la matrice de chemins W précédente, qui est bien faite, la matrice U correspondante se présente comme suit :

U =

4. Bijection entre les matrices de chemins et les tableaux de Young

D’après la section précédente, à toute matrice de chemins W, on peut faire correspondre un et un seul entier n ≥ 0, tel que les n matrices de chemins

φ^{0}(W), φ^{1}(W), φ^{2}(W), ⋯, φ^{n−1}(W)

sont bien faites, et tel que φ^{n}(W) ne l’est pas. Cette matrice W est dite admissible, si φ^{n}(W) est égale à la matrice dont tous les chemins sont vides. Dans ce cas, on dit que le poids de W est n.

D^{}ÉFINITION. — Soient W = (w_{ij})_{1≤i≤l+1, 1≤j≤c} une matrice de chemins de taille (l + 1) × c et m ∈ M(l, c). On dit que W et m sont compatibles si, pour tout 1 ≤ j ≤ c et tout 1 ≤ i ≤ l, on a

\{ \begin{matrix}|w_{i,j}|_{b} = e_{i,j}, |w_{l+1,j}|_{b} = 0; \\ |w_{i+1,j}|_{a} = f_{i,j}, |w_{1,j}|_{a} = 0; \end{matrix}

où e, f sont les deux escaliers associés à m.

Par exemple, la matrice de chemins W dans la section précédente est compatible avec la matrice admissible m suivante (on reproduit aussi les matrices e, E, F et f pour une vérification directe) :

\begin{matrix}e = ( \begin{matrix}2 & 2 & 0 & 3 \\ 0 & 1 & 0 & 2 \\ 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{matrix} ) & E = ( \begin{matrix}7 & 5 & 3 & 3 \\ 3 & 3 & 2 & 2 \\ 2 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{matrix} ) & m = ( \begin{matrix}7 & 12 & 15 & 18 \\ 3 & 6 & 8 & 10 \\ 2 & 3 & 4 & 4 \\ 1 & 1 & 1 & 1 \end{matrix} ) \\ f = ( \begin{matrix}3 & 3 & 3 & 2 \\ 0 & 1 & 1 & 3 \\ 0 & 1 & 2 & 2 \\ 1 & 1 & 1 & 1 \end{matrix} ) & F = ( \begin{matrix}4 & 6 & 7 & 8 \\ 1 & 3 & 4 & 6 \\ 1 & 2 & 3 & 3 \\ 1 & 1 & 1 & 1 \end{matrix} ) \end{matrix}

LEMME 2. — Si la matrice de chemins W est compatible avec une matrice centrale admissible non nulle m, alors W est bien faite. De plus, φ(W) est compatible avec une autre matrice centrale admissible m′ telle que

poids(W) = poids(m) = poids(φ(W)) + 1 = poids(m′) + 1.

D^{}ÉMONSTRATION. — (i) Il faut démontrer qu’on n’arrive jamais à une intersection sans direction avant de sortir de la ville. Soient e, f les deux escaliers associés à m et e_{ij} = f_{i−1,j} = 0. On reproduit les matrices e, E, m et f dans un cas arbitraire, mais on inscrit seulement la partie utile autour des coefficients d’indices i, j. (f_{i−1,j} = y et e_{ij} = β − β′) :

\begin{matrix}e = ( \begin{matrix}∗ & α − α′ & ∗ \\ ∗ & β − β′ & ∗ \\ ∗ & γ − γ′ & ∗ \end{matrix} ) & E = ( \begin{matrix}∗ & α & α′ \\ ∗ & β & β′ \\ ∗ & γ & γ′ \end{matrix} ) \\ m = ( \begin{matrix}A & A + α & A + α + α′ \\ B & B + β & B + β + β′ \\ C & C + γ & C + γ + γ′ \end{matrix} ) & f = ( \begin{matrix}x & y & z \\ ∗ & ∗ & ∗ \\ ∗ & ∗ & ∗ \end{matrix} ) \end{matrix}

Les conditions peuvent être rassemblées ainsi :

\{ \begin{matrix}A − 2B + C & & & = x & ≥ 0 \\ A − 2B + C & +α − 2β + γ & & = y & = 0 \\ A − 2B + C & +α − 2β + γ & +α′ − 2β′ + γ′ & = z & ≥ 0 \\ β − β′ & & & = 0 \end{matrix}

cela implique α + γ ≤ 2β = 2β′ ≤ α′ + γ′; d’où α = α′ et β = β′. De plus, on a x = 0 et z = 0. Autrement dit, le chemin situé au-dessus ou au-dessous (resp. à gauche ou à droite) d’un chemin vide n’a pas de pas vertical (resp. horizontal). D’où W est bien faite.

(ii) D’après la construction de φ(W), il est facile d’obtenir explicitement une matrice centrale admissible m′ compatible avec φ(W), à partir de m. La trace de W sépare W en deux parties. Si (i, j) est un point dans la partie supérieure-droite (resp. inférieure-gauche), on pose m′_{i,j} = m_{i,j} − 1 (resp. m′_{i,j} = m_{i,j}). Le dessin suivant aide à vérifier que m′ et φ(W) sont compatibles :

e^{+ + + +} ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}} ^{+ + + +} ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}  E_{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}  ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}  m_{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}} ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}} ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}} ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}} ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}} ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}} ^{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}_{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}_{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}_{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}_{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}_{\begin{matrix}− \\ − \\ − \\ − \end{matrix}}_{−}_{−}_{−}_{−}_{−} ; V_{−}_{+}_{−} ; F_{−}_{−}_{−}_{−}_{−}_{−}_{−}_{−} ; f_{−}_{−}_{−}_{−}_{−}_{−}_{−}_{−}_{+}_{+}_{+}_{+}_{+}_{+}_{+}_{+}

Nous énonçons maitenant un critère d’admissibilité utile.

TH^{}ÉO^{}ÈME 3. — Une matrice de chemins W est admissible, si et seulement si elle est compatible avec une matrice centrale admissible m.

D^{}ÉMONSTRATION. — (i) La partie “si”. Si m est nulle, alors W est admissible avec le poids n = 0 ; sinon, d’après le lemme précédent, on sait que φ(W) est compatible avec une autre matrice admissible m′. Puisque le poids diminue strictement, on obtient forcément la matrice nulle en itérant l’application φ un nombre fini de fois.

(ii) La partie “seulement si”. Si W est admissible, alors φ(W) l’est aussi. D’après l’hypothèse de récurrence, φ(W) est compatible avec une matrice admissible m′. On construit la matrice m à partir de m′ en appliquant l’inverse de l’algorithme décrit dans la partie (ii) de la démonstration du lemme précédent.

Soient W une matrice de chemins admissible de poids n. Pour tout 1 ≤ i ≤ n, on note L_{i} = L(φ^{i−1}(W)) et R_{i} = R(φ^{i−1}(W)) la lettre et le rang de la matrice de chemins φ^{i−1}(W), respectivement. On obtient ainsi un bimot

( \begin{matrix}R \\ L \end{matrix} ) = ( \begin{matrix}R_{1}R_{2} ⋯ R_{n} \\ L_{1}L_{2} ⋯ L_{n} \end{matrix} ) .

Il est clair que le mot du bas L est faiblement décroissant. En utilisant la commutation de Cartier-Foata [CF] (consistant à permuter deux colonnes consécutives si les deux lettres du haut sont différentes), on peut envoyer le bimot ( \begin{matrix}R \\ L \end{matrix} ) sur le bimot ( \begin{matrix}R \\ L \end{matrix} ) dont le mot du haut R̃ est faiblement croissant. On a le résultat suivant :

TH^{}ÉOR^{}ÈME 4. — Le retournement du mot L̃ est un tableau de Young t. La lettre L_{i} figure sur la ligne R_{i} dans t. De plus, si W est compatible avec la matrice centrale admissible m, alors t et m ont la même forme et la même évaluation.

Avant de démontrer ce théorème, donnons un exemple qui utiliser de nouveau la matrice de chemins W de la section 3, qui est compatible avec la matrice m de la section 4. La forme et l’évaluation de m sont respectivement λ = 8, 6, 3, 1 et μ = 4, 4, 4, 2, 2, 1. La figure suivante donne le calcul complet permettant de trouver le bimot

( \begin{matrix}R \\ L \end{matrix} ) = ( \begin{matrix}341223112312221111 \\ 765544333322221111 \end{matrix} ) .

\begin{matrix}\begin{matrix}bb & bb & . & bbb \\ aaa & aaab & aaa & abba \\ b & a & ab & aaa \\ b & a & aa & aa \\ a & a & a & a \end{matrix} & \begin{matrix}b & bb & . & bbb \\ aab & aaaa & aaa & abba \\ b & b & aa & aaaa \\ b & a & a & a \\ a & a & a & a \end{matrix} & \begin{matrix}. & bb & . & bbb \\ aa & aaaa & aaa & abba \\ . & b & aa & aaaa \\ a & aa & aa & aa \\ . & . & . & . \end{matrix} & \begin{matrix}b & b & . & bbb \\ aa & aaa & aa & abb \\ . & b & aa & aaaa \\ a & aa & aa & aa \\ . & . & . & . \end{matrix} \\ L=7, R=3 & L=6, R=4 & L=5, R=1 & L=5, R=2 \end{matrix}

\begin{matrix}\begin{matrix}. & b & . & bbb \\ a & aa & ab & aba \\ . & b & aa & aaa \\ a & aa & aa & aa \\ . & . & . & . \end{matrix} & \begin{matrix}b & . & . & bbb \\ a & ab & aa & abaa \\ . & b & a & aa \\ a & aa & aa & aa \\ . & . & . & . \end{matrix} & \begin{matrix}. & . & . & bbb \\ b & a & aa & abaa \\ b & a & aa & aaa \\ a & a & a & a \\ . & . & . & . \end{matrix} & \begin{matrix}. & . & b & bb \\ b & a & aa & aba \\ b & a & aa & aaa \\ a & a & a & a \\ . & . & . & . \end{matrix} & \begin{matrix}. & b & . & bb \\ b & a & a & ab \\ b & a & aa & aaa \\ a & a & a & a \\ . & . & . & . \end{matrix} & \begin{matrix}b & . & . & bb \\ b & . & b & aa \\ b & a & aa & aa \\ a & a & a & a \\ . & . & . & . \end{matrix} \\ L=4, R=2 & L=4, R=3 & L=3, R=1 & L=3, R=1 & L=3, R=2 & L=3, R=3 \end{matrix}

\begin{matrix}\begin{matrix}. & . & . & bb \\ . & . & b & aa \\ a & aa & aaa & aaa \\ . & . & . & . \\ . & . & . & . \end{matrix} & \begin{matrix}. & . & b & b \\ . & . & b & a \\ a & aa & aaa & aaa \\ . & . & . & . \\ . & . & . & . \end{matrix} & \begin{matrix}. & b & . & b \\ . & b & a & aa \\ a & aa & aa & aa \\ . & . & . & . \\ . & . & . & . \end{matrix} & \begin{matrix}b & . & . & b \\ b & a & aa & aaa \\ a & a & a & a \\ . & . & . & . \\ . & . & . & . \end{matrix} & \begin{matrix}. & . & . & b \\ a & aa & aaa & aaaa \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \end{matrix} \\ L=2, R=1 & L=2, R=2 & L=2, R=2 & L=2, R=2 & L=1, R=1 \end{matrix}

\begin{matrix}\begin{matrix}. & . & b & . \\ a & aa & aaa & aaa \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \end{matrix} & \begin{matrix}. & b & . & . \\ a & aa & aa & aa \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \end{matrix} & \begin{matrix}b & . & . & . \\ a & a & a & a \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \end{matrix} & \begin{matrix}. & . & . & . \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \end{matrix} \\ L=1, R=1 & L=1, R=1 & L=1,R=1 \end{matrix}

On a ainsi

( R̃ ; L̃ ) = ( \begin{matrix}111111112222223334 \\ 533211115432227436 \end{matrix} ) .

Le retournement de L̃ fournit le le tableau de Young :

t = 634722234511112335 = 6 3 4 7 2 2 2 3 4 5 1 1 1 1 2 3 3 5

On vérifie que t est de forme λ et d’évaluation μ.

D^{}ÉMONSTRATION. — Par récurrence, on suppose que φ(W) correspond au tableau t′. On ajoute maintenant la lettre L_{1} à la fin de la ligne R_{1} dans le tableau t′ et l’on obtient un objet t. D’une part, on vérifie facilement que la “forme” de t est la forme de la matrice m. D’autre part, la lettre L_{1} est la plus grande lettre (faiblement) dans t. De plus, si L_{1} = L_{2} = ⋯ = L_{k}, alors R_{1} ≤ R_{2} ≤ ⋯ ≤ R_{k} (vérifier !). On a donc ajouté une plus grande lettre à une ligne plus bas que les autres grandes lettres. Ainsi, on sait que t est un tableau de Young.

En résumé, on obtient une application ψ : W ↦ t définie sur l’ensemble des matrices de chemins admissibles, à valeurs dans l’ensemble des tableaux de Young T .

On note C(l, c) l’ensemble des matrices de chemins compatibles avec une matrice m ∈ M(l, c). Soient l^{∗} ≥ l et c^{∗} ≥ c deux entiers, on peut vérifier qu’il existe une injection canonique satisfaisant le diagramme commutatif suivant :

[figure]

C(l, c)

compatibilité ⟶ M(l, c)

ψ  ↓ \begin{matrix}injection \\ canonique \end{matrix}  ↓ \begin{matrix}injection de \\ la section 2 \end{matrix}

T ⟵^{ψ} C(l^{∗}, c^{∗})

compatibilité ⟶ M(l^{∗}, c^{∗})

On forme la limite inverse C = lim_{\overleftarrow{l,c}} C(l, c). Soient λ, μ deux partitions,

on note C_{λ,μ} l’ensemble des éléments de C compatibles avec une matrice m ∈ M_{λ,μ}.

TH^{}ÉOR^{}ÈME 5. — L’application ψ est une bijection de C_{λ,μ} sur T_{λ,μ}, où T_{λ,μ} est l’ensemble de tableaux de Young de forme λ et d’évaluation μ.

D^{}ÉMONSTRATION. — Il suffit de montrer que ψ est inversible. Pour tout t ∈ T_{λ,μ}, il est facile de construire le bimot ( _{R} ; _{L}). On retrouve le bimot ( \begin{matrix}R \\ L \end{matrix} ) en utilisant la commutation de Cartier-Foata tel que le mot du bas L est faiblement décroissant. Maintenant, on prend une matrice de chemins vide de “grande taille” ayant par exemple |L| lignes et |L| colonnes. Pour une taille fixée, les deux algorithmes “marcher” et “déplacer” sont inversibles. On peut ainsi reconstruire la matrice de chemins W de taille fixée qui peut être identifiée à un élément de C_{λ,μ}.

D’après cette bijection ψ, puisque le nombre de matrices de chemins compatibles avec m ∈ M_{λ,μ} n’est d’autre que K_{m}, on a

K_{λ,μ} = #T_{λ,μ} = #C_{λ,μ} = ∑_{m∈M_{λ,μ}} K_{m}.

Ceci achève la démonstration du théorème 1.

Une version géométrique 15

RÉFÉRENCES

[CF] P. CARTIER, D. FOATA. — Problèmes combinatoires de permutations et réarrangements. — Lecture Notes in Math., Berlin, Springer-Verlag, 1969 v. 85.

[Ki] A. N. KIRILLOV. — On the Kostka-Green-Foulkes polynomials and Clebsch-

Gordan numbers, J. Geom. and Phys., t. 5, 1988, p. 365–389.

[KKR] S. V. KEROV, A. N. KIRILLOV, N. Yu. RESHETIKHIN. — Combinatorics, Bethe Ansatz, and representations of the symmetric group, J. Soviet Math., t. 41, 1988, p. 916-924.

[Kn] D. E. KNUTH. — Permutation matrices and generalised Young tableau, Pacific J. Math., t. 34, 1970, p. 709–727.

[KR] A. N. KIRILLOV, N. Yu. RESHETIKHIN. — The Bethe ansatz and the combinatorics of Young tableaux, J. Soviet Math., t. 41, 1988, p. 925–955.

[LS1] A. LASCOUX, M. -P. SCH^{}ÜTZENBERGER. — Le monoïde plaxique, dans “Non-Commutative structures in algebra and geometric combinatorics”, A. de Luca Ed., Quaderni della Ricerca Scientifica del C. N. R., Roma, 1981.

[LS2] A. LASCOUX, M. -P. SCH^{}ÜTZENBERGER. — Keys and standard bases, dans

“Invariant theory and tableaux”, D. Stanton Ed., Springer, 1990.

[M] I. G. MACDONALD. — Symmetric functions and Hall polynomials. — Oxford Math. Monographs, Oxford University Press., 1979.

Guo-Niu HAN,

Institut de Recherche Mathématique Avancée, ULP et CNRS, 7, rue René-Descartes, F-67084 Strasbourg, France.

email : guoniu@math.u-strasbg.fr