Tableaux de Young semi-standard

Saturne · August 2018

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, .... ?

claude quitté · September 2018

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 ?

Math Coss · September 2018

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

claude quitté · September 2018

@Math Coss
Du pognon en vue ?

Saturne · October 2018

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

Tableaux de Young semi-standard

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 25