Algorithme de Pak et Stoyanovskii


I.M.Pak, A.V.Stoyanovskii : A bijective proof of the hook-length formula and its analogs. Functional Analysis and its Applications, vol.26, number 3, pages 216-218 (1992).

Cet article décrit l'algorithme direct, et annonce qu'il est bijectif. L'algorithme inverse a été reconstruit par Jean-Christophe Novelli, qui l'a exposé au groupe de travail de combinatoire énumérative de Bordeaux en Juin 1995, avec l'idée de la preuve.

Note ajoutée en octobre 1998 : l'article Another involution principle-free bijective proof of Stanley's hook-content formula contient une extension remarquable de l'algorithme, par Christian Krattenthaler, avec une preuve claire et rigoureuse, et toutes les références souhaitables. De même que l'algorithme de Robinson et Schensted est désormais souvent désigné par le sigle RSK, pour tenir compte de l'apport de Knuth (1970), je propose de désigner désormais l'algorithme de Pak et Stoyanovskii par le sigle PSK.


Bijection

Soit une partition donnée lambda de n, représentée par son diagramme de Ferrers; chaque case du diagramme est repérée par ses coordonnées matricielles (i,j) (ligne i, colonne j). L'algorithme transforme une permutation de 1, 2, ... n en: Le nombre de choix pour e(i,j) est donc égal à équerre (i,j), et le nombre de diagrammes annexes possible est donné par le produit des équerres. Comme cet algorithme est bijectif, il fournit une preuve combinatoire et bijective de la formule des équerres.

Cet algorithme permet de construire des tableaux standard aléatoires (avec distribution uniforme, pour une forme donnée) ; en voici quelques-uns, dessinés en 3 dimensions par Maple.


Algorithme direct

On inscrit la permutation de départ dans un diagramme de Ferrers delta de forme lambda (par exemple ligne par ligne). L'algorithme parcourt le diagramme de bas en haut et de droite à gauche (en adoptant les conventions américaines), et trie progressivement la permutation, pour la transformer en un tableau standard. En même temps, il construit le diagramme annexe.

L'algorithme comporte donc n étapes, une par case du diagramme. Voici:


Algorithme inverse

L'algorithme inverse parcourt évidemment le tableau de haut en bas et de gauche à droite, et reconstruit la permutation initiale en utilisant les informations du diagramme annexe. Il inverse exactement chaque étape de l'algorithme direct, en évacuant une case désignée par le diagramme annexe.

La difficulté de cette partie réside dans le choix de la case à évacuer, car l'information contenue dans le diagramme annexe est a priori ambiguë.


Document réalisé par J.Bétréma le 4 Octobre 1995.