Voir la source de Correspondance de Robinson-Schensted

En [[mathématiques]], et notamment en [[combinatoire algébrique]], la '''correspondance de Robinson-Schensted''' est une [[bijection]] entre [[permutation]]s et paires de [[tableau de Young|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 [[figure]]s par Zelevinsky.

La description la plus simple de la correspondance est par l''''algorithme de [[Craige Schensted|Schensted]]''' ({{harvsp|Schensted, 1961|réf=Schensted}}), 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 {{harvsp|(Robinson,1938)|réf=Robinson}}, 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 :
:<math>\sum_{\lambda} (f^\lambda)^2= n!</math>
où la somme est sur les [[Partition d'un entier|partitions]] de <math>n</math> (ou des [[tableau de Young|diagrammes de Young]] avec <math>n</math> carrés), et <math>f^\lambda</math> est le nombre de tableaux de Young standard de forme <math>\lambda</math>.

== L'algorithme de Schensted ==

L'algorithme de Schensted part d'une permutation <math>\sigma</math> écrite en forme fonctionnelle :

:<math>\sigma=\begin{pmatrix}1 & 2 & 3 & \cdots & n\\ \sigma_1 & \sigma_2 & \sigma_3 & \cdots & \sigma_n \end{pmatrix}</math>,

où <math>\sigma_i=\sigma(i)</math>, 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 :

:<math>(P_0,Q_0),\quad(P_1,Q_1),\quad(P_2,Q_2),\quad\ldots\,,\quad(P_n,Q_n)</math>,

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

=== Insertion ===
[[Fichier:Young-Schensted.png|vignette|Insertion de 4 dans un tableau incomplet (notation anglaise): <br />sur la première ligne, 4 remplace 5<br />sur la deuxième ligne, 5 remplace 8<br />et 8 crée une troisième ligne.]]
La procédure de base, qui insère une valeur <math>\sigma_i</math>, 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) <math>T</math> et une valeur <math>x</math> qui ne figure pas dans <math>T</math>, l'insertion de Schensted construit un tableau <math>T\leftarrow x</math> et un carré <math>s</math> qui contient les coordonnées de la nouvelle cellule.

La valeur <math>x</math> figure dans la première ligne de <math>T\leftarrow x</math>, soit parce qu'elle a été ajoutée à la fin (c'est le cas quand toutes les valeurs présentes sont plus petites que <math>x</math>), soit parce qu'elle parce qu'elle a remplacé la plus petite valeur <math>y>x</math> dans la première ligne de <math>T</math>. Dans le premier cas, <math>s</math> est le carré où <math>x</math> 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 <math>T'\leftarrow y</math>, où <math>T'</math> est le tableau privé de sa première ligne, par l'insertion de <math>y</math> dans la deuxième ligne de <math>T</math>, 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 <math>s</math> est le carré qui a été ajouté à la forme.

Une description formelle de l'algorithme d'insertion de <math>x</math> dans <math>T</math> est donnée par Knuth<ref name=Kn>{{harv|Knuth, 2005|réf=Knuth3}}, pages 49-50 </ref>. Elle est légèrement adaptée ici :
# Soit <math>i=1</math>
# Soit <math>j</math> le plus petit indice telle que <math>x<T_{i,j}</math> ou, sinon, soit <math>j</math> la longueur de la ligne plus 1.
# Si la cellule <math>(i,j)</math> est vide dans <math>T</math>, poser <math>T_{i,j}=x</math> et <math>s=(i,j)</math> et terminer.
# Sinon échanger les valeurs <math>x</math> et <math>T_{i,j}</math>, augmenter <math>i</math> de 1 et continuer à l'étape 2.

=== Correction ===

Le fait que le tableau <math>T\leftarrow x</math> 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 <math>x</math> remplace la valeur <math>y=T_{i,j}</math> dans la cellule <math>(i,j)</math>, on a <math>y>x</math>. La nouvelle valeur est donc inférieure à l'ancienne, et donc inférieure à la valeur <math>T_{i+1,j}</math> si la cellule <math>(i+1,j)</math> n'est pas vide. Vérifions que l'insertion de <math>y</math> laisse les colonnes croissantes. Comme on a <math>y < T_{i+1,j}</math>, l'insertion de <math>y</math> ne peut se faire que parmi les <math>T_{i+1,j'}</math> pour <math>j'\le j</math>. Lorsque <math>y</math> remplace une de ces valeurs <math>T_{i+1,j'}</math>, on a <math>T_{i,j'}<x<y</math>, donc la nouvelle valeur <math>y</math> de la cellule <math>T_{i+1,j'}</math> est inférieure à <math>T_{i,j'}</math>, 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 <math>T\leftarrow x</math> est au plus égal au nombre de lignes plus le nombre de colonnes du tableau.

=== La construction complète ===

L'algorithme de Schensted complet, appliqué à une permutation <math>\sigma</math>, procède comme suit :
# initialiser <math>P</math> et <math>Q</math> au tableau vide ;
# pour <math>i</math> variant de 1 à <math>n</math>, calculer le tableau <math>P\leftarrow x</math> et la cellule <math>s</math> par l'insertion de Schensted, remplacer <math>P</math> par <math>P\leftarrow x</math> et ajouter l'entrée <math>i</math> à la cellule <math>s</math> du tableau <math>Q</math>;
# terminer et retourner la paire <math>(P,Q)</math>.

L'algorithme produit une paire de tableaux de Young standard; sa [[complexité en temps]] est au plus <math>O(n^2)</math>.

=== Inversion de la construction ===

On peut voir que chaque paire <math>(P,Q)</math> 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 <math>(P,Q)</math>. 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 <math>\sigma_n</math> 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.

=== Construction géométrique de Viennot ===

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.

{{article détaillé|construction géométrique de Viennot}}

== Propriétés ==

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 <math>(P,Q)</math> à la permutation <math>\sigma</math>, elle associe la paire <math>(Q,P)</math> à la permutation <math>\sigma^{-1}</math>.
: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 <math>(P,Q)</math> la paire associée à la permutation <math>\sigma=(\sigma_1,\ldots,\sigma_n)</math> :

* Soit <math>(P',Q')</math> la paire de tableaux associée à la permutation retournée <math>(\sigma_n,\ldots,\sigma_1)</math>. Le tableau <math>P'</math> est le transposé du tableau <math>P</math>, et le tableau <math>Q'</math> est déterminé uniquement par <math>Q</math> : c'est le transposé du tableau obtenu, à partir de <math>Q</math>, par l'[[jeu de taquin de Schützenberger|involution de Schützenberger]].
* La longueur de la plus longue [[sous-suite]] croissante de <math>\sigma_1,\ldots,\sigma_n</math> est la longueur de la première ligne de <math>P</math> (ou de <math>Q</math>).
* La longueur de la plus longue sous-suite décroissante de <math>\sigma_1,\ldots,\sigma_n</math> est la longueur de la première colonne de <math>P</math> (ou de <math>Q</math>), 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 :
:<math>\sum_{\lambda\in\mathcal{P}_n} (f^\lambda)^2= n!</math>
où <math>\mathcal{P}_n</math> est l'ensemble des [[Partition d'un entier|partitions]] de <math>n</math> (ou des [[tableau de Young|diagrammes de Young]] avec <math>n</math> carrés), et <math>f^\lambda</math> est le nombre de tableaux de Young standard de forme <math>\lambda</math>. Une autre preuve peut être obtenue à l’aide du [[treillis de Young]].

== Annexes ==

=== Références ===
{{Références}}
{{Traduction/Référence|en|Robinson–Schensted correspondence|477143442|type=note}}

=== Bibliographie ===
* {{Ouvrage| prénom1=William| nom1=Fulton| titre=Young tableaux| éditeur=Cambridge University Press| collection=London Mathematical Society Student Texts| numéro dans collection=35| année=1997| isbn=978-0-521-56144-0| isbn2=978-0-521-56724-4| math reviews=1464693}}
* {{article | nom1=Knuth | prénom1=Donald E. | lien auteur=Donald Knuth | titre=Permutations, matrices, and generalized Young tableaux | url=http://projecteuclid.org/euclid.pjm/1102971948 | math reviews = 0272654| id={{MathSciNet | id = 0272654}} | année=1970 | journal=Pacific Journal of Mathematics | issn=0030-8730 | volume=34 | pages=709–727}}
* {{Ouvrage
| auteur1=Donald E. Knuth
| titre=[[The Art of Computer Programming]]
| volume=3
| titre volume=Sorting and Searching, Second Edition
| éditeur=Addison-Wesley
| année=2005
| isbn=0-201-89685-0
| présentation en ligne=http://www-cs-faculty.stanford.edu/~knuth/taocp.html
| id=Knuth3
}}
* {{article|prénom1=Gilbert de Beauregard |nom1=Robinson
  |titre=On the Representations of the Symmetric Group
  |journal=American Journal of Mathematics|volume=60|numéro=3|année=1938|pages=745–760
  | issn=0002-9327| jstor=2371609| doi=10.2307/2371609 
  |id=Robinson}} [http://www.zentralblatt-math.org/zmath/en/search/?q=an:0019.25102 Zentralblatt 0019.25102]
* {{Ouvrage|langue=en|prénom1=Bruce E.|nom1=Sagan|titre=The Symmetric Group : Representations, Combinatorial Algorithms, and Symmetric Functions|éditeur=Springer|collection=Graduate Texts in Mathematics|lieu=New York/Berlin/Heidelberg etc.|numéro dans collection=203|année=2001|numéro d'édition=2|pages totales=238|isbn=0-387-95067-2|lire en ligne=https://books.google.com/books?id=Jm-HBaMdt8sC&printsec=frontcover}}
* {{Enumerative Combinatorics |vol=2}} {{MathSciNet | id = 1676282}}
* {{article|prénom1=Craige |nom1= Schensted|titre=Longest increasing and decreasing subsequences
  |journal=Canadian Journal of Mathematics|volume=13|numéro=|année=1961
  |pages=179–191| doi=10.4153/CJM-1961-015-3
  |url=https://books.google.com/?id=G3sZ2zG8AiMC
  | issn=0008-414X|math reviews = 0121305|id=Schensted}}
* {{article | auteur=Andrei V. Zelevinsky  | titre=A generalization of the Littlewood–Richardson rule and the Robinson–Schensted–Knuth correspondence | doi=10.1016/0021-8693(81)90128-9      | année=1981 | journal=Journal of Algebra | issn=0021-8693 | volume=69 | numéro=1 | pages=82–94|math reviews = 613858}}
* {{Article |prénom1=Antoine |nom1=Abram |prénom2=Christophe |nom2=Reutenauer 
 | titre=The stylic monoid 
 |périodique=Semigroup Forum |volume=105 |numéro=1 |date=2022-08-01 
 |doi=10.1007/s00233-022-10285-3 
 |pages=1–45|arxiv= 2106.06556}}
* {{Article |prénom1=Christian |nom1=Choffrut 
 |titre=Grammic monoids with three generators 
 |périodique=Semigroup Forum |volume=105 |numéro=3 |date=2022-12-01 
 |doi=10.1007/s00233-022-10316-z 
 |pages=680–692|arxiv = 2207.13043}}

=== Articles connexes ===
* [[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]]

=== Lien externe ===
{{EncycloMath|prénom1=Mark A. A.|nom1=van Leeuwen|id=Robinson%E2%80%93Schensted_correspondence&oldid=17200|titre=Robinson–Schensted correspondence}}

{{Portail|mathématiques}}

[[Catégorie:Combinatoire algébrique]]
[[Catégorie:Permutation]]