Nombre de Kostka

En mathématiques, le nombre de Kostka ${\displaystyle K_{\lambda \mu }}$, paramétré par deux partition d'un entier ${\displaystyle \lambda }$ et ${\displaystyle \mu }$, est un entier naturel qui est égal au nombre de tableaux de Young semi-standard de forme ${\displaystyle \lambda }$ et de poids ${\displaystyle \mu }$. Ils ont été introduits par le mathématicien Carl Kostka dans ses études des fonctions symétriques^[1],[2].

Par exemple, si ${\displaystyle \lambda =(3,2)}$ et ${\displaystyle \mu =(1,1,2,1)}$, le nombre de Kostka ${\displaystyle K_{\lambda \mu }}$ compte le nombre de manières de remplir une collection de 5 cellules alignée à gauche, avec 3 cellules dans la première ligne et 2 dans la seconde, et contenant une fois les entiers 1 et 2, deux fois l'entier 3 et une fois l'entier 4. De plus, les entiers doivent être strictement croissants en colonne, et faiblement croissants en ligne. Les trois tableaux possibles sont montrés sur la figure, et on a donc ${\displaystyle K_{(3,2)(1,1,2,1)}=3}$.

Pour toute partition ${\displaystyle \lambda }$, le nombre de Kostka ${\displaystyle K_{\lambda \lambda }}$ est égal à 1 : c'est l'unique manière de remplir le diagramme de Young de forme ${\displaystyle \lambda =(\lambda _{1},\lambda _{2},\ldots ,\lambda _{m})}$ avec ${\displaystyle \lambda _{1}}$ exemplaires du nombre 1, ${\displaystyle \lambda _{2}}$ exemplaires de 2, etc, tout en respectant les conditions de croissance sur les lignes et les colonnes : tous les 1 sont placés dans la première ligne, les 2 dans la deuxième ligne, etc. Un tel tableau est parfois appelé le tableau de Yamanouchi de forme ${\displaystyle \lambda }$.

Le nombre de Kostka ${\displaystyle K_{\lambda \mu }}$ est positif ou, en d'autres termes, il existe au moins un tableau de Young de forme ${\displaystyle \lambda }$ et de poids ${\displaystyle \mu }$ si et seulement si ${\displaystyle \lambda }$ et ${\displaystyle \mu }$ sont toutes deux des partitions d'un même entier, et si ${\displaystyle \lambda }$ est plus grande que ${\displaystyle \mu }$ dans l'ordre de domination, c'est-à-dire si ${\displaystyle \lambda _{1}+\cdots +\lambda _{k}\geq \mu _{1}+\cdots +\mu _{k}}$ pour tout ${\displaystyle k}$^[3].

Il n'existe en général pas de formules closes pour les nombres de Kostka. Quelques cas particuliers sont connus. Par exemple, si ${\displaystyle \mu =(1,1,1,\ldots ,1)}$, alors un tableau de Young semi-standard de ce poids ${\displaystyle \mu }$ est un tableau de Young standard, et le nombre de tableaux de Young standard de forme ${\displaystyle \lambda }$ est donnée par la formule des équerres (en) des tableaux de Young.

En plus de la définition purement combinatoire donnée ci-dessus, les nombres de Kostka peuvent également être définis comme les coefficients dans l'expression d'un polynôme de Schur ${\displaystyle s_{\lambda }}$ comme combinaison linéaire de fonctions symétriques monomiales ${\displaystyle m_{\mu }}$. Ces fonctions sont définies, pour une partition donnée ${\displaystyle \mu =(\mu _{1},\mu _{2},\ldots ,\mu _{n})}$, par^[4] :

${\displaystyle m_{\mu }=\sum x_{i_{1}}^{\mu _{1}}x_{i_{2}}^{\mu _{2}}\cdots x_{i_{n}}^{\mu _{n}}}$

où la sommation est sur toutes les permutations ${\displaystyle (i_{1},i_{2},\ldots ,i_{n})}$ des entiers de 1 à ${\displaystyle n}$^[5].

L'expression est alors :

${\displaystyle s_{\lambda }=\sum _{\mu }K_{\lambda \mu }m_{\mu }.\ }$

Exemple

Les nombres de Kostka pour les sept partitions en au plus trois termes sont :

• ${\displaystyle K_{()()}=1}$. Ici ${\displaystyle ()}$ dénote la partition vide.
• ${\displaystyle K_{(1)(1)}=1}$
• ${\displaystyle K_{(2)(2)}=K_{(2)(1,1)}=1}$
• ${\displaystyle K_{(1,1)(1,1)}=1,K_{(1,1)(2)}=0}$
• ${\displaystyle K_{(3)(3)}=K_{(3)(2,1)}=K_{(3)(1,1,1)}=1}$
• ${\displaystyle K_{(2,1)(3)}=0,K_{(2,1)(2,1)}=1,K_{(2,1),(1,1,1)}=2}$
• ${\displaystyle K_{(1,1,1)(3)}=K_{(1,1,1)(2,1)}=0,K_{(1,1,1)(1,1,1)}=1}$

Ces valeurs sont les coefficients des développements des polynômes de Schur dans la base des fonctions symétriques monomiales :

• ${\displaystyle s_{()}=m_{()}=1}$ (l'indice est la partition vide)
• ${\displaystyle s_{1}=m_{1}}$
• ${\displaystyle s_{2}=m_{2}+m_{11}}$
• ${\displaystyle s_{11}=m_{11}=1}$
• ${\displaystyle s_{3}=m_{3}+m_{21}+m_{111}}$
• ${\displaystyle s_{21}=m_{21}+2m_{111}}$
• ${\displaystyle s_{111}=m_{111}}$

Kostka^[6] donne les tables de ces nombres pour les partitions d'entiers inférieurs ou égaux à 8.

Les liens entre la théorie des fonctions symétriques et la théorie des représentations montrent que les nombres de Kostka expriment également la décomposition du module ${\displaystyle M_{\mu }}$ en termes des représentations ${\displaystyle V_{\lambda }}$ correspondant aux caractères de ${\displaystyle s_{\lambda }}$, c'est-à-dire que

${\displaystyle M_{\mu }=\bigoplus _{\lambda }K_{\lambda \mu }V_{\lambda }.}$

Quant aux représentations du groupe général linéaire ${\displaystyle \mathrm {GL} _{n}(\mathbb {C} )}$, le nombre de Kostka ${\displaystyle K_{\lambda \mu }}$ compte la dimension de l'espace de poids (en) correspondant à ${\displaystyle \mu }$ dans la représentation irréductible ${\displaystyle V_{\lambda }}$ (ici ${\displaystyle \mu }$ et ${\displaystyle \lambda }$ sont supposées avoir au moins ${\displaystyle n}$ termes).

Les nombres de Kostka sont des valeurs particulières des polynômes de Kostka (en) en une ou deux variables :

${\displaystyle K_{\lambda \mu }=K_{\lambda \mu }(1)=K_{\lambda \mu }(0,1).}$

• Alain Lascoux, « Fonctions symétriques », Séminaire Lotharingien de Combinatoire, vol. 8,‎ 1984, p. 37-58, article n^o B08f (lire en ligne)
• Carl Kostka, « Über den Zusammenhang zwischen einigen Formen von symmetrischen Funktionen », Journal für die reine und angewandte Mathematik, vol. 93,‎ 1882, p. 89–123 (lire en ligne)
• (en) Alain Lascoux, Bernard Leclerc et Jean-Yves Thibon, « The plactic monoid », dans M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (n^o 90), 2002 (ISBN 978-0-521-81220-7, lire en ligne), p. 164-196
• (en) Ian G. Macdonald, Symmetric functions and Hall polynomials, Oxford University Press, coll. « Oxford Mathematical Monographs », 1995, 2^e éd., 475 p. (ISBN 978-0-19-853489-1, MR 1354144, présentation en ligne)
• (en) Bruce E. Sagan, The Symmetric Group : Representations, Combinatorial Algorithms, and Symmetric Functions, New York/Berlin/Heidelberg etc., Springer, coll. « GTM » (n^o 203), 2001, 2^e éd., 238 p. (ISBN 0-387-95067-2, présentation en ligne)
• (en) Bruce E. Sagan, « Schur functions in algebraic combinatorics », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)
• (en) Richard P. Stanley, Enumerative Combinatorics, vol. 2, Cambridge/New York/Melbourne etc., Cambridge University Press, 1999, 585 p. (ISBN 0-521-56069-1), lien Math Reviews

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kostka number » (voir la liste des auteurs).

• Portail des mathématiques