Correspondance de Robinson-Schensted-Knuth
En mathématiques, et notamment en combinatoire algébrique, la correspondance de Robinson–Schensted–Knuth, aussi appelée la correspondance RSK ou l'algorithme RSK, est une bijection entre matrices à coefficients entiers naturels et paires de tableaux de Young semi-standard de même forme, dont la taille est égale à la somme des entrées de la matrice . Cette correspondance généralise la correspondance de Robinson-Schensted, en ce sens que si est une matrice de permutation, alors la paire est la paire de tableaux standard associés à la permutation par la correspondance de Robinson-Schensted.
La correspondance de Robinson-Schensted-Knuth étend bon nombre des propriétés remarquables de la correspondance de Robinson-Schensted, et notamment la propriété de symétrie : la transposition de la matrice revient à l'échange des tableaux et .
La correspondance de Robinson-Schensted-Knuth
Introduction
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 construite au moyen d'un algorithme appelé l'insertion de Schensted. Cet algorithme commence avec un tableau vide et insère successivement les valeurs de la permutation , avec donnée sous forme fonctionnelle :
- .
Le tableau obtenu est le premier de la paire correspondant à ; le deuxième tableau standard, noté , enregistre les formes successives parcourues durant la construction de .
La construction de Schensted peut en fait prendre en compte des suites de nombres plus générales que celles obtenues par des permutations (notamment on peut autoriser des répétitions); dans ce cas, la construction produit un tableau semi-standard plutôt qu'un tableau standard, mais reste un tableau standard. La correspondance RSK rétablit la symétrie entre tableaux en produisant un tableau semi-standard pour aussi.
Tables à deux lignes
Une table à deux lignes (« two-line array » en anglais) ou bimot[1] ou permutation généralisée correspondant à une matrice est définie comme suit[2] est une matrice
qui vérifie les propriétés suivantes :
- Les colonnes sont ordonnées en ordre lexicographique, ce qui signifie que
- , et
- si et , alors .
- pour chaque paire d'indices de la matrice , il y a colonnes égales à .
En particulier, l'entier est égal à la somme des coefficients de la matrice .
Exemple
La table à deux lignes correspondant à la matrice :
est :
Définition de la correspondance
En appliquant l'algorithme d'insertion de Schensted à la deuxième ligne d'une table à deux lignes, on obtient une paire consistant en un tableau semi-standard et un tableau standard noté . Le tableau peut lui aussi être transformé en un tableau semi-standard noté en remplaçant chaque entrée de par la -ième entrée de la première ligne de .
On obtient ainsi[3] une bijection des matrices sur des paires de tableaux de Young semi-standard de même forme; les coefficients de sont les éléments de la deuxième ligne de , et les coefficients de sont les éléments de la première ligne de . De plus, le nombre de coefficients de égaux à est égal à la somme des coefficients de la colonne d'indice de , et le nombre de coefficients égaux à dans est égal à la somme des coefficients de la ligne d'indice de .
Exemple
Pour l'exemple ci-dessus, si l'on applique l'insertion de Schensted à l'insertion de la suite 1,3,3,2,2,1,2 dans un tableau initialement vide, on obtient un tableau , et un tableau d'enregistrement des formes successives, qui sont égaux à :
- .
Après avoir remplacé les entrées 1,2,3,4,5,6,7 dans par 1,1,1,2,2,3,3 respectivement, on obtient la paire de tableaux semi-standard suivante :
Définition directe de la correspondance RSK
La définition ci-dessus utilise l'algorithme de Schensted qui produit un tableau d'enregistrement standard; ce tableau est modifié ensuite pour tenir compte de la première ligne de la table à deux lignes et obtenir un tableau d'enregistrement semi-standard. Cette définition montre clairement la relation avec la correspondance de Robinson-Schensted. D'un autre côté, il est naturel de simplifier la partie de la construction concernant l'enregistrement de la forme en prenant en compte directement en compte la première ligne de la table à deux lignes. C'est sous cette forme que l'algorithme de construction de la correspondance RSK est habituellement décrit. Cela signifie simplement qu'après chaque étape d'insertion de Schensted, le tableau est augmenté en ajoutant, comme valeur dans le nouveau carré, l'élément de la première ligne de , où est la taille courante des tableaux. Le fait que ceci produit toujours un tableau semi-standard est une conséquence de la propriété (observée pour la première fois par Knuth[3]) que lors d'insertions d'une même valeur dans la première ligne de , chaque carré ajouté dans la forme est dans une colonne strictement plus grande que la précédente.
Exemple détaillé
Voici un exemple détaillé de cette construction des deux tableaux semi-standard. On part de la matrice :
- ,
et on obtient la table à deux lignes suivante :
La table suivant montre les étapes de la construction des deux tableaux pour cet exemple.
Paire insérée
Propriétés combinatoires de la correspondance RSK
Le cas des matrices de permutation
Si A est une matrice de permutation, la correspondance RSK produit une paire de tableaux de Young standard de même forme, disons . Réciproquement, si sont de tableaux de Young standard de même forme , alors la matrice correspondante est une matrice de permutation. Comme conséquence de cette propriété nous obtenons, simplement en comparant la cardinalité des ensembles ainsi mis en bijection, la propriété suivante :
Identité de Frobenius — Pour , on a
où est l'ensemble des partitions de , et est le nombre de tableaux de Young standard de forme .
Symétrie
Soit une matrice à éléments entiers naturels. Supposons que l'algorithme RSK envoie sur . Alors l'algorithme RSK envoie la matrice transposée sur [2].
Dans le cas particulier des matrices de permutations, on retrouve la symétrie de la correspondance de Robinson-Schensted, à savoir[4] :
Théorème — Si la permutation correspond au triplet , alors la permutation inverse correspond au triplet .
Ceci conduit à la relation suivante entre le nombre d'involutions sur et le nombre de tableaux que l'on peut former à partir de [4] :
Propriété — Le nombre de tableaux standard sur est égal au nombre d'involutions sur
.
Soit une involution correspondant à la paire ; alors correspond à , donc . Réciproquement, si est une permutation correspondant à , alors correspond aussi à , et donc . Ceci montre la bijection entre involutions et tableaux .
Le nombre d'involutions sur , et donc le nombre de tableau de Young standard à éléments, est donné par la relation de récurrence :
avec . C'est la suite A00085 de l'OEIS. Elle admet l'expression :
Matrices symétriques
Soit = une matrice symétrique. Soit la paire de tableau de Young semi-standard obtenue par l'algorithme RSK pour . Soit le poids (ou le contenu, selon les auteurs) de , défini par : est le nombre de fois que l'entier figure dans . Alors[2] l'application
est une bijection entre matrices symétriques vérifiant et tableaux de Young semi-standard de poids . Ici, est le vecteur dont la -ème composante est la somme des éléments de la -ème ligne de .
Exemple
Soit la matrice symétrique :
Un calcul montre que
Le poids de est , et le vecteur des sommes de lignes de est .
Applications de la correspondance RSK
Identité de Cauchy
Soient et des variables. L'identité qui remonte à Cauchy[1] est :
où les sont des polynômes de Schur. La définition la plus appropriée ici des polynômes de Schur est
où la sommation est sur tous les tableaux de Young semi-standard de forme et où les exposants donnent le poids de , en d'autre termes, compte le nombre d'occurrences de dans .
Nombres de Kostka
Soient et deux partitions de l'entier . Ici et sont vus comme , c'est-à-dire comme vecteur d'entiers pas nécessairement décroissants, dont la somme est . Alors
où et dénotent les nombres de Kostka et est le nombre de matrices à coefficients entiers naturels, avec et . Ici, est le vecteur dont la -ème coordonnée est la somme des éléments de la -ème colonne de .
Notes et références
Notes
- ↑ a et b (Lascoux, Leclerc et Thibon 2002)
- ↑ a b et c (Stanley, 1999, p. 316-380)
- ↑ a et b (Knuth 1970)
- ↑ a et b (Knuth 2005), section 5.1.4, pages 47-72
Bibliographie
- (en) Alain Lascoux, Bernard Leclerc et Jean-Yves Thibon, « The plactic monoid », dans M. Lothaire, Algebraic Combinatorics on Words, CUP, coll. « Encyclopedia of Mathematics and its Applications » (no 90), (ISBN 978-0-521-81220-7, lire en ligne), p. 164-196
- (en) William Fulton, Young tableaux, CUP, coll. « London Mathematical Society Student Texts » (no 35), (ISBN 978-0-521-56144-0 et 978-0-521-56724-4, MR 1464693)
- (en) Donald E. Knuth, « Permutations, matrices, and generalized Young tableaux », Pacific Journal of Mathematics, vol. 34, , p. 709–727 (ISSN 0030-8730, MR 0272654, lire en ligne)
- (en) Donald E. Knuth, The Art of Computer Programming, vol. 3 : Sorting and Searching, Second Edition, Addison-Wesley, (ISBN 0-201-89685-0, présentation en ligne)
- (en) Bruce E. Sagan, The Symmetric Group : Representations, Combinatorial Algorithms, and Symmetric Functions, Springer, coll. « Graduate Texts in Mathematics » (no 203), , 2e éd., 240 p. (ISBN 978-0-387-95067-9, lire en ligne)
- (en) Richard P. Stanley, Enumerative Combinatorics, vol. 2 [détail des éditions] (présentation en ligne)
Voir aussi
Lien externe
(en) Bruce E. Sagan, « Schur functions in algebraic combinatorics », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, (ISBN 978-1556080104, lire en ligne)
Portail des mathématiques