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:
- un tableau standard
(ie. les numéros des cases sont croissants,
dans chaque ligne et chaque colonne),
de forme lambda;
- un diagramme annexe de même forme,
rempli avec des entiers e(i,j) vérifiant:
-jambe (i,j)
<= e(i,j)
<= bras (i,j)
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.