Correspondance de Robinson-Schensted

En mathématiques, et notamment en combinatoire algébrique, la correspondance de Robinson-Schensted est une bijection entre permutations et paires de tableaux de Young standard de même forme. Cette bijection peut être décrite de diverses manières, toutes algorithmiques. Elle a de nombreuses propriétés remarquables, et des applications en combinatoire et dans d'autres domaines comme la représentation des groupes finis. La correspondance a été généralisée de plusieurs façons, notamment par Knuth en ce qui est connu maintenant comme la correspondance de Robinson-Schensted-Knuth, et plus généralement encore en des objets appelés figures par Zelevinsky.

La description la plus simple de la correspondance est par l'algorithme de Schensted (Schensted, 1961), une procédure qui construit un tableau par insertion successive des valeurs d'une permutation selon une règle précises, et un deuxième tableau qui enregistre l'évolution de la forme pendant la construction. La correspondance a été décrite, dans une forme différente, bien plus tôt par Gilbert de Beauregard Robinson dans (Robinson,1938), dans une tentative de preuve de la règle de Littlewood-Richardson. La correspondance est souvent appelée l'algorithme de Robinson-Schensted , alors que la procédure employée par Robinson est radicalement différente de celle de Schensted, et est presque totalement oubliée. Parmi les autres méthodes pour définir la correspondance, il y a un algorithme non déterministe basé sur le jeu de taquin de Schützenberger.

La nature bijective de la correspondance se reflète dans des identités combinatoires comme :

${\displaystyle \sum _{\lambda }(f^{\lambda })^{2}=n!}$

où la somme est sur les partitions de ${\displaystyle n}$ (ou des diagrammes de Young avec ${\displaystyle n}$ carrés), et ${\displaystyle f^{\lambda }}$ est le nombre de tableaux de Young standard de forme ${\displaystyle \lambda }$.

L'algorithme de Schensted part d'une permutation ${\displaystyle \sigma }$ écrite en forme fonctionnelle :

${\displaystyle \sigma ={\begin{pmatrix}1&2&3&\cdots &n\\\sigma _{1}&\sigma _{2}&\sigma _{3}&\cdots &\sigma _{n}\end{pmatrix}}}$,

où ${\displaystyle \sigma _{i}=\sigma (i)}$, et procède par la construction séquentielle d'une suite de paires ordonnées de tableaux de Young de la même forme, notées :

${\displaystyle (P_{0},Q_{0}),\quad (P_{1},Q_{1}),\quad (P_{2},Q_{2}),\quad \ldots \,,\quad (P_{n},Q_{n})}$,

où ${\displaystyle P_{0}=Q_{0}}$ est le tableau vide. Les tableaux recherchés sont ${\displaystyle P=P_{n}}$ et ${\displaystyle Q=Q_{n}}$. À partir de ${\displaystyle P_{i-1}}$ on construit ${\displaystyle P_{i}}$ en insérant ${\displaystyle \sigma _{i}}$ dans ${\displaystyle P_{i-1}}$, puis ${\displaystyle Q_{i}}$ en ajoutant la valeur ${\displaystyle i}$ à ${\displaystyle Q_{i-1}}$ dans le carré qui vient d'être ajouté par l'insertion, de sorte que ${\displaystyle P_{i}}$ et ${\displaystyle Q_{i}}$ ont la même forme. Comme les tableaux ${\displaystyle Q_{i}}$ jouent un rôle plus secondaire, le tableau ${\displaystyle Q_{n}}$ (dont les ${\displaystyle Q_{i}}$ se déduisent immédiatement) est appelé le « tableau enregistrement », alors que les tableaux ${\displaystyle P_{i}}$ sont appelés les « tableaux d'insertion ».

La procédure de base, qui insère une valeur ${\displaystyle \sigma _{i}}$, est appelée l'« insertion de Schensted » ou « insertion en ligne » (pour la distinguer d'une variante appelée l'insertion en colonne). La procédure opère sur des « tableaux standard incomplets » : ce sont des tableaux croissants en ligne et en colonne, mais qui ne contiennent pas nécessairement les entiers consécutifs de 1 à la taille du tableau.

Étant donné un tableau (incomplet) ${\displaystyle T}$ et une valeur ${\displaystyle x}$ qui ne figure pas dans ${\displaystyle T}$, l'insertion de Schensted construit un tableau ${\displaystyle T\leftarrow x}$ et un carré ${\displaystyle s}$ qui contient les coordonnées de la nouvelle cellule.

La valeur ${\displaystyle x}$ figure dans la première ligne de ${\displaystyle T\leftarrow x}$, soit parce qu'elle a été ajoutée à la fin (c'est le cas quand toutes les valeurs présentes sont plus petites que ${\displaystyle x}$), soit parce qu'elle parce qu'elle a remplacé la plus petite valeur ${\displaystyle y>x}$ dans la première ligne de ${\displaystyle T}$. Dans le premier cas, ${\displaystyle s}$ est le carré où ${\displaystyle x}$ a été ajouté, et la procédure s'arrête. Dans le deuxième cas, la procédure continue, mais cette fois-ci on construit ${\displaystyle T'\leftarrow y}$, où ${\displaystyle T'}$ est le tableau privé de sa première ligne, par l'insertion de ${\displaystyle y}$ dans la deuxième ligne de ${\displaystyle T}$, et ainsi de suite jusqu'à ce que le premier cas s'applique, ce qui est certainement le cas lorsque l'on arrive à une ligne vide. La case ${\displaystyle s}$ est le carré qui a été ajouté à la forme.

Une description formelle de l'algorithme d'insertion de ${\displaystyle x}$ dans ${\displaystyle T}$ est donnée par Knuth^[1]. Elle est légèrement adaptée ici :

1. Soit ${\displaystyle i=1}$
2. Soit ${\displaystyle j}$ le plus petit indice telle que ${\displaystyle x<T_{i,j}}$ ou, sinon, soit ${\displaystyle j}$ la longueur de la ligne plus 1.
3. Si la cellule ${\displaystyle (i,j)}$ est vide dans ${\displaystyle T}$, poser ${\displaystyle T_{i,j}=x}$ et ${\displaystyle s=(i,j)}$ et terminer.
4. Sinon échanger les valeurs ${\displaystyle x}$ et ${\displaystyle T_{i,j}}$, augmenter ${\displaystyle i}$ de 1 et continuer à l'étape 2.

Le fait que le tableau ${\displaystyle T\leftarrow x}$ a des lignes croissantes est évident par construction. En revanche, que ses colonnes sont aussi croissantes demande réflexion, notamment parce que les colonnes ne sont jamais comparées durant l'algorithme. Lorsque ${\displaystyle x}$ remplace la valeur ${\displaystyle y=T_{i,j}}$ dans la cellule ${\displaystyle (i,j)}$, on a ${\displaystyle y>x}$. La nouvelle valeur est donc inférieure à l'ancienne, et donc inférieure à la valeur ${\displaystyle T_{i+1,j}}$ si la cellule ${\displaystyle (i+1,j)}$ n'est pas vide. Vérifions que l'insertion de ${\displaystyle y}$ laisse les colonnes croissantes. Comme on a ${\displaystyle y<T_{i+1,j}}$, l'insertion de ${\displaystyle y}$ ne peut se faire que parmi les ${\displaystyle T_{i+1,j'}}$ pour ${\displaystyle j'\leq j}$. Lorsque ${\displaystyle y}$ remplace une de ces valeurs ${\displaystyle T_{i+1,j'}}$, on a ${\displaystyle T_{i,j'}<x<y}$, donc la nouvelle valeur ${\displaystyle y}$ de la cellule ${\displaystyle T_{i+1,j'}}$ est inférieure à ${\displaystyle T_{i,j'}}$, ce qui montre que le tableau est croissant en colonne.

On vient de constater que les indices de colonnes décroissent lors des insertions dans les lignes successives (dans l'exemple, les colonnes sont successivement 3, 2, 1). Ceci montre que le nombre total de cellules à examiner lors de la construction d'un tableau ${\displaystyle T\leftarrow x}$ est au plus égal au nombre de lignes plus le nombre de colonnes du tableau.

L'algorithme de Schensted complet, appliqué à une permutation ${\displaystyle \sigma }$, procède comme suit :

1. initialiser ${\displaystyle P}$ et ${\displaystyle Q}$ au tableau vide ;
2. pour ${\displaystyle i}$ variant de 1 à ${\displaystyle n}$, calculer le tableau ${\displaystyle P\leftarrow x}$ et la cellule ${\displaystyle s}$ par l'insertion de Schensted, remplacer ${\displaystyle P}$ par ${\displaystyle P\leftarrow x}$ et ajouter l'entrée ${\displaystyle i}$ à la cellule ${\displaystyle s}$ du tableau ${\displaystyle Q}$;
3. terminer et retourner la paire ${\displaystyle (P,Q)}$.

L'algorithme produit une paire de tableaux de Young standard; sa complexité en temps est au plus ${\displaystyle O(n^{2})}$.

On peut voir que chaque paire ${\displaystyle (P,Q)}$ de tableaux de Young standard de même forme provient d'une permutation qui permet de la construire. Esquissons l'inversion de la construction. Pour trouver cette permutation, on opère en retraçant en sens inverse, les étapes qui auraient pu donner la paire ${\displaystyle (P,Q)}$. C'est le tableau Q qui donne la cellule où la dernière insertion s'est terminée. Ensuite, on remonte les lignes pour trouver les cellules contenant les valeurs remplacées; arrivé eu première ligne, on obtient la valeur ${\displaystyle \sigma _{n}}$ de la permutation.

Ainsi, la procédure et son inverse juste esquissée donne une bijection effective entre permutations et paires de tableaux de Young standard de même forme: c'est la correspondance de Robinson-Schensted.

Une construction géométrique de la correspondance de Robinson-Schensted entre permutations et paires de tableaux de Young standard de même forme a été donnée par Viennot.

Une des propriétés fondamentales, mais qui n'est pas une conséquence évidente de la construction, est la symétrie :

• Si la correspondance de Robinson-Schensted associe les tableaux ${\displaystyle (P,Q)}$ à la permutation ${\displaystyle \sigma }$, elle associe la paire ${\displaystyle (Q,P)}$ à la permutation ${\displaystyle \sigma ^{-1}}$.

Cette propriété peut être prouvée par exemple en faisant appel à la construction géométrique de Viennot.

Voici d'autres propriétés. Soit ${\displaystyle (P,Q)}$ la paire associée à la permutation ${\displaystyle \sigma =(\sigma _{1},\ldots ,\sigma _{n})}$ :

• Soit ${\displaystyle (P',Q')}$ la paire de tableaux associée à la permutation retournée ${\displaystyle (\sigma _{n},\ldots ,\sigma _{1})}$. Le tableau ${\displaystyle P'}$ est le transposé du tableau ${\displaystyle P}$, et le tableau ${\displaystyle Q'}$ est déterminé uniquement par ${\displaystyle Q}$ : c'est le transposé du tableau obtenu, à partir de ${\displaystyle Q}$, par l'involution de Schützenberger.
• La longueur de la plus longue sous-suite croissante de ${\displaystyle \sigma _{1},\ldots ,\sigma _{n}}$ est la longueur de la première ligne de ${\displaystyle P}$ (ou de ${\displaystyle Q}$).
• La longueur de la plus longue sous-suite décroissante de ${\displaystyle \sigma _{1},\ldots ,\sigma _{n}}$ est la longueur de la première colonne de ${\displaystyle P}$ (ou de ${\displaystyle Q}$), comme il suit des deux propriétés précédentes.

Enfin, la bijection entre paires de tableaux standard et permutations donne la preuve de l'identité combinatoire déjà annoncées plus haut :

${\displaystyle \sum _{\lambda \in {\mathcal {P}}_{n}}(f^{\lambda })^{2}=n!}$

où ${\displaystyle {\mathcal {P}}_{n}}$ est l'ensemble des partitions de ${\displaystyle n}$ (ou des diagrammes de Young avec ${\displaystyle n}$ carrés), et ${\displaystyle f^{\lambda }}$ est le nombre de tableaux de Young standard de forme ${\displaystyle \lambda }$. Une autre preuve peut être obtenue à l’aide du treillis de Young.

• William Fulton, Young tableaux, Cambridge University Press, coll. « London Mathematical Society Student Texts » (n^o 35), 1997 (ISBN 978-0-521-56144-0 et 978-0-521-56724-4, MR 1464693)
• Donald E. Knuth, « Permutations, matrices, and generalized Young tableaux », Pacific Journal of Mathematics, vol. 34,‎ 1970, p. 709–727 (ISSN 0030-8730, MR 0272654, lire en ligne)
• Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, Second Edition, Addison-Wesley, 2005 (ISBN 0-201-89685-0, présentation en ligne)
• Gilbert de Beauregard Robinson, « On the Representations of the Symmetric Group », American Journal of Mathematics, vol. 60, n^o 3,‎ 1938, p. 745–760 (ISSN 0002-9327, DOI 10.2307/2371609, JSTOR 2371609) Zentralblatt 0019.25102
• (en) Bruce E. Sagan, The Symmetric Group : Representations, Combinatorial Algorithms, and Symmetric Functions, New York/Berlin/Heidelberg etc., Springer, coll. « Graduate Texts in Mathematics » (n^o 203), 2001, 2^e éd., 238 p. (ISBN 0-387-95067-2, lire en ligne)
• (en) Richard P. Stanley, Enumerative Combinatorics, vol. 2 [détail des éditions] (présentation en ligne) lien Math Reviews
• Craige Schensted, « Longest increasing and decreasing subsequences », Canadian Journal of Mathematics, vol. 13,‎ 1961, p. 179–191 (ISSN 0008-414X, DOI 10.4153/CJM-1961-015-3, MR 0121305, lire en ligne)
• Andrei V. Zelevinsky, « A generalization of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence », Journal of Algebra, vol. 69, n^o 1,‎ 1981, p. 82–94 (ISSN 0021-8693, DOI 10.1016/0021-8693(81)90128-9, MR 613858)
• Antoine Abram et Christophe Reutenauer, « The stylic monoid », Semigroup Forum, vol. 105, n^o 1,‎ 1^er août 2022, p. 1–45 (DOI 10.1007/s00233-022-10285-3, arXiv 2106.06556)
• Christian Choffrut, « Grammic monoids with three generators », Semigroup Forum, vol. 105, n^o 3,‎ 1^er décembre 2022, p. 680–692 (DOI 10.1007/s00233-022-10316-z, arXiv 2207.13043)

• Construction géométrique de Viennot : elle donne une interprétation par diagrammes de la correspondance.
• Treillis de Young
• Monoïde plaxique
• Monoïde chinois

(en) Mark A. A. van Leeuwen, « Robinson–Schensted correspondence », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)

• Portail des mathématiques