Bull. Soc. math. France, 113, 1985, p. 3-22.

FONCTIONS SYMÉTRIQUES ET SÉRIES

HYPERGÉOMÉTRIQUES BASIQUES MULTIVARIÉES

PAR

Jacques DÉSARMÉNIEN et Dominique FOATA (^{∗})

R^{}ÉSUM^{}É. — L’étude de certaines statistiques sur le groupe symétrique fait apparaître des fonctions hypergéométriques basiques multivariées. De nouvelles identités sur ces fonctions, ainsi que leurs interprétations combinatoires, sont obtenues ici à partir d’un calcul classique sur les fonctions de Schur gauches.

ABSTRACT. — Multivariate basic hypergeometric series occur in the study of certain statistics on the symmetric group. New identities on those functions as well as their combinatorial interpretations are here obtained by means of a classical calculation on the skew Schur functions.

1. Introduction

La théorie des fonctions hypergéométriques basiques [2, 3, 23] fait apparaître des séries normalisées par des quantités de la forme (a; q)_{n}

(^{∗}) Texte reçu le 30 mai 1984, révisé le 28 novembre 1984.

Cet article a été composé au moyen du logiciel TEX par le laboratoire de typographie informatique du département de mathématique de Strasbourg, puis envoyé sur bande magnétique pour révision au département d’informatique de l’Université Stanford, où le premier auteur était en détachement en 1983-84.

Les légères modifications proposées par l’arbitre anonyme ont été intégrées dans le fichier de saisie rapatrié à Strasbourg. Ce fichier a été ensuite envoyé à la Société Américaine de Mathématique à Providence, R.I. (Etats-Unis), qui, après traitement sur une photo-composeuse ALPHATYPE, d’une résolution de 6.000 points par pouce, a renvoyé un film à partir duquel le présent texte a été imprimé et reproduit.

J. D^{}ÉSARM^{}ÉNIEN et D. FOATA, département de mathématique, Université Louis-Pasteur de Strasbourg, 7, rue René-Descartes, 67084 Strasbourg Cedex.

BULLETIN DE LA SOCIÉTÉ MATHÉMATIQUE DE FRANCE

0037-9484/1985/3/$ 5.00

◯^{c} Gauthier-Villars

et (a; q)_{∞} définies par :

\begin{aligned}(a; q)_{0} & = 1 \\ (a; q)_{n} & = (1 − a)(1 − aq) … (1 − aq^{n−1}) \\ (a; q)_{∞} & = lim_{n}(a; q)_{n} = ∏_{n≥0}(1 − aq^{n}). \end{aligned}

Les formules suivantes :

(1.1a)  ∑_{n} \frac{u^{n}}{(q; q)_{n}} = \frac{1}{(u; q)_{∞}} ,
(1.1b)  ∑_{n} q^{n(n−1)/2} \frac{u^{n}}{(q; q)_{n}} = (−u; q)_{∞},

(1.1c)  ∑_{n}(a; q)_{n} \frac{u^{n}}{(q; q)_{n}} = \frac{(au; q)_{∞}}{(u; q)_{∞}} ,

où n varie de 0 à +∞, sont les outils de base de cette théorie. Les deux premières apparaissent comme des q-analogues de la formule exponentielle. Elles sont aussi deux cas particuliers de la troisième, qu’on désigne habituellement par formule q-binomiale (cf. [1, 2]).

On connaît assez peu de choses sur les fonctions hypergéométriques basiques à plusieurs variables (cf. [2, 3, 23]). En revanche, le développement de certains produits infinis et aussi l’étude de certaines statistiques sur le groupe symétrique font apparaître des identités qui sont probablement des cas particuliers de formules de transformation sur ces fonctions. Pour chaque paire d’entiers positifs r, s, posons :

(u; q_{1}, q_{2})_{r,s} = 1,  si r ou s est nul ;

= ∏_{1≤i≤r} ∏_{1≤j≤s}(1 − uq_{1}^{i−1}q_{2}^{j−1}), si r, s ≥ 1,

et

\begin{aligned}(u; q_{1}, q_{2})_{∞,∞} & = lim_{r,s}(u; q_{1}, q_{2})_{r,s} \\ & = ∏_{i≥1} ∏_{j≥1}(1 − uq_{1}^{i−1}q_{2}^{j−1}). \end{aligned}

Les trois développements de produits infinis :

(1.2a)  ∑_{n} A_{n}(q_{1}, q_{2})\frac{u^{n}}{(q_{1}; q_{1})_{n} (q_{2}; q_{2})_{n}} = \frac{1}{(u; q_{1}, q_{2})_{∞,∞}} ,
(1.2b)  ∑_{n} B_{n}(q_{1}, q_{2})\frac{u^{n}}{(q_{1}; q_{1})_{n} (q_{2}; q_{2})_{n}} = (−u; q_{1}, q_{2})_{∞,∞},

(1.2c) ∑_{n} C_{n}(z, q_{1}, q_{2})\frac{u^{n}}{(q_{1}; q_{1})_{n} (q_{2}; q_{2})_{n}} = \frac{(−zu; q_{1}, q_{2})_{∞,∞}}{(u; q_{1}, q_{2})_{∞,∞}} ,

TOME 113 — 1985 — N^{o} 1

peuvent être ainsi considérés comme des identités sur les fonctions hypergéométriques basiques à deux variables.

Considérons enfin les trois identités :

(1.3a) ∑_{n} A_{n} \frac{u^{n}}{(t_{1}; q_{1})_{n+1} (t_{2}; q_{2})_{n+1}} = ∑_{r,s} t_{1}^{r}t_{2}^{s} \frac{1}{(u; q_{1}, q_{2})_{r+1,s+1}} ,

(1.3b) ∑_{n} B_{n} \frac{u^{n}}{(t_{1}; q_{1})_{n+1} (t_{2}; q_{2})_{n+1}} = ∑_{r,s} t_{1}^{r}t_{2}^{s}(−u; q_{1}, q_{2})_{r+1,s+1},

(1.3c) ∑_{n} C_{n} \frac{u^{n}}{(t_{1}; q_{1})_{n+1} (t_{2}; q_{2})_{n+1}} = ∑_{r,s} t_{1}^{r}t_{2}^{s} \frac{(−zu; q_{1}, q_{2})_{r+1,s+1}}{(u; q_{1}, q_{2})_{r+1,s+1}} ,

où n, r et s varient de 0 à +∞. Ces trois formules expriment le fait que la série en deux variables t_{1}, t_{2} du second membre peut se développer en une série en une variable u, convenablement normalisée, les coefficients, comme nous allons le voir, étant des polynômes : A_{n} = A_{n}(t_{1}, t_{2}, q_{1}, q_{2}), B_{n} = B_{n}(t_{1}, t_{2}, q_{1}, q_{2}) et C_{n} = C_{n}(z, t_{1}, t_{2}, q_{1}, q_{2}), respectivement à quatre et cinq variables.

Comme le suggère la numérotation utilisée et comme nous l’indiquerons dans cet article, chaque formule (1.ic) entraîne (1.ib) et (1.ia) pour i = 1, 2, 3. De même, pour x fixé égal à l’une des lettres a, b, c, on a les implications (1.3x) ⇒ (1.2x) ⇒ (1.1x). La formule (1.3c) entraîne donc toutes les précédentes.

C’est CARLITZ [4] qui a montré que (1.2a), (1.2b) et (1.2c), cette dernière pour z fixé égal à 1, définissaient trois suites de polynômes A_{n} = A_{n}(q_{1}, q_{2}), B_{n} = B_{n}(q_{1}, q_{2}) et C_{n} = C_{n}(z, q_{1}, q_{2}) (n ≥ 0) à coefficients entiers positifs et satisfaisant à A_{n}(1, 1) = B_{n}(1, 1) = n!, C_{n}(1, 1, 1) = n! 2^{n}. Plus tard, GARSIA et GESSEL [10] ont obtenu l’extension (1.3a) de (1.2a) et montré que l’on définissait ainsi, pour chaque n ≥ 0, un polynôme A_{n} à coefficients entiers positifs de somme n!. En fait, ils ont trouvé, tout comme RAWLINGS [16], une interprétation combinatoire pour les polynômes A_{n}, dont nous reparlerons plus loin.

Il semble que personne jusqu’ici n’ait songé à donner une extension analogue aux formules (1.2b) et (1.2c). Le premier but de cet article est de les fournir. Ces extensions sont précisément (1.3b) et (1.3c), où B_{n} et C_{n} sont encore des polynômes à coefficients entiers positifs, la somme de leurs coefficients étant égale à n! et n! 2^{n}, respectivement.

La variable z que nous rajoutons aussi à (1.2c) a l’avantage de permettre de faire le lien avec le formulaire des fonctions hypergéométriques basiques à une variable.

Par ailleurs, la structure formelle des deux identités (1.2a) et (1.2b) ressemble trop à celle d’identités dues à CAUCHY sur les séries bilinéaires de fonctions de Schur S_{λ} pour qu’il n’existe pas de lien direct entre ces deux familles de formules. Rappelons que ces identités s’écrivent (cf. par exemple MACDONALD [15, p. 33 et 35]) :

(1.4)  ∑_{λ} S_{λ}(x)S_{λ}(y) = ∏_{i,j}(1 − x_{i}y_{j})^{−1},
(1.5)  ∑_{λ} S_{λ}(x)S_{λ′}(y) = ∏_{i,j}(1 + x_{i}y_{j}),

où λ varie dans l’ensemble de toutes les partitions d’entiers, où i et j varient de 0 à +∞ et enfin où λ′ désigne la partition conjuguée de λ.

Comme second but de cet article, nous nous proposons de montrer que les expressions analytiques des formules (1.2a) – (1.3c), ainsi que leurs contenus combinatoires, peuvent se déduire des formules (1.4) et (1.5) et des propriétés géométriques des fonctions de Schur, tout particulièrement de leur interprétation en termes de fonctions génératrices de tableaux (cf. [15, p. 42]).

Le troisième but de cet article est de calculer les fonctions génératrices des involutions en utilisant toujours les propriétés combinatoires et algébriques des fonctions de Schur. Rappelons que les formules (linéaires) de Schur sur les fonctions du même nom s’écrivent :

(1.6)  ∑_{λ} z^{c(λ)}S_{λ}(x) = ∏_{i}(1 − zx_{i})^{−1} ∏_{i<j}(1 − x_{i}x_{j})^{−1},
(1.7)  ∑_{λ} z^{r(λ)}S_{λ}(x) = ∏_{i}(1 + zx_{i}) ∏_{i≤j}(1 − x_{i}x_{j})^{−1},

où c(λ) (resp. r(λ)) désigne le nombre de colonnes (resp. de lignes) de longueur impaire de la partition λ (cf. [15, p. 46]). Notons H_{n}(z_{1}, z_{2}, t, q) le polynôme générateur des involutions de [n] = {1, 2, …, n} par nombre de points fixes, nombre de transpositions, nombre de descentes, indice majeur (ces deux dernières notions seront rappelées au début de la section 2). Notre troisième but est ainsi de montrer que (1.6) et (1.7) permettent d’établir les formules :

(1.8) ∑_{n} H_{n} \frac{u^{n}}{(q; q)_{n}} = ∑_{r} t^{r} \frac{1}{(z_{1}u; q)_{r+1}} ∏_{0≤i<j≤r} \frac{1}{(1 − u^{2}z_{2}q^{i+j})},

(1.9) ∑_{n} K_{n} \frac{u^{n}}{(q; q)_{n}} = ∑_{r} t^{r}(−z_{1}u; q)_{r+1} ∏_{0≤i≤j≤r} \frac{1}{(1 − u^{2}z_{2}q^{i+j})},

où n, r ≥ 0 et où K_{n} = K_{n}(z_{1}, z_{2}, t, q) désigne un autre polynôme générateur des involutions par des statistiques que nous préciserons dans la section 6. L’identité (1.8) a été obtenue par GESSEL [11] au moyen d’autres techniques combinatoires.

Cette méthode qui consiste à déduire des identités entre q-séries et q_{1}q_{2}- séries, ainsi que leur contenu combinatoire, de propriétés géométriques sur le groupe symétrique a été utilisée par D^{}ÉSARM^{}ÉNIEN [6, 7]. Elle a l’avantage de nécessiter peu de calculs et de n’impliquer aucune vérification de formules de récurrence.

L’organisation de l’article est la suivante. La section 2 contient une description de tous les outils combinatoires mis en œuvre. On y montre en particulier que l’identité (1.3c) entraîne toutes les précédentes formules, son contenu géométrique fournissant également l’interprétation combinatoire de chacune d’elles.

Pour établir ensuite (1.3c), on part d’une définition combinatoire du polynôme C_{n} = C_{n}(z, t_{1}, t_{2}, q_{1}, q_{2}) donnée en (2.10). On exprime ensuite (formule (3.3)) ce polynôme en termes de fonction génératrice de paires de tableaux standard d’une forme appropriée, en faisant appel à la correspondance de Robinson-Schensted (cf. [12, p. 48–73] et [18, 20, 22]).

Par ailleurs, on introduit une classe de fonctions de Schur gauches, notées S_{λ⊗μ}(x), qui permet d’intégrer les propriétés géométriques des tableaux dans le contenu algébrique des fonctions S_{λ⊗μ}(1, q, q^{2}, …, q^{r}). Le théorème 4.1 est en fait l’outil de transfert fondamental.

Partant enfin des formules bilinéaires (1.4) et (1.5), un simple jeu de substitution des indéterminés par des puissances de deux variables q_{1}, q_{2} permet d’établir (1.3c). Ceci fait l’objet de la section 5.

La dernière section, comme nous l’avons dit, est consacrée au calcul des fonctions génératrices des involutions, en faisant usage encore des techniques développées dans les sections précédentes.

2. Statistiques et résultats combinatoires

Soient n ≥ 0 et I = {i_{1} < i_{2} < ⋯ < i_{n}}, K = {k_{1} < k_{2} < ⋯ < k_{n}} deux sous-ensembles finis de N de cardinal n. Si σ est une bijection de I sur K, on note également σ le mot σ = σ(i_{1})σ(i_{2}) … σ(i_{n}). La ligne inverse de route de σ est définie comme l’ensemble noté Iligne σ de tous les entiers j tels que j et (j + 1) sont des lettres du mot σ, la lettre (j + 1) étant située à la gauche de j dans ce mot. On adopte les notations :

Ides σ = |Iligne σ|  et  Imaj σ = ∑{j : j ∈ Iligne σ}.

Le renversé de σ est défini comme le mot :

r σ = σ(i_{n}) … σ(i_{2})σ(i_{1}),

et si σ^{−1} désigne la bijection inverse de σ, on pose :

i σ = σ^{−1} = σ^{−1}(k_{1})σ^{−1}(k_{2}) … σ^{−1}(k_{n}).

En particulier,

(2.1)  r i σ = σ^{−1}(k_{n}) … σ^{−1}(k_{2})σ^{−1}(k_{1}).

Lorsque I = K = [n] (= {1, 2, …, n}), c’est-à-dire lorsque σ est une permutation de [n], on introduit les notations supplémentaires :

Ligne σ = {i : 1 ≤ i ≤ n − 1, σ(i) > σ(i + 1)}

Coligne σ = [n − 1] \ Ligne σ,

Des σ = |Ligne σ| , Maj σ = ∑{i : i ∈ Ligne σ},
Codes σ = |Coligne σ| , Comaj σ = ∑{i : i ∈ Coligne σ}.

Traditionnellement (cf. [8]), Ligne σ (resp. Coligne σ) est appelé ligne de route (resp. coligne de route) de σ, tandis que Des σ (resp. Codes σ, resp. Maj σ) est le nombre de descentes (resp. nombre de codescentes, resp. l’indice majeur) de σ. Enfin, le complément à (n + 1) de σ est défini comme le mot :

c σ = (n + 1 − σ(1))(n + 1 − σ(2)) … (n + 1 − σ(n)).

On peut faire agir le groupe diédral D_{4} d’ordre 8 sur l’ensemble S_{n} de toutes les permutations σ de [n] comme décrit dans le lemme suivant, dont la démonstration peut être trouvée dans [8].

Lemme 2.1. — Le sous-groupe des transformations de S_{n} engendré par {c, i, r} est le groupe diédral D_{4}. On a, de plus, les relations :

r c = c r,  r i = i c,  i r c = r c i, (2.2)

Ligne c σ = Coligne σ, Ligne i σ = Iligne σ, (2.3) Des i σ = Ides σ, Maj i σ = Imaj σ. (2.4)

CHEEMA et MOTZKIN [5], d’une part, ROSELLE [19], d’autre part, ont démontré que le polynôme A_{n}(q_{1}, q_{2}) défini par (1.2a) (resp. B_{n}(q_{1}, q_{2}) défini par (1.2b)) était la fonction génératrice du groupe symétrique S_{n} par le couple (Maj, Imaj) (resp. (Imaj, Comaj)).

L’interprétation combinatoire obtenue par GARSIA et GESSEL [10] (voir aussi RAWLINGS [16]) pour les polynômes A_{n} de la formule (1.3a) est consignée dans le théorème suivant.

Théorème 2.2. — Dans l’identité (1.3a) l’expression A_{n} est le polynôme générateur de S_{n} par le 4-vecteur (Des, Ides, Maj, Imaj).

En d’autres termes, on a :

(2.5)  A_{n} = A_{n}(t_{1}, t_{2}, q_{1}, q_{2}) = ∑_{σ} t_{1}^{Des σ}t_{2}^{Ides σ}q_{1}^{Maj σ}q_{2}^{Imaj σ},

avec σ variant dans S_{n}.

Ce théorème va apparaître comme cas particulier du résultat principal de cet article dont l’énoncé nécessite les notations suivantes.

Appelons permutation colorée d’ordre n tout couple a constitué par une permutation σ de [n] et par un choix de couples (i, σ(i)) supposés colorés en rouge, les autres couples l’étant en bleu. La restriction de σ aux couples rouges (resp. bleus) est une bijection σ_{1} : I → K (resp. σ_{2} : J → L). On a naturellement : I ∩ J = K ∩ L = ∅ et I ∪ J = K ∪ L = [n], de sorte qu’on peut aussi décrire une permutation colorée d’ordre n comme un quintuplet a = (σ, I, J, K, L), où σ est une permutation de [n] et où (I, J), (K, L) sont deux partitions de [n] en deux blocs, telles que |I| = |K| et |J| = |L|.

Le premier associé de a est défini comme le produit de juxtaposition :

(2.6)  a_{1} = σ_{1}σ_{2},

et le second associé comme :

(2.7)  a_{2} = (r i σ_{1})(i σ_{2})

(cf. la convention d’écriture donnée au début du paragraphe et tout particulièrement (2.1)). On note également R a le nombre de couples rouges de a. Si I = K = ∅, tous les couples sont bleus. On a alors :

(2.8)  a_{1} = σ  et  a_{2} = i σ.

Si J = L = ∅, tous les couples sont rouges, les deux associés devenant :

(2.9)  a_{1} = σ  et  a_{2} = r i σ.

Par exemple, soit :

σ = (\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 6 & 4 & 3 & 1 & 2 & 8 & 9 & 5 & 7 \end{matrix})

une permutation colorée d’ordre n = 9, les couples verticaux colorés en rouge (resp. bleu) apparaissant en maigre (resp. gras). Les deux associés s’écrivent :

a_{1} = 6, 4, 8, 9, 5, 3, 1, 2, 7  et  a_{2} = 7, 6, 1, 8, 2, 4, 5, 3, 9.

De plus, R a = 5.

Chaque associé a_{i} (i = 1, 2) possède une ligne de route bien définie. On peut donc considérer le 5-vecteur :

V (a) = (R a, Ides a_{1}, Ides a_{2}, Imaj a_{1}, Imaj a_{2}).

Dans l’exemple précédent, Iligne a_{1} = {2, 3, 5, 7}, Iligne a_{2} = {3, 5, 6}, de sorte que V (a) = (5, 4, 3, 17, 14).

Notre résultat fondamental est le suivant.

Théorème 2.3. — Dans l’identité (1.3c) l’expression C_{n} est le polynôme générateur des permutations colorées d’ordre n par le vecteur V.

Par conséquent, on a :

(2.10) C_{n} = C_{n}(z, t_{1}, t_{2}, q_{1}, q_{2}) = ∑_{a} z^{R a}t_{1}^{Ides a_{1}}t_{2}^{Ides a_{2}}q_{1}^{Imaj a_{1}}q_{2}^{Imaj a_{2}},

avec a variant dans l’ensemble des permutations colorées d’ordre n.

Faisons z = 0 dans (2.10). Les seules contributions non nulles à la somme sont les permutations colorées a dont les couples (i, σ(i)) sont bleus. D’après (2.8) et (2.4), on en déduit Ides a_{1} = Ides σ, Ides a_{2} = Des σ, Imaj a_{1} = Imaj σ et Imaj a_{2} = Maj σ. D’où C_{n}(0, t_{1}, t_{2}, q_{1}, q_{2}) (donné par (2.10)) est égal à A_{n}(t_{1}, t_{2}, q_{1}, q_{2}) (donné par (2.5)), puisque A_{n} est évidemment symétrique en t_{1}, t_{2} et q_{1}, q_{2}. On retrouve donc bien l’interprétation combinatoire des polynômes A_{n} obtenue par GARSIA et GESSEL [10] et RAWLINGS [16], à savoir le théorème 2.2. En particulier, (1.3c) ⇒ (1.3a).

Faisons tendre maintenant z vers l’infini dans z^{−n}C_{n}(z, t_{1}, t_{2}, q_{1}, q_{2}) donnée par (2.10). Il reste, pour le second membre, une somme sur les seules permutations colorées a dont tous les couples sont rouges. D’après (2.9) et le lemme 2.1, il en résulte : Iligne a_{2} = Iligne r i σ = Ligne i r i σ = Ligne c σ = Coligne σ. D’où Ides a_{1} = Ides σ, Ides a_{2} = Codes σ, Imaj a_{1} = Imaj σ et Imaj a_{2} = Comaj σ. On en tire le corollaire suivant.

Corollaire 2.4. — Dans l’identité (1.3b), l’expression B_{n} est le polynôme générateur de S_{n} par le 4-vecteur (Ides, Codes, Imaj, Comaj).

De même (1.3c) (resp. (1.3b), resp. (1.3a)) entraîne (1.2c) (resp. (1.2b), resp. (1.2a)). Il suffit de multiplier l’identité initiale par (1 − t_{1}) et de faire t_{1} = 1, puis par (1 − t_{2}) et de faire t_{2} = 1. On retrouve, en plus, les interprétations combinatoires des polynômes A_{n}(q_{1}, q_{2}) et B_{n}(q_{1}, q_{2}), que nous avons mentionnées juste après l’énoncé du LEMME 2.1, ainsi que l’interprétation nouvelle :

(2.11)  C_{n}(z, q_{1}, q_{2}) = ∑_{a} z^{R a}q_{1}^{Imaj a_{1}}q_{2}^{Imaj a_{2}}.

On se convainc ensuite que la substitution de q_{2} par 0 dans (1.2a) et (1.2b) donne (1.1a) et (1.1b), respectivement. De même (1.2c) ⇒ (1.1c), pourvu que l’on puisse établir l’identité :

(2.12)  C_{n}(z, q_{1}, 0) = (−z; q_{1})_{n}.

Or, d’après (2.11), on a :

C_{n}(z, q_{1}, 0) = ∑_{a} z^{R a}q_{1}^{Imaj a_{1}}

où la somme est faite sur les seules permutations dont le second associé est a_{2} = 12 … n. Les couples rouges et bleus de ces permutations colorées sont donc de la forme (1, k_{n_{1}}), …, (n_{1}, k_{1}) et (n_{1} + 1, l_{1}), …, (n, l_{n_{2}}), respectivement, avec k_{n_{1}} > ⋯ > k_{1} et l_{1} < ⋯ < l_{n_{2}}. Leur premier associé est alors :

(2.13)  a_{1} = k_{n_{1}} … k_{1}l_{1} … l_{n_{2}}.

Or il est immédiat de vérifier, par exemple par récurrence sur n, que la fonction génératrice des permutations a_{1} de la forme (2.13) par nombre de couples rouges et par Imaj est égale à (−z; q_{1})_{n}. Ceci prouve (2.12).

Notons enfin que RAWLINGS [17] a récemment obtenu une autre interprétation combinatoire pour C_{n}(z = 1, q_{1}, q_{2}) que l’on peut aussi déduire de la théorie des fonctions symétriques développée ci-dessous, mais qui ne permet pas d’extension facile à plus de deux variables.

3. La correspondance de Robinson-Schensted

Comme il est d’usage, on désigne par partition toute suite finie décroissante ν = (ν_{1}, ν_{2}, …, ν_{p}) d’entiers supérieurs ou égaux à 1. Si la somme ν_{1} + ν_{2} + ⋯ + ν_{p} de ces entiers est égale à n, on dit que ν est une partition de n et on pose |ν| = n. Le diagramme de Ferrers associé à ν est l’ensemble des couples (i, j) du plan euclidien satisfaisant à 1 ≤ i ≤ ν_{j}, 1 ≤ j ≤ p. Il est commode de l’identifier à la partition elle-même.

Soient ν = (ν_{1}, ν_{2}, …, ν_{p}) et θ = (θ_{1}, θ_{2}, …, θ_{r}) deux diagrammes de Ferrers. Si ν ⊃ θ, la différence ensembliste ν − θ, qu’on note le plus souvent ν/θ, est appelée diagramme gauche. Dans cet article, on s’intéressera plus particulièrement aux diagrammes gauches ν/θ de la forme suivante : on part de deux diagrammes de Ferrers quelconques λ = (λ_{1}, λ_{2}, …, λ_{p}) et μ = (μ_{1}, μ_{2}, …, μ_{r}) et l’on considère l’ensemble, noté λ ⊗ μ, de tous les translatés (λ_{1} + i, j) (1 ≤ i ≤ μ_{j} ; 1 ≤ j ≤ r) et (i, r + j) (1 ≤ i ≤ λ_{j} ; 1 ≤ j ≤ p).

Par exemple, avec λ = (3, 2) et μ = (3, 1), on obtient pour λ ⊗ μ le diagramme gauche matérialisé par les croix :

\begin{aligned}× & × \\ × & × & × \\ & & & × \\ & & & × & × & × \end{aligned}

La notation λ ⊗ μ nous a été conseillée par l’arbitre : le produit tensoriel des représentations associées aux partitions λ et μ est, en effet, la représentation associée au diagramme gauche λ ⊗ μ.

Soit I un sous-ensemble de cardinal n et ν/θ un diagramme gauche contenant n points. Supposons que l’on écrive les n entiers de I sur les n points du diagramme ν/θ de façon à obtenir une croissance dans chaque ligne (de gauche à droite) et chaque colonne (de bas en haut). La configuration obtenue est appelée tableau standard, de contenu I et de forme ν/θ. Lorsque I = [n], on remplace “de contenu I” par “d’ordre n”. Dans la suite, on utilisera essentiellement les tableaux standard d’ordre n, de forme ν/θ (et plus particulièrement ceux de forme λ ⊗ μ pour λ et μ quelconques tels que |λ| + |μ| = n) et les tableaux standard, de contenu I et de forme λ.

La ligne inverse de route (cf. [9]) d’un tableau standard T, de contenu I et de forme ν/θ, est l’ensemble des entiers k tels que k et (k + 1) sont dans I, l’entier (k + 1) étant écrit plus haut que k dans T. Cette ligne inverse de route est notée Iligne T. On pose également :

Ides T = |Iligne T |  et  Imaj T = ∑{i : i ∈ Iligne T }.

Par exemple,

P_{1} = 6 8 4 5 9 ; Q_{1} = 2 8 1 6 7 ; P_{2} = 3 1 2 7 ; Q_{2} = 4 3 5 9 ;

sont des tableaux standard, de forme λ = (3, 2), pour les deux premiers et μ = (3, 1) pour les deux derniers. Ils ont des contenus différents les uns des autres.

Les deux tableaux :

T_{1} = 6 8 4 5 9 3 1 2 7 T_{2} = 7 6 8 1 2 4 3 5 9

sont standard, d’ordre 9 ; le premier est de forme λ ⊗ μ, le second λ′ ⊗ μ. Ils sont formés au moyen des précédents tableaux de façon claire. La notation :

T_{1} = P_{1} ⊗ P_{2}  et  T_{2} = Q′_{1} ⊗ Q_{2}

est alors évidente. Notons que l’on a :

Iligne T_{1} = {2, 3, 5, 7}  et  Iligne T_{2} = {3, 5, 6}.

Le théorème suivant permet d’exprimer le polynôme générateur des permutations colorées en termes de fonction génératrice de paires de tableaux.

Théorème 3.1. — A toute permutation colorée a = (σ, I, J, K, L) d’ordre n, ayant pour associés a_{1} et a_{2}, correspond bijectivement un diagramme gauche λ ⊗ μ et une paire de tableaux standard (T_{1}, T_{2}), respectivement de forme λ ⊗ μ et λ′ ⊗ μ, tels que :

|I| = |K| = |λ|  et  |J| = |L| = |μ| , (3.1)
Iligne a_{1} = Iligne T_{1}  et  Iligne a_{2} = Iligne T_{2}. (3.2)

Le théorème 3.1 entraîne immédiatement le corollaire suivant.

Corollaire 3.2. — Soit C_{n} le polynôme générateur des permutations colorées, comme défini par l’identité (2.10). Alors, on a aussi :

(3.3)  C_{n} = ∑_{λ,μ} z^{|λ|} ∑_{T_{1}} t_{1}^{Ides T_{1}}q_{1}^{Imaj T_{1}} ∑_{T_{2}} t_{2}^{Ides T_{2}}q_{2}^{Imaj T_{2}},

où la première somme est sur l’ensemble des couples de diagrammes de Ferrers (λ, μ) tels que |λ| + |μ| = n, la seconde (resp. la troisième) sur les tableaux standard T_{1} (resp. T_{2}) d’ordre n et de forme λ ⊗ μ (resp. λ′ ⊗ μ).

La démonstration du théorème 3.1 se fait comme suit. Soit Bij(I, K) l’ensemble des bijections de I sur K, où I et K sont deux sous-ensembles finis de N de même cardinal. La correspondance de Robinson-Schensted (telle qu’elle est par exemple très bien expliquée dans [12, p. 48–72]) est une bijection ρ de Bij(I, K) sur l’ensemble de tous les couples (P, Q) de tableaux standard, de même forme λ avec |λ| = n, le contenu de P étant K, celui de Q étant I.

Pour utiliser pleinement ses propriétés, reprenons les mêmes notations qu’au début de la section 2, en particulier la convention d’écriture de chaque bijection comme un mot en ses valeurs prises. Si σ est une bijection telle que ρ(σ) = (P, Q), on a :

(3.4)  ρ(i σ) = (Q, P),
(3.5)  ρ(r σ) = (P′, R′),

où R est un tableau standard, de forme égale à celle de P et de contenu I. (Comme démontré par SCH^{}ÜTZENBERGER [21, 22], le tableau R se déduit de Q par l’opération de vidage-remplissage, décrite également — c’est l’opération S — dans [12, p. 57–79]. Les propriétés de cette opération ne sont pas utilisées ici.) On a, de plus (cf. [22]) :

(3.6)  Iligne σ = Iligne P.

De (3.4), (3.5) et (3.6), on déduit :

(3.7)  Iligne i σ = Iligne Q,
(3.8)  Iligne r i σ = Iligne Q′.

La bijection a ↦ (T_{1}, T_{2}) du théorème 3.1 se déduit comme suit. Partant du quintuplet a = (σ, I, J, K, L), on extrait les deux bijections σ_{1} : I ↦ K et σ_{2} : J ↦ L. Par la correspondance de Robinson-Schensted, on a :

ρ(σ_{1}) = (P_{1}, Q_{1}), ρ(σ_{2}) = (P_{2}, Q_{2}).

On pose alors :

T_{1} = P_{1} ⊗ P_{2}  et  T_{2} = Q′_{1} ⊗ Q_{2}.

Le caractère bijectif est évident, de même que les propriétés (3.1). Pour se convaincre de la véracité de (3.2), on peut remarquer que le contenu de P_{1} (resp. P_{2}) est J (resp. I). Donc l’ensemble noté Iligne(P_{1} ← P_{2}) des entiers k tels que k apparaît dans P_{2} et (k + 1) dans P_{1}, est égal à l’ensemble Iligne(σ_{1} ← σ_{2}) des lettres k du mot σ_{2} telles que (k + 1) est dans σ_{1}. Comme a_{1} = σ_{1}σ_{2}, on déduit de (3.7) :

Iligne σ_{1}σ_{2} = Iligne σ_{1} + Iligne σ_{2} + Iligne(σ_{1} ← σ_{2})
= Iligne P_{1} + Iligne P_{2} + Iligne(P_{1} ← P_{2})
= Iligne P_{1} ⊗ P_{2}.

La propriété (3.8) permet, de la même manière, de démontrer la seconde relation de (3.2).

On pourra vérifier que la paire de tableaux (T_{1}, T_{2}) décrite juste avant l’énoncé du théorème 3.1 correspond à la permutation colorée donnée à titre d’exemple dans la section 2.

Remarque. — Pour établir le théorème 3.1, on peut également faire appel aux techniques du monoïde plaxique [13, 14] et démontrer que les tableaux P_{1} ⊗ P_{2} et Q′_{1} ⊗ Q_{2} sont équivalents par le jeu de taquin aux permutations a_{1} et a_{2}, respectivement. En particulier, les propriétés (3.2) disent simplement que dans une même classe d’équivalence les propriétés plaxiques des éléments sont conservées.

4. Codage des tableaux semi-standard

Dans l’identité (4.1) ci-dessous, S_{ν/θ}(1, q, q^{2}, …, q^{r}) désigne la fonction de Schur gauche associée au diagramme gauche ν/θ, en (r + 1) variables égales respectivement à 1, q, q^{2}, …, q^{r} (voir [15, p. 42]).

Théorème 4.1. — Soit ν/θ un diagramme gauche de n éléments. On a l’identité :

(4.1)  \frac{1}{(t; q)_{n+1}} ∑_{T} t^{Ides T} q^{Imaj T} = ∑_{r} t^{r}S_{ν/θ}(1, q, q^{2}, …, q^{r}),

où la première sommation est faite sur l’ensemble des tableaux standard d’ordre n, de forme ν/θ et la seconde sur les entiers r ≥ 0.

La démonstration du théorème 4.1 nécessite la manipulation d’une nouvelle classe de tableaux, les tableaux semi-standard (“column strict”), qu’on construit de la façon suivante : on part d’un diagramme gauche ν/θ de n points, sur lesquels, on place n entiers, non nécessairement distincts, de façon à obtenir une décroissance au sens large dans les lignes (de gauche à droite) et une décroissance stricte dans les colonnes (de bas en haut). Par exemple,

τ = 2 1 3 3 1 5 8 6 2

est un tel tableau.

Tout tableau semi-standard τ, de forme ν/θ définit un ordre total sur les points du diagramme ν/θ, si l’on convient que le point (i, j) est avant (i′, j′) lorsque l’entier τ(i, j) écrit sur ce point est supérieur à τ(i′, j′), ou lorsque τ(i, j) = τ(i′, j′) et le point (i, j) est à la gauche de (i′, j′), c’est-à-dire si i < i′.

En écrivant k sur le point (i, j) de ν/θ, si ce point est le k^{ième} dans cet ordre, on obtient un tableau standard T, d’ordre n (si ν/θ a n éléments) et de forme ν/θ. D’autre part, la lecture des éléments du tableau semi-standard τ suivant cet ordre fournit une suite décroissante c = (c_{1}, c_{2}, …, c_{n}). Naturellement, k ∈ Iligne T ⇒ c_{k} > c_{k+1}. On définit une suite d = (d_{1}, d_{2}, …, d_{n}) par :

(4.2)  d_{k} = \{ \begin{matrix}c_{k} − c_{k+1}, & si k ∉ Iligne T et k ≤ n − 1; \\ c_{k} − c_{k+1} − 1, & si k ∈ Iligne T; \\ c_{n} − 1, & si k = n. \end{matrix}

Dans l’exemple ci-dessus, le tableau standard associé est le tableau T = T_{1} décrit dans l’exemple de la section 3. De plus,

\begin{aligned}c & = (8, 6, 5, 3, 3, 2, 2, 1, 1), Iligne T = \{2, 3, 5, 7\}, \\ d & = (2, 0, 1, 0, 0, 0, 0, 0, 0). \end{aligned}

Le couple (T, d) est le codage du tableau semi-standard τ et il est clair qu’à tout τ correspond une et une seule paire (T, d). Nous n’avons ici fait qu’adapter le codage des tableaux semi-standard de forme λ décrit dans [15, p. 42], aux mêmes types de tableaux, mais dont la forme est un diagramme gauche.

Soit maintenant (x_{1}, x_{2}, …) une suite de variables. La fonction de Schur gauche S_{ν/θ} associée à ν/θ est définie par (cf. [15, p. 42]) :

(4.3)  S_{ν/θ}(x_{1}, x_{2}, …) = ∑_{τ} ∏ x_{τ(i,j)},

où la somme est étendue à tous les tableaux semi-standard τ de forme ν/θ et le produit à tous les points (i, j) contenus dans ν/θ.

L’identité (4.1) se démontre alors de la façon suivante. Le développement du premier membre de (4.1) est une somme de la forme ∑ q^{γ}t^{δ}, étendue aux couples (T, d), où T est un tableau standard d’ordre n de forme ν/θ et d = (d_{0}, d_{1}, …, d_{n}) une suite de longueur (n + 1) d’entiers positifs ou nuls. De plus, pour chaque couple (T, d), on a :

γ = Imaj T + ∑_{k} kd_{k}  et  δ = Ides T + ∑_{k} d_{k} (0 ≤ k ≤ n).

D’après le codage décrit précédemment, la série est étendue, en fait, aux couples (τ, d_{0}), où τ est un tableau semi-standard de forme ν/θ et d_{0} un entier positif. Or, d’après (4.2) :

∑_{k=0}^{n} kd_{k} = ∑_{k=1}^{n} c_{k} − n − Imaj T  et  ∑_{k=0}^{n} d_{k} = d_{0} + c_{1} − 1 − Ides T.

Le premier membre de (4.1) est ainsi égal à ∑ q^{γ}t^{δ}, où la somme est étendue à toutes les paires (τ, d_{0}) et où γ = ∑_{k=1}^{k=n} c_{k} −n et δ = d_{0} +c_{1} −1. D’où :

(4.4)  ∑ q^{γ}t^{δ} = (1 − t)^{−1} ∑_{r} t^{r} ∑ q^{γ},

où la dernière somme est faite sur les tableaux τ tels que c_{1}(τ) = r + 1.

Or le développement de S_{ν/θ}(x_{1}, x_{2}, …, x_{r+1}) ne porte que sur les seuls tableaux semi-standard τ tels que c_{1}(τ) ≤ r + 1. Si, de plus, on fait la substitution x_{i} ← q^{i−1} (i = 1, 2, …, r + 1) dans S_{ν/θ}(x_{1}, x_{2}, …, x_{r+1}), le monôme ∏ x_{τ(i,j)} correspondant à τ est transformé en une puissance de q égale à ∑_{k=1}^{k=n} c_{k} − n = γ. De là :

∑ q^{γ}t^{δ} = (1 − t)^{−1} ∑_{r} t^{r}(S_{ν/θ}(1, q, …, q^{r}) − S_{ν/θ}(1, q, …, q^{r−1}))

= (1 − t)^{−1} ∑_{r}(t^{r} − t^{r+1})S_{ν/θ}(1, q, …, q^{r})

= ∑_{r} t^{r}S_{ν/θ}(1, q, …, q^{r}).

Ceci démontre le théorème 4.1.

5. Algèbre des fonctions de Schur

Nous disposons maintenant de tous les ingrédients pour démontrer le théorème 2.3. Partons des deux identités (1.4) et (1.5). D’après la définition de S_{ν/θ}(x) donnée en (4.3), on a pour un diagramme gauche de la forme ν/θ = λ ⊗ μ l’identité :

S_{λ⊗μ}(x) = S_{λ}(x)S_{μ}(x).

On en tire :

∑_{n} u^{n} ∑_{λ,μ} z^{|λ|}S_{λ⊗μ}(x)S_{λ′⊗μ}(y) = ∏_{i,j} \frac{(1 + zux_{i}y_{j})}{(1 − ux_{i}y_{j})},

où pour chaque n ≥ 0 fixé, la seconde sommation est sur les paires de partitions (λ, μ) telles que |λ| + |μ| = n. En prenant pour x (resp. y) un ensemble fini {x_{1}, …, x_{r+1}} (resp. {y_{1}, …, y_{s+1}}) de variables et en faisant les substitutions x_{i} ← q_{1}^{i−1}, y_{j} ← q_{2}^{j−1}, on en déduit la formule :

∑_{n} u^{n} ∑_{λ,μ} z^{|λ|}S_{λ⊗μ}(1, q_{1}, …, q_{1}^{r})S_{λ′⊗μ}(1, q_{2}, …, q_{2}^{s})

= \frac{(−zu; q_{1}, q_{2})_{r+1,s+1}}{(u; q_{1}, q_{2})_{r+1,s+1}} .

Multipliant les deux membres par t_{1}^{r}t_{2}^{s} et sommant par rapport à r et s, on obtient bien la formule (1.3c), compte-tenu d’abord de (4.1) appliquée à ν/θ = λ ⊗ μ, puis de (3.3). Ceci achève la démonstration de toutes les formules (1.1a) – (1.3c).

6. Involutions

On note Inv_{n} l’ensemble des involutions de [n]. Si σ est dans Inv_{n}, sa décomposition en cycles ne comporte que des points fixes et des transpositions. Leur nombre respectif sera désigné par Fix σ et Trans σ. Comme dans la section 2, le symbole σ représente aussi le mot σ = σ(1)σ(2) … σ(n), de sorte qu’on peut définir les notions de Des σ, Maj σ, Codes σ et Comaj σ. Soient H_{n}(z_{1}, z_{2}, t, q) et K_{n}(z_{1}, z_{2}, t, q) les polynômes définis sur Inv_{n} par :

H_{n}(z_{1}, z_{2}, t, q) = ∑_{σ} z_{1}^{Fix σ}z_{2}^{Trans σ}t^{Des σ}q^{Maj σ},
K_{n}(z_{1}, z_{2}, t, q) = ∑_{σ} z_{1}^{Fix σ}z_{2}^{Trans σ}t^{Codes σ}q^{Comaj σ}.

Notre but reste donc d’établir les formules (1.8) et (1.9) à partir de (1.6) et (1.7).

On a noté ρ : σ ↦ (P, Q), la correspondance de Robinson-Schensted. D’après (3.4), l’application σ ↦ P est une bijection de Inv_{n} sur l’ensemble P_{n} des tableaux standard d’ordre n dont la forme est un diagramme de Ferrers. On sait, de plus, (cf. [22, p. 93, prop. 4.4]) que le nombre de points fixes de l’involution σ est égal au nombre c(λ) de colonnes de P de longueur impaire. D’où, d’après (3.6), puisque ligne de route et ligne inverse de route coïncident pour une involution,

(6.1)  H_{n}(z, 1, t, q) = ∑_{λ} z^{c(λ)} ∑_{P} t^{Ides P} q^{Imaj P} ,

où λ varie dans l’ensemble des partitions de n et P dans l’ensemble des tableaux standard d’ordre n de forme λ.

Le théorème 4.1 entraîne alors avec ν/θ = λ :

∑_{n} H_{n}(z, 1, t, q)\frac{u^{n}}{(q; q)_{n}} = ∑_{n} u^{n} ∑_{λ} z^{c(λ)} ∑_{r} t^{r}S_{λ}(1, q, …, q^{r}).

D’autre part, (1.6) implique que pour chaque r ≥ 0 on a :

∑_{n} u^{n} ∑_{λ} z^{c(λ)}S_{λ}(1, q, …, q^{r}) = \frac{1}{(zu; q)_{r+1}} ∏_{0≤i<j≤r} \frac{1}{(1 − u^{2}q^{i+j})}.

Des deux dernières identités résulte :

(6.2) ∑_{n} H_{n}(z, 1, t, q)\frac{u^{n}}{(q; q)_{n}} = ∑_{r} t^{r} \frac{1}{(zu; q)_{r+1}} ∏_{0≤i<j≤r} \frac{1}{(1 − u^{2}q^{i+j})}.

Or pour σ ∈ Inv_{n}, on a Trans σ = (n − Fix σ)/2. D’où :

H_{n}(z_{1}, z_{2}, t, q)u^{n} = H_{n}(z_{1}/z_{2}^{1/2}, 1, t, q)(uz_{2}^{1/2})^{n}.

En reportant dans (6.2), on obtient bien (1.8).

L’identité (1.9) se démontre de la même façon, une fois trouvée pour K_{n}(z, 1, t, q) une formule de transcription analogue à celle trouvée en (6.1) pour H_{n}(z, 1, t, q). Or, lorsque σ est une involution, on a en vertu de (2.2) et (2.3) : Coligne σ = Iligne r σ. Reprenant les mêmes notations que dans (3.4) – (3.6), en particulier posant ρ(σ) = (P, Q) (avec P = Q puisque σ est une involution), on en déduit : Coligne σ = Iligne P′. D’où l’on tire :

K_{n}(z, 1, t, q) = ∑_{λ} z^{c(λ)} ∑_{P} t^{Des P′}q^{Maj P′},

= ∑_{λ} z^{r(λ)} ∑_{P} t^{Des P} q^{Maj P} .

La formule (1.9) s’en déduit par exactement les mêmes méthodes que précédemment, utilisant cette fois (1.7) au lieu de (1.6).

Faisant q = 1 dans (1.8) et dans (1.9), on obtient la fonction génératrice des involutions par nombre de points fixes et nombre de descentes, d’une part, nombre de points fixes et nombre de codescentes, d’autre part. Ces fonctions génératrices s’écrivent :

(6.3) ∑_{n} H_{n}(z, 1, t, 1)\frac{u^{n}}{(1 − t)^{n+1}} = ∑_{r} \frac{t^{r}}{(1 − zu)^{r+1}(1 − u^{2})^{r(r+1)/2}} ,

(6.4) ∑_{n} K_{n}(z, 1, t, 1)\frac{u^{n}}{(1 − t)^{n+1}} = ∑_{r} \frac{t^{r}(1 + zu)^{r+1}}{(1 − u^{2})^{(r+1)(r+2)/2}} .

Si on désigne par I_{n,p} (resp. J_{n,p}) le nombre d’involutions sans points fixes sur [n] ayant p descentes (resp. p codescentes), un calcul simple à partir des identités (6.3) et (6.4) donne :

(6.5)  I_{n,p} = ∑_{k}(−1)^{k}\binom{n + 1}{k}\binom{\binom{p−k+1}{2} + n/2 − 1}{n/2},

(6.6)  J_{n,p} = ∑_{k}(−1)^{k}\binom{n + 1}{k}\binom{\binom{p−k+2}{2} + n/2 − 1}{n/2}.

D’après la définition des codescentes, on a I_{n,p} = J_{n,n−1−p}. En reportant cette égalité dans (6.6), on obtient :

(6.7)  I_{n,p} = ∑_{k}(−1)^{k}\binom{n + 1}{k}\binom{\binom{n−p−k+1}{2} + n/2 − 1}{n/2}.

En comparant (6.5) et (6.7), on trouve la propriété suivante, conjecturée par DUMONT et démontrée combinatoirement par STREHL [24].

Proposition 6.1. — La statistique du nombre des descentes sur l’ensemble des involutions sans points fixes possède la propriété de symétrie :

I_{n,p} = I_{n,n−p}.

BIBLIOGRAPHIE

[1] ANDREWS (George E.). — The Theory of Partitions. — Reading, Mass., Addison-Wesley, 1976 (Encyclopedia of Math. and Its Appl., 2).

[2] ANDREWS (George E.) and ASKEY (Richard). — The Classical Orthogonal Polynomials and their Discrete and q-Analogues, Penn. State Univ. and Wisconsin Univ., en préparation.

[3] BAILEY (W.N.). — Generalized Hypergeometric Series. — Cambridge University Press, 1935.

[4] CARLITZ (Leonard). — The Expansion of certain Products, Proc. Amer. Math. Soc., t. 7, 1956, p. 558–564.

[5] CHEEMA (M.S.) and MOTZKIN (T.S.). — Multipartitions and Multipermutations, Combinatorics [Los Angeles. 1968], p.,39–70. — Providence, Amer. Math. Soc., 1971 (Proc. Symposia in Pure Math., 19).

[6] D^{}ÉSARM^{}ÉNIEN (Jacques). — Un analogue des congruences de Kummer pour les q-nombres d’Euler, Europ. J. Comb., t. 3, 1982, p. 19–28.

[7] D^{}ÉSARM^{}ÉNIEN (Jacques). — Fonctions symétriques associées à des suites classiques de nombres, Ann. scient. Éc. Norm. Sup., 4^{e} série, t. 16, 1983, p. 271–304.

[8] FOATA (Dominique) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Major Index and Inversion of Permutations, Math. Nachr., t. 83, 1978, p. 143–159.

[9] FOULKES (Herbert). — Enumeration of Permutations with Prescribed Up-down and Inversion Sequences, Discrete Math., t. 15, 1976, p. 235–252.

[10] GARSIA (Adriano M.) and GESSEL (Ira). — Permutation Statistics and Partitions, Advances in Math., t. 31, 1979, p. 288–305.

[11] GESSEL (Ira). — Counting Permutations by Descents, Greater Index, and Cycle Structure, preprint, Dept. Math., M.I.T., Cambridge, Mass., 1983.

[12] KNUTH (Donald E.). — The Art of Computer Programming, vol. 3, Sorting and Searching. — Don Mills, Ontario, Addison-Wesley, 1972.

[13] LASCOUX (Alain) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Le monoïde plaxique, Non-commutative Structures in Algebra and geometric Combinatorics [A. de Luca, ed., Napoli. 1978], p. 129–156. — Roma, Consiglio Nazionale delle Ricerche, 1981 (Quaderni de “La Ricerca Scientifica”, 109).

[14] LASCOUX (Alain) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Polynômes de Schubert, C.R. Acad. Sci. Paris, t. 294, 1982, p. 447–450.

[15] MACDONALD (Ian G.). — Symmetric Functions and Hall Polynomials. — Oxford, Clarendon Press, 1979.

[16] RAWLINGS (Don). — Generalized Worpitzky Identities with Applications to Permutation Enumeration, Europ. J. Comb., t. 2, 1981, p. 67–78.

[17] RAWLINGS (Don). — The Combinatorics of certain Products, Proc. Amer. Math. Soc., t. 83, 1983, p. 560–562.

[18] ROBINSON (Gilbert de Beauregard). — On the Representations of the Symmetric Group, Amer. J. Math., t. 60, 1938, p. 745–760.

[19] ROSELLE (David P.). — Coefficients associated with the Expansion of certain Products, Proc. Amer. Math. Soc., t. 45, 1974, p. 144–150.

[20] SCHENSTED (C.). — Longest Increasing and Decreasing Sequences, Canad. J. Math., t. 13, 1961, p. 179–192.

[21] SCH^{}ÜTZENBERGER (Marcel-Paul). — Quelques remarques sur une construction de Schensted, Math. Scand., t. 12, 1963, p. 117–128.

[22] SCH^{}ÜTZENBERGER (Marcel-Paul). — La correspondance de Robinson, Combinatoire et représentation du groupe symétrique [Actes Table Ronde C.N.R.S., Strasbourg. 1976], p. 59–113. — Berlin, Springer-Verlag, 1977 (Lecture Notes in Math., 579).

[23] SLATER (Lucy Joan). — Generalized Hypergeometric Functions. — Cambridge Univ. Press, 1966.

[24] STREHL (Volker). — Symmetric Eulerian Distributions for Involutions, Séminaire lotharingien de combinatoire (Bayreuth, Erlangen, Strasbourg), première session [Strasbourg. 1980], p. 12. — Publ. IRMA Strasbourg, 140/S-02, 1981.