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 :

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

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

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

,

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

,

est le tableau vide. Les tableaux recherchés sont et . À partir de on construit en insérant dans , puis en ajoutant la valeur à dans le carré qui vient d'être ajouté par l'insertion, de sorte que et ont la même forme. Comme les tableaux jouent un rôle plus secondaire, le tableau (dont les se déduisent immédiatement) est appelé le « tableau enregistrement », alors que les tableaux sont appelés 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 , 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) et une valeur qui ne figure pas dans , l'insertion de Schensted construit un tableau et un carré qui contient les coordonnées de la nouvelle cellule.

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

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

  1. Soit
  2. Soit le plus petit indice telle que ou, sinon, soit la longueur de la ligne plus 1.
  3. Si la cellule est vide dans , poser et et terminer.
  4. Sinon échanger les valeurs et , augmenter de 1 et continuer à l'étape 2.

Correction[modifier | modifier le code]

Le fait que le tableau 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 remplace la valeur dans la cellule , on a . La nouvelle valeur est donc inférieure à l'ancienne, et donc inférieure à la valeur si la cellule n'est pas vide. Vérifions que l'insertion de laisse les colonnes croissantes. Comme on a , l'insertion de ne peut se faire que parmi les pour . Lorsque remplace une de ces valeurs , on a , donc la nouvelle valeur de la cellule est inférieure à , 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 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 , procède comme suit :

  1. initialiser et au tableau vide ;
  2. pour variant de 1 à , calculer le tableau et la cellule par l'insertion de Schensted, remplacer par et ajouter l'entrée à la cellule du tableau ;
  3. terminer et retourner la paire .

L'algorithme produit une paire de tableaux de Young standard; sa complexité en temps est au plus .

Inversion de la construction[modifier | modifier le code]

On peut voir que chaque paire 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 . 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 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 à la permutation , elle associe la paire à la permutation .
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 la paire associée à la permutation  :

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

est l'ensemble des partitions de (ou des diagrammes de Young avec carrés), et est le nombre de tableaux de Young standard de forme . 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]

Articles connexes[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, (ISBN 978-1556080104, lire en ligne)