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 A à 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 A. Cette correspondance généralise la correspondance de Robinson-Schensted, en ce sens que si A est une matrice de permutation, alors la paire (P,Q) 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 A revient à l'échange des tableaux P et Q.

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 P vide et insère successivement les valeurs \sigma_1,\ldots,\sigma_n de la permutation \sigma, avec \sigma donnée sous forme fonctionnelle :

 \sigma= \begin{pmatrix}1 & 2 & \ldots & n\\\sigma_1 & \sigma_2 & \ldots & \sigma_n\end{pmatrix}.

Le tableau P obtenu est le premier de la paire correspondant à \sigma; le deuxième tableau standard, noté Q, enregistre les formes successives parcourues durant la construction de P.

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 P semi-standard plutôt qu'un tableau standard, mais Q reste un tableau standard. La correspondance RSK rétablit la symétrie entre tableaux en produisant un tableau semi-standard pour Q 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 w_A correspondant à une matrice A est définie comme suit[2] est une matrice

 w_A = \begin{pmatrix}i_1 & i_2 & \cdots & i_m\\j_1 & j_2 & \cdots & j_m\end{pmatrix}

qui vérifie les propriétés suivantes:

  • Les colonnes sont ordonnées en ordre lexicographique, ce qui signifie que
    1. i_1 \leq i_2 \leq i_3\le\cdots \leq i_m, et
    2. si i_r = i_s et r \leq s, alors j_r \leq j_s.
  • pour chaque paire d'indices (i,j) de la matrice A, il y a A_{i,j} colonnes égales à \tbinom{i}{j}.

En particulier, l'entier m est égal à la somme des coefficients de la matrice A.

Exemple[modifier | modifier le code]

La table à deux lignes correspondant à la matrice :

A=\begin{pmatrix}1&0&2\\0&2&0\\1&1&0\end{pmatrix}

est :

w_A =\begin{pmatrix}1 & 1 & 1 & 2 & 2 & 3 & 3\\
                           1 & 3 & 3 & 2 & 2 & 1 & 2\end{pmatrix}

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 P et un tableau standard noté Q_0. Le tableau Q_0 peut lui aussi être transformé en un tableau semi-standard noté Q en remplaçant chaque entrée h de Q_0 par la h-ième entrée de la première ligne de w_A.

On obtient ainsi[3] une bijection des matrices A sur des paires (P,Q) de tableaux de Young semi-standard de même forme; les coefficients de P sont les éléments de la deuxième ligne de w_A, et les coefficients de Q sont les éléments de la première ligne de w_A. De plus, le nombre de coefficients de P égaux à j est égal à la somme des coefficients de la colonne d'indice j de A, et le nombre de coefficients égaux à i dans Q est égal à la somme des coefficients de la ligne d'indice i de A.

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 P, et un tableau Q_0 d'enregistrement des formes successives, qui sont égaux à :

P\quad=\quad\begin{matrix}1&1&2&2\\2&3\\3\end{matrix}, \qquad Q_0\quad=\quad\begin{matrix}1&2&3&7\\4&5\\6\end{matrix}.

Après avoir remplacé les entrées 1,2,3,4,5,6,7 dans Q_0 par 1,1,1,2,2,3,3 respectivement, on obtient la paire de tableaux semi-standard suivante :

P\quad=\quad\begin{matrix}1&1&2&2\\2&3\\3\end{matrix}, \qquad Q\quad=\quad\begin{matrix}1&1&1&3\\2&2\\3\end{matrix}.

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 Q_0 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 Q est augmenté en ajoutant, comme valeur dans le nouveau carré, l'élément i_h de la première ligne de w_A, où 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 w_A, 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 :

A=\begin{pmatrix}
0&0&0&0&0&0&0\\
0&0&0&1&0&1&0\\
0&0&0&1&0&0&0\\
0&0&0&0&0&0&1\\
0&0&0&0&1&0&0\\
0&0&1&1&0&0&0\\
0&0&0&0&0&0&0\\
1&0&0&0&0&0&0\\
\end{pmatrix},

et on obtient la table à deux lignes suivante :

 w_A=
\begin{pmatrix}2 & 2 & 3 & 4 & 5 & 6 & 6 & 8 \\
               4 & 6 & 4 & 7 & 5 & 3 & 4 & 1 
\end{pmatrix}.

La table suivant montre les étapes de la construction des deux tableaux pour cet exemple.

Paire insérée \tbinom24 \tbinom26 \tbinom34 \tbinom47 \tbinom55 \tbinom63 \tbinom64 \tbinom81
P \begin{matrix}4\end{matrix} \begin{matrix}4&6\end{matrix} \begin{matrix}4&4\\6\end{matrix} \begin{matrix}4&4&7\\6\end{matrix} \begin{matrix}4&4&5\\6&7\end{matrix} \begin{matrix}3&4&5\\4&7\\6\end{matrix} \begin{matrix}3&4&4\\4&5\\6&7\end{matrix} \begin{matrix}1&4&4\\3&5\\4&7\\6\end{matrix}
Q \begin{matrix}2\end{matrix} \begin{matrix}2&2\end{matrix} \begin{matrix}2&2\\3\end{matrix} \begin{matrix}2&2&4\\3\end{matrix} \begin{matrix}2&2&4\\3&5\end{matrix} \begin{matrix}2&2&4\\3&5\\6\end{matrix} \begin{matrix}2&2&4\\3&5\\6&6\end{matrix} \begin{matrix}2&2&4\\3&5\\6&6\\8\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 \lambda. Réciproquement, si P,Q sont de tableaux de Young standard de même forme \lambda, alors la matrice A 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 n\ge1, on a

\sum_{\lambda\in \mathcal{P}_n} f_\lambda^2= n!

\mathcal{P}_n est l'ensemble des partitions de n, et f_\lambda est le nombre de tableaux de Young standard de forme \lambda.

Symétrie[modifier | modifier le code]

Soit A une matrice à éléments entiers naturels. Supposons que l'algorithme RSK envoie A sur (P,Q). Alors l'algorithme RSK envoie la matrice transposée ^tA sur (Q,P)[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 \sigma correspond au triplet (\lambda,P,Q), alors la permutation inverse \sigma^{-1} correspond au triplet (\lambda,Q,P).

Ceci conduit à la relation suivante entre le nombre d'involutions sur \{1,2,3, \ldots,n\} et le nombre de tableaux que l'on peut former à partir de \{1,2,3, \ldots,n\}[4] :

Propriété — Le nombre de tableaux standard sur \{1,2,3, \ldots,n\} est égal au nombre d'involutions sur \{1,2,3, \ldots,n\}

.

Preuve: Soit \pi une involution correspondant à la paire (P,Q); alors \pi^{-1} = \pi correspond à (Q,P), donc P = Q. Réciproquement, si \pi est une permutation correspondant à (P,P), alors \pi^{-1} correspond aussi à (P,P), et donc \pi^{-1} = \pi. Ceci montre la bijection entre involutions \pi et tableaux P.

Le nombre d'involutions sur \{1,2,3, \ldots,n\}, et donc le nombre de tableau de Young standard à n éléments, est donné par la relation de récurrence :

a(n) = a(n-1)+(n-1)a(n-2) \,

avec a(1) = 1,a(2) = 2. C'est la suite A00085 de l'OEIS. Elle admet l'expression :

a(n) = \sum_{k=0}^{\lfloor n/2 \rfloor} \frac{n!}{2^kk!(n-2k)!}

Matrices symétriques[modifier | modifier le code]

Soit A=^tA une matrice symétrique. Soit (P,P) la paire de tableau de Young semi-standard obtenue par l'algorithme RSK pour A. Soit \alpha= (\alpha_1,\alpha_2,\ldots) le poids (ou le contenu, selon les auteurs) de P, défini par : \alpha_i est le nombre de fois que l'entier i figure dans P. Alors[2] l'application

A \longmapsto P

est une bijection entre matrices symétriques vérifiant \text{row}(A)= \alpha et tableaux de Young semi-standard de poids \alpha. Ici, \text{row}(A) est le vecteur dont la i-ème composante est la somme des éléments de la i-ème ligne de A.

Exemple[modifier | modifier le code]

Soit A la matrice symétrique :

A=\begin{pmatrix}1&0&2\\0&1&1\\2&1&0\end{pmatrix}

Un calcul montre que

P=\begin{matrix}1&1&1&2\\2&3&3\\3\end{matrix}

Le poids de P est \alpha=(3,2,3), et le vecteur des sommes de lignes de A est \text{row}(A)=(3,2,3).

Applications de la correspondance RSK[modifier | modifier le code]

Identité de Cauchy[modifier | modifier le code]

Soient x_1,x_2,\ldots et y_1,y_2,\ldots des variables. L'identité qui remonte à Cauchy[1] est :

\prod_{i,j} (1 - x_iy_j)^{-1} = \sum_{\lambda} s_{\lambda}(x)s_{\lambda}(y)

où les s_{\lambda} sont des polynômes de Schur. La définition la plus appropriée ici des polynômes de Schur est

s_\lambda(x)=s_\lambda(x_1,x_2,\ldots,x_n)=\sum_T x^T = \sum_T x_1^{t_1}\cdots x_n^{t_n}

où la sommation est sur tous les tableaux de Young semi-standard de forme \lambda et où les exposants t_1,\ldots,t_n donnent le poids de T, en d'autre termes, t_i compte le nombre d'occurrences de i dans T.

Nombres de Kostka[modifier | modifier le code]

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

\sum_{\lambda\in\mathcal{P}_n} K_{\lambda \mu} K_{\lambda \nu} = N_{\mu \nu}

K_{\lambda \mu} et  K_{\lambda \nu} denotent les nombres de Kostka (en) et N_{\mu \nu} est le nombre de matrices A à coefficients entiers naturels, avec \text{row}(A)=\mu et \text{column}(A)= \nu. Ici, \text{column}(A) est le vecteur dont la j-ième coordonnée est la somme des éléments de la j-ième colonne de A.

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,‎ 2002 (ISBN 978-1556080104, lire en ligne)