Correspondance de Robinson-Schensted-Knuth

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–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[modifier | modifier le code]

Introduction[modifier | modifier le code]

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 :

Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): {\displaystyle \sigma= \begin{pmatrix}1 & 2 & \ldots & n\\\sigma_1 & \sigma_2 & \ldots & \sigma_n\end{pmatrix}} .

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[modifier | modifier le code]

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
    1. , et
    2. 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[modifier | modifier le code]

La table à deux lignes correspondant à la matrice :

est :

Définition de la correspondance[modifier | modifier le code]

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 Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): h de par la Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): h -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 à Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): j est égal à la somme des coefficients de la colonne d'indice Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): j de , et le nombre de coefficients égaux à dans est égal à la somme des coefficients de la ligne d'indice de .

Exemple[modifier | modifier le code]

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[modifier | modifier le code]

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ù Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): h 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é[modifier | modifier le code]

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
Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): {\displaystyle \begin{matrix}2&2&4\\3\end{matrix}}

Propriétés combinatoires de la correspondance RSK[modifier | modifier le code]

Le cas des matrices de permutation[modifier | modifier le code]

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

est l'ensemble des partitions de , et est le nombre de tableaux de Young standard de forme .

Symétrie[modifier | modifier le code]

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

.

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

Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): {\displaystyle a(n) = a(n-1)+(n-1)a(n-2) \, }

avec . C'est la suite A00085 de l'OEIS. Elle admet l'expression :

Matrices symétriques[modifier | modifier le code]

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 Échec d'analyse (MathML avec SVG ou PNG en secours (recommandé pour les navigateurs modernes et les outils d’accessibilité): Réponse invalide(« Math extension cannot connect to Restbase. ») du serveur « /mathoid/local/v1/ » :): \alpha . Ici, est le vecteur dont la -ème composante est la somme des éléments de la -ème ligne de .

Exemple[modifier | modifier le code]

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[modifier | modifier le code]

Identité de Cauchy[modifier | modifier le code]

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[modifier | modifier le code]

Soient et deux partitions de l'entier . Ici et sont vu comme , c'est-à-dire comme vecteur d'entiers pas nécessairement décroissants, dont la somme est . Alors

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[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Robinson–Schensted–Knuth correspondence » (voir la liste des auteurs).

Notes[modifier | modifier le code]

  1. a et b (Lascoux, Leclerc et Thibon 2002)
  2. a, b et c (Stanley, 1999, p. 316-380)
  3. a et b (Knuth 1970)
  4. a et b (Knuth 2005), section 5.1.4, pages 47-72

Bibliographie[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Bruce E. Sagan, « Schur functions in algebraic combinatorics », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, (ISBN 978-1556080104, lire en ligne)