STATISTIQUES D’ORDRE

SUR LES PERMUTATIONS COLORÉES

PAR

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

R^{}ÉSUM^{}É. — Un calcul explicite de distributions de statistiques d’ordre sur les permutations colorées est obtenu à l’aide de l’algèbre des fonctions de Schur.

ABSTRACT. — An explicit calculation of distributions of order statistics on colored permutations is derived by means of the Schur function algebra.

1. Introduction

L’étude des statistiques d’ordre sur le groupe symétrique remonte à MACMAHON [Mac1, 2, 3, 4], qui a introduit les notions de nombre de descentes (“des”) et d’indice majeur (“maj”) pour une suite finie de nombres et calculé les premières séries génératrices. Le polynôme générateur du groupe des permutations par nombre de descentes est le polynôme eulérien (cf. [Fo-Sch1]). Le polynôme q-eulérien est le polynôme générateur pour le couple (des, maj) (cf. [Car1, 2, 3]). Avec la statistique nombre des inversions, on obtient un autre polynôme q-eulérien (cf. [St2, Ro, Fo1, De]). Un pas décisif a été fait par GARSIA et GESSEL [Ga-Ge] (voir aussi [Ra1]), lorqu’il ont trouvé la bonne normalisation des séries de faculté à considérer. Il fallait prendre des produits de deux q-factorielles montantes. Pour chaque permutation σ on peut, en plus, introduire le nombre de descentes et l’indice majeur de l’inverse σ^{−1}, notés ides σ et imaj σ. La distribution du 4-vecteur (des, ides, maj, imaj) est alors calculable (cf. [Ga-Ge, Ra1]), ainsi que son groupe de symétrie (cf. [Fo-Sch2]). D’autres résultats parallèles ont été obtenus par différents auteurs (cf. [Car4, Che-Mo, St1, Ge, Ra2]).

J. DÉSARMÉNIEN ET D. FOATA

C’est, en fait, l’étude approfondie de l’algèbre combinatoire des tableaux réalisée par SCH^{}ÜTZENBERGER [Sch1, 2, La-Sch1, 2, 3, 4], qui a permis une insertion complète du calcul des statistiques d’ordre sur le groupe des permutations dans l’algèbre des fonctions symétriques. Il devenait enfin possible d’utiliser toute la richesse de cette dernière algèbre et de puiser les ingrédients utiles dans les ouvrages classiques [St1, Macd, Ja-Ke, Wy].

(^{∗}) Avec le soutien du PRC Mathématiques et Informatique.

Les deux auteurs du présent article ont ainsi utilisé l’algèbre des fonctions de Schur pour reprendre le calcul de GARSIA-GESSEL [Ga-Ge] et l’insérer dans son cadre naturel [De-Fo1, 2]. La distribution du 4-vecteur (des, ides, maj, imaj) peut être évaluée pour une classe d’objets plus importante que la classe des permutations. On obtient ainsi des extensions des formules classiques sur les séries hypergéométriques basiques au cas de plusieurs bases.

Plus récemment, REMMEL [Re3] a prolongé ces précédents travaux et calculé des distributions explicites de statistiques d’ordre sur des bipermutations. (La définition sera rappelée ci-dessous.) Il s’est appuyé sur l’algèbre des fonctions de Schur (k, l)-crochets, introduite par BERELE et REGEV (cf. [Be-Reg, Be-Rem, Re1, Re2]). Il ne semble pas que ces fonctions de Schur (k, l)-crochets apportent quelque chose de vraiment nouveau d’un point de vue combinatoire. Elles ont cependant permis à REMMEL d’imaginer ce nouveau concept de bipermutation et de l’exploiter.

Le but du présent article est de calculer la fonction génératrice de plusieurs statistiques d’ordre sur des objets combinatoires plus généraux que les bipermutations appelés permutations (k, l)-colorées. Il s’agit simplement de triplets τ = (σ, a, b), où σ est une permutations de l’intervalle [ n] = {1, 2, …, n} et où a = (a_{1}, …, a_{k}) et b = (b_{1}, …, b_{l}) sont deux suites de k et l entiers positifs de somme n. Les suites a et b servent à cloisonner les deux mots σ(1)σ(2) … σ(n) et σ^{−1}(1)σ^{−1}(2) … σ^{−1}(n) en k et l facteurs, respectivement. Notre but est non seulement de faire le calcul explicite des distributions de statistiques d’ordre sur ces permutations colorées, mais de montrer que ce calcul repose entièrement sur l’algèbre des fonctions de Schur ordinaires, en faisant appel à une simple extension de la correspondance de Robinson-Schensted.

On trouvera dans la prochaine section la définition des statistiques d’ordre considérées ici, ainsi que le résultat principal de cet article (TH^{}ÉOR^{}ÈME 2.1). Le calcul sur les fonctions de Schur nécessaire pour établir ce théorème est consigné dans la section 3. Les objets combinatoires qui servent de support à ce calcul sont des tableaux gauches d’une forme particulière. A partir de la formule de Cauchy sur les fonctions de Schur, on obtient d’abord une expression pour la fonction génératrice de cette classe de tableaux gauches (cf. PROPOSITION 4.1). Il reste à établir une bijection entre cette classe de tableaux gauches et les permutations (k, l)-colorées pour montrer que l’expression trouvée est aussi la fonction génératrice des permutations (k, l)-colorées. Ceci est donné dans la section 5. Nous avons reproduit dans la dernière section certaines spécialisations des formules obtenues.

PERMUTATIONS COLORÉES

2. Permutations (k, l)-colorées

Quand σ est une permutation de l’intervalle [ n], la ligne de route Ligne σ, la ligne inverse de route Iligne σ, la coligne de route Coligne σ et la coligne inverse de route Icoligne σ sont habituellement définies (cf. [Foulk], [Fo-Sch2]) par

Ligne σ = {r : 1 ≤ r ≤ n − 1, σ(r) > σ(r + 1)} ;
Iligne σ = Ligne σ^{−1} ; Coligne σ = [ n − 1 ] \ Ligne σ ;
Icoligne σ = [ n − 1 ] \ Iligne σ (= Coligne σ^{−1}) ;

où σ^{−1} désigne l’inverse de σ. Le cardinal de Ligne σ et la somme des éléments de Ligne σ sont respectivement appelés nombre de descentes et indice majeur de σ. Il y a des définitions analogues pour les autres lignes de route.

On peut prolonger la définition de ces lignes de route aux permutations (k, l)-colorées. Soit τ = (σ, a, b) une permutation (k, l)-colorée ; son inverse est la permutation (l, k)-colorée τ^{−1} = (σ^{−1}, b, a). Il est commode de poser a_{0} = b_{0} = 0 et de noter a_{i} et b_{j} les sommes partielles a_{i} = a_{1} + ⋯ + a_{i} (0 ≤ i ≤ k) et b_{j} = b_{1} + ⋯ + b_{j} (0 ≤ j ≤ l).

Les suites a et b déterminent des sous-intervalles de [ n] dans lesquels les différentes lignes de route peuvent aussi être définies : pour chaque i = 1, …, k et j = 1, …, l on pose :

Ligne_{i} τ = {r : a_{i−1} + 1 ≤ r ≤ a_{i} − 1, σ(r) > σ(r + 1)} ;

Coligne_{i} τ = [a_{i−1} + 1, a_{i} − 1] \ Ligne_{i} τ ; Iligne_{j} τ = Ligne_{j} τ^{−1} ;

Icoligne_{j} τ = Coligne_{j} τ^{−1} = [b_{j−1} + 1, b_{j} − 1] \ Iligne_{j} τ.

Autrement dit :

Iligne_{j} τ = {s : b_{j−1} + 1 ≤ s ≤ b_{j} − 1, σ^{−1}(s) > σ^{−1}(s + 1)}.

2.1. Exemple. — Soient n = 12, (k, l) = (3, 2), a = (5, 4, 3), b = (7, 5) et τ = (σ, a, b) la permutation (k, l)-colorée d’ordre n

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

Les éléments de Ligne_{i} σ (i = 1, 2, 3) sont reproduits en gras. Puisque σ(9) = 8 > 3 = σ(10), l’entier 8 est bien un élément de la ligne de route de σ, mais non pas de Ligne_{2} τ.

La permutation σ^{−1} s’écrit :

σ^{−1} = ( \begin{matrix}1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 6 & 10 & 3 & 5 & 1 & 12 \end{matrix} | \begin{matrix}8 & 9 & 10 & 11 & 12 \\ 9 & 8 & 4 & 7 & 11 \end{matrix} ) .

Les éléments de Ligne_{j} σ^{−1} (j = 1, 2) sont également reproduits en gras.

A chacune de ces lignes de route correspond un nombre de descentes et un indice majeur définis comme suit :

des_{i} τ = |Ligne_{i} τ|; maj_{i} τ = ∑{r − a_{i−1} : r ∈ Ligne_{i} τ};

codes_{i} τ = |Coligne_{i} τ|; comaj_{i} τ = ∑{r − a_{i−1} : r ∈ Coligne_{i} τ};

ides_{j} τ = |Iligne_{j} τ|; imaj_{j} τ = ∑{r − b_{j−1} : r ∈ Iligne_{j} τ};

icodes_{j} τ = |Icoligne_{j} τ|; icomaj_{j} τ = ∑{r − b_{j−1} : r ∈ Icoligne_{j} τ}.

Il faut remarquer que les indices majeurs relatifs au i^{ième} (resp. j^{ième}) compartiment de σ (resp. σ^{−1}) sont des sommes d’entiers de l’intervalle [a_{i}] (resp. [b_{j}]). Dans l’exemple ci-dessus, on a ainsi : maj_{1} τ = 1 + 4 = 5 ; maj_{2} τ = (7 − 5) + (8 − 5) = 5 ; maj_{3} τ = 11 − 9 = 2.

Posons finalement :

f_{i}(τ) = s_{i}^{des_{i} τ} p_{i}^{maj_{i} τ} ; f′_{i}(τ) = s_{i}^{codes_{i} τ} p_{i}^{comaj_{i} τ} ;
g_{j}(τ) = t_{j}^{ides_{j} τ} q_{j}^{imaj_{j} τ} ; g′_{j}(τ) = t_{j}^{icodes_{j} τ} q_{j}^{icomaj_{j} τ} .

Du fait du cloisonnement, plusieurs lignes de route (une par compartiment) doivent être considérées. Pour chaque compartiment, on peut s’intéresser, en fait, soit à la ligne de route, soit à la coligne de route. On peut donc définir 2^{k} types de ligne de route pour la permutation colorée τ et 2^{l} pour τ^{−1}. On est donc amené à introduire deux partitions ordonnées K = (K_{1}, K_{2}) et L = (L_{1}, L_{2}) des intervalles [ k] et [ l], respectivement (l’un des blocs K_{1} ou K_{2}, L_{1} ou L_{2} pouvant être vide). Ce choix de K et L étant fait, on pose :

h(K, L; τ) = ∏_{i∈K_{1}} f_{i}(τ) ∏_{i∈K_{2}} f′_{i}(τ) ∏_{j∈L_{1}} g_{j}(τ) ∏_{j∈L_{2}} g′_{j}(τ).

Les suites de couleurs a, b étant fixées, on forme alors le polynôme :

(2.1)  P (a, b) = P (a, b; K, L; s, t, p, q) = ∑_{σ∈𝔖_{n}} h(K, L; (σ, a, b)).

Lorsque toutes les variables s_{i} et t_{j} sont égales à 1, on pose :

(2.2)  P (a, b; K, L; p, q) = P (a, b; K, L; 1, 1, p, q).

Le reste de l’article est consacré au calcul de la fonction génératrice des polynômes P (a, b). Cette fonction génératrice s’exprime à l’aide des séries hypergéométriques à deux classes de bases. Il est donc utile de rappeler les notations usuelles utilisées dans l’étude de ces séries, comme la q-factorielle montante :

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

ainsi que la q_{1}, q_{2}-factorielle :

(a; q_{1}, q_{2})_{r,s} = \{ \begin{matrix}1, & si r ou s est nul ; \\ ∏_{1≤i≤r} ∏_{1≤j≤s}(1 − aq_{1}^{i−1}q_{2}^{j−1}), & si r, s ≥ 1 ; \end{matrix}
(a; q_{1}, q_{2})_{∞,∞} = lim_{r,s}(a; q_{1}, q_{2})_{r,s} = _{∏i≥1 ∏j≥1}(1 − aq_{1}^{i−1}q_{2}^{j−1}).

On utilisera également les notations abrégées pour les produits :

A^{a} = ∏_{1≤i≤k} A_{i}^{a_{i}}, B^{b} = ∏_{1≤j≤l} B_{j}^{b_{j}},

(p; p)_{a} = ∏_{1≤i≤k}(p_{i}; p_{i})_{a_{i}}, (s; p)_{a+1} = ∏_{1≤i≤k}(s_{i}; p_{i})_{a_{i}+1},

(uA_{K}B_{L}; p, q)_{c+1,d+1} = ∏_{i∈K, j∈L}(uA_{i}B_{j}; p_{i}, q_{j})_{c_{i}+1,d_{j}+1},

(uA_{K}B_{L}; p, q)_{∞,∞} = ∏_{i∈K, j∈L}(uA_{i}B_{j}; p_{i}, q_{j})_{∞,∞}.

Dans les identités (2.3) et (2.4) ci-après, la première sommation est faite sur tous les entiers n positifs. Pour n ≥ 0 fixé, la seconde sommation est étendue à toutes les paires (a, b) de suites d’entiers a = (a_{1}, …, a_{k}) et b = (b_{1}, …, b_{l}) satisfaisant ∑_{i} a_{i} = ∑_{j} b_{j} = n. Finalement, la paire (c, d) varie dans l’ensemble de toutes les suites c = (c_{1}, …, c_{k}) et d = (d_{1}, …, d_{l}) de k et l entiers positifs, respectivement.

Théorème 2.1. — La fonction génératrice des polynômes P (a, b) est donnée par :

(2.3) ∑_{n} u^{n} ∑_{a,b} A^{a}B^{b} \frac{P (a, b; K, L; s, t, p, q)}{(s; p)_{a+1}(t; q)_{b+1}}

= ∑_{c,d} s^{c}t^{d} \frac{(−uA_{K_{1}}B_{L_{2}}; p, q)_{c+1,d+1}(−uA_{K_{2}}B_{L_{1}}; p, q)_{c+1,d+1}}{(uA_{K_{1}}B_{L_{1}}; p, q)_{c+1,d+1}(uA_{K_{2}}B_{L_{2}}; p, q)_{c+1,d+1}}

et (2.4) ∑_{n} u^{n} ∑_{a,b} A^{a}B^{b} \frac{P (a, b; K, L; p, q)}{(p; p)_{a}(q; q)_{b}}

= \frac{(−uA_{K_{1}}B_{L_{2}}; p, q)_{∞,∞}(−uA_{K_{2}}B_{L_{1}}; p, q)_{∞,∞}}{(uA_{K_{1}}B_{L_{1}}; p, q)_{∞,∞}(uA_{K_{2}}B_{L_{2}}; p, q)_{∞,∞}} .

On obtient la seconde identité à partir de la première en multipliant celle-ci par (1 − s_{1}) et en faisant s_{1} = 1, puis en recommençant ces deux manipulations pour chacune des autres variables s_{i} et t_{j}.

Dans le membre de droite de (2.3) et de (2.4), les bases p_{i}, q_{j} apparaissent par paires, tandis que des q-factorielles montantes ordinaires apparaissent dans le membre de gauche. Ces deux formules peuvent être considérées comme des formules de transformation d’une série hypergéométrique basique bivariée en une série de la classe des séries hypergéométriques univariées à plusieurs bases. L’identité (2.4) peut aussi être vue comme une extension de l’identité q-binomiale à plusieurs bases (cf. [De-Fo1]).

Dans le cas k = l = 2, K_{1} = {1}, K_{2} = {2}, L_{1} = {1}, L_{2} = {2}, on retrouve les identités de REMMEL sur les bipermutations.

3. Les fonctions de Schur

Nous renvoyons au livre de MACDONALD [Macd] pour toutes les propriétés concernant les fonctions de Schur. L’identité de base sous-jacente à tout le calcul qui va suivre est l’identité de Cauchy pour les fonctions de Schur S_{λ}(x), ainsi que l’identité duale. Elles s’écrivent :

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

la sommation portant sur l’ensemble de toutes les partitions λ d’entiers et λ′ désignant la partition conjuguée de λ (voir [Macd, p. 33]).

Nous aurons aussi besoin des fonctions de Schur gauches S_{ν/θ}(x) associées aux diagrammes gauches ν/θ. Lorsque ν/θ est le produit d’un nombre fini de diagrammes de Ferrers ν/θ = ⨂_{j} λ_{i,j} = λ_{i,1} ⊗ ⋯ ⊗ λ_{i,l}, il résulte de la définition des fonctions de Schur que l’on a l’identité :

(3.3)  S_{⊗_{j}λ_{i,j}}(x) = S_{λ_{i,1}}(x) ⋯ S_{λ_{i,l}}(x).

En plus des notations données dans la section 2, nous introduisons deux familles de variables (A_{i}) et (B_{j}), ainsi que k + l ensembles de variables x^{(i)} = (x_{1}^{(i)}, x_{2}^{(i)}, …) (1 ≤ i ≤ k) et y^{(j)} = (y_{1}^{(j)}, y_{2}^{(j)}, …) (1 ≤ j ≤ l). Pour tout couple (i, j) posons :

(3.4)  Sch(i, j) = ∏_{p,q}(1 − uA_{i}B_{j}x_{p}^{(i)}y_{q}^{(j)})^{−1},
(3.5)  Sch′(i, j) = ∏_{p,q}(1 + uA_{i}B_{j}x_{p}^{(i)}y_{q}^{(j)}).

Les partitions K = (K_{1}, K_{2}) et L = (L_{1}, L_{2}) de [ k] et [ l] étant données, on pose pour r, s = 1, 2

(3.6)  Sch(K_{r}, L_{s}) = ∏_{i,j} Sch(i, j)  ((i, j) ∈ K_{r} × L_{s}),
(3.7)  Sch′(K_{r}, L_{s}) = ∏_{i,j} Sch′(i, j)  ((i, j) ∈ K_{r} × L_{s}).

D’abord les deux identités de Cauchy (3.1) et (3.2) peuvent être récrites :

(3.8)  Sch(i, j) = ∑_{n_{i,j}} u^{n_{i,j}} ∑_{λ_{i,j}}(A_{i}B_{j})^{|λ_{i,j}|}S_{λ_{i,j}}(x^{(i)})S_{λ_{i,j}}(y^{(j)}),

= ∑_{n_{i,j}} u^{n_{i,j}} ∑_{λ_{i,j}}(A_{i}B_{j})^{|λ_{i,j}|}S_{λ′_{i,j}}(x^{(i)})S_{λ′_{i,j}}(y^{(j)}), (3.9)

(3.10) Sch′(i, j) = ∑_{n_{i,j}} u^{n_{i,j}} ∑_{λ_{i,j}}(A_{i}B_{j})^{|λ_{i,j}|}S_{λ_{i,j}}(x^{(i)})S_{λ′_{i,j}}(y^{(j)}),

= ∑_{n_{i,j}} u^{n_{i,j}} ∑_{λ_{i,j}}(A_{i}B_{j})^{|λ_{i,j}|}S_{λ′_{i,j}}(x^{(i)})S_{λ_{i,j}}(y^{(j)}), (3.11)

où la seconde sommation dans chaque identité est sur toutes les partitions λ_{i,j} de l’entier n_{i,j}.

Maintenant exprimons chaque élément du produit

Sch(K_{1}, L_{1})Sch′(K_{1}, L_{2})Sch′(K_{2}, L_{1})Sch(K_{2}, L_{2})

comme somme infinie de fonctions de Schur à l’aide des identités (3.8), (3.10), (3.11) et (3.9), respectivement et calculons ce produit. On obtient :

(3.12) Sch(K_{1}, L_{1})Sch′(K_{1}, L_{2})Sch′(K_{2}, L_{1})Sch(K_{2}, L_{2})

= ∑_{n} u^{n} ∑_{(λ_{i,j})} ∏_{i,j}(A_{i}B_{j})^{|λ_{i,j}|}

× ∏_{i∈K_{1}} ∏_{j∈L_{1}} S_{λ_{i,j}}(x^{(i)})S_{λ_{i,j}}(y^{(j)}) ∏_{i∈K_{1}} ∏_{j∈L_{2}} S_{λ_{i,j}}(x^{(i)})S_{λ′_{i,j}}(y^{(j)})

× ∏_{i∈K_{2}} ∏_{j∈L_{1}} S_{λ′_{i,j}}(x^{(i)})S_{λ_{i,j}}(y^{(j)}) ∏_{i∈K_{2}} ∏_{j∈L_{2}} S_{λ′_{i,j}}(x^{(i)})S_{λ′_{i,j}}(y^{(j)})

= ∑_{n} u^{n} ∑_{(λ_{i,j})} ∏_{i,j}(A_{i}B_{j})^{|λ_{i,j}|} ∏_{i∈K_{1}} ∏_{j} S_{λ_{i,j}}(x^{(i)}) ∏_{i∈K_{2}} ∏_{j} S_{λ′_{i,j}}(x^{(i)})

× ∏_{j∈L_{1}} ∏_{i} S_{λ_{i,j}}(y^{(j)}) ∏_{j∈L_{2}} ∏_{i} S_{λ′_{i,j}}(y^{(j)}).

Soit, d’après (3.3)

(3.13) Sch(K_{1}, L_{1})Sch′(K_{1}, L_{2})Sch′(K_{2}, L_{1})Sch(K_{2}, L_{2})

= ∑_{n} u^{n} ∑_{(λ_{i,j})} ∏_{i,j}(A_{i}B_{j})^{|λ_{i,j}|} ∏_{i∈K_{1}} S_{⊗_{j}λ_{i,j}}(x^{(i)}) ∏_{i∈K_{2}} S_{⊗_{j}λ′_{i,j}}(x^{(i)})

× ∏_{j∈L_{1}} S_{⊗_{i}λ_{i,j}}(y^{(j)}) ∏_{j∈L_{2}} S_{⊗_{i}λ′_{i,j}}(y^{(j)}).

Dans toutes ces sommations, la matrice (λ_{i,j}) varie dans l’ensemble de toutes les matrices k × l dont les coefficients λ_{i,j} sont des partitions satisfaisant ∑_{i,j} |λ_{i,j}| = n.

Prenons maintenant pour x^{(i)} et y^{(j)} les ensembles finis

{x_{1}^{(i)}, …, x_{c_{i}+1}^{(i)}}  et  {y_{1}^{(j)}, …, y_{d_{j}+1}^{(j)}}

et faisons les substitutions x_{r}^{(i)} ← p_{i}^{r−1} (resp. y_{s}^{(j)} ← q_{j}^{s−1}) dans (3.13). Compte-tenu des notations (3.4)–(3.7) et de nos conventions sur les produits, on obtient l’identité :

(3.14) \frac{(−uA_{K_{1}}B_{L_{2}}; p, q)_{c+1,d+1}(−uA_{K_{2}}B_{L_{1}}; p, q)_{c+1,d+1}}{(uA_{K_{1}}B_{L_{1}}; p, q)_{c+1,d+1}(uA_{K_{2}}B_{L_{2}}; p, q)_{c+1,d+1}}

= ∑_{n} u^{n} ∑_{(λ_{i,j})} ∏_{i,j}(A_{i}B_{j})^{|λ_{i,j}|}

× ∏_{i∈K_{1}} S_{⊗_{j}λ_{i,j}}(1, p_{i}, …, p_{i}^{c_{i}}) ∏_{i∈K_{2}} S_{⊗_{j}λ′_{i,j}}(1, p_{i}, …, p_{i}^{c_{i}})

× ∏_{j∈L_{1}} S_{⊗_{i}λ_{i,j}}(1, q_{j}, …, q_{j}^{d_{j}}) ∏_{j∈L_{2}} S_{⊗_{i}λ′_{i,j}}(1, q_{j}, …, q_{j}^{d_{j}}).

Multiplions les deux membres par s^{c}t^{d} et sommons sur toutes les suites c = (c_{1}, …, c_{k}) et d = (d_{1}, …, d_{l}) d’entiers positifs. Le premier membre de (3.14) devient alors identique au second membre de (2.3).

4. Tableaux gauches

Nous reprenons les conventions habituelles sur les formes gauches ν/θ, qui sont des différences ensemblistes de deux diagrammes de Ferrers ν et θ. Si la forme ν/θ contient n points et si I est un ensemble fini d’entiers de cardinal n, on construit un tableau gauche T, de forme ν/θ et de contenu I en plaçant les n entiers de I sur les n points de la forme de façon à obtenir une croissance stricte dans chaque ligne (de gauche à droite) et dans chaque colonne (de bas en haut). Il est commode d’écrire :

Cont T = I, |T | = ν/θ.

Lorsque Cont T = [ n], on dit que T est d’ordre n.

La ligne inverse de route d’un tableau T, de contenu I et de forme ν/θ est définie comme l’ensemble de tous les entiers k tels que k et k + 1 apparaissent dans T, l’entier k + 1 étant situé plus haut que k dans T. On note Iligne T la ligne inverse de route de T. Comme de coutume, le transposé T′ d’un tableau T est obtenu par réflexion de celui-ci par rapport à la diagonale principale.

Par exemple, les tableaux

P_{1,1} = 6 1 4 5 P_{2,1} = 2 P_{3,1} = 3 7

sont de forme λ_{1,1} = (3, 1), λ_{2,1} = (1) and λ_{3,1} = (2), respectivement. Le tableau

T = 6 1 4 5 2 3 7

est d’ordre 7 et de forme |T_{1}| = λ_{1,1} ⊗ λ_{2,1} ⊗ λ_{3,1}. On l’obtient à partir des précédents tableaux de façon évidente. La notation :

T_{1} = P_{1,1} ⊗ P_{2,1} ⊗ P_{3,1}

n’est donc pas ambiguë. Les éléments de Iligne T ont été reproduits en gras (Iligne T = {3, 5}).

Soit T un tableau gauche d’ordre n. Par analogie avec les permutations colorées, on pose :

ides T = |Iligne T | ; imaj T = ∑{r : r ∈ Iligne T };

puis :

(4.1)  F_{i}(T) = s_{i}^{ides T} p_{i}^{imaj T};  G_{j}(T) = t_{j}^{ides T} q_{j}^{imaj T} .

Les suites a = (a_{1}, …, a_{k}) et b = (b_{1}, …, b_{l}) étant données, on considère l’ensemble Λ(a, b) des matrices (λ_{i,j}) d’ordre k × l dont les coefficients sont des partitions satisfaisant les relations

(4.2)  |λ_{i,1}| + ⋯ + |λ_{i,l}| = a_{i},  |λ_{1,j}| + ⋯ + |λ_{k,j}| = b_{j}

pour chaque i = 1, …, k et j = 1, …, l. On forme ensuite l’ensemble T (λ_{i,j}) de toutes les suites (T, U) = (T_{1}, …, T_{l}, U_{1}, …, U_{k}) de (l + k) tableaux gauches, respectivement d’ordre b_{1}, …, b_{l}, a_{1}, …, a_{k} et de forme

(4.3)  |T_{j}| = λ_{1,j} ⊗ ⋯ ⊗ λ_{k,j},  |U_{i}| = λ_{i,1} ⊗ ⋯ ⊗ λ_{i,l},

pour j = 1, …, l et i = 1, …, k.

Relativement à la paire de partitions K = (K_{1}, K_{2}) et L = (L_{1}, L_{2}), une telle suite (T, U) de tableaux gauches est munie d’un poids défini par :

H(K, L; T, U) = ∏_{i∈K_{1}} F_{i}(U_{i}) ∏_{i∈K_{2}} F_{i}(U′_{i}) ∏_{j∈L_{1}} G_{j}(T_{j}) ∏_{j∈L_{2}} G_{j}(T′_{j}).

On se propose de calculer la fonction génératrice des suites (T, U) par rapport à ce poids.

Dans la proposition suivante, la paire (a, b) étant fixée, la première sommation est sur toutes les matrices (λ_{i,j}) appartenant à Λ(a, b) (cf. (4.2)) et la seconde sur les paires (T, U) de l’ensemble T (λ_{i,j}) (cf. (4.3)). Enfin, la paire (c, d) est étendue à toutes les suites c et d d’entiers positifs respectivement de longueur k et l.

Proposition 4.1. — On a l’identité :

(4.4) \frac{1}{(s; p)_{a+1}(t; q)_{b+1}} ∑_{(λ_{i,j})} ∑_{(T,U)} H(K, L; T, U)

= ∑_{c,d} s^{c}t^{d} ∑_{(λ_{i,j})} ∏_{i∈K_{1}} S_{⊗_{j}λ_{i,j}}(1, p_{i}, …, p_{i}^{c_{i}}) ∏_{i∈K_{2}} S_{⊗_{j}λ′_{i,j}}(1, p_{i}, …, p_{i}^{c_{i}})

× ∏_{j∈L_{1}} S_{⊗_{i}λ_{i,j}}(1, q_{j}, …, q_{j}^{d_{j}}) ∏_{j∈L_{2}} S_{⊗_{i}λ′_{i,j}}(1, q_{j}, …, q_{j}^{d_{j}}).

Cette proposition est une conséquence banale du lemme suivant déjà prouvé dans [De-Fo1, théorème 4.1], qui s’énonce comme suit :

Lemme. — Soit ν/θ un diagramme gauche de n éléments. On a alors l’identité :

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

où la première sommation est sur tous les tableaux d’ordre n, de forme ν/θ et la seconde sur tous les entiers d ≥ 0.

Multiplions l’identité (4.4) par u^{n}A^{a}B^{b} et sommons par rapport aux paires (a, b) d’entiers de somme n, puis par rapport à n ≥ 0. En remarquant que

A^{a}B^{b} = ∏_{i,j}(A_{i}B_{j})^{|λ_{i,j}|},

on obtient :

(4.5) ∑_{n} ∑_{a,b} \frac{1}{(s; p)_{a+1}(t; q)_{b+1}} ∑_{(λ_{i,j})} ∑_{(T,U)} H(K, L; T, U)

= ∑_{n} u^{n} ∑_{(λ_{i,j})}(A_{i}B_{j})^{|λ_{i,j}|} ∑_{c,d} s^{c}t^{d}

× ∏_{i∈K_{1}} S_{⊗_{j}λ_{i,j}}(1, p_{i}, …, p_{i}^{c_{i}}) ∏_{i∈K_{2}} S_{⊗_{j}λ′_{i,j}}(1, p_{i}, …, p_{i}^{c_{i}})

× ∏_{j∈L_{1}} S_{⊗_{i}λ_{i,j}}(1, q_{j}, …, q_{j}^{d_{j}}) ∏_{j∈L_{2}} S_{⊗_{i}λ′_{i,j}}(1, q_{j}, …, q_{j}^{d_{j}}).

Le second membre de (4.5) n’est autre que la somme sur c et d du produit du second membre de (3.14) par le monôme s^{c}t^{d}. Par conséquent,

(4.6) ∑_{n} ∑_{a,b} \frac{1}{(s; p)_{a+1}(t; q)_{b+1}} ∑_{(λ_{i,j})} ∑_{(T,U)} H(K, L; T, U)

= ∑_{c,d} s^{c}t^{d} \frac{(−uA_{K_{1}}B_{L_{2}}; p, q)_{c+1,d+1}(−uA_{K_{2}}B_{L_{1}}; p, q)_{c+1,d+1}}{(uA_{K_{1}}B_{L_{1}}; p, q)_{c+1,d+1}(uA_{K_{2}}B_{L_{2}}; p, q)_{c+1,d+1}}

En comparant avec l’identité (2.3) à démontrer, il reste donc à établir :

(4.7)  P (a, b; K, L; s, t, p, q) = ∑_{(λ_{i,j})} ∑_{(T,U)} H(K, L; T, U).

5. La bijection

Soit τ = (σ, a, b) une permutation (k, l)-colorée. Pour chaque couple (i, j) telle que 1 ≤ i ≤ k et 1 ≤ j ≤ l notons I_{ij} l’ensemble de tous les entiers de l’intervalle [ a_{i−1} + 1, a_{i}], qui sont envoyés par σ dans [ b_{j−1} + 1, b_{j} ]. Notons τ_{ij} la restriction de σ à I_{ij}, qui envoie donc bijectivement I_{i,j} sur J_{i,j} = σ(I_{i,j}).

Si on reprend l’exemple 2.1, les bijections τ_{i,j} et leurs inverses τ_{i,j}^{−1} sont données par :

τ_{11} = ( \begin{matrix}1 & 2 & 3 & 5 \\ 6 & 1 & 4 & 5 \end{matrix} ); τ_{12} = ( \begin{matrix}4 \\ 10 \end{matrix} ); τ_{21} = ( \begin{matrix}6 \\ 2 \end{matrix} );

τ_{22} = ( \begin{matrix}7 & 8 & 9 \\ 11 & 9 & 8 \end{matrix} ); τ_{31} = ( \begin{matrix}10 & 12 \\ 3 & 7 \end{matrix} ); τ_{32} = ( \begin{matrix}11 \\ 12 \end{matrix} );

τ_{11}^{−1} = ( \begin{matrix}1 & 4 & 5 & 6 \\ 2 & 3 & 5 & 1 \end{matrix} ); τ_{12}^{−1} = ( \begin{matrix}10 \\ 4 \end{matrix} ); τ_{21}^{−1} = ( \begin{matrix}2 \\ 6 \end{matrix} );

τ_{22}^{−1} = ( \begin{matrix}8 & 9 & 11 \\ 9 & 8 & 7 \end{matrix} ); τ_{31}^{−1} = ( \begin{matrix}3 & 7 \\ 10 & 12 \end{matrix} ); τ_{32}^{−1} = ( \begin{matrix}12 \\ 11 \end{matrix} ) .

Lorsque les éléments de I_{i,j} (resp. J_{i,j}) sont écrits en ordre croissant (comme dans les lignes du haut des précédentes matrices), les lignes du bas forment des mots que l’on désigne par les mêmes symboles τ_{i,j} (resp. τ_{i,j}^{−1}). On note maintenant τ_{1}, τ_{2}, …, τ_{l} (resp. τ_{1}^{−1}, τ_{2}^{−1}, …, τ_{k}^{−1}) le produit de juxtaposition des mots :

τ_{j} = τ_{1,j}τ_{2,j} … τ_{k,j} ; τ_{i}^{−1} = τ_{i,1}^{−1}τ_{i,2}^{−1} … τ_{i,k}^{−1},

pour j = 1, …, l et i = 1, …, k.

Dans l’exemple traité ci-dessus, on a :

τ_{1} = 6, 1, 4, 5, 2, 3, 7 ; τ_{2} = 10, 11, 9, 8, 12 ;
τ_{1}^{−1} = 2, 3, 5, 1, 4 ; τ_{2}^{−1} = 6, 9, 8, 7 ; τ_{3}^{−1} = 10, 12, 11 ;

où, dans chaque mot, les éléments de la ligne inverse de route ont été reproduits en gras. On peut constater que l’on a : Ligne_{1} τ = Iligne τ_{1}^{−1} = {1, 4}, Ligne_{2} τ = Iligne τ_{2}^{−1} = {7, 8}, Ligne_{3} τ = Iligne τ_{3}^{−1} = {11}, Iligne_{1} τ = Ligne_{1} τ^{−1} = Iligne τ_{1} = {3, 5}, Iligne_{2} τ = Ligne_{2} τ^{−1} = Iligne τ_{2} = {8, 9}.

Le résultat est général et simple à vérifier. Nous nous contentons d’énoncer cette propriété sans démonstration.

Proposition 5.1. — Pour tout i = 1, …, k et j = 1, …, l on a :

(5.1)  Ligne_{i} τ = Iligne τ_{i}^{−1};  Iligne_{j} τ = Iligne τ_{j}.

Nous sommes maintenant en mesure de démontrer (4.7) et par là même le TH^{}ÉOR^{}ÈME 2.1. Il s’agit de construire une bijection entre permutations (k, l)-colorées et tableaux gauches de la classe T (λ_{i,j}) où (λ_{i,j}) ∈ Λ(a, b) (cf. (4.2) et (4.3)).

Théorème 5.2. — A toute permutation (k, l)-colorée τ = (σ, a, b) correspond de façon biunivoque :

(i) une famille (λ_{ij}) (1 ≤ i ≤ k; 1 ≤ j ≤ l) de diagrammes de Ferrers tels que pour tout i = 1, …, k et j = 1, …, l on ait les relations :

|λ_{i,1}| + ⋯ + |λ_{i,l}| = a_{i}, |λ_{1,j}| + ⋯ + |λ_{k,j}| = b_{j},

(ii) une suite (T, U) = (T_{1}, …, T_{l}, U_{1}, …, U_{k}) de (l + k) tableaux gauches, d’ordre b_{1}, …, b_{l}, a_{1}, …, a_{k} et de forme |T_{j}| = λ_{1,j} ⊗ ⋯ ⊗ λ_{k,j}, |U_{i}| = λ_{i,1} ⊗ ⋯ ⊗ λ_{i,l}, ayant la propriété :

(5.2)  Iligne_{j} τ − b_{j−1} = Iligne T_{j} Ligne_{i} τ − a_{i−1} = Iligne U_{i}

pour tout j = 1, …, l et i = 1, …, k.

L’ingrédient de base de cette bijection est la correspondence de Robinson-Schensted (cf., par exemple, [Knu, p. 48–72] pour un excellent exposé de la question), que l’on prolonge à l’ensemble des tableaux gauches. Soit Bij(I, J) l’ensemble de toutes les bijections d’un ensemble fini I sur un ensemble J. La correspondance de Robinson-Schensted ρ envoie bijectivement Bij(I, J) sur l’ensemble de tous les couples (P, Q) de tableaux injectifs, de même forme λ, le contenu de P (resp. Q) étant J (resp. I). Soient σ ∈ Bij(I, J) et ρ(σ) = (P, Q). Alors ρ a la propriété supplémentaire suivante :

Iligne σ = Iligne P  et  Iligne σ^{−1} = Iligne Q.

Partons donc d’une permutation (k, l)-colorée τ. Associons-lui la famille des bijections (τ_{i,j} : I_{i,j} → J_{i,j}) comme il a été décrit plus haut. La correspondance de Robinson-Schensted envoie chacune des bijections τ_{i,j} sur un couple (P_{i,j}, Q_{i,j}) de tableaux (droits) de la même forme, dont les contenus et les lignes inverses de route sont donnés par :

Cont P_{i,j} = J_{i,j}, Cont Q_{i,j} = I_{i,j},
Iligne τ_{i,j} = Iligne P_{i,j}, Iligne τ_{i,j}^{−1} = Iligne Q_{i,j}.

Soit λ_{i,j} la forme commune de P_{i,j} et Q_{i,j}. Les tableaux gauches \overline{T}_{j} = P_{1,j} ⊗⋯⊗P_{k,j} et \overline{U}_{i} = Q_{i,1} ⊗⋯⊗Q_{i,l} sont alors de forme λ_{1,j} ⊗⋯⊗λ_{k,j} et λ_{i,1} ⊗ ⋯ ⊗ λ_{i,l}, respectivement. De plus,

Cont \overline{T}_{j} = ∑_{i} J_{i,j} = [b_{j−1} + 1, b_{j}], Cont \overline{U}_{i} = ∑_{j} I_{i,j} = [a_{i−1} + 1, a_{i}]

et donc |λ_{1,j}| + ⋯ + |λ_{k,j}| = b_{j}, |λ_{i,1}| + ⋯ + |λ_{i,l}| = a_{i}.

Pour chaque i = 1, …, k soit Iligne(← P_{i,j}) (resp. Iligne(← τ_{i,j})) l’ensemble de tous les entiers s dans [b_{j−1} + 1, b_{j} − 1] tels que s soit dans P_{i,j} (resp. soit une lettre de τ_{i,j}) et tels que (s + 1) apparaisse dans P_{i′,j} (resp. dans τ_{i′,j}) pour un certain i′ < i. Comme dans le produit P_{1,j} ⊗ ⋯ ⊗ P_{k,j} le tableau P_{i′,j} se trouve en haut et à gauche de P_{i,j} si i′ < i, on a : ∑_{i} Iligne(← τ_{i,j}) = ∑_{i} Iligne(← P_{i,j}). Par suite :

Iligne \overline{T}_{j} = Iligne P_{1,j} ⊗ ⋯ ⊗ P_{k,j} = ∑_{i} Iligne P_{i,j} + ∑_{i} Iligne(← P_{i,j})
= ∑_{i} Iligne τ_{i,j} + ∑_{i} Iligne(← τ_{i,j})
= Iligne τ_{1,j} ⋯ τ_{k,j} = Iligne τ_{j} = Iligne_{j} τ,

d’après (5.1). De la même manière, Iligne \overline{U}_{i} = Ligne_{i} τ.

On obtient enfin la suite (T, U) = (T_{1}, …, T_{l}, U_{1}, …, U_{k}) en partant de la suite (\overline{T}_{1}, …, \overline{T}_{l}, \overline{U}_{1}, …, \overline{U}_{k}) et en remplaçant chaque élément r du tableau \overline{T}_{j} (resp. \overline{U}_{i}) par l’élément r − b_{j−1} (resp. r − a_{i−1}). Les tableaux qui en résultent sont alors d’ordre b_{1}, …, b_{l}, a_{1}, …, a_{k}. Les relations (5.2) sont alors vérifiées.

Ceci achève la démonstration du théorème 5.2.

Illustrons la construction du précédent théorème à l’aide de l’exemple considéré tout au long de cet article. Les différents éléments τ_{ij} sont envoyés sur les couples de tableaux :

τ_{11} ↦ (P_{1,1}, Q_{1,1}) = (\begin{matrix}6 \\ 1 & 4 & 5 \end{matrix} , \begin{matrix}2 \\ 1 & 3 & 5 \end{matrix} ); τ_{1,2} ↦ (P_{1,2}, Q_{1,2}) = (10, 4) ;

τ_{2,1} ↦ (P_{2,1}, Q_{2,1}) = (2, 6) ; τ_{2,2} ↦ (P_{2,2}, Q_{2,2}) = (\begin{matrix}11 \\ 9 \\ 8 \end{matrix}, \begin{matrix}9 \\ 8 \\ 7 \end{matrix});

τ_{3,1} ↦ (P_{31}, Q_{3,1}) = (3 7 , 10 12) τ_{3,2} ↦ (P_{3,2}, Q_{32}) = (12, 11).

D’où l’on a :

T_{1} = 6 1 4 5 2 3 7 ; T_{2} = 3 4 2 1 5 ;

U_{1} = 2 1 3 5 4 ;  U_{2} = 1 4 3 2 ;  U_{3} = 1 3 2 .

6. Spécialisations

Dans [De-Fo1] les identités linéaires sur les fonctions de Schur avaient été exploitées pour obtenir des identités sur les polynômes générateurs des involutions par rapport à des statistiques d’ordre. REMMEL [Re3] a prolongé ces résultats au cas des bipermutations (σ; a, b) pour lesquelles σ est une involution. Suivant la méthode développée dans cet article, on peut obtenir des identités concernant les involutions (k, l)-colorées, pour une paire (k, l) quelconque. Nous ne le ferons pas ici. En revanche, nous aimerions donner quelques spécialisations des formules (2.3) et (2.4).

Convenons d’écrire des_{a_{i}}, maj_{a_{i}},…, pour des_{i}, maj_{i},…, lorsque les nombres de descentes et les indices majeurs sont calculés par rapport à la partition a. Prenons d’abord K = ({1}, {2}), L = ({1}, ∅), puis faisons les substitutions B ← 1, A_{2} ← z, A_{1} ← 1, p_{1} ← q_{1}, p_{2} ← q_{1}, q ← q_{2} dans l’identité (2.4). Celle-ci devient :

(6.1)  ∑_{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})_{∞,∞}} ,

c’est-à-dire l’extension à deux bases de la formule q-binomiale avec l’interprétation combinatoire

C_{n}(z; q_{1}, q_{2}) = ∑_{a_{1}+a_{2}=n} z^{a_{2}} \left[{n \atop a_{1}}\right]_{q_{1}} ∑_{σ∈𝔖_{n}} q_{1}^{maj_{a_{1}} σ + comaj_{a_{2}} σ}q_{2}^{imaj σ},

interprétation différente de celle trouvée dans [De-Fo1].

Posons maintenant :

A_{n}(s, q) = ∑_{σ∈𝔖_{n}} s^{des σ}q^{imaj σ}; B_{n}(s, q) = ∑_{σ∈𝔖_{n}} s^{codes σ}q^{imaj σ}.

L’identité (2.3) se spécialise aisément en :

(6.2)  ∑_{n} \frac{u^{n}}{(q; q)_{n}} A_{n}(s, q) = \frac{1 − s}{−s + (u(1 − s); q)_{∞}} ,
(6.3)  ∑_{n} \frac{u^{n}}{(q; q)_{n}} B_{n}(s, q) = \frac{1 − s}{−s + (−u(1 − s); q)_{∞}^{−1}} ,

deux expressions bien connues pour les q-analogues des polynômes eulériens (cf. [St2], [De]). A leur tour, (6.2) et (6.3) se réduisent à l’identité classique donnant la fonction génératrice des polynômes eulériens ordinaires.

Prenons maintenant K quelconque et L = ({1}, ∅). De plus, si ∑_{i} a_{i} = n, posons :

P_{a}(s, q) = ∑_{σ∈𝔖_{n}}( ∏_{i∈K_{1}} s_{i}^{des_{a_{i}} σ})( ∏_{i∈K_{2}} s_{i}^{codes_{a_{i}} σ})q^{imaj σ}.

On déduit aisément de (2.3), (6.2) et (6.3) la relation :

(6.4)  P_{a}(s, q) = \left[{a_{1} + ⋯ + a_{k} \atop a_{1}, …, a_{k}}\right]_{q} ∏_{i∈K_{1}} A_{a_{i}}(s_{i}, q) ∏_{i∈K_{2}} B_{a_{i}}(s_{i}, q).

Cette dernière relation peut s’établir directement si l’on se souvient (cf. [Fo-Sch2]) que sur le groupe 𝔖_{n}, les paires de statistiques (des, inv), (des, imaj) et (ides, maj) (où l’on a noté “inv σ” le nombre d’inversions de σ) sont identiques. Il suffit, en effet, d’établir (6.4) pour les statistiques : (des_{a_{i}})_{i∈K_{1}}, (codes_{a_{i}})_{i∈K_{2}}, inv.

BIBLIOGRAPHIE

[Be-Reg] BERELE (A.) and REGEV (A.). — Hook Young diagrams with applications to combinatorics and to representations of Lie superalgebras, Adv. in Math., t. 64, 1987, p. 118–175.

[Be-Rem] BERELE (A.) and REMMEL (J.B.). — Hook flag characters and their combina-

torics, J. Pure and Appl. Algebra, t. 35, 1985, p. 222-245.

[Car1] CARLITZ (Leonard). — q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc., t. 76, 1954, p. 332–350.

[Car2] CARLITZ (Leonard). — Eulerian numbers and polynomials, Math. Magazine, t. 33, 1959, p. 247–260.

[Car3] CARLITZ (Leonard). — A combinatorial property of q-Eulerian numbers, Amer. Math. Monthly, t. 82, 1975, p. 51–54.

[Car4] CARLITZ (Leonard). — The Expansion of certain Products, Proc. Amer. Math.

Soc., t. 7, 1956, p. 558–564.

[Che-Mo] 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).

[De] D^{}ÉSARM^{}ÉNIEN (Jacques). — Fonctions symétriques associées à des suites clas-

siques de nombres, Ann. scient. Éc. Norm. Sup., t. 16, 1983, p. 271–304.

[De-Fo1] 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.

[De-Fo2] D^{}ÉSARM^{}ÉNIEN (Jacques) et FOATA (Dominique). — Fonctions symétriques et séries hypergéométriques basiques multivariées, II, Combinatoire Énumérative [Actes Colloque Univ. Québec, Montréal. 1985], p. 68–90. — Berlin, Springer-Verlag, 1987 (Lecture Notes in Math., 1234).

[Fo1] FOATA (Dominique). — Distributions eulériennes et mahonniennes sur le groupe des permutations, Higher Combinatorics [M. Aigner, ed., Berlin. 1976], p. 27– 49. — Amsterdam, D. Reidel, 1977 (Proc. NATO Adv. Study Inst.).

[Fo-Sch1] FOATA (Dominique) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Théorie géométrique des polynômes eulériens. — Berlin, Springer-Verlag, 1970 (Lecture Notes in Math., 138).

[Fo-Sch2] FOATA (Dominique) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Major Index and

Inversion of Permutations, Math. Nachr., t. 83, 1978, p. 143–159.

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

[Ga-Ge] GARSIA (Adriano M.) and GESSEL (Ira). — Permutation Statistics and Parti-

tions, Advances in Math., t. 31, 1979, p. 288–305.

[Ge] GESSEL (Ira). — Generating functins and enumeration of sequences, Ph.D. thesis,

department of mathematics, M.I.T., Cambridge, Mass., 111 p., 1977.

[Ja-Ke] JAMES (Gordon) and KERBER (Adalbert). — The Representation Theory of the Symmetric Group. — Reading, Mass., Addison-Wesley, 1981 (Encyclopedia of Math. and Its Appl., 16).

[Knu] KNUTH (Donald E.). — The Art of Computer Programming, vol. 3, Sorting and

Searching. — Don Mills, Ontario, Addison-Wesley, 1972.

[La-Sch1] LASCOUX (Alain) et SCH^{}ÜTZENBERGER (Marcel-Paul). — A new statistics on words, Combinatorial Mathematics, Optimal Designs and their Applications [J. Srivastava, ed., Fort Collins, Colorado. 1978], p. 251–255. — Amsterdam, North-Holland, 1980 (Annals of Discrete Math., 6).

[La-Sch2] LASCOUX (Alain) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Sur une conjecture de

H.O. Foulkes, C.R. Acad. Sc. Paris, t. 286A, 1978, p. 385–387.

[La-Sch3] LASCOUX (Alain) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Formulaire raisonné

des fonctions symétriques, L.I.T.P., U.E.R. Math., Univ. Paris VII, 138 p., 1984.

[La-Sch4] 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).

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

[Mac1] MACMAHON (Percy Alexander). — The indices of permutations and the derivation therefrom of functions of a single variable associated with the permutations of any assemblage of objects, Amer. J. Math., t. 35, 1913, p. 314–321.

[Mac2] MACMAHON (Percy Alexander). — Combinatory Analysis, vol. 1. — Cambridge, Cambridge Univ. Press, 1915 (Réimprimé par Chelsea, New York, 1955).

[Mac3] MACMAHON (Percy Alexander). — Two applications of general theorems in combinatory analysis, Proc. London Math. Soc., t. 15, 1916, p. 314–321.

[Mac4] MACMAHON (Percy Alexander). — Collected Papers, vol. 1 [G.E. ANDREWS, ed.]. — Cambridge, Mass., The M.I.T. Press, 1978.

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

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

[Re1] REMMEL (J.B.). — The combinatorics of (k, l)-hook Schur functions, Cont. Math., t. 34, 1984, p. 253–287.

[Re2] REMMEL (J.B.). — A bijective proof of a factorization theorem for (k, l)-hook Schur functions, Preprint, Univ. Calif. San Diego, 1985.

[Re3] REMMEL (J.B.). — Permutation Statistics and (k, l)-hook Schur functions, Discrete Math., à paraître.

[Ro] ROSELLE (David P.). — Coefficients associated with the Expansion of certain

Products, Proc. Amer. Math. Soc., t. 45, 1974, p. 144–150.

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

[Sch2] 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).

[St1] STANLEY (Richard P.). — Ordered Structures and Partitions. — Providence, R.I., Amer. Math. Soc., 1972 (Memoirs Amer. Math. Soc., 119).

[St2] STANLEY (Richard P.). — Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A, t. 20, 1976, p. 336–356.

[Wy] WYBOURNE (Brian G.). — Symmetry principles and atomic spectroscopy. New York, Wiley 1970.

Jacques Désarménien, Département d’informatique, Institut universitaire de technologie, Université Robert-Schumann, 72, route du Rhin, F-67400 Illkirch-Graffenstaden.

email : A18630@FRCCSC21.BITNET

Dominique Foata,

Département de mathématique, Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg Cedex.

email : A18621@FRCCSC21.BITNET