Algorithme de Pak et Stoyanovskii (original) (raw)

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'articleAnother involution principle-free bijective proof of Stanley's hook-content formulacontient 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 preuvecombinatoire et bijective de laformule des �querres.

Cet algorithme permet de construire destableaux standard al�atoires(avec distribution uniforme, pour une forme donn�e) ; en voici quelques-uns,dessin�s en 3 dimensionspar 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:

• la d�finition g�n�rale d'une �tape, qui, pour l'essentiel, ins�re la case courante dans le tableau standard situ� au Sud-Est de cette case;
• un exemple d'ex�cution d�taill�e des 7 �tapes de l'algorithme appliqu� � une permutation inscrite dans un diagramme de forme 3 2 2.

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. Ilinverse exactement chaque �tapede 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� parJ.B�tr�male 4 Octobre 1995.