PERMUTATIONS COLORÉES ET TABLEAUX GAUCHES

PAR

Dominique FOATA

R^{}ÉSUM^{}É. — Une correspondance est proposée entre permutations colorées et tableaux gauches permettant le calcul de certaines statistiques sur les permutations à partir de l’algèbre des fonctions de Schur.

1. Introduction. — L’algèbre des fonctions de Schur a été utilisée dans [Desfo1] et [Desfo2] pour le calcul des distributions de statistiques classiques sur le groupe symétrique. Plus récemment, REMMEL [Rem3] a pu prolonger ce calcul à l’aide des fonctions de Schur (k, l)-crochets. Il a introduit le concept fort utile de bipermutation et calculé les fonctions génératrices correspondantes. Comme il est exposé dans [Fo2], on peut reprendre toute l’approche de REMMEL et la prolonger à une classe plus importante de permutations dites (k, l)-colorées. La théorie combinatoire des fonctions de Schur (k, l)-crochets, telle qu’elle est exposée dans [Bereg, Berem, Rem1, Rem3] et habilement utilisée par REMMEL [Rem3], n’est alors plus indispensable, on peut simplement s’appuyer sur l’algèbre des fonctions de Schur usuelles. L’outil de transfert fondamental est alors une correspondance entre tableaux gauches d’une forme bien particulière et des triplets formés par une permutation et deux partitions ordonnées.

L’objet de cet article est de décrire cette correspondance. A titre d’illustration, un calcul de fonctions génératrices pour les permutations (3, 2)- colorées est reproduit à la fin. On se reportera à [Fo2] pour un exposé exhaustif, réalisé dans le cadre des fonctions hypergéométriques à plusieurs bases.

D. FOATA

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. [Fosch1]). 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]). Un pas décisif a été fait par GARSIA et GESSEL [Gage] (voir aussi [Ra1]) lorsqu’ils 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. [Gage, Ra1]) ainsi que son groupe de symétrie (cf. [Fosch2]). D’autres résultats parallèles ont été obtenus par différents auteurs (cf. [Car4, Chemo, St1, Ge, Ra2]).

C’est, en fait, l’étude approfondie de l’algèbre combinatoire des tableaux réalisée par SCH^{}ÜTZENBERGER [Sch1, 2, Lasch1, 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 indispensables dans les ouvrages classiques [St1, Macd, Jake, Wy]. La très célèbre correspondance de Robinson-Schensted (cf. [Knu, p. 48–72]) était le passage obligé entre le calcul des distributions de statistiques d’ordre et celui des fonctions symétriques.

Le présent article montre que ladite correspondance reste encore ce passage obligé lorsqu’on veut prolonger ce calcul de distributions à des classes plus importantes d’objets combinatoires, comme les permutations (k, l)-colorées dont il est question ci-après.

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], [FoSch2]) 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. On désigne par là des triplets τ = (σ, a, b), où σ est une permutation de l’intervalle [ n] et où a = (a_{1}, …, a_{k}) et b = (b_{1}, …, b_{l}) sont des suites de k et l entiers positifs, respectivement, de somme n. L’inverse d’une permutation (k, l)-colorée τ = (σ, a, b) est définie comme 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_{i} = b_{1} + ⋯ + b_{j} (0 ≤ j ≤ l).

Les partitions 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} τ.

Par conséquent :

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

Remarque 2.1. — Notons que si σ(a_{i}) > σ(a_{i}+1), l’entier a_{i} appartient à Ligne σ, mais n’apporte aucune contribution à Ligne_{i} σ; on a donc simplement l’inclusion ∑_{i} Ligne_{i} τ ⊂ Ligne σ. Notons aussi que Ligne_{i} τ peut aussi être définie comme l’ensemble de tous les entiers r tels que a_{i−1} + 1 ≤ r ≤ a_{i} − 1 ayant la propriété que

(2.1)  (r + 1) est à la gauche de r dans le mot σ^{−1}(1) ⋯ σ^{−1}(n).

Notation 2.2. — Considérons une bijection σ d’un sous-ensemble {r_{1} < r_{2} < ⋯ < r_{n}} de ℕ sur un sous-ensemble J de ℕ. Par convention, σ désigne à la fois la bijection elle-même et le mot σ(r_{1})σ(r_{2}) ⋯ σ(r_{n}).

Définition 2.3. — La ligne inverse de route peut être prolongée au cas des mots σ = σ(r_{1})σ(r_{2}) ⋯ σ(r_{n}) ayant des lettres différentes en désignant également par Iligne σ l’ensemble de tous les entiers s tels que s et (s + 1) sont des lettres de σ, l’entier (s + 1) étant à la gauche de s dans le mot σ = σ(r_{1})σ(r_{2}) ⋯ σ(r_{n}).

Lorsque {r_{1} < r_{2} < ⋯ < r_{n}} = J = [ n], i.e., quand σ est une permutation de [ n], on vérifie immédiatement que la ligne inverse de route qui vient d’être définie coïncide avec la définition donnée au début de ce paragraphe.

Soient τ_{1,j}, …, τ_{k,j} des bijections d’ensembles finis sur des sousensembles disjoints J_{1,j}, …, J_{k,j} de N. Pour chaque i = 1, …, k soit Iligne(← τ_{i,j}) l’ensemble et tous les entiers r tels que r est une lettre de τ_{i,j} et (r + 1) est une lettre de τ_{i′,j} pour un certain i′ < i. Alors, la ligne inverse de route du produit de juxtaposition τ_{1,j} ⋯ τ_{k,j} est égale à :

(2.2)  Iligne τ_{1,j} ⋯ τ_{k,j} = ∑_{i} Iligne τ_{i,j} + ∑_{i} Iligne(← τ_{i,j}).

3. Une première bijection. — Soit τ = (σ, a, b) une permutation (k, l)-colorée. Pour chaque couple (i, j) tel 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} ]. En d’autres termes, r appartient à I_{ij} si et seulement si les deux relations a_{i−1}+1 ≤ r ≤ a_{i} et b_{j−1}+1 ≤ σ(r) ≤ b_{j} sont satisfaites. Posons J_{ij} = σ(I_{ij}) et notons τ_{ij} la restriction de σ à I_{ij}. Il est clair que τ_{ij} est une bijection de I_{ij} sur J_{ij}; notons τ_{ij}^{−1} la bijection inverse envoyant J_{ij} sur I_{ij}. On a :

(3.1)  \begin{aligned}∑_{1≤j≤l} I_{ij} & = [ a_{i−1} + 1, a_{i}]  (1 ≤ i ≤ k), \\ ∑_{1≤i≤k} J_{ij} & = [ b_{j−1} + 1, b_{j} ]  (1 ≤ j ≤ l), \end{aligned}

de sorte que la réunion des valeurs prises par τ_{i1}^{−1}, τ_{i2}^{−1}, …, τ_{il}^{−1} (resp. τ_{1j}, τ_{2j}, …, τ_{kj}) n’est autre que l’intervalle [ a_{i−1}+1, a_{i}] (resp. [ b_{j−1}+1, b_{j} ]). Par conséquent, le produit de juxtaposition τ_{i}^{−1} = τ_{i1}^{−1}τ_{i2}^{−1} ⋯ τ_{il}^{−1} des mots (cf. notation 2.1) τ_{i1}^{−1}, τ_{i2}^{−1},…, τ_{il}^{−1} et le produit de juxtaposition τ_{j} = τ_{1j}τ_{2j} ⋯ τ_{kj} des mots τ_{1j}, τ_{2j},…, τ_{kj} sont des réarrangements de (a_{i−1} + 1)(a_{i−1} + 2) ⋯ a_{i} et (b_{j−1} + 1)(b_{j−1} + 2) ⋯ b_{j}, respectivement. On peut donc parler des lignes inverses de route de τ_{i}^{−1} et τ_{j}, suivant la définition 2.3.

Proposition 3.1. — On a :

(3.2)  Ligne_{i} τ = Iligne τ_{i}^{−1} , Iligne_{j} τ = Iligne τ_{j} ,

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

Démonstration. — Comme noté dans (2.1), Ligne_{i} τ est aussi l’ensemble de tous les r tels que a_{i−1} + 1 ≤ r ≤ a_{i} − 1 et tels que (r + 1) soit à la gauche de r dans σ^{−1}(1) ⋯ σ^{−1}(n). Or, d’après la définition 2.3, ceci est précisément la ligne inverse de route du mot τ^{−1}.

La même observation s’applique à Iligne_{j} τ et Iligne τ_{j}.

Ainsi, l’application τ ↦ (τ_{ij}) est une bijection de l’ensemble de toutes les permutations (k, l)-colorées τ = (σ, c, d) telles que c = a et d = b sur l’ensemble des k × l bijections (τ_{ij} : I_{ij} → J_{ij}) satisfaisant (3.1). De plus, la PROPOSITION 3.1 est vérifiée.

Pour mieux suivre les différentes étapes de la construction, il semble utile de donner l’exemple suivant qui sera traité tout au long de l’article.

3.2. 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 Iligne_{i} σ (i = 1, 2, 3) sont reproduits en gras.) 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). Quant aux bijections τ_{ij} (1 ≤ i ≤ k = 3, 1 ≤ j ≤ l = 2), elles sont égales à :

\begin{aligned}τ_{11} & = ( \begin{matrix}1 & 2 & 3 & 5 \\ 6 & 1 & 4 & 5 \end{matrix} ); \\ tau_{22} & = ( \begin{matrix}7 & 8 & 9 \\ 11 & 9 & 8 \end{matrix} ); \end{aligned} \begin{aligned}τ_{12} & = ( \begin{matrix}4 \\ 10 \end{matrix} ); \\ τ_{21} & = ( \begin{matrix}6 \\ 2 \end{matrix} ); \end{aligned} \begin{aligned}τ_{31} & = ( \begin{matrix}10 & 12 \\ 3 & 7 \end{matrix} ); \\ τ_{32} & = ( \begin{matrix}11 \\ 12 \end{matrix} ); \end{aligned}

et les mots τ_{i} et τ_{j}^{−1} à :

τ_{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 ;

et 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}.

4. La seconde bijection. — Comme d’habitude, on désigne par partition tout suite finie décroissante ν = (ν_{1}, ν_{2}, …, ν_{p}) d’entiers au moins égaux à 1. Si la somme ν_{1} + ν_{2} + ⋯ + ν_{p} est égale à n, alors ν est dite partition de n et l’on écrit |ν| = n. Le diagramme de Ferrers associé à ν est l’ensemble de tous les couples (i, j) du plan euclidien satisfaisant 1 ≤ i ≤ ν_{j} et 1 ≤ j ≤ p. On identifie le diagramme de Ferrers à la partition elle-même.

Soient ν = (ν_{1}, ν_{2}, …, ν_{p}) et θ = (θ_{1}, θ_{2}, …, θ_{r}) deux diagrammes de Ferrers. Si ν ⊃ θ, la différence d’ensemble ν \ θ, notée ν/θ, est appelée diagramme gauche. On note (ν/θ)′ le conjugué (ou le transposé) de ν/θ, obtenu en faisant pivoter le diagramme gauche autour de sa diagonale principale. Si λ/μ est un autre diagramme gauche tel que λ = (λ_{1}, …, λ_{s}), μ = (μ_{1}, …, μ_{t}) et λ ⊃ μ, le produit (ν/θ) ⊗ (λ/μ) est défini comme l’ensemble de tous les éléments de 𝔑^{2}, qui sont ou bien de la forme (i, s+j) avec (i, j) ∈ (ν/θ), ou bien de la forme (ν_{1} + i, j) avec (i, j) ∈ (λ/μ).

Le produit de l diagrammes de Ferrers λ_{i,1}, …, λ_{i,l} est noté λ_{i,1} ⊗ ⋯ ⊗ λ_{i,l}, ou simplement ⊗_{j=1}^{j=l}λ_{i,j}, ou encore ⊗_{j}λ_{i,j}.

Par exemple, soient λ_{1,1} = (3, 1), λ_{2,1} = (1) et λ_{3,1} = (2) trois diagrammes de Ferrers. Leur produit λ_{1,1} ⊗ λ_{2,1} ⊗ λ_{3,1} est le diagramme gauche de la forme :

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

Soient I un sous-ensemble fini de 𝔑 de cardinal n et ν/θ un diagramme gauche de n points. En écrivant les n entiers de I sur les n points du diagramme ν/θ de façon à obtenir une croissance dans les lignes (de gauche à droite) et dans les colonnes (de bas en haut). La configuration T obtenue est appelée tableau injectif de contenu I et de forme ν/θ. Il est commode d’écrire Cont T = I et |T | = ν/θ. Lorsque I = [ n], on remplace “de contenu I” par “d’ordre n”.

La ligne inverse de route d’un tableau injectif T de contenu I et de forme ν/θ est définie comme l’ensemble de tous les entiers k tels que k et (k+1) appartiennent à I, l’entier (k+1) étant écrit plus haut que k dans T. On note Iligne T la ligne inverse de route de T. Lorsque T est d’ordre n, on définit aussi sa coligne inverse de route par Icoligne T = [n − 1] \ Iligne T.

Par ailleurs, le transposé d’un tableau gauche T est le tableau T′ obtenu en faisant pivoter T autour de sa diagonale. En d’autres termes, l’entier m se trouve sur le point (i, j) dans T′, lorsque m est sur (j, i) dans T. Si |T | = ν/θ, alors |T′| = (ν/θ)′ = (ν′/θ′). Par exemple, si |T | = λ_{i,1} ⊗ ⋯ ⊗ λ_{i,l}, alors |T′| = λ′_{i,l} ⊗ ⋯ ⊗ λ′_{i,1}. Si, de plus, T est d’ordre n, son transposé T′ est aussi d’ordre n et

(4.1)  Icoligne T′ = Iligne T.

Par exemple, les tableaux P_{1,1} = 6 1 4 5 ; P_{2,1} = 2 ; P_{3,1} = 3 7 sont tous injectifs, de forme λ_{1,1} = (3, 1), λ_{2,1} = (1) et λ_{3,1} = (2) respectivement. Ils sont aussi de contenu différent. Par ailleurs, les deux tableaux

T_{1} = 6 1 4 5 2 3 7 T′_{1} = 7 3 2 5 4 1 6

sont injectifs d’ordre 7 et de forme |T_{1}| = λ_{1,1} ⊗ λ_{2,1} ⊗ λ_{3,1} et |T′_{1}| = λ′_{3,1} ⊗ λ′_{2,1} ⊗ λ′_{1,1} respectivement. On a aussi Iligne T_{1} = {3, 5} et Icoligne T_{1} = Iligne T′_{1} = {1, 2, 4, 6}. Ils sont obtenus à partir des tableaux précédents de façon évidente, de sorte que la notation

T_{1} = P_{1,1} ⊗ P_{2,1} ⊗ P_{3,1}, T′_{1} = P′_{3,1} ⊗ P′_{2,1} ⊗ P′_{1,1}

est claire.

Venons-en au principal théorème de cet article.

4.1. Théorème. — A toute permutation (k, l)-colorée τ = (σ, c, d) telle que c = a et d = 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 (k + l) tableaux gauches injectifs, d’ordres 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é :

(4.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’outil de base pour démontrer ce théorème est la correspondance de Robinson-Schensted (cf., par exemple, [Knu, p. 48–72] pour un excellent exposé de la question), correspondance qu’il faut prolonger à 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.

La correspondance de Robinson-Schensted envoie donc chacune des bijections τ_{i,j} : I_{i,j} → J_{i,j} sur un couple (P_{i,j}, Q_{i,j}) de tableaux injectifs de la même forme, dont les contenus et les lignes inverses de routes 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}) l’ensemble de tous les entiers s dans [b_{j−1} + 1, b_{j} − 1] tels que s soit dans P_{i,j} et tels que (s + 1) apparaisse dans P_{i′,j} pour un certain i′ < i. Alors

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} τ.

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 (4.2) sont alors vérifiées.

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

Illustrons la construction du précédent théorème à l’aide de l’exemple du § 3. 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 .

5. Application. — Le théorème combinatoire précédent permet de calculer les fonctions génératrices des permutations (k, l)-colorées pour différentes statistiques.

Rappelons tout d’abord quelques notations usuelles, comme la factorielle q-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}),

et une notation analogue dans le cas de deux bases q_{1}, q_{2} :

(u; q_{1}, q_{2})_{r,s} = \{ \begin{matrix}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 ; \end{matrix}

(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}).

Pour ne pas surcharger les notations, considérons le cas particulier k = 3, l = 2 (correspondant aux données de l’exemple traité ci-dessus) et introduisons les indices majeurs attachés à une permutation (3, 2)-colorée τ = (σ, a, b) comme étant les nombres :

maj_{i} τ = ∑{r − a_{i−1} : r ∈ Ligne_{i} τ},  (i = 1, 2) ;
comaj_{3} τ = ∑{r − a_{2} : r ∈ Coligne_{3} τ};
imaj_{1} τ = ∑{r − a_{0} : r ∈ Iligne_{1} τ};
icomaj_{2} τ = ∑{r − a_{1} : r ∈ Icoligne_{2} τ}.

Formons ensuite le monôme

h(τ) = p_{1}^{maj_{1} τ} p_{2}^{maj_{2} τ} p_{3}^{comaj_{3} τ} q_{1}^{imaj_{1} τ} q_{2}^{icomaj_{2} τ}

puis, pour tout couple (a, b), notons P (a, b) le polynôme P (a, b) = ∑ h(τ), où la sommation est étendue à toutes les permutations (3, 2)- colorée τ = (σ, c, d) telles que c = a et d = b.

On peut alors montrer (cf. [Fo2]) que la fonction génératrice des polynômes P (a, b) est donnée par :

∑_{n} u^{n} ∑_{a,b} \frac{A_{1}^{a_{1}}A_{2}^{a_{2}}A_{3}^{a_{3}}B_{1}^{b_{1}}B_{2}^{b_{2}}}{(p_{1}; p_{1})_{a_{1}}(p_{2}; p_{2})_{a_{2}}(p_{3}; p_{3})_{a_{3}}(q_{1}; q_{1})_{b_{1}}(q_{2}; q_{2})_{b_{2}}} P (a, b)

= \frac{(−uA_{1}B_{2}; p_{1}, q_{2})_{∞,∞}(−uA_{2}B_{2}; p_{2}, q_{2})_{∞,∞}(−uA_{3}B_{1}; p_{3}, q_{1})_{∞,∞}}{(uA_{1}B_{1}; p_{1}, q_{1})_{∞,∞}(uA_{2}B_{1}; p_{2}, q_{1})_{∞,∞}(uA_{3}B_{2}; p_{3}, q_{2})_{∞,∞}},

où la seconde sommation est étendue à toutes les partitions ordonnées a = (a_{1}, a_{2}, a_{3}) et b = (b_{1}, b_{2}) satisfaisant a_{1} + a_{2} + a_{3} = b_{1} + b_{2} = n.

Il existe toute une famille de ces identités que l’on obtient à partir du théorème combinatoire précédent et de l’algèbre des fonctions de Schur. Notons qu’une formule comme la précédente apparaît comme une formule de transformation d’un rapport de produits infinis, où les bases interviennent par paires, en une somme où le dénominateur de normalisation ne contient que des factorielles montantes à une seule base.

Une telle identité se spécialise évidemment en l’identité q-binomiale :

∑_{n}(z; q)_{n} \frac{u^{n}}{(q; q)_{n}} = \frac{(zu; q)_{∞}}{(u; q)_{∞}} ·

Posons, en effet, A_{1} = B_{1} = 1, A_{2} = B_{2} = 0, A_{3} = −z, p_{1} = p_{2} = p_{3} = q_{2} = 0 et q_{1} = q. On obtient :

∑_{n} u^{n} ∑_{a,b} \frac{(−z)^{a_{3}}}{(q; q)_{b_{1}}} P (a, b) = \frac{(uz; q)_{∞}}{(u; q)_{∞}} ·

Les seules paires a, b qui apportent une contribution non nulle à la seconde sommation se réduisent aux partitions a_{1} + a_{3} = n et b_{1} = n. Par ailleurs, P (a, b) est une sommation sur les seules permutations (3, 2)- colorées τ = (σ, a, b) telles que maj_{1} τ = comaj_{3} τ = 0. De là, σ est de la forme

(5.1)  σ = r_{1} < r_{2} < ⋯ < r_{a_{1}} ; s_{1} > s_{2} > ⋯ > s_{a_{3}}.

Enfin, le monôme h(τ) se réduit à q^{imaj_{1} τ}. On a donc

∑_{a,b} z^{a_{3}}P (a, b) = ∑(−z)^{a_{3}}q^{imaj_{1} τ} ,

où la dernière sommation est sur les seules permutations τ = (σ, a, b) avec σ de la forme (5.1). Il est immédiat de voir, par exemple par récurrence sur n, que la précédente somme vaut (−z; q)_{n}. On retrouve donc bien la formule q-binomiale.

BIBLIOGRAPHIE

[Bereg] BERELE (A.) and REGEV (A.). — Hook Young diagrams with applications to combinatorics and to representations of Lie superalgebras, Adv. in Math., à paraître.

[Berem] BERELE (A.) and REMMEL (J.B.). — Hook flag characters and their combinatorics, J. Pure and Appl. Algebra, t. 35, 1985, p. 22-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.

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

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

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

[Fo2] FOATA (Dominique). — Fonctions symétriques et séries hypergéomé-

triques basiques multivariées, IV, Preprint, Univ. Strasbourg, 1987.

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

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

[Gage] GARSIA (Adriano M.) and GESSEL (Ira). — Permutation Statistics

and Partitions, 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.

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

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

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

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

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