Correspondance de Robinson-Schensted

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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, toute 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 successsive 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 un 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  :

\sum_{\lambda} (f^\lambda)^2= n!

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

L'algorithme de Schensted[modifier | modifier le code]

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

\sigma=\begin{pmatrix}1 & 2 & 3 & \cdots & n\\ \sigma_1 & \sigma_2 & \sigma_3 & \cdots & \sigma_n \end{pmatrix},

\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 :

(P_0,Q_0),\quad(P_1,Q_1),\quad(P_2,Q_2),\quad\ldots\,,\quad(P_n,Q_n),

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

Insertion[modifier | modifier le code]

Insertion de 4 dans un tableau incomplet (notation anglaise):
sur la première ligne, 4 remplace 7
sur la deuxième ligne, 7 remplace 8
et 8 crée une troisième ligne.

La procédure de base, qui insère une valeur \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) T et une valeur x qui ne figure pas dans T, l'insertion de Schensted construit un tableau T\leftarrow x et un carré s qui contient les coordonnées de la nouvelle cellule.

La valeur x figure dans la première ligne de 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 x), soit parce qu'elle parce qu'elle a remplacé la plus petite valeur y>x dans la première ligne de T. Dans le premier cas, s est le carré où 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 T'\leftarrow y, où T' est le tableau privé de sa première ligne, par l'insertion de y dans la deuxième ligne de 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 s est le carré qui a été ajouté à la forme.

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

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

Correction[modifier | modifier le code]

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

La construction complète[modifier | modifier le code]

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

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

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

Inversion de la construction[modifier | modifier le code]

On peut voir que chaque paire (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 (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 \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.

Construction géométrique de Viennot[modifier | modifier le code]

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.

Propriétés[modifier | modifier le code]

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

  • Soit (P',Q') la paire de tableaux associée à la permutation retournée (\sigma_n,\ldots,\sigma_1). Le tableau P' est le transposé du tableau P, et le tableau Q' est déterminé uniquement par Q : c'est le transposé du tableau obtenu, à partir de Q, par l'involution de Schützenberger.
  • La longueur de la plus longue sous-suite croissante de \sigma_1,\ldots,\sigma_n est la longueur de la première ligne de P (ou de Q).
  • La longueur de la plus longue sous-suite décroissante de \sigma_1,\ldots,\sigma_n est la longueur de la première colonne de P (ou de 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 :

\sum_{\lambda\in\mathcal{P}_n} (f^\lambda)^2= n!

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

Annexes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. (Knuth, 2005), pages 49-50

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Robinson–Schensted correspondence » (voir la liste des auteurs)

Bibliographie[modifier | modifier le code]

Article connexe[modifier | modifier le code]

Lien externe[modifier | modifier le code]

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