FONCTIONS SYMÉTRIQUES ET SÉRIES

HYPERGÉOMÉTRIQUES BASIQUES MULTIVARIÉES, II ^{1}

PAR

Jacques DÉSARMÉNIEN et Dominique FOATA ^{2}

En l’honneur de Marcel-Paul SCH^{}ÜTZENBERGER

R^{}ÉSUM^{}É. — Dans un article précédent [8], nous avons fait apparaître des fonctions hypergéométriques basiques multivariées dans l’étude de certaines statistiques sur le groupe symétrique. Nous établissons ici les propriétés de symétrie de ces fonctions en faisant appel à l’algèbre des tableaux de Young.

ABSTRACT. — In a previous paper [8] we showed how some multivariate basic hypergeometric functions arose in the study of certain statistics on the symmetric group. Here we establish symmetry properties of those fonctions by means of the Young tableau algebra.

1. Introduction

Pour chaque entier n ≥ 0, posons :

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

D’autre part, pour chaque paire d’entiers positifs r, s, adoptons la notation :

(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,

1 Ce texte a été composé par le laboratoire de typographie informatique de l’Université Louis-Pasteur à Strasbourg, au moyen du préprocesseur STRATEC. Le fichier obtenu a été ensuite traité par le logiciel TEX/SM 90. 2 Département de Mathématique, Université Louis-Pasteur de Strasbourg, 7, rue René-Descartes, F-67084 Strasbourg Cedex.

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}

Dans [8] nous avons établi que l’identité :

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

définissait une suite de polynômes

C_{n} = ∑ C(n; m, r, s, i, j)z^{m}t_{1}^{r}t_{2}^{s}q_{1}^{i}q_{2}^{j}

à cinq variables z, t_{1}, t_{2}, q_{1}, q_{2}, où les coefficients C(n; m, r, s, i, j) étaient des entiers positifs, de somme égale à n! 2^{n}.

Cette identité contenait comme cas particuliers, d’une part, les formules classiques sur les q-séries (par exemple, la formule q-binomiale [1, p. 17, 2, p. 66]), d’autre part, les identités sur les distributions multivariées de statistiques sur le groupe symétrique.

Soient (a_{1}, a_{2}, …, a_{k}) une suite d’entiers positifs de somme n et W = W (a_{1}, a_{2}, …, a_{k}) l’ensemble de tous les réarrangements du mot 1^{a_{1}}2^{a_{2}} ⋯ k^{a_{k}}. Si w = x_{1}x_{2} ⋯ x_{n} est un tel réarrangement, sa ligne de route, notée Ligne w, est définie comme l’ensemble des entiers i tels que 1 ≤ i ≤ n − 1 et x_{i} > x_{i+1}, tandis que le nombre de descentes Des w et l’indice majeur Maj w sont définis par :

Des w = |Ligne w| Maj w = ∑{i : i ∈ Ligne w}.

On doit à MACMAHON d’avoir introduit la notion d’indice majeur (“major index”), d’avoir également calculé sa fonction génératrice sur tout ensemble W de réarrangements, enfin d’avoir montré qu’elle était la même que celle du nombre des inversions (cf. [22, 23 § 104, 24, 25]).

Lorsque tous les a_{i} sont égaux à 1 (et donc k à n), chaque réarrangement w dans W est une permutation de 12 ⋯ n. On peut alors définir les quantités :

Ides w = Des w^{−1} Imaj w = Maj w^{−1},

où w^{−1} est l’inverse de w dans le groupe (symétrique) W. Les distributions univariées ou multivariées des statistiques Des, Ides, Maj, Imaj sur V ont fait l’objet de nombreuses études et ont été calculées avec succès. Par exemple, le polynôme générateur de Des sur W n’est autre que le polynôme eulérien (cf. [10]), les q-nombres eulériens donnent la distribution du couple (Des, Maj) (cf. [3, 4, 5]). La fonction génératrice du quadruplet (Des, Ides, Maj, Imaj), toujours sur le groupe symétrique W, fut calculée par GARSIA–GESSEL [13] et RAWLINGS [26], tandis que le groupe de symétrie de la distribution de ce quadruplet fut obtenu dans le contexte des tableaux de Young (cf. [11]). D’autres résultats sur ces statistiques sont dues à CARLITZ [6], CHEEMA–MOTZKIN [7], GESSEL [14], RAWLINGS [27], ROSELLE [29], STANLEY [33]. Voir également [9].

Dans [8], nous avons étendu la définition des statistiques Des, Ides, Maj, Imaj à l’ensemble des permutations colorées, ensemble de cardinal n! 2^{n}, et fait apparaître les polynômes C_{n} de la formule (1.1) comme des fonctions génératrices d’un 5-vecteur sur cet ensemble. Nous avons ainsi pu démontrer que, par spécialisation, on obtenait toutes les formules sur le groupe symétrique faisant intervenir les quatre statistiques ci-dessus.

Rappelons également que (1.1) se particularise en la formule :

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

(les C_{n}(z, q_{1}, q_{2}) étant des polynômes), formule considérée comme un analogue de la formule q-binomiale au cas de deux bases q_{1}, q_{2}.

Dans notre article, nous n’avions cependant pas respecté le principe de RIORDAN, qui veut que toute définition nouvelle de polynômes ou de suites de nombres soit nécessairement accompagnée de la table des premières valeurs (permettant ainsi au lecteur de vérifier aisément les relations de récurrence dans les cas initiaux). Nous nous proposons ici de réparer cette offense et de calculer les premières valeurs de C_{n} pour n = 1, 2, 3, 4, 5, 6. On trouvera celles-ci dans l’annexe 2, qui contient les tables des coefficients C(n; m, r, s, i, j).

Comme le lecteur peut le constater ces tables présentent plusieurs symétries, suivant la diagonale principale, à l’intérieur de chaque bloc correspondant à une valeur fixée de i, j, entre blocs, … Le but principal de cet article sera de prouver ces symétries, de façon plus essentielle, de dégager le groupe de symétrie sous-jacent. Le résultat prouvé s’exprime analytiquement sous la forme suivante :

Théorème 1.1. — Pour tout 5-vecteur v = (m, r, s, i, j), on a les relations :

(1.2) C(n; m, r, s, i, j) = C(n; m, s, r, j, i), (1.3) C(n; m, r, s, i, j) = C(n; m, r, s, i, ns − j), (1.4) C(n; m, r, s, i, j) = C(n; m, n − 1 − r, n − 1 − s, \binom{n}{2} − i, \binom{n}{2} − j),

(1.5) C(n; m, r, s, i, j) = C(n; n − m, r, n − 1 − s, i, \binom{n}{2} − j).

Le calcul effectif des polynômes C_{n} repose sur la manipulation des (t, q)-tableaux F_{ν/θ}(t, q). Ceux-ci sont introduits dans la prochaine section comme polynômes générateurs de tableaux gauches d’une forme donnée ν/θ. L’algèbre des fonctions de Schur permet d’exprimer les polynômes C_{n} en fonction des (t, q)-tableaux (formule (3.5)). De façon équivalente, C_{n} s’exprime comme fonction génératrice de paires de tableaux gauches par une certaine statistique V (formule (3.8)). La section 4 contient des indications pour le calcul effectif des (t, q)-tableaux. Dans la section 5, nous donnons la construction de trois involutions sur les tableaux de forme λ⊗μ, permettant dans la section suivante de dégager le groupe de symétrie d’ordre 32 de la distribution V.

2. Les (t, q)-tableaux

Désignons 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. 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 λ = (2, 1) et μ = (3, 1), on obtient pour λ ⊗ μ le diagramme gauche matérialisé par les croix :

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

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 λ. On dira aussi qu’un tableau est droit (resp. gauche), si sa forme est un diagramme de Ferrers (resp. diagramme gauche).

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

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

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

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

est alors évidente.

La ligne inverse de route (cf. [11]) d’un tableau standard R, d’ordre n, de forme ν/θ, est l’ensemble des entiers k tels que 1 ≤ k ≤ n − 1 et tels que (k + 1) soit écrit plus haut que k dans R. Cette ligne inverse de route est notée Iligne R. On pose également :

(2.1) Ides R = |Iligne R|  et  Imaj R = ∑{i : i ∈ Iligne R}.

Dans l’exemple précédent, on a Iligne R_{1} = {2, 3, 5, 7}, de sorte que Ides R_{1} = 4 et Imaj R_{1} = 2 + 3 + 5 + 7 = 17.

La statistique Imaj introduite ici sur les tableaux gauches reprend l’information contenue dans la charge et la cocharge des tableaux, deux notions introduites par LASCOUX–SCH^{}ÜTZENBERGER [17, 18]. Voir également MACDONALD [21, p. 129].

Pour chaque diagramme gauche ν/θ de cardinal n, on introduit le polynôme générateur du couple (Ides, Imaj) sur l’ensemble de tous les tableaux standard R, d’ordre n, de forme ν/θ, à savoir le polynôme :

(2.2) F_{ν/θ}(t, q) = ∑ t^{Ides R}q^{Imaj R}  (R standard, de forme ν/θ).

Ce polynôme sera désigné par (t, q)-tableau.

Dans le présent article, on considèrera essentiellement les (t, q)-tableaux F_{λ⊗μ}(t, q) correspondant aux diagrammes λ ⊗ μ.

3. Fonctions de Schur

Nous rappelons brièvement ici comment les polynômes C_{n} (cf. (1.1) et (1.2)) s’expriment en fonction des (t, q)-tableaux et comment l’algèbre des fonctions de Schur fournit tous les éléments de calcul nécessaires.

On note S_{ν/θ}(x) la fonction de Schur gauche associée au diagramme gauche ν/θ, avec x comme ensemble de variables (cf. [13, p. 42]). Lorsque ν/θ = λ ⊗ μ (avec λ et μ diagrammes de Ferrers, comme indiqué dans la section précédente), il résulte de la définition même des fonctions de Schur (cf. [13, p. 42]) que l’on a :

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

Par ailleurs, les produits de fonctions de Schur s’expriment comme combinaisons linéaires d’autres fonctions de Schur :

(3.2)  S_{λ}(x)S_{μ}(x) = ∑_{ν} g_{λμν}S_{ν}(x),

où les coefficients g_{λμν} sont des entiers positifs, qu’on peut évaluer par l’algorithme de Littlewood-Richardson.

Partons alors des deux formules de Cauchy (cf. [13, p. 33 et 35]) :

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

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

et multiplions les membre à membre compte tenu de (3.1) tout en introduisant une variable d’homogénéité u. Nous obtenons :

∑_{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}^{r})S_{λ′⊗μ}(1, …, q_{2}^{s}) = \frac{(−zu; q_{1}, q_{2})_{r+1,s+1}}{(u; q_{1}, q_{2})_{r+1,s+1}} .

Multipliant par t_{1}^{r}t_{2}^{s} et sommant par rapport à r et s, on obtient, comme second membre, le second membre de l’identité (1.1). Le premier membre, lui, s’écrit :

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

Comparant avec (1.1), on voit donc que C_{n} est égal à l’expression :

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

∑_{r,s} t_{1}^{r}t_{2}^{s}S_{λ⊗μ}(1, …, q_{1}^{r})S_{λ′⊗μ}(1, …, q_{2}^{s}).

Le lemme suivant, énoncé et démontré dans [6, théorème 4.1], permet non seulement de prouver que C_{n} est un polynôme, mais fournit aussi une interprétation combinatoire pour C_{n}, compte tenu des propriétés bien connues des fonctions de Schur. REMMEL [16] a utilisé récemment ce lemme pour exploiter combinatoirement plusieurs formules classiques sur les fonctions de Schur. Notre collègue Richard STANLEY, dans une correspondance privée, nous a fait savoir que ce lemme pouvait se déduire de la proposition 8.3, p. 24 de sa thèse [20], pourvu que l’on sache faire le rapprochement souhaité entre (P, ω)-partitions et (t, q)-tableaux.

Lemme. — Soit ν/θ un diagramme gauche de n éléments, alors le (t, q)-tableau F_{ν/θ}(t, q), tel qu’il est défini en (2.2) est donné par :

(3.4)  F_{ν/θ}(t, q) = (t; q)_{n+1} ∑_{r} t^{r}S_{ν/θ}(1, q, q^{2}, …, q^{r}).

Comparant (3.3) et (3.4), on en déduit que C_{n} est un polynôme et qu’il peut être exprimé au moyen de la formule :

(3.5)  C_{n} = ∑_{λ,μ} z^{|λ|}F_{λ⊗μ}(t_{1}, q_{1})F_{λ′⊗μ}(t_{2}, q_{2}),

où la somme est étendue sur l’ensemble des couples de diagrammes de Ferrers tels que |λ| + |μ| = n.

Donnons enfin une autre expression pour C_{n}, qui prend en charge la définition (2.2) des (t, q)-tableaux. Soient R_{1}, R_{2} deux tableaux standard, d’ordre n, de forme λ_{1} ⊗ μ_{1} et λ_{2} ⊗ μ_{2}, respectivement. On dit qu’ils sont jumelables si λ_{1} = λ′_{2} et μ_{1} = μ_{2}. La paire λ_{1} ⊗ μ_{1}, λ_{2} ⊗ μ_{2} ( = λ_{1} ⊗ μ_{1}, λ′_{1} ⊗ μ_{1}) est appelée forme de R_{1}R_{2}. Le V -vecteur de la paire R_{1}R_{2} est, par définition, le vecteur :

(3.6)  V (R_{1}R_{2}) = (|λ_{1}| , Ides R_{1}, Ides R_{2}, Imaj R_{1}, Imaj R_{2}).

On note aussi v(R_{1}R_{2}) le monôme :

(3.7)  v(R_{1}R_{2}) = z^{|λ|}t_{1}^{Ides R_{1}}t_{2}^{Ides R_{2}}q_{1}^{Imaj R_{1}}q_{2}^{Imaj R_{2}}.

Enfin, on désigne par T′_{n} l’ensemble des couples jumelables de tableaux standard d’ordre n. Il résulte de (3.5) et de (2.1) que C_{n} est le polynôme générateur des paires de tableaux standard d’ordre n, jumelables, par le vecteur V, ou encore que l’on a :

(3.8)  C_{n} = ∑_{R_{1}R_{2}} v(R_{1}R_{2})  (R_{1}R_{2} ∈ T′_{n}).

4. Le calcul des polynômes

Nous montrons ici comment on peut simplement calculer les polynômes F_{λ}(t, q), puis en déduire l’expression de F_{λμ}(t, q), enfin déterminer C_{n} au moyen de la formule (3.5).

Chaque (t, q)-tableau F_{λ}(t, q) sera représenté par son diagramme de Ferrers sous-jacent. Par exemple :

F_{4,2}(t, q) = .

De la même manière, le symbole 6 désigne la fonction génératrice, par Ides et Imaj (cf. (2.1)), des tableaux standard de forme λ = 4, 2, ayant l’entier 6 dans le coin supérieur droit.

En se reportant à la définition même de la ligne inverse d’un tableau et de Ides et Imaj, on a :

= 6  +  6 ,
= 5 6  + 6 5 +  ,
= tq^{4}  + tq^{5}  +  ,
= tq^{4}F_{4}(t, q) + tq^{5}F_{3,1}(t, q) + F_{3,2}(t, q).

Si on connait déjà l’expression des polynômes F_{λ}(t, q) pour les λ tels que |λ| ≤ 5, on obtient donc celle de F_{4,2}(t, q). Dans l’annexe 1, c’est ainsi que les F_{λ}(t, q) ont été calculés jusqu’à l’ordre 6.

Maintenant, les identités (3.1) et (3.2) sur les fonctions de Schur entraînent les formules :

(4.1)  F_{λ⊗μ}(t, q) = F_{μ⊗λ}(t, q)

et

(4.2)  F_{λ⊗μ}(t, q) = ∑_{ν} g_{λμν}F_{ν}(t, q).

La première de ces formules permet de ne calculer F_{λ⊗μ}(t, q) que pour les couples λ, μ tels que λ ≤ μ (pour un ordre total donné sur les partitions). La seconde dit qu’une bonne table des coefficients g_{λμν} de Littlewood-Richardson, telle qu’elle est donnée dans JAMES-KERBER [10] ou WYBOURNE [21], suffit pour déduire l’expression de F_{λ⊗μ}(t, q) de celle des F_{λ}(t, q).

Muni de la table des F_{λ⊗μ}(t, q), on peut utiliser directement la formule (3.5) pour calculer les polynômes C_{n}. On peut aussi faire usage de la formule :

(4.3)  C_{n} = ∑_{λ,μ} z^{|λ|} ∑_{ν_{1},ν_{2}} g_{λμν_{1}}g_{λ′μν_{2}}F_{ν_{1}}(t_{1}, q_{1})F_{ν_{2}}(t_{2}, q_{2}).

5. Les involutions

Soit T_{n} l’ensemble de tous les tableaux standard d’ordre n dont la forme est un produit λ ⊗ μ (éventuellement réduite à un diagramme de Ferrers). Nous nous proposons de montrer qu’on peut construire trois involutions J, S et T de T_{n} ayant les propriétés suivantes :

Si P ⊗ Q est un tableau standard d’ordre n, de forme λ ⊗ μ, alors

(5.1)  (P ⊗ Q)^{S} est de forme μ ⊗ λ et
(5.1′)  Iligne(P ⊗ Q)^{S} = Iligne P ⊗ Q;
(5.2)  (P ⊗ Q)^{J} est de forme λ ⊗ μ et
(5.2′)  Iligne(P ⊗ Q)^{J} = n − Iligne P ⊗ Q;
(5.3)  (P ⊗ Q)^{T} est de forme μ′ ⊗ λ′ et
(5.3′)  Iligne(P ⊗ Q)^{T} = [n − 1] \ Iligne P ⊗ Q.

De plus, (5.4) S, J et T commutent deux à deux.

L’involution T est simplement la transposition des tableaux, de sorte que (5.3) et (5.3′) sont des propriétés immédiates.

La construction des deux autres involutions repose sur les propriétés du jeu de taquin et sur les propriétés de l’opération de vidage-remplissage J des tableaux droits (cf. [18, 19, 11, p. 48–73]). Rappelons qu’à tout tableau gauche (par exemple un tableau P ⊗ Q de forme λ ⊗ μ), on peut faire correspondre un tableau droit de même contenu et ayant la même ligne inverse de route. Ce tableau droit, que l’on notera Taq(P ⊗Q) (si l’on part du tableau gauche P ⊗ Q), s’obtient à partir de P ⊗ Q en appliquant un nombre suffisant de fois les mouvements de base du jeu de taquin (cf. [19, 12]). On a donc :

(5.5)  Iligne P ⊗ Q = Iligne Taq(P ⊗ Q).

Considérons, par exemple, les deux tableaux :

P ⊗ Q = 6 8 4 5 9 3 1 2 7  et  R = 6 4 8 3 5 9 1 2 7

On vérifie qu’ils ont la même ligne inverse de route {2, 3, 5, 7} et que l’on a R = Taq(P ⊗ Q).

Rappelons aussi que le vidage-remplissage des tableaux droits est une involution R ↦ R^{J}, conservant le contenu et la forme et satisfaisant à

(5.6)  Iligne R^{J} = n − Iligne R,

si R est d’ordre n (cf. [7]).

Par exemple, le vidé-rempli R^{J} du tableau R ci-dessus est donné par :

R^{J} = 8 7 9 3 5 6 1 2 4

et l’on a Iligne R^{J} = {2, 4, 6, 7} = 9 − {2, 3, 5, 7} = n − Iligne R.

Soient maintenant λ, μ, ν trois partitions de l, m, n, respectivement, telles que l + m = n et λ, μ ⊂ ν et soit R_{0} un tableau standard, d’ordre n, de forme ν. On note W_{1} = W (λ, μ, R_{0}) l’ensemble des tableaux standard P ⊗ Q, d’ordre n, de forme λ ⊗ μ, tels que Taq(P ⊗ Q) = R_{0}. Le résultat remarquable dû à SCH^{}ÜTZENBERGER (cf. [19, p. 95]) est que le cardinal de W (λ, μ, R_{0}) ne dépend que de la paire non ordonnée {λ, μ} et de la forme ν de R_{0} ; il est, de plus, égal au coefficient g(λ, μ, ν) de Littlewood-Richardson. On a, enfin,

(5.7)  g(λ, μ, ν) = g(λ′, μ′, ν′).

Comme le vidage-remplissage conserve la forme des tableaux droits, on conclut immédiatement que les huit ensembles W_{1}, W_{s} = W (μ, λ, R_{0}), W_{j} = W (λ, μ, R_{0}^{J}), W_{sj} = W (μ, λ, R_{0}^{J}), W_{t} = W (μ′, λ′, R_{0}^{T}), W_{st} = W (λ′, μ′, R_{0}^{T}), W_{jt} = W (μ′, λ′, R_{0}^{JT}), W_{sjt} = W (λ′, μ′, R_{0}^{JT}) ont tous même cardinal, égal à g(λ, μ, ν).

Supposons que le triplet (λ, μ, ν) soit tel que ν ≤ ν′ (par exemple, par rapport à l’ordre lexicographique inverse des partitions), le tableau droit R_{0} étant toujours supposé de forme ν. Au quadruplet (W_{1}, W_{s}, W_{j}, W_{js}) faisons correspondre quatre bijections arbitraires, comme indiqué dans le diagramme :

W (λ, μ, R_{O}) ⟶^{S} W (μ, λ, R_{0})
↓^{J}  ↓^{J}
W (λ, μ, R_{0}^{J}) ⟶^{S} W (μ, λ, R_{0}^{JS})

Si P ⊗ Q est dans W_{1}, notons (P ⊗ Q)^{S}, P ⊗ Q)^{J}, (P ⊗ Q)^{JS} les images de P ⊗ Q par les applications de ce diagramme, soit :

P ⊗ Q ⟶ (P ⊗ Q)^{S}
↓  ↓
(P ⊗ Q)^{J} ⟶ (P ⊗ Q)^{JS}

Ce diagramme étant construit, formons ensuite le diagramme obtenu en remplaçant les quatre tableaux par leurs transposés :

(P ⊗ Q)^{T} ⟶ (P ⊗ Q)^{ST}
↓  ↓
(P ⊗ Q)^{JT} ⟶ (P ⊗ Q)^{JST}

Comme on sait (cf. [7, 19]) que, si Taq(P ⊗Q) = R_{0}, alors Taq((P ⊗Q)^{T}) = R_{0}^{T}, il est clair que ces quatre tableaux transposés (P ⊗ Q)^{T}, (P ⊗ Q)^{ST}, (P ⊗ Q)^{JT} et (P ⊗ Q)^{JST} appartiennent respectivement à W_{t}, W_{st}, W_{jt}, W_{jst}. Ceci prouve les propriétés (5.1) et (5.2). La propriété (5.4) résulte de la construction même de ces involutions.

Enfin, les propriétés (5.1′) et (5.2′) sont automatiquement vérifiées, puisque l’on a pour tout P ⊗ Q ∈ W (λ, μ, R_{0}), la relation Taq(P ⊗ Q) = Taq R_{0}, d’où Iligne P ⊗ Q = Iligne R_{0}. Par définition même des ensembles W, on en tire :

Iligne(P ⊗ Q)^{S} = Iligne R_{0} = Iligne P ⊗ Q ;

Iligne(P ⊗ Q)^{J} = Iligne R_{0}^{J} = n − Iligne R_{0} = n − Iligne P ⊗ Q.

Remarque. — On peut obtenir une construction explicite des involutions S, J et T en utilisant les deux lemmes 3.7 et 4.5 de SCH^{}ÜTZENBERGER [19]. Cependant les bijections entre les ensembles W dépendent de deux tableaux standard P_{0} et Q_{0}, de forme λ et μ, choisis arbitrairement.

6. Les symétries

Nous disposons de tous les éléments pour démontrer le théorème 1.1. Pour visualiser les quatre propriétés à établir, il est bon de se reporter aux tables de l’annexe 2, où sont reproduites les tables des valeurs C(n; v) pour tous les vecteurs v et les valeurs n de 1 à 6.

La relation (1.2) dit que chaque table est symétrique par rapport à sa diagonale principale.

La relation (1.3) exprime le fait que, dans chaque table, pour tout couple de valeurs (r, s), le bloc correspondant à (r, s) a un axe de symétrie vertical. Il a donc aussi un axe de symétrie horizontal en conjuguant les propriétés (1.2) et (1.3).

La relation (1.4) dit que le centre de la table est un centre de symétrie. Enfin, (1.5) affirme que la table correspondant à la première valeur

n − m du vecteur V se déduit de la table correspondant à m par une symétrie par rapport à son axe vertical. De ce fait, on peut représenter en une seule fois les tables m et les tables n − m en disposant les variables de façon adéquate.

Notons T′_{n} l’ensemble de toutes les paires R_{1}R_{2} jumelables (cf. section 3). Pour démontrer (1.2), on considère l’involution i de T′_{n} définie par :

(6.2′)  i(R_{1}R_{2}) = R_{2}R_{1}.

Cette involution envoie bien chaque paire R_{1}R_{2}, de forme λ ⊗ μ, λ′ ⊗ μ, de V -vecteur (m, r, s, i, j) sur R_{2}R_{1} de forme λ′ ⊗ μ, λ ⊗ μ et de V -vecteur (m, s, r, j, i).

Pour obtenir (1.3), on considère la bijection de T′_{n} sur lui-même définie par :

(6.3′)  j(R_{1}R_{2}) = R_{1}R_{2}^{J}.

D’après (3.5) et (5.5), on définit bien là une bijection, qui envoie chaque R_{1}R_{2} de forme λ ⊗ μ, λ′ ⊗ μ, de V -vecteur (m, r, s, i, j) sur R_{1}R_{2}^{J}, de forme λ ⊗ μ, λ′ ⊗ μ et de V -vecteur (m, r, s, i, ns − j).

Avec t définie par :

(6.4′)  t(R_{1}R_{2}) = R_{1}^{ST} R_{2}^{ST} .

on tient une involution de T′_{n}, qui d’après (5.3) envoie R_{1}R_{2} sur R_{1}^{ST}R_{2}^{ST}, de forme λ′ ⊗ μ′, λ ⊗ μ′ et de V -vecteur

(m, n − 1 − r, n − 1 − s, \binom{n}{2} − i, \binom{n}{2} − j).

La dernière involution, notée s, est définie par :

(6.5′)  s(R_{1}R_{2}) = R_{1}^{S}R_{2}^{T} .

Elle envoie la paire R_{1}R_{2}, de forme λ⊗μ, λ′⊗μ et de V -vecteur (m, r, s, i, j) sur une paire R_{1}^{S}R_{2}^{T}, de forme μ ⊗ λ, μ′ ⊗ λ, de V -vecteur

(n − m, r, n − 1 − s, i, \binom{n}{2} − j).

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

Soit G le groupe engendré par les involutions i, j, t et s. On vérifie immédiatement les relations :

i^{2} = j^{2} = t^{2} = s^{2} = (ij)^{4} = (is)^{4} = 1, it = ti, jt = tj, st = ts, js = sj.

Par conséquent, le groupe G contient le groupe diédral D_{4}(i, j), d’ordre 8, engendré par {i, j}, ainsi que le produit de ce groupe par le groupe {1, t} d’ordre 2.

Soit R_{1}R_{2} un élément de T′_{n}. Les éléments de l’orbite de R_{1}R_{2}, par rapport au groupe G, sont de la forme R_{k}^{α}R_{l}^{β}, avec {k, l} = {1, 2} et α, β des monômes de degré au plus égal à 1 en chacune des variables S, J, T. Les éléments R_{k}^{α}R_{l}^{β} de l’orbite ne contenant ni S, ni T dans les exposants α et β sont au nombre de huit. Ce sont en fait les huit éléments de l’orbite de R_{1}R_{2} par rapport au sous-groupe D_{4}(i, j) :

R_{1}R_{2}, R_{2}R_{1}, R_{2}R_{1}^{J}, R_{1}^{J}R_{2}, R_{1}^{J}R_{2}^{J}, R_{2}^{J}R_{1}^{J}, R_{2}^{J}R_{1}, R_{1}R_{2}^{J}.

Les éléments R_{k}^{α}R_{l}^{β} tels que α et β sont divisibles par ST sont au nombre de huit :

R_{1}^{ST} R_{2}^{ST} , R_{2}^{ST} R_{1}^{ST} , R_{2}^{ST} R_{1}^{JST} , R_{1}^{JST} R_{2}^{ST} ,
R_{1}^{JST} R_{2}^{JST} , R_{2}^{JST} R_{1}^{JST} , R_{2}^{JST} R_{1}^{ST} , R_{1}^{ST} R_{2}^{JST} .

Les seize éléments écrits constituent l’orbite de R_{1}R_{2} par rapport au produit D_{4}(i, j) × {1, t}.

À cause de la définition de s, les seules autres paires R_{k}^{α}R_{l}^{β} possibles doivent satisfaire l’une des deux conditions :

(i) S divise α, T ne divise pas α, T divise β, S ne divise pas β,
(ii) T divise α, S ne divise pas α, S divise β, T ne divise pas β.

Ces paires forment l’orbite de R_{1}^{S}R_{2}^{T} par rapport au groupe D_{4}(i, j) × {1, t} et sont au nombre de seize :

R_{1}^{S}R_{2}^{T} , R_{2}^{T} R_{1}^{S}, R_{2}^{T} R_{1}^{JS}, R_{1}^{JS}R_{2}^{T} ,
R_{1}^{JS}R_{2}^{JT} , R_{2}^{JT} R_{1}^{JS}, R_{2}^{JT} R_{1}^{S}, R_{1}^{S}R_{2}^{JT} ,
R_{1}^{T} R_{2}^{S}, R_{2}^{S}R_{1}^{T} , R_{2}^{S}R_{1}^{JT} , R_{1}^{JT} R_{2}^{S},
R_{1}^{JT} R_{2}^{JS}, R_{2}^{JS}R_{1}^{JT} , R_{2}^{JS}R_{1}^{T} , R_{1}^{T} R_{2}^{JS}.

Il n’y a pas d’autres paires possibles. Le groupe G est donc d’ordre 32.

BIBLIOGRAPHIE

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

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

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

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

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

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

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

[8] 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.

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

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

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

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

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

[14] GESSEL (Ira). — Generating functions and enumeration of sequences, Ph.D. thesis, department of mathematics, M.I.T., Cambridge, Mass., 111 p., 1977.

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

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

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

[18] 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.

[19] 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.

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

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

[22] 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.

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

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

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

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

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

[28] REMMEL (Jeff). — Symmetric functions and q-series, preprint, Univ. Calif. San Diego, 1984.

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

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

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

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

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

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