Tableaux de Young semi-standard
Bonjour,
Etant donnée une partition $\lambda$, connaissez-vous un algorithme pour énumérer (lister) tous les tableaux de Young semi-standard de forme $\lambda$ et de contenu 1, 2, 3, .... ?
Etant donnée une partition $\lambda$, connaissez-vous un algorithme pour énumérer (lister) tous les tableaux de Young semi-standard de forme $\lambda$ et de contenu 1, 2, 3, .... ?
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Deux semaines sont passées et toujours rien. Je prends 5 minutes pour dire 2 ou 3 petites bricoles mais cela n'ira pas loin. Tu as bien dit semi-standard. La première chose est de savoir dénombrer ces tableaux (pour être sûr de l'algorithme de génération). Il y a une formule qui est appelée je crois ``hook-content formula'' (Stanley) et une autre dont je ne connais pas le nom. Rassure toi, je ne vais pas coucher les 450 tableaux de forme $\lambda$, $n$-garnis. Juste un, pour que l'on soit bien d'accord sur standard versus semi-standard. La formule que je connais est :
$$
N_{\lambda,n} = \prod_{1 \le i < j \le n} {\lambda_i - \lambda_j + j-i \over j-i}
$$
La voici opérant ci-dessous. Petit détail technique : je suis obligé de compléter $\lambda$ à 0 pour avoir la longueur $n$. Un truc qui m'a toujours semblé étrange : quand tu translates les termes d'une partition par une constante, cela ne change pas le nombre de tableaux. Cela se voit sur la formule plus haut. NumberOfTableauxOnAlphabet c'est le logiciel qui bosse et il lui faut presque 7 secondes. J'en ai déduit qu'il s'agit d'une autre formule (celle de Stanley ?).
Quant à la génération, je n'en sais rien. As tu regardé chez les combinatoriciens concepteurs de Symmetrica par exemple https://www.sciencedirect.com/science/article/pii/0747717192900353 ?
Question indiscrète (tu n'es pas obligé de répondre) : dans quel but ? Pour faire mumuse avec les fonctions de Schur ? Pour faire tourner dans l'espace tes truc diaboliques (genre tores ..etc..) que l'on voit dans les fils de géométrie ?
En pratique, on stocke la liste des tableaux partiellement remplis dans une liste tmp.
On sort le premier tableau T de tmp (pop(0)) et on le traite.
Si T est rempli, on l'ajoute dans la liste de résultats, res.
Sinon, on essaie d'ajouter une case. Si la dernière ligne du tableau, disons la $k$-ième est complète (i.e. sa longueur est $\lambda_k$), on ouvre une ligne supplémentaire ; sinon, on ajoute un coefficient. Pour ajouter un coefficient, on fait une boucle sur les valeurs permises, de max(coeff de gauche, coeff au-dessus +1) à n. Il y a des cas qui correspondent aux situations où il n'y a pas de coefficient au-dessus ou à gauche. Pour chaque case que l'on peut ajouter, on complète le tableau qu'on met dans la liste tmp pour le traitement suivant. On continue tant que tmp n'est pas vide. En sortie, et test de cohérence avec les résultats de Claude et ceux de Sage, qui connaît les tableaux semi-standards (pas pour me vanter, hein...) :
Du pognon en vue ?
Pour rien... Je me suis amusé à programmer les tableaux standard, je me demandais par curiosité comment faire pour les semi-standard. Je n'ai trouvé aucune doc à ce sujet. J'ai trouvé un code en Haskell mais je ne l'ai pas compris (d'ailleurs je trouve que Haskell est parfois plus facile à écrire qu'à lire).