Redresser une permutation
Si vous avez parcouru les pages précédentes et si vous avez réduit quelques tableaux avec l'animation Flash, vous admirez certainement le métier de redresseur de tableaux, mais peut-être vous posez-vous des questions sur son utilité. Cette page et les suivantes sont consacrées à l'application de cette technique aux permutations. Il existe deux façons simples et naturelles de représenter une permutation par un tableau, illustrées ci-contre à droite sur le cas de la permutation :
3 7 4 1 2 6 5
A gauche la permutation est représentée en diagonale, et à droite sous forme d'un serpent : un élément est ajouté à droite du précédent s'il est supérieur, et en-dessous s'il est inférieur. Ces deux représentations sont équivalentes, on passe facilement de l'une à l'autre par une suite de réductions et/ou de dilatations, essayez avec l'animation Flash.
Un petit programme qui effectue le calcul résultant de la formule des équerres indique qu'il existe plus d'un milliard (exactement 1 100 742 656) façons de réduire le tableau diagonal, contre seulement 6 pour le serpent — en écrivant les 6 tableaux de forme [3 1 1] on voit vite qu'il s'agit de choisir deux éléments parmi quatre — et quel que soit l'ordre des réductions on obtient le tableau redressé P ci-dessous.
Ce tableau P de forme [3 3 1] résulte donc du tri en deux dimensions de la permutation. Lors d'un tri ordinaire (en une dimension) des éléments d'une permutation de 7 éléments, on obtient toujours la suite 1 2 3 4 5 6 7 et on perd toute information sur la permutation de départ. Ici le résultat est nettement plus subtil et il est naturel de se demander quelle est l'information cachée dans la permutation et révélée par ce tableau.
Le plus étonnant est que cette idée d'associer des tableaux aux permutations est apparue dès 1938 dans un article de Robinson sur les représentations du groupe symétrique, mais n'a pas eu de suite. Une guerre mondiale et une quinzaine d'années plus tard, en 1961 précisément, Schensted publie un article sur les sous-suites croissantes d'une permutation dans lequel il décrit explicitement un algorithme qui calcule le tableau P et répond (partiellement) à la question qui termine le paragraphe précédent : P nous révèle les plus longues sous-suites croissantes de la permutation. Par je ne sais quelle intuition extraordinaire caractéristique du personnage, Schützenberger s'est intéressé au sujet, a découvert que l'algorithme de Schensted possède une description en termes de jeu de taquin, en a formulé et démontré des propriétés étonnantes — à la fois simples et pas du tout évidentes — et … a redécouvert l'article de Robinson ; dans un compte-rendu de 1971 à l'Académie des Sciences il écrit :
Je profite de cette occasion pour m'excuser d'avoir commis dans une publication antérieure une attribution incorrecte de ce résultat par ignorance du mémoire de G. de B. Robinson.
L'algorithme de Schensted a du coup été rebaptisé algorithme de Robinson-Schensted et a fait l'objet de très nombreuses recherches et applications, en particulier en théorie des fonctions symétriques. On en trouve facilement la description sur Internet, y compris sous forme animée, ici disons seulement que son principe est d'insérer un nouvel élément dans un tableau droit : cet élément est inséré dans la première ligne du tableau, en général à la place d'un autre qu'il chasse dans la seconde ligne, et ainsi de suite. Voyons comment on peut employer le jeu de taquin (dont la définition est beaucoup plus simple et naturelle) pour simuler cet algorithme.
Il existe une façon particulièrement intéressante de réduire le tableau diagonal : choisir toujours le creux le plus haut. Cela revient à réduire d'abord le tableau constitué des cellules numérotées 3 et 7, puis à traiter la cellule numéro 4, et ainsi de suite. A mesure qu'on ajoute des éléments à la permutation, on calcule le nouveau tableau redressé ; utlisez l'animation Flash et vous obtiendrez les tableaux suivants :
On translate vers la gauche la diagonale 1 2 6 5 avant de continuer :
On translate vers la gauche la diagonale 2 6 5 etc.
Examinons maintenant les tableaux droits associés aux suites successives 3, 3 7, 3 7 4, 3 7 4 1… :
On remarque que les formes de ces tableaux sont croissantes — autrement dit chaque diagramme est inclus dans son successeur :
La page suivante est consacrée à l'explication et à l'exploitation de cette observation. Si vous utilisez l'animation Flash (ce que j'espère) vous souhaitez probablement sauvegarder parfois la configuration obtenue : il suffit de cliquer avec le bouton droit sur une cellule et de choisir l'option Save dans le menu déroulant ; pour recharger plus tard cette configuration, affichez le menu attaché à la même cellule (ie même numéro), et sélectionnez Load.