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, .... ?
Réponses
-
Saturne,
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.[color=#000000] > lambda := [4,3,3,2] ; > n := 5 ; > NumberOfTableauxOnAlphabet(lambda,n) ; 450 > T := TableauxOfShape(lambda,n) ; > #T ; 450 [/color]
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.[color=#000000] > t := Random(T) ; > t ; Tableau of shape: 4 3 3 2 1 1 1 3 2 2 3 4 4 5 5 5 [/color]
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$.[color=#000000] > lambda := lambda cat [0^^(n-#lambda)] ; > lambda ; [ 4, 3, 3, 2, 0 ] > N := func < lambda, n | &*[(lambda[k]-lambda[j] + j-k)/(j-k) : k in [1..j-1], j in [1..n]] > ; > N(lambda,n) ; 450 [/color]
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.[color=#000000] > time N(lambda,n) ; 450 Time: 0.000 > time NumberOfTableauxOnAlphabet(lambda,n) ; 450 Time: 6.940 [/color]
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 ? -
Voici une implémentation de l'algorithme idiot : on remplit case par case de gauche à droite et de haut en bas en mettant toutes les valeurs autorisées à chaque fois.
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.def tableaux_ss(lam,n): tmp, res = [[]], [] while tmp!= []: T = tmp.pop(0) #print "T : %s" % T if len(T)==len(lam) and len(T[-1])>=lam[-1]: res.append(T) else: k = len(T)-1 # indice de la ligne de T à traiter if len(T)==0 or len(T[k])==0 or len(T[k])==lam[k]: # le tableau T est vide ou la ligne k est vide ou pleine # il faut donc ajouter une nouvelle ligne # calculons le premier élément, debut if k==-1: # le tableau est vide, on part de 1 debut = 1 else: # le tableau a au moins une ligne # on part du premier coefficient +1 debut = T[k][0]+1 # on ajoute une ligne contenant une case # contenant toutes les valeurs autorisées for u in range(debut,n+1): U = deepcopy(T) U.append([ u]) tmp.append(U) else: # la ligne k n'est pas pleine # il faut ajouter une case à la ligne k # calcul du debut if k==0: # pas de ligne au-dessus # seul compte le coefficient à gauche debut = T[k][-1] else: # il y a une ligne au-dessus # il faut être >= coeff de gauche et < coeff de dessus debut = max(T[k][-1],T[k-1][len(T[k])]+1) for u in range(debut,n+1): U = deepcopy(T) U[k].append(u) tmp.append(U) return res
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...) :time len(tableaux_ss([4,3,3,2],5)) 450 Time: CPU 0.10 s, Wall: 0.10 s SST = SemistandardTableaux([4,3,3,2],max_entry=5) time len(SST.list()) 450 Time: CPU 0.15 s, Wall: 0.15 s
-
@Math Coss
Du pognon en vue ? -
Merci à vous !Question indiscrète (tu n'es pas obligé de répondre) : dans quel but ?
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).
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.8K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres