Extraire une permutation

La cellule numéro 5 est sortie du tableau P, on la décale d'une case à droite pour qu'elle ne gêne pas la suite des opérations, et on recommence avec ce nouveau tableau P et le tableau Q privé de la cellule numéro 7 — le plus grand numéro de Q vaut maintenant 6 et est à nouveau situé colonne 3, d'où la figure (en haut le tableau Q, en dessous le tableau P avant dilatation, et à droite le même tableau après dilatation) :

La permutation se termine donc par 6 5, c'est encourageant. Maintenant le plus grand numéro de Q vaut 5 et est situé colonne 2 :

La permutation se termine par 2 6 5, et cette fois le plus grand numéro de Q vaut 4 et est situé colonne 1 :

Je vous laisse terminer avec l'animation Flash l'exécution de cet algorithme inverse, qui reconstruit la permutation π = 3 7 4 1 2 6 5 à partir de la paire de tableaux P, Q.

Ces algorithmes — construction d'une paire de tableaux de même forme à partir d'une permutation (voir page précédente), et inversement (re)construction de la permutation à partir d'une paire de tableaux (voir ci-dessus) — ont une conséquence tout à fait remarquable :

Théorème : une permutation est caractérisée par une paire de tableaux droits de même forme.

Ou bien, en utilisant le jargon combinatoire usuel : l'algorithme de Robinson-Schensted (et sa version jeu de taquin présentée ici) établit une bijection entre les permutations de n éléments et les paires de tableaux droits de même forme et de taille n (c'est-à-dire comportant n cellules). Ce théorème découle des algorithmes, qui sont inverses l'un de l'autre, et de la constatation que le second (celui présenté sur cette page) fonctionne quelle que soit la paire de tableaux de même forme à laquelle on l'applique. Un sous-produit de ce théorème est une identité numérique que nous allons exposer dans le cas particulier des permutations de 7 éléments.

La formule des équerres indique qu'il y a 21 tableaux standard de forme [3 3 1], donc il existe 21 permutations dont le tableau redressé est le même que celui de la permutation π : à chaque choix du tableau Q pour piloter la dilatation de P correspond une nouvelle permutation. De même sur les 5040 permutations de 7 éléments il en existe 21 * 21 = 441 dont le redressé a pour forme [3 3 1].

Voici la liste des partitions de 7 regroupées par symétrie (on peut lire le diagramme d'une partition colonne par colonne au lieu de ligne par ligne, on parle alors de partition duale) :

• [7] et [1 1 1 1 1 1 1] : 1 tableau standard dans chaque cas,
• [6 1] et [2 1 1 1 1 1] : 6 tableaux standard dans chaque cas,
• [5 2] et [2 2 1 1 1] : 14 tableaux standard dans chaque cas,
• [5 1 1] et [3 1 1 1 1] : 15 tableaux standard dans chaque cas,
• [4 3] et [2 2 2 1] : 14 tableaux standard dans chaque cas,
• [4 2 1] et [3 2 1 1] : 35 tableaux standard dans chaque cas,
• [4 1 1 1] : 20 tableaux standard pour cette forme qui est sa propre duale,
• [3 3 1] et [3 2 2] : 21 tableaux standard dans chaque cas.

et miracle des mathématiques on a bien :

2 * (1 + 6*6 + 14*14 + 15*15 + 14*14 + 35*35 + 21*21) + 20*20 = 5040

Ce type de formule qui exprime n! comme somme des carrés des nombres de tableaux standard, où la somme porte sur toutes les partitions de l'entier n, est bien connu en théorie de la représentation des groupes finis : il y a exactement 15 représentations irréductibles du groupe symétrique S₇ (autant que de partitions de l'entier 7), et pour chacune la dimension de la représentation est égale au nombre de tableaux standard, si, si ! Par exemple la partition [3 3 1] correspond à une représentation des permutations de 7 éléments par des matrices sur un espace de dimension 21 ; la théorie enseigne aussi que toutes les matrices carrées de taille 21x21 sont combinaisons linéaires des matrices de ces permutations qui engendrent donc un espace de dimension 21 * 21 = 441.

Sauf erreur de ma part c'est Schützenberger qui au début des années 60 a saisi ce lien entre les travaux combinatoires de Schensted (qui s'intéressait aux sous-suites croissantes des permutations) et la théorie des représentations du groupe symétrique, et a redécouvert à cette occasion l'article de Robinson publié en 1938.

Reste une question naturelle : que se passe-t-il si on échange le rôle des tableaux P et Q, c'est-à-dire si on utilise P pour piloter la dilatation de Q ? La réponse est une autre découverte étonnante de Schützenberger à laquelle est consacrée la page suivante.