(P,Q) versus (Q,P)

L'échange des tableaux P et Q donne un résultat très simple :

Théorème : la permutation associée à la paire de tableaux (Q, P) est l'inverse π ^-1 de la permutation π associée à la paire (P, Q).

Dans l'algorithme de Robinson-Schensted les éléments du tableau P sont les éléments de la permutation π alors qu'on enregistre leurs places dans le tableau Q, d'où l'impression que ce théorème est évident. Mais les éléments de P ne cessent de se déplacer à mesure qu'on construit le tableau en lui appliquant de façon répétée les règles du jeu de taquin, tandis que ceux de Q ne bougent plus, d'où le trouble après réflexion. Et pourtant le théorème est vrai, des preuves variées sont disponibles, et beaucoup d'élèves de Schützenberger ont cherché une preuve naturelle ; les avis divergent sur le succès de ces preuves, c'est-à-dire sur leur capacité à rendre le théorème évident. Cette page va seulement illustrer le théorème sur notre exemple de la permutation π = 3 7 4 1 2 6 5.

Comme l'élément numéro 7 occupe la place numéro 2, le dernier élément de la permutation inverse π ^-1 est donc 2, qui devrait apparaître en dilatant le tableau Q :

En haut le tableau P pilote la dilatation de Q : comme le plus grand élément de P est situé dans la première colonne, on place une cellule verte au-dessus de chaque colonne de Q sauf la première, et on dilate en cliquant (shift-clic) sur ces cellules de gauche à droite ; le résultat est à droite, c'est bien la cellule numéro 2 qui est sortie sur la première ligne, le miracle a eu lieu.

On peut continuer l'exécution de cet algorithme pour reconstruire la permutation inverse π ^-1, ce qui indique que le tableau P privé de son plus grand élément (ici 7) et le tableau Q de droite (privé de la cellule numéro 2 qui vient d'en être extraite) sont associés à la permutation 3 4 1 2 6 5, c'est-à-dire à la permutation π privée de son plus grand élément. D'où cette version duale de l'algorithme de construction des tableaux P et Q associés à une permutation — prouver que cette version est correcte, c'est-à-dire fournit le même résultat que la version classique de l'algorithme de Robinson-Schensted, équivaut à prouver le théorème énoncé en haut de page :

Algorithme : soit π une permutation de n - 1 éléments et π' la permutation obtenue en insérant la valeur n en position i dans π ; la paire de tableaux P', Q' associée à π' se déduit de la paire P, Q associée à π de la façon suivante :

• ajouter 1 à tous les éléments de Q supérieurs ou égaux à i,
• insérer i dans le tableau Q en utilisant le jeu de taquin (ou la version classique de l'algorithme de Robinson-Schensted), ce qui fournit Q',
• ajouter n au tableau P dans le coin créé en passant de Q à Q'.

Illustration : construisons les tableaux associés à la permutation 3 7 4 1 2 6 5 avec cet algorithme dual. On commence par les éléments 1 et 2 qui sont dans l'ordre, puis on insère 3 en position 1 :

A gauche ci-dessus on a le tableau P et à droite le tableau Q dont on a incrémenté les valeurs avant d'insérer 1 (en haut) ; en bas on a le résultat de l'algorithme. Continuons, il faut maintenant insérer 4 en position 2 :

On a incrémenté les valeurs 2 et 3 du tableau Q avant d'insérer 2 (en haut à droite sur le cliché ci-dessus). Le résultat de l'algorithme (en bas) a une particularité, les tableaux P et Q sont égaux, ce qui indique que la permutation 3 4 1 2 est une involution, ce qui est bien le cas, car la décomposition en cycles de cette permutation est (1 3) (2 4). Continuons, il faut maintenant insérer 5 en position 5 :

L'algorithme est trivial dans ce cas, et la permutation reste une involution. Insérons 6 en position 5 :

C'est toujours une involution — on a ajouté le cycle (5 6). Insérons enfin 7 en position 2 :

Ouf ce n'est plus une involution — la décomposition en cycles de cette permutation est (1 3 4) (2 7 5) (6) — et nous avons bien retrouvé les tableaux P et Q obtenus avec la version directe de l'algorithme ; cette dernière étape est par définition l'inverse de la dilatation décrite en haut de page.