Voir la source de Tableau de Young

Les '''tableaux de Young''' sont des objets [[combinatoire]]s qui jouent un rôle important en théorie des [[Représentation de groupe|représentations des groupes]] et dans la théorie des [[fonction symétrique|fonctions symétriques]]. Ils permettent en particulier de construire les [[représentation irréductible|représentations irréductibles]] du [[groupe symétrique]], ainsi que celles du [[groupe général linéaire]] sur le [[Corps commutatif|corps]] des [[nombre complexe|complexes]]. Les tableaux de Young ont été introduits par [[Alfred Young]], un mathématicien de l'[[université de Cambridge]], en 1900. Ils ont été appliqués à l'étude du groupe symétrique par [[Georg Frobenius]] en 1903. Leur théorie a été développée par de nombreux mathématiciens, parmi lesquels [[Percy Alexander MacMahon|Percy MacMahon]], [[W. V. D. Hodge]], [[Gilbert de Beauregard Robinson|G. de B. Robinson]], [[Gian-Carlo Rota]], [[Alain Lascoux]], [[Marcel-Paul Schützenberger]] et [[Richard Peter Stanley|Richard P. Stanley]].

== Définition ==
=== Diagramme de Young ===
[[Image:Young diagram for 541 partition.svg|thumb|Diagramme de Young de forme (5, 4, 1), notation anglaise]]
[[Fichier:Young diagram for 541 partition french.svg|thumb|Diagramme de Young de forme (5, 4, 1), notation française]]
Un '''diagramme de Young''' (aussi appelé diagramme de Ferrers) est une collection finie de cases, ou cellules, organisée en lignes alignées à gauche, avec la propriété que les longueurs des lignes croissent au sens large (chaque ligne est aussi longue ou plus longue que la précédente). La suite des longueurs des lignes donne une [[partition d'un entier|partition]] <math>\lambda</math> de l'entier <math>n</math> qui est le nombre total de cases du diagramme. L'image à droite montre le diagramme associé à la partition <math>(5,4,1)</math>. La partition <math>\lambda</math> est appelée la '''forme''' du diagramme. L'inclusion d'un diagramme de Young dans un autre définit une structure de [[Treillis (ensemble ordonné)|treillis]] connue sous le nom de [[treillis de Young]]. Si l'on énumère le nombre de cases d'un diagramme par colonnes, on obtient une autre partition, appelée la ''partition conjuguée'' ou transposée de <math>\lambda</math>. 

Les cases d'un diagramme de Young sont généralement indicées par des paires d'entiers, le premier indice dénotant la ligne, le deuxième la colonne. Toutefois, il existe deux conventions pour représenter ces diagrammes, la première qui place chaque ligne en dessous de la précédente, la deuxième qui la place au-dessus. La première convention est principalement utilisée par les [[anglophones]], la deuxième est souvent préférée par les [[francophones]] ; c'est pourquoi ces notations sont appelées ''notation anglaise'' et ''notation française''<ref>{{ouvrage|lang=en|auteur=[[Ian G. Macdonald]]|titre=Symmetric functions and Hall polynomials|collection=Oxford Mathematical Monographs|lien éditeur=Oxford University Press|éditeur=OUP|année=1979|isbn=0-19-853530-9}} recommande aux lecteurs qui préfèrent la notation française de lire ce livre « du bas vers le haut dans un miroir ».</ref>. La notation anglaise correspond aux matrices, la notation française aux coordonnées cartésiennes.

=== Tableau de Young ===
[[Image:Ferrer_331.png|thumb|Le diagramme de Young associé à la partition 7=3+3+1 (notation française).]]
[[Fichier:Young 331.png|thumb|Un tableau de Young semi-standard de forme <math>(3,3,1)</math> à valeurs dans <math>[4]</math>. Son poids est <math>(1,3,1,2)</math>.]]
Pour un entier naturel <math>m</math>, on note <math>[m]</math> l'ensemble des entiers de <math>1</math> à <math>m</math>.
Un '''tableau de Young''' est obtenu en remplissant les cellules d'un diagramme de Young avec des entiers. À l'origine, les entrées étaient des variables <math>x_1,x_2,x_3,\ldots</math>; maintenant, on utilise des entiers. Dans leur application originale aux [[représentations du groupe symétrique]], les tableaux de Young ont <math>n</math> entrées distinctes, associées arbitrairement aux cellules du tableau.
Un tableau de Young est '''standard''' quand les valeurs des entrées sont distinctes deux-à-deux, et sont les entiers de 1 jusqu'au nombre total de cellules. Les entrées sont alors strictement croissantes dans les lignes et dans les colonnes, et . Un tableau est '''semi-standard''' quand les lignes sont ''croissantes au sens large'', et les colonnes ''croissantes au sens strict'', et quand tous les entiers de 1 à la valeur maximale sont présentes.

Le ''poids'' d'un tableau est une suite qui, pour chaque valeur présente dans un tableau de Young, indique le nombre de fois qu'elle y figure. Ainsi, un tableau de Young semi-standard est un tableau standard quand son poids est <math>(1,1,\ldots,1)</math>.

=== Tableau de Young gauche ===
[[Fichier:Ferrer 5441-432.png|thumb|Les cellules hachures forment un diagramme de Young de forme gauche <math>(5,4,4,1)/(4,3,2)</math>, (notation française). ]]
[[Image:Skew tableau 5422-21.svg|thumb|Tableau de Young gauche de forme <math>(5, 4, 2, 2) / (2, 1)</math>, (notation anglaise)]]
Une '''forme gauche''' est un couple <math>(\lambda,\mu)</math> de partitions tel que le diagramme de Young de la partition <math>\lambda</math> contient le diagramme de Young de la partition <math>\mu</math>; ceci signifie que si <math>\lambda=(\lambda_1,\lambda_2,\ldots)</math> et <math>\mu=(\mu_1,\mu_2,\ldots)</math>, alors <math>\lambda_i\ge\mu_i</math> pour tout <math>i</math>. Une forme gauche est notée <math>\lambda/\mu</math> ou <math>\lambda\setminus\mu</math>. Le diagramme gauche d'une forme gauche est la différence ensembliste des diagrammes de Young de <math>\lambda</math> et de <math>\mu</math> : il contient les cases qui sont dans le diagramme de <math>\lambda</math> et pas dans le diagramme de <math>\mu</math>. Un '''tableau de Young gauche''' est obtenu en remplissant les cases du diagramme gauche correspondant. À nouveau, un tableau est semi-standard si les entrées sont strictement croissantes en colonne, et croissantes au sens large en ligne. Si de plus, tous les entiers de 1 au nombre de cellules apparaissent exactement une fois, le tableau est standard.

La forme gauche d'un diagramme de Young gauche ne peut pas toujours être déterminée à partir de l'ensemble de cellules du diagramme. Par exemple, si <math>\lambda = (5,4,2,1)</math> et <math>\mu=(5,3,2,1)</math>, le diagramme gauche de forme <math>\lambda/\mu</math> consiste en une seule cellule en position <math>(2,4)</math>. Mais cette cellule peut être obtenue d'une infinité d'autres façons, par exemple en allongeant la première ligne des deux formes, ou en ajoutant d'autres lignes identiques. De même, si un diagramme est composé de plusieurs parties non connexes, il peut être obtenue à partir de plusieurs formes différentes.

Tout tableau semi-standard gauche <math>T</math> de forme <math>\lambda/\mu</math> à entrées positives détermine une suite de partitions (ou de diagrammes de Young) comme suit : on commence avec <math>\mu</math>; à la <math>i</math>-ème étape, on prend comme partition celle dont le diagramme est obtenu à partir de <math>\mu</math> en ajoutant toutes les cellules de <math>T</math> qui contiennent une valeur <math>\le i</math>; la partition finale est la partition <math>\lambda</math>. Toute paire consécutive de diagrammes de cette suite définit une forme gauche dont le diagramme contient au plus une entrée dans chaque colonne (parce que les entrées sont croissantes en colonne). De telles formes sont appelées ''bandes horizontales'' (''horizontal strips'' en anglais). Cette suite de partitions détermine entièrement <math>T</math><ref>Et on peut définir les tableaux semi-standard gauche comme de telles séquences ; c'est ainsi que procède {{harvsp|Macdonald|1979|p=4}}.</ref>.

=== Extension ===
[[Fichier:Young 7642.png|thumb|Tableau de Young de forme (7, 6, 4, 2). Le mot correspondant est {{formatnum:6845562233571112444}}.]]
Au lieu de prendre les valeurs d'un tableau de Young dans les entiers, on les prend dans un [[alphabet]] quelconque, totalement ordonné<ref>{{Chapitre|lang=en
|auteur=[[Alain Lascoux]]|auteur2=Bernard Leclerc|auteur3=Jean-Yves Thibon  
| titre chapitre = The plactic monoid
| auteurs ouvrage =[[M. Lothaire]]
| titre ouvrage = Algebraic Combinatorics on Words
| éditeur=[[Cambridge University Press|CUP]] 
| collection=Encyclopedia of Mathematics and its Applications | isbn=978-0-521-81220-7| année=2002 |lire en ligne=http://www.combinatorics.net/lascoux/articles/plactic.ps
| numéro dans collection=90
| passage=164-196}}.</ref>. Lorsque l'on lit successivement les lignes d'un tableau de Young semi-standard, on obtient une suite de mots croissants au sens large sur cet alphabet. Chaque mot <math>x=x_1\cdots x_r</math> de cette suite ''domine'' le suivant <math>y=y_1\cdots y_s</math> dans le sens que <math>r\le s</math> et de plus <math>x_i< y_i</math> pour <math>1\le i\le r</math>. Pour le diagramme de Young de la partition (3,3,1), les mots des lignes sont <math>4\,234\,122</math>, et chacune domine la suivante. Le produit des mots de lignes est parfois lui-même appelé tableau<ref>{{harvsp|Lascoux|Leclerc|Thibon|2002|p=166}}.</ref>. Dans notre exemple, c'est le mot <math>4234122</math>. La correspondance entre mots et tableau semi-standard est bijective : pour décoder le mot, il suffit à chaque fois de prendre le préfixe le plus long qui est croissant au sens large. Dans le tableau ci-contre de forme <math>(7,6,4,2)</math>, le mot-tableau <math>684556223357111444</math> se factorise en lignes dont chacune domine la suivante.
== Propriétés combinatoires ==

=== Algorithme de Schensted ===
{{article détaillé|correspondance de Robinson-Schensted|correspondance de Robinson-Schensted-Knuth}}
L'[[correspondance de Robinson-Schensted|algorithme de Schensted]] est un algorithme qui permet d'insérer un entier dans un tableau semi-standard ou standard, de manière à obtenir un nouveau tableau du même type. Cet algorithme permet :

* de munir l'ensemble des tableaux d'une [[loi de composition interne]], en insérant successivement les éléments d'un tableau dans un autre.
* d'établir une bijection entre permutations, et plus généralement suites d'entiers positifs et paires de tableaux de Young standard (resp. semi-standard) <math>(P,Q)</math> de même forme, connue sous le nom de [[correspondance de Robinson-Schensted-Knuth]]. 
* d'induire une relation d'équivalence sur l'ensemble des suites finies d'entiers positifs. Deux mots sont équivalents si dans la correspondance de Robinson-Schensted, ils ont même tableau P.

Une construction géométrique de la correspondance de Robinson-Schensted entre permutations et paires de tableaux de Young standard de même forme a été donnée par Viennot.

{{article détaillé|construction géométrique de Viennot}}

=== Relations de Knuth ===
À partir de l'étude de cette relation d'équivalence sur les mots de longueur 3, [[Donald Knuth]] a défini des [[Réécriture (informatique)|règles de réécriture]] sur l'ensemble des mots sur <math>[m]</math>. Ces règles de réécriture induisent également une relation d'équivalence, et Knuth a démontré qu'elle coïncide avec la relation de Schensted. Une conséquence importante de ce théorème est que la loi de composition qui découle de l'algorithme de Schensted possède toutes les propriétés requises pour donner à l'ensemble des tableaux une structure de [[monoïde]] : '''le monoïde plaxique'''.
{{article détaillé|Monoïde plaxique}}

=== Formule des équerres ===
[[Image:Hook length for 541 partition.svg|thumb|Longueurs des équerres pour la partition de ''10=5+4+1''.]]

La ''formule des équerres'' (''hook-length formula'' en anglais) est une formule qui permet de calculer le nombre de tableaux de Young standard de forme <math>\lambda</math> donnée. Ce nombre est important, car le nombre de tableaux de Young standard de forme donnée est égal à la dimension de la représentation irréductible du groupe symétrique <math>S_n</math> correspondant à une partition <math>\lambda</math> de <math>n</math>.

L{{'}}''équerre'' associée à une cellule <math>x</math> du diagramme de Ferrers <math>Y(\lambda)</math> de forme <math>\lambda</math> est composé de cette cellule, et de toutes les cellules à droite et en dessous (dans la notation anglaise), respectivement à droite et au-dessus (dans la notation française) de la cellule <math>x</math>. La ''longueur de l'équerre'' <math>h(x)</math> (en anglais ''hook-length'') est le nombre de cellules composant l'équerre. Dans l'exemple de la partition <math>\lambda=(5,4,1)</math>, la cellule en haut à gauche a 5 cellules sur la même ligne et 3 sur la même colonne. Sa longueur d'équerre est donc 7. 

On note <math>f^\lambda</math> le nombre de tableaux de Young standard de forme <math>\lambda</math>, pour une partition de <math>n</math>. 

{{théorème|Formule des équerres|Soit <math>f^\lambda</math> le nombre de tableaux de Young standard de forme <math>\lambda</math> pour une partition de <math>n</math>. Alors on a
:<math>f^\lambda=\frac{n!}{\prod_{x \in Y(\lambda)} h(x)}</math>.}}

La figure ci-contre donne les longueurs des équerres pour la partition <math>\lambda=(5,4,1)</math>. On obtient

:<math>f^\lambda= \frac{10!}{7\cdot5\cdot 4 \cdot 3\cdot 1\cdot 5\cdot 3\cdot 2\cdot 1\cdot1} = 288.</math>

Il y a donc 288 tableaux de Young standard de cette forme, et il y a autant de représentations irréductibles du groupe symétrique ''S''{{ind|10}} correspondant à cette partition.

La formule des équerres est aussi appelée le théorème de Frame-Robinson-Thrall d'après les auteurs d'une preuve<ref>{{article|lang=en|auteur= J. S. Frame|auteur2= Gilbert de B. Robinson|auteur3=Robert M. Thrall|titre=The hook graphs of the symmetric groups|journal= Canadian Journal of Mathematics|volume=6|année=1954| pages=316-324}}.</ref>. Une preuve combinatoire, utilisant le [[jeu de taquin de Schützenberger]] a été donnée par Novelli, Pak et Stoyanovskii<ref>{{article|lang=en|auteur= Jean-Christophe Novelli|auteur2=Igor Pak|auteur3= Alexander V. Stoyanovskii|titre=A direct bijective proof of the hook-length formula|journal= Discrete Math. Theor. Comput. Sci.|volume=1|année=1997| numéro=1|pages=53-67|math reviews=99h:05123}}.</ref>. En fait, de nombreuses preuves ont été données, parmi lesquelles d'autres preuves bijectives. La preuve de Novelli, Pak et Stoyanovskii est considérée par Krattenthaler comme la plus naturelle : « ''The bijection presented in the paper under review must be considered as the natural hook bijection'' »<ref>[http://ams.u-strasbg.fr/mathscinet/search/publdoc.html?arg3=&co4=AND&co5=AND&co6=AND&co7=AND&dr=all&pg4=AUCN&pg5=AUCN&pg6=PC&pg7=ALLF&pg8=ET&r=1&review_format=html&s4=Novelli&s5=Pak&s6=&s7=&s8=All&vfpref=html&yearRangeFirst=&yearRangeSecond=&yrop=eq Revue de l’article de Novelli, Pak et Stoyanovskii dans MathSciNet]. Accès limité.</ref>. Les livres de référence, comme {{harvsp|Sagan|2001}} ou {{harvsp|Fulton|1997}}, contiennent des preuves. Une démonstration élémentaire et détaillée, par Jason Bandlow, existe en ligne<ref>{{article|lang=en|auteur=Jason Bandlow|titre=An elementary proof of the hook formula|journal=The Electronic Journal for Combinatorics|année=2008|volume=15|url=http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1r45}}.</ref>.

=== Formule de la somme des carrés ===
Une formule proche de la formule des équerres est la suivante :

{{théorème|Somme des carrés|Soit <math>n</math> un entier. On a :
: <math>\sum_{\lambda}(f^\lambda)^2=n\,!</math>, 
où la somme est sur toutes les partitions <math>\lambda</math> de <math>n</math>, et <math>f^\lambda</math> est le nombre de tableaux de Young standard de forme <math>\lambda</math>.}}

Par exemple, pour les partitions (3), (2,1) et (1,1,1) de l'entier 3, il y a respectivement 1, 2 et 1 tableau(x) de Young standard de cette forme, d'où le total 1+4+1=6=3!.
Une démonstration de cette formule se fait bien au moyen des [[treillis de Young]].

== Survol des applications ==
Les tableaux de Young ont de nombreuses application en [[combinatoire]], en [[théorie des représentations]] et en [[géométrie algébrique]]. Diverses façons de compter les tableaux de Young ont été explorées, et ont conduit à la définition et à des identités sur les [[Polynôme de Schur|polynômes de Schur]]. De nombreux algorithmes ont été développés, y compris le [[jeu de taquin de Schützenberger]], la [[correspondance de Robinson-Schensted-Knuth]], ou la [[construction géométrique de Viennot]]. Lascoux et Schützenberger ont introduit un produit associatif sur l'ensemble des tableaux de Young semi-standard qui muni cet ensemble d'une structure de monoïde, appelé le ''[[monoïde plaxique]]''.

En théorie des représentations, les tableaux de Young standard de taille <math>k</math> décrivent des bases des représentations irréductibles du [[groupe symétrique]] sur <math>k</math> lettres. Les bases monomiales standard d'une représentation irréductible de dimension finie du [[groupe général linéaire]] <math>\text{GL}_n</math> sont paramétrées par l'ensemble des tableaux de Young semi-standard de forme fixée sur l'alphabet <math>\{1,2,\ldots,n\}</math>. Ceci a des conséquences importantes en [[théorie des invariants]].
La [[règle de Littlewood-Richardson]] qui décrit, entre autres, la décomposition du produit tensoriel de représentations irréductibles de <math>\text{GL}_n</math> en composantes irréductibles est formule en termes de tableaux de Young gauches.

Les applications en géométrie algébrique se concentrent sur le {{Lien|fr=calcul de Schubert|lang=en|trad=Schubert calculus}}, sur les [[grassmannienne]]s et les [[variété de drapeaux généralisée|variétés de drapeaux]]. Certaines [[Homologie et cohomologie|classes de cohomologie]] importantes peuvent être représentées par des {{Lien|fr=polynômes de Schubert|lang=en|trad=Schubert polynomial}} et décrites en termes de tableaux de Young.

== Applications au représentations des groupes ==

=== Représentations du groupe symétrique ===
{{Voir|Théorie des représentations d'un groupe fini|Représentations du groupe symétrique}}
<!--
Les tableaux de Young permettent de calculer simplement les {{subst:Lien/Conversion automatique|Symétriseur de Young|trad=Young symmetrizer|texte=symétriseurs de Young}}.-->

=== Représentation de GL(''E'') ===
Si ''E'' est un ℂ-espace vectoriel de dimension ''m'', et λ une partition, on définit le '''module de Schur''' ''E''{{exp|λ}} comme étant le ℂ-espace vectoriel dont une base est formée par l'ensemble des tableaux de Young de forme λ et à valeur dans [''m'']. Sachant qu'il est possible d'identifier un tableau de Young à valeurs dans [''m''] à un polynôme de ℂ[''X{{ind|i,j}}''|1≤''i,j≤m''], il existe une action naturelle de GL(''E'') sur les tableaux de Young par simple multiplication matricielle. Les modules de Schur sont donc des représentations de GL(''E''). On peut montrer que toute représentation polynomiale irréductible de GL(''E'') est isomorphe à un unique module de Schur.

=== Fonctions symétriques ===
Les [[Caractère d'une représentation d'un groupe fini|caractères]] des modules de Schur (en tant que représentations de GL(''E'')) sont des polynômes symétriques appelés [[Polynôme de Schur|polynômes de Schur]], d'après le mathématicien russe [[Issai Schur]]. Les tableaux de Young fournissent un moyen élégant pour exprimer ces polynômes. Par ailleurs, il existe une règle purement combinatoire qui fait appel aux tableaux de Young, et qui permet de décomposer le produit de deux polynômes de Schur. Ceci implique en particulier que les tableaux permettent de décomposer le produit tensoriel de deux représentations irréductibles de GL(''E'') en somme directe de représentations irréductibles.

== Notes et références ==
{{Références}}

==Bibliographie==
* {{ouvrage|lang=en|nom=Fulton|prénom=William|lien auteur1=William Fulton|titre=Young tableaux | éditeur=Cambridge University Press | collection=London Mathematical Society Student Texts | isbn=978-0-521-56144-0 |isbn2=978-0-521-56724-4  | année=1997 | numéro dans collection=35|math reviews=1464693}}
* {{article|lang=en|auteur=[[Donald Knuth|Donald E. Knuth]]| titre=Permutations, matrices, and generalized Young tableaux | url=http://projecteuclid.org/euclid.pjm/1102971948|math reviews= 0272654| year=1970 | journal=Pacific Journal of Mathematics | issn=0030-8730 | volume=34 | pages=709–727}}
*{{Knuth-TAOCPVol3}}
* {{ouvrage|lang=en|auteur={{Lien|Bruce Sagan|texte=Bruce E. Sagan}}
 |titre=The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions
 |sous-titre=|numéro d'édition=2
 |collection =[[Graduate Texts in Mathematics|GTM]]|numéro dans collection=203
 |éditeur=Springer|année=2001|isbn=0-387-95067-2}}
* {{Enumerative Combinatorics|vol=2}}

{{Palette|Représentations des groupes finis}}

{{portail|mathématiques}}

[[Catégorie:Combinatoire algébrique]]
[[Catégorie:Théorie des représentations]]
[[Catégorie:Théorie des groupes]]
[[Catégorie:Diagramme|Young]]