CONSÉQUENCES ÉNUMÉRATIVES DE LA SYMÉTRIE DES FONCTIONS DE SCHUR (*)

Jacques Désarménien (**)

R^{}ÉSUM^{}É. — Nous donnons les conséquences combinatoires de la symétrie des fonctions de Schur sur les tableaux et permutations sous-jacents.

ABSTRACT. — We indicate the combinatorial consequences of the symmetry of Schur functions for the underlying tableaux and permutations.

Introduction

Nous avons grandement exploité dans plusieurs publications le lien existant entre fonctions symétriques (plus spécialement certaines fonctions de Schur) et dénombrement de permutations par nombre de reculs et indice majeur inverse (cf. [D–F] et [D–W], entre autres). Assez curieusement, l’une des caractéristiques des fonctions de Schur, la symétrie, n’y est pas utilisée. Elle se traduit pourtant de manière simple et les interprétations bijectives se transportent sans peine des unes aux autres. De plus, une bijection de Gessel [G] permet de donner le même type de résultat pour les permutations de structure cyclique donnée.

1. Résultats

Soit σ une permutation dans 𝔖_{n}. Un recul de σ est un entier i ∈ [n − 1] tel que σ(i + 1) < σ(i). On note rec(σ) l’ensemble des reculs de σ.

Les sous-ensembles de [n] sont en bijection avec les compositions (ou permutations ordonnées) de n. À l’ensemble E = {e_{1}, e_{2}, …, e_{k}}, dont les éléments sont ordonnés de façon croissante, on associe la composition (e_{1}, e_{2}−e_{1}, …, e_{k}−e_{k−1}, n−e_{k}) de n. On identifiera par la suite l’ensemble E et la composition associée. En “oubliant” l’ordre des éléments de la composition E, on obtient une partition π(E) de n.

On dira enfin que la permutation σ est de classe E lorsque rec(σ) ∈ E. Nous distinguerons la forme (“up-down sequence”) et le type (stucture

en cycles) d’une permutation. Soient φ une forme et λ une partition de n, ainsi que E une composition de n.

(*) Soutien par le P.R.C. Mathématiques et Informatique.

(**) Département d’informatique, I.U.T. Strasbourg III, 72, route du Rhin, F-67400 Illkirch-Graffenstaden.

Notons respectivement A_{φ}(E) et B_{λ}(E) les ensembles de permutations de classe E et de forme φ ou de type λ. Notons pour finir A_{φ}(E) et B_{λ}(E) le nombre respectif d’éléments des deux ensembles précédents.

Théorème 1. — La forme φ et le type λ étant fixés, les nombres A_{φ}(E) et B_{λ}(E) ne dépendent que de la partition π(E) sous-jacente à E.

La démonstration de ce résultat va être illustrée par un exemple dans la section suivante. Les détails des constructions utilisées et les justificatifs se trouvent résumés dans [D–W].

2. Exemples

Considérons la permutation σ = 623471598 de 𝔖_{9}. On a rec(σ) = {1, 5, 8}. Sa forme est représentée de manière commode en assimilant cette permutation à un tableau de Young :

6 2 3 4 7 1 5 9 8 .

Fixons-nous maintenant un sous-ensemble E ⊂ [n] contenant rec(σ) de façon que σ soit de classe E. Prenons E = {1, 5, 7, 8} dont la composition associée est E = (1, 4, 2, 1, 1). Pour illustrer le théorème, nous allons montrer comment construire une permutation σ′ de même forme et dont la classe E′ = (1, 2, 4, 1, 1) s’obtient en permutant deux éléments consécutifs de E.

À partir de E = (e_{1}, e_{2}, …, e_{k}) on construit la suite s constituée de e_{1} fois k, e_{2} fois k − 1, …, e_{k} fois 1, en ordre décroissant. Ici, s = (5, 4, 4, 4, 4, 3, 3, 2, 1).

Reportons ces valeurs dans l’ordre dans le tableau de Young associé à σ :

3 4 4 4 3 5 4 1 2 .

On obtient ainsi un tableau semi-standard dont les éléments sont strictement décroissants dans les colonnes et décroissants au sens large dans les lignes. Ce sont précisément ces tableaux qui interviennent dans les fonctions de Schur.

Il s’agit maintenant de permuter convenablement les 3 et les 4 de ce tableau. Les groupes constitués de ces deux nombres superposés sont laissés inchangés ; dans une même ligne, les 4 et les 3 restants sont permutés puis réordonnés. Le tableau semi-standard ainsi obtenu est :

3 4 4 3 3 5 3 1 2 .

Enfin, on renormalise en numérotant par ordre décroissant et de gauche à droite :

4 2 3 5 6 1 7 9 8 .

La permutation associée σ′ = 423561798 a la même forme que σ; elle est bien de classe E′ = (1, 2, 4, 1, 1) = {1, 3, 7, 8}, puisque rec(σ′) = {1, 3, 8}.

L’argument utilisé ici est la proposition 2 de [D–W] (cf. [M]), et la symétrie des fonctions de Schur.

En utilisant la bijection de Gessel (cf.[G] et proposition 8 de [D–W]), on obtient une construction analogue qui préserve le type.

Reprenons la permutation σ plus haut. Sa décomposition en cycles est :

σ = (16)(2)(3)(4)(57)(89).

Récrivons ces cycles en commençant par leur plus grand élément et par ordre croissant de celui-ci : 2 3 4 61 75 98. Cette écriture permet de reconstituer σ : les débuts de cycles ne sont autres que les éléments saillants du mot. Utilisons maintenant la même suite s = (5, 4, 4, 4, 4, 3, 3, 2, 1) définie par la composition E que nous plaçons dans le mot précédent dans l’ordre indiqué par celui-ci :

4 4 4 35 34 12.

Nous obtenons ainsi un mot dont la factorisation de Lyndon (cf. [L] et [D–W]) correspond au type cyclique de σ.

Permutons maintenant les 3 et les 4 dans chacun des facteurs :

3 3 3 45 43 12.

Après permutation circulaire éventuelle des facteurs et leur réordonnement de manière à obtenir de nouveau une factorisation de Lyndon :

45 34 3 3 3 12,

puis normalisation dont la méthode est indiquée dans [D–W] :

21 43 5 6 7 98.

On obtient ainsi la décomposition en cycles d’une permutation σ′′ = (12)(34)(5)(6)(7)(89)dont la suite des valeurs est σ′′ = 214356798. Cette permutation a bien entendu même type que σ. On peut, de plus, montrer que sa classe est E′ = {1, 3, 7, 8} comme pour σ′. Ici, rec(σ′′) = {1, 3, 8}.

Dans un cas comme dans l’autre, la construction sommairement décrite est évidemment une bijection.

En fait, les nombres A_{φ}(E) et B_{λ}(E) sont les coefficients des monômes x_{1}^{e_{1}}x_{2}^{e_{2}} … x_{k}^{e_{k}} dans la fonction de Schur S_{φ} et dans la fonction symétrique de colliers L_{λ} respectivement. La symétrie de ces fonctions est bien évidemment équivalente au théorème 1. Dans le premier cas, ce coefficient est bien connu.

Théorème 2. — Le nombre A_{φ}(E) est égal au nombre de Kostka K_{φ}(π(E)), coefficient de la fonction monomiale m_{π(E)} dans S_{φ}.

BIBLIOGRAPHIE

[D–F] D^{}ÉSARM^{}ÉNIEN (Jacques) et FOATA (Dominique). — Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. math. France, t. 113, 1985, p. 3–22.

[D–W] D^{}ÉSARM^{}ÉNIEN (J.) et WACHS (M.). — Descentes sur les dérangements et mots circulaires, Séminaire lotharingien de combinatoire, 19^{e} session, [Strehl (V.), éd. ; Schloß Schwannberg/Ufr. 22–25 mars 1988], p.13–21. — Strasbourg, Publ. I.R.M.A. 361/S–19, 1988.

[G] GESSEL (Ira). — Note non publiée.

[L] LOTHAIRE (M.). — Combinatorics on words. — Reading, Addison-Wesley (Encyclopedia of Mathematics and its Applications, vol. 17), 1983.

[M] MACDONALD (Ian G.). — Symmetric functions and Hall polynomials. — Oxford, Clarendon Press, 1979.