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 $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

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 $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

Une table à deux lignes (« two-line array » en anglais) ou bimot ou permutation généralisée $w_{A}$ correspondant à une matrice $A$ est définie comme suit 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}\leq \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

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

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

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

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) 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é

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	${\tbinom {2}{4}}$	${\tbinom {2}{6}}$	${\tbinom {3}{4}}$	${\tbinom {4}{7}}$	${\tbinom {5}{5}}$	${\tbinom {6}{3}}$	${\tbinom {6}{4}}$	${\tbinom {8}{1}}$
$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

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 $\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\geq 1$, on a

$\sum _{\lambda \in {\mathcal {P}}_{n}}f_{\lambda }^{2}=n!$

où ${\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

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 $^{t}A$ sur $(Q,P)$.

Dans le cas particulier des matrices de permutations, on retrouve la symétrie de la correspondance de Robinson-Schensted, à savoir :

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\}$ :

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\}$

.

Démonstration

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^{k}k!(n-2k)!}}$

Matrices symétriques

Soit $A$=$^{t}A$ 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 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

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

Identité de Cauchy

Soient $x_{1},x_{2},\ldots$ et $y_{1},y_{2},\ldots$ des variables. L'identité qui remonte à Cauchy est :

$\prod _{i,j}(1-x_{i}y_{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

Soient $\mu$ et $\nu$ deux partitions de l'entier $n$. Ici $\mu$ et $\nu$ sont vus 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 }$

où $K_{\lambda \mu }$ et $K_{\lambda \nu }$ dénotent les nombres de Kostka 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$-ème coordonnée est la somme des éléments de la $j$-ème colonne de $A$.

Notes et références

(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).

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 » (n^o 90), 2002 (ISBN 978-0-521-81220-7, lire en ligne), p. 164-196
• (en) William Fulton, Young tableaux, CUP, coll. « London Mathematical Society Student Texts » (n^o 35), 1997 (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,‎ 1970, 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, 2005 (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 » (n^o 203), 2001, 2^e é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

• Monoïde chinois
• Monoïde plaxique

Lien externe

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