CALCUL BASIQUE DES PERMUTATIONS SIGNÉES, II:

ANALOGUES FINIS DES FONCTIONS DE BESSEL (^{∗})

Dominique FOATA^{1} et GuoNiu HAN^{2}

To Herb Wilf, for his many-faceted accomplishments in Mathematics, his successful guidance of doctoral students, his scientific editorship, and last but not least, his masterly contribution to Electronic Publishing.

Abstract: The traditional basic calculus on permutation statistic distributions is extended to the case of signed permutations. This provides with a combinatorial interpretation of the basic Bessel functions and their finite analogues.

Résumé: Le calcul basique classique sur les distributions des statistiques des permutations est prolongé au cas des permutations signées. Ce calcul permet ainsi de donner une interprétation combinatoire aux fonctions basiques de Bessel et à leurs analogues finis.

Sommaire

1. Introduction

2. Les fonctions de Bessel à plusieurs bases

3. Une image homomorphe de multi-mots signés

4. Un calcul à la Fedou-Rawlings

5. Les multipermutations signées

6. Une première bijection

7. La seconde bijection

8. Le calcul de la première fonction génératrice

9. Fonction génératrice de toutes les multi-permutations signées

10. L’interprétation en termes de nombre d’inversions Bibliographie Tableau des spécialisations des distributions

(^{∗}) Avec le concours du programme des Communautés Européennes en Combinatoire Algébrique, 1994-96. 1 Département de mathématique, Université Louis Pasteur, 7, rue René-Descartes,

F-67084 Strasbourg, France. (foata@math.u-strasbg.fr)

2 I.R.M.A., Université Louis Pasteur, 7, rue René-Descartes, F-67084 Strasbourg,

France. (guoniu@math.u-strasbg.fr)

1. Introduction

Dans notre premier article sur le calcul basique des permutations signées [FoHa96], nous avons fait une étude combinatoire du développement en série en bases Q et q de la fraction

(1.1) \frac{(1 − t) J((1 − t)X; Q, q)}{−t + J((1 − t)X; Q, q) J((1 − t)Y; Q, q)}

= ∑_{n≥0} \frac{1}{(Q; Q)_{n}(q; q)_{n}} W_{n}(X, Y, t, Q, q).

Dans cette formule, nous utilisons les notations usuelles [An76, GaRa90] sur les q-factorielles montantes

\begin{aligned}(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}) ; \end{aligned}

puis, étant donnés deux entiers positifs L et l et étant données les suites de variables Q = (Q_{1}, Q_{2}, …, Q_{L}), q = (q_{1}, q_{2}, …, q_{l}), nous posons

Q^{\binom{n}{2}} = Q\binom{n}{2}_{1} … Q\binom{n}{2}_{L},
(Q; Q)_{n} = (Q_{1}; Q_{1})_{n} … (Q_{L}; Q_{L})_{n},
(q; q)_{n} = (q_{1}, q_{1})_{n} … (q_{l}; q_{l})_{n}.

La fonction de Bessel basique est alors définie par

(1.2)  J(u; Q, q) = ∑_{n≥0}(−1)^{n} \frac{Q^{\binom{n}{2}}}{(Q, Q)_{n}} \frac{1}{(q; q)_{n}} u^{n}.

Le but principal de notre premier article était de montrer que le coefficient W_{n}(X, Y, t, Q, q) était le polynôme générateur d’objets combinatoires, à savoir les multipermutations signées (\underline{Σ}, \underline{σ}, ε) par une suite de statistiques notée

(1.3)  (ddes, inv, coinv)

adaptée aux permutations signées, prolongeant, de façon naturelle, les résultats classiques sur les permutations ordinaires. Nous avons regroupé, dans le paragraphe 5, les définitions de ces statistiques.

Le but de ce second article est d’abord de faire une étude combinatoire systématique de ce que nous appelons les analogues finis des fonctions de Bessel basiques J_{k}^{K}(u; Q, q). Leur définition est donnée dans le paragraphe 2; il faut noter qu’en plus des suites de bases Q et q, ces fonctions dépendent de deux suites de paramètres K et k. Celles-ci ont déjà été introduites dans l’article de Fedou et Rawlings [FeRa94] Pour ne pas alourdir les notations dans cette introduction, nous supposons d’abord que Q, q, P, p sont de simples bases Q, q, P, p, d’autre part, que les paramètres venant en exposant et en indice dans ces fonctions de Bessel sont des entiers positifs: K, k, M, m. Le second but du présent article est d’étudier l’extension du développement (1.1) sous la forme:

(1.4) ∑_{K,M,k,m} R^{K}S^{M}r^{k}s^{m} \frac{(1 − t) J_{k}^{K}((1 − t)X; P, p)}{−t + J_{k}^{K}((1 − t)X; P, p) J_{m}^{M}((1 − t)Y; Q, q)}

= ∑_{α≥0, β≥0} \frac{1}{(R; P)_{α+1}} \frac{1}{(S; Q)_{β+1}} \frac{1}{(r; p)_{α+1}} \frac{1}{(s; q)_{β+1}} X^{α}Y^{β}W_{α,β}.

Nous montrerons (Théorème 8.1) que le coefficient W_{α,β} est le polynôme générateur des multipermutations signées d’ordre (α, β) (α+β = n), dites compatibles, par une suite de statistiques

(1.5) (ddes, ides_{x}, ides_{y}, imaj_{x}, imaj_{y}, icodes_{x}, icodes_{y}, icomaj_{x}, icomaj_{y}).

Le troisième but de l’article sera de montrer que l’identité (1.4) se spécialise en (1.1) en donnant une nouvelle interprétation combinatoire au polynôme W_{n}(X, Y, t, Q, q), qui apparaîtra alors comme la fonction génératrice des multipermutations signées par une autre suite de statistiques que la suite (1.3), à savoir

(1.6)  (ddes, imaj, icomaj),

où “imaj” et “icomaj” sont des statistiques sur les permutations signées, se réduisant aux statistiques du même nom connues pour les permutations ordinaires.

Pour retrouver le résultat de notre article précédent et donc montrer que le polynôme W_{n}(X, Y, t, Q, q) est la fonction génératrice de ces multipermutations signées par la suite (1.3) au lieu de la suite (1.6), nous construirons une bijection de l’ensemble des multipermutations signées d’ordre n sur lui-même, qui enverra le vecteur (1.3) sur le vecteur (1.6).

L’organisation de l’article est la suivante. Le prochain paragraphe est consacré à l’étude des fonctions de Bessel. On y introduit notamment les analogues finis e_{q}^{k}(u) et E_{Q}^{K}(u) des fonctions q-exponentielles et Qexponentielles. En prenant le produit d’Hadamard de telles fonctions, on peut définir les analogues finis des fonctions de Bessel à plusieurs bases, en toute généralité.

Dans les paragraphes 3 et 4, nous montrons que la fraction apparaissant dans le membre de gauche de (1.4) est l’image homomorphe de la fonction génératrice de tous les multi-mots signés par une certaine statistique appelée “rise.” Le paragraphe 5 est consacré à la description de toutes les statistiques utilisées. Nous donnons ensuite dans les paragraphes 6 et 7, les correspondances entre mots signés et permutations signées, permettant dans le paragraphe 8 de calculer la fonction génératrice des multipermutations signées par la statistique (1.5) dont les composantes auront été précisées. Nous terminons l’article par un paragraphe 9, qui fait apparaître des spécialisations utiles et par un paragraphe 10 qui donne une nouvelle démonstration du résultat principal de notre premier article.

Pour la commodité du lecteur, nous avons construit une table de plusieurs spécialisations du Théorème 8.1, qui nous semblent les plus intéressantes. Cette table est accessible sur le réseau WWW [FoHa96a]. On y retrouve, notamment, les résultats antérieurs dûs à Carlitz, Stanley, Fedou et Rawlings…

2. Les fonctions de Bessel à plusieurs bases

D’abord rappelons (voir, e.g., [An76, GaRa90]) le célèbre théorème q-binomial

∑_{n≥0}(a; q)_{n} \frac{u^{n}}{(q; q)_{n}} = \frac{(au; q)_{∞}}{(u; q)_{∞}} ;

ainsi que les développements des deux q-exponentielles

e(u) = e_{q}(u) = ∑_{n≥0} \frac{u^{n}}{(q; q)_{n}} = \frac{1}{(u; q)_{∞}} ;

E(u) = E_{Q}(u) = ∑_{n≥0} \frac{Q^{\binom{n}{2}}u^{n}}{(Q; Q)_{n}} = (−u; Q)_{∞};

enfin, la notation pour le coefficient q-binomial

\left[{n \atop k}\right]_{q} = \frac{(q; q)_{n}}{(q; q)_{k} (q; q)_{n−k}} .

Les q-factorielles montantes et les coefficients q-binomiaux s’interprètent en termes de comptage de mot croissants. Les formules suivantes sont classiques et sont des conséquences faciles du théorème q-binomial. Les symboles b et B ci-dessous représentent des suites croissantes b_{1} ≤ b_{2} ≤ ⋯ ≤ b_{n} et strictement croissantes B_{1} < B_{2} < ⋯ < B_{n} d’entiers positifs, respectivement. On pose ∥b∥ = b_{1}+b_{2}+⋯+b_{n} et ∥B∥ = B_{1}+B_{2}+⋯+B_{n}. Dans la mesure du possible, les lettres minuscules se rapportent aux suites croissantes (au sens large), les lettres majuscules aux suites strictement croissantes. Les formules suivantes

(2.1)  \left[{n + k \atop n}\right]_{q} = ∑_{0≤b_{1}≤···≤b_{n}<k+1} q^{∥b∥},

(2.2)  Q^{\binom{n}{2}}\left[{K + 1 \atop n}\right]_{Q} = ∑_{0≤B_{1}<···<B_{n}<K+1} Q^{∥B∥},

sont vraies pour tout entier k ≥ 0 et tout entier K ≥ 0. Comme on a

(2.3)  \frac{1}{(q; q)_{n}} = ∑_{0≤b_{1}≤···≤b_{n}} q^{∥b∥},

(2.4)  \frac{Q^{\binom{n}{2}}}{(Q; Q)_{n}} = ∑_{0≤B_{1}<···<B_{n}} Q^{∥B∥},

on posera

(2.5)  \left[{n + ∞ \atop n}\right]_{q} = \frac{1}{(q; q)_{n}} ,

(2.6)  Q^{\binom{n}{2}}\left[{∞ + 1 \atop n}\right]_{Q} = \frac{Q^{\binom{n}{2}}}{(Q; Q)_{n}} ,

de sorte que (2.1) et (2.2) sont vraies pour k et K finis ou non.

Notons e_{q}^{k}(u) et E_{Q}^{K}(u) les fonctions génératrices ordinaires de (2.1) et (2.2), soit

(2.7)  e_{q}^{k}(u) = ∑_{n≥0} \left[{n + k \atop n}\right]_{q}u^{n}, encore égal à \frac{1}{(u; q)_{k+1}} ,

(2.8)  E_{Q}^{K}(u) = ∑_{n≥0} Q^{\binom{n}{2}}\left[{K + 1 \atop n}\right]_{Q}u^{n}.

On retrouve, en particulier, les deux q-exponentielles

e_{q}(u) = e_{q}^{∞}(u) = ∑_{n≥0} \frac{1}{(q; q)_{n}} u^{n},

E_{Q}(u) = E_{Q}^{∞}(u) = ∑_{n≥0} \frac{Q^{\binom{n}{2}}}{(Q; Q)_{n}} u^{n}.

Notons tout de suite, qu’à cause de (2.1) et (2.2), les fonctions e_{q}^{k}(u) et E_{Q}^{K}(u) s’expriment comme des fonctions génératrices de suites croissantes et de suites croissantes au sens strict.

Pour définir les fonctions de Bessel à plusieurs bases et en toute généralité, convenons des notations suivantes: L, l sont des entiers positifs; les Q_{i}, q_{i}, P_{i}, p_{i} des bases quelconques (des variables); K_{i}, k_{i}, M_{i}, m_{i} des entiers positifs. L’indice i varie de 1 à L (resp. de 1 à l) lorsqu’il se réfère à des lettres majuscules (resp. minuscules). On utilisera aussi les notations vectorielles

\begin{aligned}Q & = (Q_{1}, Q_{2}, …, Q_{L}), \\ P & = (P_{1}, P_{2}, …, P_{L}), \\ K & = (K_{1}, K_{2}, …, K_{L}), \\ M & = (M_{1}, M_{2}, …, M_{L}), \end{aligned}  \begin{aligned}q & = (q_{1}, q_{2}, …, q_{l}), \\ p & = (p_{1}, p_{2}, …, p_{l}), \\ k & = (k_{1}, k_{2}, …, k_{l}), \\ m & = (m_{1}, m_{2}, …, m_{l}), \end{aligned}

écrivant seulement Q, q, P, p, K, k, M et m, lorsque L = l = 1.

Utilisant la notation “H” pour le produit d’Hadamard de deux séries, à savoir

(∑_{n≥0} α_{n}u^{n}) H(∑_{n≥0} β_{n}u^{n}) = ∑_{n≥0}(α_{n}β_{n})u^{n},

on définit la fonction de Bessel à plusieurs bases par

(2.9) J_{k}^{K}(u; Q, q) = (∑_{n≥0}(−u)^{n}) H E_{Q_{1}}^{K_{1}}(u) H E_{Q_{2}}^{K_{2}}(u) H ⋯

H e_{q_{1}}^{k_{1}}(u) H e_{q_{2}}^{k_{2}}(u) H ⋯

On peut imaginer d’autres récritures pour cette fonction de Bessel, si, en plus des notations vectorielles apparaissant dans l’introduction, on utilise aussi les notations suivantes:

\left[{n + k \atop n}\right]_{q} = \left[{n + k_{1} \atop n}\right]_{q_{1}} \left[{n + k_{2} \atop n}\right]_{q_{2}} ⋯
\left[{K + 1 \atop n}\right]_{Q} = \left[{K_{1} + 1 \atop n}\right]_{Q_{1}} \left[{K_{2} + 1 \atop n}\right]_{Q_{2}} ⋯

On a, en effet,

(2.10) J_{k}^{K}(u; Q, q) = ∑_{n≥0}(−1)^{n}Q^{\binom{n}{2}}\left[{K + 1 \atop n}\right]_{Q} \left[{n + k \atop n}\right]_{q}u^{n}.

La fonction de Bessel dont tous les paramètres sont infinis vaut

J(u; Q, q) = J_{∞}^{∞}(u; Q, q) = ∑_{n≥0}(−1)^{n} \frac{Q^{\binom{n}{2}}}{(Q, Q)_{n}} \frac{1}{(q; q)_{n}} u^{n},

et, si L = l = 1,

J(u; Q, q) = J_{∞}^{∞}(u; Q, q) = ∑_{n≥0}(−1)^{n} \frac{Q^{\binom{n}{2}}}{(Q, Q)_{n}} \frac{1}{(q; q)_{n}} u^{n}.

Cette fonction de Bessel à plusieurs bases ayant été définie, en (2.9) ou en (2.10), nous nous proposons de développer en série la fraction apparaissant dans le membre de gauche de (1.4), récrite avec les paramètres K, k, M, m, p, q, à savoir

(2.11) F = F \binom{K,M}{k,m} = \frac{(1 − t) J_{k}^{K}((1 − t)X; P, p)}{−t + J_{k}^{K}((1 − t)X; P, p) J_{m}^{M}((1 − t)Y; Q, q)}

et de la faire apparaître comme fonction génératrice, d’abord sur des multimots signés, ensuite sur des multipermutations signées. Il faut remarquer que la fraction rationnelle ci-dessus fait intervenir deux fonctions de Bessel, à savoir J_{k}^{K}(u; P, p) et J_{m}^{M}(u; Q, q). Notons encore plusieurs cas particuliers.

Si L = l = 1, alors

F = F \binom{K,M}{k,m} = \frac{(1 − t) J_{k}^{K}((1 − t)X; P, p)}{−t + J_{k}^{K}((1 − t)X; P, p) J_{m}^{M}((1 − t)Y; Q, q)};

si, de plus, K, k, M et m sont infinis,

F = F \binom{∞,∞}{∞,∞} = \frac{(1 − t) J((1 − t)X; P, p)}{−t + J((1 − t)X; P, p) J((1 − t)Y; Q, q)}.

3. Une image homomorphe de multimots signés

Reprenons les notations du paragraphe précédent pour L, l, Q, P, K, M, q, p, k, m. En particulier, les entiers positifs L et l sont fixés une fois pour toutes et supposés non tous les deux nuls. Un multimot est défini comme une suite w = (B_{1}, …, B_{L}, b_{1}, …, b_{l}), où les B_{i} (1 ≤ i ≤ L) et les b_{i} (1 ≤ i ≤ l) sont des mots de même longueur. Cette longueur commune est la longueur ℓ(w) du multimot. Un multimot signé est un couple (w, ε), où w est un multimot et où ε est un mot-xy, c’est-à-dire un mot en les lettres x et y, tous deux de même longueur. Tout multimot signé (w, ε) peut être visualisé comme une matrice (L + l + 1) × n (ℓ(w) = n)

(w, ε) = w^{(1)} … w^{(i)} … w^{(n)}
B_{1} B_{1}(1) … B_{1}(i) … B_{1}(n)
⋮  ⋮  ⋮  ⋮
B_{L} B_{L}(1) … B_{L}(i) … B_{L}(n)
b_{1}  b_{1}(1) … b_{1}(i) … b_{1}(n)
⋮  ⋮  ⋮  ⋮
b_{l}  b_{l}(1) … b_{l}(i) … b_{l}(n)
ε  ε(1) … ε(i) … ε(n)

Fig. 1

où les mots B_{1}, …, B_{L}, b_{1}, …, b_{l}, ε forment les (L + l + 1) lignes de la matrice. Si on note w^{(1)}, w^{(2)}, …, w^{(n)} les colonnes de cette matrice, le mot signé (w, ε) peut encore être vu comme le mot w^{(1)}w^{(2)} … w^{(n)}, où chaque lettre est un vecteur-colonne à (L + l + 1) composantes.

On note MMS l’ensemble de tous les multimots signés. Maintenant, si K, M, k, m sont quatre suites fixées d’entiers (cf. § 2), on note MMS\binom{K,M}{k,m} le sous-ensemble des multimots signés (w, ε) = (B_{1}, …, B_{L}, b_{1}, …, b_{l}, ε) dont les coefficients entiers sont ainsi majorés:

(3.1) lorsque ε(i) = x, alors \begin{matrix}B_{1}(i) ≤ K_{1}, …, B_{L}(i) ≤ K_{L}; \\ b_{1}(i) ≤ k_{1}, …, b_{l}(i) ≤ k_{l}; \end{matrix}

(3.2) lorsque ε(i) = y, alors \begin{matrix}B_{1}(i) ≤ M_{1}, …, B_{L}(i) ≤ M_{L}; \\ b_{1}(i) ≤ m_{1}, …, b_{l}(i) ≤ m_{l}. \end{matrix}

Lorsque ε ne contient que des lettres égales à x (resp. à y), on dit que le multimot signé (w, ε) = (B_{1}, …, B_{L}, b_{1}, …, b_{l}, ε) est croissant, si les mots B_{1}, …, B_{L} sont strictement croissants et les mots b_{1}, …, b_{l} sont croissants au sens large. On note MMSC_{x^{∗}} (resp. MMSC_{y^{∗}}) l’ensemble des multimots signés croissants (w, ε) tels que ε ne contient que des lettres égales à x (resp. à y). Enfin, MMSC_{x^{∗}y^{∗}} désigne l’ensemble des produits de juxtaposition (w, ε)(w′, ε′), où (w, ε) ∈ MMSC_{x^{∗}} et (w′, ε′) ∈ MMSC_{y^{∗}}.

De même, la suite (K, M, k, m) étant donnée, on désigne par MMSC_{x^{∗}} \binom{K}{k} (resp. MMSC_{y^{∗}} \binom{M}{m}) le sous-ensemble de MMSC_{x^{∗}} (resp. de MMSC_{y^{∗}}) des multimots signés (w, ε) satisfaisant (3.1) (resp. satisfaisant (3.2)). Enfin, on pose MMSC_{x^{∗}y^{∗}} \binom{K,M}{k,m} = MMSC_{x^{∗}y^{∗}} ∩ MMS\binom{K,M}{k,m}.

Soient b = b(1)b(2) … b(n) un mot dont les lettres b(i) sont des entiers positifs et ε = ε(1)ε(2) … ε(n) un mot-xy de même longueur n. On note b_{ε|x} (resp. b_{ε|y}) le sous-mot de b restreint aux seules lettres b(i) dont la lettre correspondante ε(i) est égale à x (resp. à y). Deux bases p et q étant données, on pose

(3.3)  φ(b, ε; p, q) = p^{∥b_{ε|x}∥} q^{∥b_{ε|y}∥}.

Maintenant la suite de bases (Q, P, q, p) étant donnée (cf. § 2) et utilisant toujours les notations ci-dessus, on peut associer à tout multimot signé (w, ε) le monôme défini par

(3.4) Φ(w, ε) = Φ(w, ε, P, Q, p, q) = φ(B_{1}, ε; P_{1}, Q_{1}) … φ(B_{L}, ε; P_{L}, Q_{L}) ×φ(b_{1}, ε; p_{1}, q_{1}) … φ(b_{l}, ε; p_{l}, q_{l})X^{ℓ(ε|x)}Y^{ℓ(ε|y)}.

D’après (2.1), (2.2) et (2.10), on voit alors que la fonction de Bessel J_{k}^{K}(X; P, p) s’exprime comme une image homomorphe de multimots signés, à savoir:

J_{k}^{K}(X; P, p) = ∑_{(w,ε)}(−1)^{ℓ(w)}Φ(w, ε) ((w, ε) ∈ MMSC_{x^{∗}} \binom{K}{k}).

La prochaine étape est de faire entrer cette expression dans la fraction rationnelle F de (2.11). D’abord,

J_{k}^{K}((1 − t)X; P, p) = ∑_{(w,ε)}(t − 1)^{ℓ(w)}Φ(w, ε) ((w, ε) ∈ MMSC_{x^{∗}} \binom{K}{k});

J_{m}^{M}((1 − t)Y; Q, q) = ∑_{(w,ε)}(t − 1)^{ℓ(w)}Φ(w, ε) ((w, ε) ∈ MMSC_{y^{∗}} \binom{M}{m}).

Pour simplifier les notations notons ces deux fonctions de Bessel, respectivement, J(X) et J(Y). Leur produit est égal à

J(X) J(Y) = ∑_{(w,ε)}(t − 1)^{ℓ(w)}Φ(w, ε) ((w, ε) ∈ MMSC_{x^{∗}y^{∗}} \binom{K,M}{k,m}).

De là, notant “e” le multimot signé de longueur 0,

\frac{1 − t}{−t + J(X) J(Y)} = \frac{1 − t}{−t + ∑_{(w,ε)}(t − 1)^{ℓ(w)} Φ(w, ε)}

= (1 − ∑_{(w,ε)≠e}(t − 1)^{ℓ(w)−1} Φ(w, ε))^{−1}.

Ainsi F \binom{K,M}{k,m} = Φ(G\binom{K,M}{k,m}), où

(3.5) G\binom{K,M}{k,m} = (1− ∑_{(w,ε)}(t−1)^{ℓ(w)−1} (w, ε))^{−1}( ∑_{(w′,ε′)}(t−1)^{ℓ(w′)}(w′, ε′)),

et

(w, ε) ∈ MMSC_{x^{∗}y^{∗}} \binom{K,M}{k,m} \ \{e\} et (w′, ε′) ∈ MMSC_{x^{∗}} \binom{K}{k}.

4. Un calcul à la Fedou-Rawlings

Cette étape consiste à exprimer G comme une fonction génératrice de tous les multimots signés par la statistique suivante appelée “rise.” Soient B = B(1) … B(n), b = b(1) … b(n), deux mots, ε = ε(1) … ε(n) un motxy et i un entier compris entre 1 et n (bornes incluses). On dit que i est une ε-montée stricte de B, si l’une des conditions est satisfaite:

(i) i = n et ε(n) = x; (ii) 1 ≤ i ≤ n − 1, ε(i) = x, ε(i + 1) = y; (iii) 1 ≤ i ≤ n − 1, ε(i) = ε(i + 1) et B(i) < B(i + 1);

Si (i) ou (ii) est satisfaite, ou si la condition (iii′), à savoir 1 ≤ i ≤ n−1, ε(i) = ε(i + 1) et b(i) ≤ b(i + 1), est réalisée, on dit que i est une ε-montée de b.

Remarque. Il est important de noter que les ε-montées strictes (resp. les ε-montées) sont de deux natures: il y a celles qui ne dépendent que du mot-xy (conditions (i) et (ii) et dans ce cas on reprend les mêmes conventions que pour les descentes des permutations signées données dans la Définition 1) et celles qui prennent en charge les montées strictes (resp. les montées) classiques B(i) < B(i + 1) (resp. b(i) ≤ b(i + 1)), pourvu que l’on ait ε(i) = ε(i + 1).

Si (w, ε) un multimot signé tel que w = (B_{1}, …, B_{L}, b_{1}, …, b_{l}), la statistique rise(w, ε) est définie comme le nombre d’indices i tels que i est une ε-montée stricte commune à B_{1}, …, B_{L} et une ε-montée commune à b_{1}, …, b_{l}. Autrement dit, rise(w, ε) est égal au nombre d’indices i tels que l’une des trois conditions est réalisée: (i), (ii) (comme ci-dessus) ou

(iii′′) 1 ≤ i ≤ n − 1, ε(i) = ε(i + 1) et B_{j}(i) < B_{j}(i + 1) pour tout j = 1, …, L et b_{j}(i) ≤ b_{j}(i + 1) pour tout j = 1, …, l.

Proposition 4.1. On a l’identité

(4.1) G = ∑_{(w,ε)} t^{rise(w,ε)} (w, ε)

et par conséquent [cf. (2.11)]

(4.2) F \binom{K,M}{k,m} = ∑_{(w,ε)} t^{rise(w,ε)} Φ(w, ε),

où (w, ε) varie dans l’ensemble des multimots signés MMS\binom{K,M}{k,m} et où Φ est l’homomorphisme défini en (3.4).

Pour établir (4.1), nous reprenons ici une formule d’inversion classique, imaginée par plusieurs auteurs dans des contextes plus ou moins différents (voir Goulden et Jackson [GoJa83, p. 131], Stanley [St86, p. 266], Viennot [Vi86], Hutchinson et Wilf [HuWi75], [Fo79]), bien explicitée par Fedou et Rawlings [FeRa94, FeRa95] et que ces derniers auteurs ont exprimé ainsi. Formons l’algèbre large du monoïde libre X^{∗} engendré par un certain ensemble X sur un anneau de polynômes Ω. Donnons-nous une application a : X^{2} → Ω, qu’on prolonge en une application a : X^{∗} → Ω en posant pour w = x_{1}x_{2} … x_{n} ∈ X^{∗}:

a(w) = \{ \begin{matrix}a(x_{1}, x_{2}) … a(x_{n−1}, x_{n}), & si n ≥ 2; \\ 1, & si n = 0 ou 1; \end{matrix}

et définissons ensuite:

\overline{a}(w) = \{ \begin{matrix}(a(x_{1}, x_{2}) − 1) … (a(x_{n−1}, x_{n}) − 1), & si n ≥ 2; \\ 1, & si n = 0 ou 1. \end{matrix}

Soient encore U et V deux sous-ensembles non-vides de l’alphabet X. Les expressions U^{+} et U^{∗}V désignent les ensembles des mots non vides w = x_{1}x_{2} … x_{n} dont, respectivement, toutes les lettres sont dans U, la dernière lettre x_{n} est dans V.

La formule d’inversion, dont la démonstration est tout à fait banale (il suffit de multiplier à gauche chaque membre par (1 − ∑_{w∈U^{+}} \overline{a}(w) w) et

de vérifier que les coefficients de chaque mot w sont les mêmes dans les deux membres), est la suivante:

(4.3)  ∑_{w∈U^{∗}V} a(w) w = (1 − ∑_{w∈U^{+}} \overline{a}(w) w)^{−1} × ∑_{w∈U^{∗}V} \overline{a}(w) w.

Pour utiliser ici cette formule, il faut considérer tout multimot signé comme un mot w^{(1)}w^{(2)} … w^{(n)} dont les lettres sont des vecteurs de (L + l + 1) composantes (cf. Fig. 1). Notons Y Y l’alphabet dont les lettres sont des vecteurs dont les (L + l) premières composantes sont des entiers et la (L + l) plus unième composante est égale à x ou y

Dans la formule (4.3) prenons les ingrédients suivants: d’abord X = Y Y∪\{\underline{∞}\}, où “\underline{∞}” est un vecteur de longueur (L+l+1) dont toutes les composantes sont égales à ∞, de sorte que les multimots signés sont les mots du monoïde libre Y Y^{∗}. Soient w^{(i)} = (B_{1}(i), …, B_{L}(i), b_{1}(i), …, b_{l}(i), ε(i)) et w^{(i+1)} = (B_{1}(i + 1), …, B_{L}(i + 1), b_{1}(i + 1), …, b_{l}(i + 1), ε(i + 1)) deux lettres de X. Suivant notre convention, ou bien toutes les composantes de w^{(i)} (resp. w^{(i+1)}) sont égales à ∞, ou bien ε(i) (resp. ε(i + 1)) est égal à x ou y.

Pour “a” prenons l’application:

a(w^{(i)}, w^{(i+1)}) = \{ \begin{matrix}t, & si ε(i) = x et ε(i + 1) = ∞, \\ t, & si ε(i) = x et ε(i + 1) = y, \\ t, & si ε(i) = ε(i + 1) et B_{j}(i) < B_{j}(i + 1) \\ & pour tout j = 1, …, L et \\ & b_{j}(i) ≤ b_{j}(i + 1) pour tout j = 1, …, l, \\ 1, & sinon. \end{matrix}

Pour V prenons le singleton \{\underline{∞}\} et pour U l’ensemble Y Y. La formule (4.3) se récrit, après simplification à droite par \underline{∞},

(4.4) ∑_{(w,ε)∈MMS}a((w, ε) \underline{∞}) (w, ε)

= (1 − ∑_{(w,ε)∈MMS\\{e\}} \overline{a}((w, ε)) (w, ε))^{−1} × ∑_{(w,ε)∈MMS} \overline{a}((w, ε) \underline{∞}) (w, ε).

Soit w = w^{(1)}w^{(2)} … w^{(n)} un multimot signé, de longueur n, écrit en les lettres de l’alphabet Y Y. Posons w^{(n+1)} = \underline{∞}. On voit alors que la statistique rise(w, ε) définie au début de cette section s’exprime encore comme:

(4.5)  rise(w, ε) = ∑_{1≤i≤n} χ(a(w^{(i)} w^{(i+1)}) = t).

Pour tout multimot signé (w, ε), on a alors:

a((w, ε) \underline{∞}) = t^{rise(w,ε)},
\overline{a}(w, ε) = \{ \begin{matrix}(t − 1)^{ℓ(w)−1}, & si (w, ε) ∈ MMSC_{x^{∗}y^{∗}} et ℓ(w) ≥ 2; \\ 1, & si ℓ(w) = 0 ou 1; \\ 0, & sinon; \end{matrix}

\overline{a}((w, ε) \underline{∞}) = \{ \begin{matrix}(t − 1)^{ℓ(w)}, & si (w, ε) ∈ MMSC_{x^{∗}} et ℓ(w) ≥ 1; \\ 1, & si ℓ(w) = 0; \\ 0, & sinon. \end{matrix}

L’identité (4.4) prend alors la forme:

(4.6) ∑_{(w,ε)∈MMS} t^{rise(w,ε)} (w, ε)

= (1− ∑_{(w,ε)∈MMSC_{x^{∗}y^{∗}} \{e}}(t−1)^{ℓ(w)−1} (w, ε))^{−1}× ∑_{(w,ε)∈MMSC_{x^{∗}}} (t−1)^{ℓ(w)} (w, ε).

L’identité (4.6) reste encore valable, si l’on remplace MMS par MMS\binom{K,M}{k,m}, MMSC_{x^{∗}y^{∗}} par MMSC_{x^{∗}y^{∗}} \binom{K,M}{k,m} et MMSC_{x^{∗}} par MMSC_{x^{∗}} \binom{K}{k}. On retrouve l’expression de G donnée en (3.5). La Proposition 4.1 est donc démontrée.

Sans ériger le principe en méthode, on peut dire que toute expression analytique comme celle de F (cf. (2.11)) est susceptible de recevoir une interprétation combinatoire en termes de mots (voir [Ehr93]), ici de multimots signés. Cette interprétation est plus ou moins difficile à obtenir, mais ne fait intervenir que des objets rudimentaires dont la géométrie reste pauvre. Pour obtenir des résultats sur des objets combinatoires dont la géométrie est riche, comme des permutations, ici des multipermutations signées, il faut recourir à une nouvelle construction envoyant les multimots sur les multipermutations. La construction décrite ici est empruntée au “MacMahon Verfahren” [Mac13, Fo95]. Elle fait l’objet des paragraphes suivants.

5. Multipermutations signées

On définit une permutation signée d’ordre n comme un couple (σ, ε), où σ est une permutation σ = σ(1)σ(2) … σ(n) du mot 12 … n et ε = ε(1)ε(2) … ε(n) est un mot de longueur n en l’alphabet à deux lettres {x, y}. On dit que ε est un mot-xy; on note ℓ(ε|x) (resp. ℓ(ε|y)) le nombre de lettres égales à x (resp. égales à y) dans ε. On note également σ_{ε|x} (resp. σ_{ε|y}) le sous-mot de σ formé par toutes les lettres σ(i) telles que ε(i) = x (resp. ε(i) = y).

On appelle multipermutation signée, d’ordre n, un triplet (\underline{Σ}, \underline{σ}, ε), où \underline{Σ} = (Σ_{1}, …, Σ_{L}) ∈ S_{n}^{L}, \underline{σ} = (σ_{1}, …, σ_{l}) ∈ S_{n}^{l} sont deux suites de L et l permutations d’ordre n et où ε est un mot-xy de longueur n.

Remarquons que chaque paire (Σ_{i}, ε) (i = 1, …, L) (resp. (σ_{i}, ε) (i = 1, …, l) est une permutation signée d’ordre n.

La notion de descente dans une multipermutation signée, introduite ci-après, prolonge la notion de descente commune introduite par Carlitz [Ca76] pour les couples de permutations ordinaires.

Définition. On dit que l’entier i est une descente de la multipermutation signée (\underline{Σ}, \underline{σ}, ε), si l’une des quatre conditions suivantes est remplie:

(i) i = n et ε(n) = x; (ii) 1 ≤ i ≤ n − 1, ε(i) = x, ε(i + 1) = y;

(iii) 1 ≤ i ≤ n − 1, ε(i) = ε(i + 1) et Σ_{1}(i) > Σ_{1}(i + 1), …, Σ_{L}(i) > Σ_{L}(i + 1), ainsi que σ_{1}(i) > σ_{1}(i + 1), …, σ_{l}(i) > σ_{l}(i + 1);

On note ddes(\underline{Σ}, \underline{σ}, ε) le nombre de descentes de (\underline{Σ}, \underline{σ}, ε).

Les statistiques intervenant dans (1.5) autres que “ddes” sont des statistiques sur les permutations signées (Σ_{i}, ε) (i = 1, …, L) et (σ_{i}, ε) (i = 1, …, l). Nous donnons leurs définitions ci-après.

Le nombre de descentes “des w,” l’indice majeur “maj w” et le nombre d’inversions “inv w” d’un mot w = x_{1}x_{2} … x_{m}, dont les lettres appartiennent à un ensemble totalement ordonné, sont traditionnellement définis par:

des w = ∑_{1≤i≤m−1} χ(x_{i} > x_{i+1}) ;
maj w = ∑_{1≤i≤m−1} i χ(x_{i} > x_{i+1}) ;
inv w = ∑_{1≤i<j≤m} χ(x_{i} > x_{j}).

Nous introduisons, en plus, le nombre de montées ou de co-descentes “codes,” l’indice co-majeur “comaj w” et le nombre de co-inversions “coinv w” définis par :

codes w = ∑_{1≤i≤m−1} χ(x_{i} < x_{i+1}) ;
comaj w = ∑_{1≤i≤m−1} i χ(x_{i} < x_{i+1}) ;
coinv w = ∑_{1≤i<j≤m} χ(x_{i} < x_{j}).

Considérons maintenant une permutation signée (σ, ε) d’ordre n. Rangeons par ordre croissant les lettres du mot σ_{ε|x}: j_{1} < j_{2} < ⋯ < j_{k}. Si maintenant σ^{−1} désignons la permutation inverse de σ, notons σ_{ε|x}^{−1} le mot σ^{−1}(j_{1})σ^{−1}(j_{2}) … σ^{−1}(j_{k}). On définirait de même σ_{ε|y}^{−1}.

Par exemple, avec la permutation signée (σ, ε) telle que

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

on obtient

σ_{ε|x} =(\begin{matrix}1 & 2 & 7 & 8 & 9 \\ 6 & 7 & 5 & 8 & 9 \end{matrix}) , σ_{ε|y} =(\begin{matrix}3 & 4 & 5 & 6 \\ 2 & 4 & 3 & 1 \end{matrix}) , σ_{ε|x}^{−1} =(\begin{matrix}5 & 6 & 7 & 8 & 9 \\ 7 & 1 & 2 & 8 & 9 \end{matrix}) , σ_{ε|y}^{−1} =(\begin{matrix}1 & 2 & 3 & 4 \\ 6 & 3 & 5 & 4 \end{matrix}) .

Les quatre mots σ_{ε|x}, σ_{ε|y}, σ_{ε|x}^{−1}, σ_{ε|y}^{−1} ont des nombres de descentes et des nombres de co-descentes, des indices majeurs et co-majeurs, ainsi que des nombres d’inversions et de co-inversions, bien définis. Par ailleurs, on peut introduire le nombre d’inversions “inv(σ_{ε|y}, σ_{ε|x})” entre les mots σ_{ε|y} et σ_{ε|x}, en posant

inv(σ_{ε|y}, σ_{ε|x}) = #{(i, j) : ε(i) = y, ε(j) = x, σ(i) > σ(j)}.

Ces statistiques sur des sous-mots permettent de définir les statistiques suivantes sur les permutations signées (σ, ε):

ides σ_{ε|x} = des σ_{ε|x}^{−1} ;
ides σ_{ε|y} = des σ_{ε|y}^{−1} ;
imaj σ_{ε|x} = maj σ_{ε|x}^{−1} ;
imaj σ_{ε|y} = maj σ_{ε|y}^{−1} ;

icodes σ_{ε|x} = codes σ_{ε|x}^{−1} ;
icodes σ_{ε|y} = codes σ_{ε|y}^{−1} ;
icomaj σ_{ε|x} = comaj σ_{ε|x}^{−1} ;
icomaj σ_{ε|y} = comaj σ_{ε|y}^{−1} ;

On introduit de plus

imaj(σ, ε) = imaj σ_{ε|x} + imaj σ_{ε|y} + inv(σ_{ε|y}, σ_{ε|x}) ;
icomaj(σ, ε) = icomaj σ_{ε|x} + icomaj σ_{ε|y} + inv(σ_{ε|y}, σ_{ε|x}) ;
inv(σ, ε) = inv σ_{ε|x} + inv σ_{ε|y} + inv(σ_{ε|y}, σ_{ε|x}) ;
coinv(σ, ε) = coinv σ_{ε|x} + coinv σ_{ε|y} + inv(σ_{ε|y}, σ_{ε|x}).

Définition. Supposons que ε a α lettres égales à x et β lettres égales à y (α + β = n). On dit que la permutation σ est compatible avec ε (ou encore que la permutation signée (σ, ε) est compatible), si

inv(σ_{ε|y}, σ_{ε|x}) = 0,

ou, de façon équivalente, si le sous-mot σ_{ε|y} est un réarrangement du mot 12 … β (et donc σ_{ε|x} est un réarrangement de (β + 1)(β + 2) … n).

Cette notion sera fondamentale dans les sections suivantes. On note PC(ε) l’ensemble des permutations compatibles avec ε. La permutation signée traitée dans l’exemple ci-dessus est compatible. En particulier, inv(2431, 67589) = 0. On a, de plus,

imaj(σ, ε) = maj 71289 + maj 6354 + inv(2431, 67589) = 5;
icomaj(σ, ε) = comaj 71289 + comaj 6354 + inv(2431, 67589) = 11;
inv(σ, ε) = inv 67589 + inv 2431 + inv(2431, 67589) = 6;
coinv(σ, ε) = coinv 67589 + coinv 2431 + inv(2431, 67589) = 10.

On dit que la multipermutation signée (\underline{Σ}, \underline{σ}, ε) est compatible, si toutes les pemutations signées (Σ_{i}, ε) et (σ_{i}, ε) sont elles-mêmes compatibles.

6. Une première bijection.

Notre prochain but est de montrer que la fonction génératrice

\begin{matrix}∑ \\ ( & {K,M \atop k,m} & ) \end{matrix} R^{K}S^{M}r^{k}s^{m} F \binom{K,M}{k,m},

où les F \binom{K,M}{k,m} sont eux-mêmes des fonctions génératrices de multimots signés (cf. (4.2)), peut s’exprimer comme fonction génératrice de multipermutations signées. Ce résultat repose sur un codage des mots signés par des permutations signées, codage que nous décrivons dans ce paragraphe et le suivant.

Si ε est un mot-xy fixé, notons Mot(ε; k, m) l’ensemble de tous les mots b, de même longueur que ε, tels que les lettres de b_{ε|x} (resp. de b_{ε|y}) sont des entiers positifs au plus égaux à k (resp. à m). Enfin, désignons par MD_{α}(k′) l’ensemble des mots croissants λ, de longueur α, dont toutes les lettres sont au plus égales à k′. Autrement dit, λ ∈ MD_{α}(k′) ssi λ = λ(1)λ(2) … λ(α) et 0 ≤ λ(1) ≤ ⋯ ≤ λ(α) ≤ k′.

Il résulte de (2.7) que l’on a

(6.1)  ∑_{k′≥0} r^{k′} ∑_{λ∈MD_{α}(k′)} p^{∥λ∥} = e_{p}^{α}(r) = \frac{1}{(r; p)_{α+1}} .

Proposition 6.1. Le mot ε étant donné, ainsi que les entiers positifs k et m, il existe une bijection qui envoie tout mot b ∈ Mot(ε; k, m) sur un quintuplet (k′, m′, σ, λ, θ) satisfaisant les relations:

(i) σ ∈ PC(ε); k = k′ + icodes σ_{ε|x}; m = m′ + icodes σ_{ε|y}; (ii) λ ∈ MD_{α}(k′), θ ∈ MD_{β}(m′), où α = ℓ(ε|x) et β = ℓ(ε|β); (iii) ∥b_{ε|x}∥ = icomaj σ_{ε|x} + ∥λ∥; ∥b_{ε|y}∥ = icomaj σ_{ε|y} + ∥θ∥. (iv) i est une ε-montée de b ssi i est une ε-descente de σ.

La bijection repose sur une méthode de réarrangement mise au point par MacMahon (voir [An76, chap. 3]), souvent appelée MacMahon Verfahren, qu’il faut chaque fois adapter au problème sous-jacent (voir [Fo95], [ClFo95], [FoZe95], [FoKr95]). Une extension de cette méthode, plus appropriée pour l’étude des ensembles partiellement ordonnés (“posets”), a été mise au point par Stanley et ses élèves (voir [St72], [Re93]) dans l’algèbre des P -ω-partitions.

Nous décrivons la construction de cette bijection à l’aide d’un exemple. Dans celui-ci, on prend d’abord:

n = 9; k = 9; m = 8; ε = x x y y y y x x x,

de sorte que α = 5 et β = 4. Soit, de plus, b = 9 5 4 0 0 6 9 1 0 ∈ Mot(ε; 9, 8).

Première étape. Noter en gras (resp. en maigre) les lettres b(i) de b telles que ε(i) = x (resp. telles que ε(i) = y). Numéroter ensuite 1 la plus grande lettre maigre de b située la plus à droite, puis 2 la plus grande lettre maigre de b située la plus à droite non encore numérotée, …, enfin β la dernière lettre maigre non encore numérotée (donc la plus petite lettre la plus à gauche). Continuer en numérotant β + 1 la la plus grande lettre grasse la plus à droite, puis β+2 la plus grande lettre grasse la plus à droite non encore numérotée, …, enfin β + α = n la dernière lettre grasse non encore numérotée (donc la plus petite lettre grasse la plus à gauche). On définit ainsi la permutation σ associée à b, qui est forcément compatible avec ε.

Dans l’exemple

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

Deuxième étape. Le icomaj-codage c pour (σ, ε) est ainsi défini: sous la lettre (maigre) β de σ on écrit (en maigre) 0 et on pose c(β) = 0; sous la lettre β − 1 on écrit (en maigre) c(β − 1) = c(β) = 0 ou c(β) + 1 = 1, suivant que β − 1 est à la gauche ou à la droite de β; sous la lettre β − 2 on écrit (en maigre) c(β − 2) = c(β − 1) ou c(β − 1) + 1, suivant que β − 2 est à la gauche ou à la droite de β − 1, etc.

De même, sous la lettre (grasse) n de σ on écrit (en gras) 0 et on pose c(n) = 0; sous la lettre n − 1 on écrit (en gras) c(n − 1) = c(n) = 0 ou c(n) + 1 = 1, suivant que n − 1 est à la gauche ou à la droite de n; sous la lettre n − 2 on écrit (en gras) c(n − 2) = c(n − 1) ou c(n − 1) + 1, suivant que n − 2 est à la gauche ou à la droite de n − 1, etc.

Dans l’exemple, écrivons c(i) sous la lettre égale à i de σ, de sorte que le mot effectivement écrit est c ∘ σ = c(σ(1))c(σ(2)) … c(σ(n)):

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

Troisième étape. Faire la différence b − c ∘ σ terme à terme, en notant maigre ou gras la différence b(i) − c ∘ σ(i) suivant que les deux termes sont eux-mêmes maigres ou gras. On obtient:

\begin{matrix}b = \\ c ∘ σ = \\ b − c ∘ σ = \end{matrix} (\begin{matrix}9 & 5 & 4 & 0 & 0 & 6 & 9 & 1 & 0 \\ 3 & 2 & 1 & 0 & 0 & 1 & 3 & 1 & 0 \\ 6 & 3 & 3 & 0 & 0 & 5 & 6 & 0 & 0 \end{matrix}) .

Le mot croissant λ (resp. θ) est simplement défini comme le réarrangement croissant des lettres grasses (resp. des lettres maigres) du mot b − c ∘ σ. Ici

λ = 0 0 3 6 6  et  θ = 0 0 3 5.

Enfin, on définit: k′ = k − icodes σ_{ε|x}, m′ = m − icodes σ_{ε|y}.

Ici

σ_{ε|x} = (\begin{matrix}1 & 2 & 7 & 8 & 9 \\ 6 & 7 & 5 & 8 & 9 \end{matrix}) , σ_{ε|y} = (\begin{matrix}3 & 4 & 5 & 6 \\ 2 & 4 & 3 & 1 \end{matrix}) ,

σ_{ε|x}^{−1} = (\begin{matrix}5 & 6 & 7 & 8 & 9 \\ 7 & 1 & 2 & 8 & 9 \end{matrix}) , σ_{ε|y}^{−1} = (\begin{matrix}1 & 2 & 3 & 4 \\ 6 & 3 & 5 & 4 \end{matrix}) ,

de sorte que icodes σ_{ε|x} = 3, icomaj σ_{ε|x} = 2 + 3 + 4 = 9, icodes σ_{ε|y} = 1, icomaj σ_{ε|y} = 2. D’où

k′ = k − icodes σ_{ε|x} = 9 − 3 = 6,
m′ = m − icodes σ_{ε|y} = 8 − 1 = 7.

La bijection suivant la méthode de MacMahon ayant été adaptée déjà à plusieurs occasions, nous pensons nous dispenser de démontrer le caractère bijectif de l’application juste construite et de devoir démontrer les propriétés (i) – (iv) de la Proposition 6.1. Nous voulons cependant vérifier les données sur l’exemple courant et faire quelques commentaires.

(i) icodes σ_{ε|x} = 3 (resp. icodes σ_{ε|y} = 1) est la plus grande lettre grasse (resp. la plus grande lettre maigre) de c ∘ σ.

(ii) Les mots λ et θ ont leurs lettres au plus égales respectivement à k′ = 6 et à m′ = 7.

(iii) icomaj σ_{ε|x} = 9 (resp. icomaj σ_{ε|y} = 2) est encore la somme des lettres grasses (resp. maigres) de c∘σ. La propriété (iii) de la Proposition 6.1 est donc évidente.

(iv) Récrivons b et σ l’un au-dessous de l’autre, comme dans la première étape, en indiquant les ε-montées pour b et les ε-descentes pour σ par le symbole “•”:

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

Il y a coïncidence complète.

On rappelle que pour un mot b ∈ Mot(k, m) on a défini en (3.3)

φ(b; ε; p, q) = p^{∥b_{ε|x}∥}q^{∥b_{ε|y}∥}.

Pour une permutation σ posons ψ(σ; ε; r, s, p, q) = r^{icodes σ_{ε|x}}s^{icodes σ_{ε|y}}p^{icomaj σ_{ε|x}}q^{icomaj σ_{ε|y}}.

La correspondance b ↦ (k′, m′, σ, λ, θ) de la Proposition 6.1 permet d’écrire

r^{k}s^{m}φ(b; ε; p, q) = r^{k}s^{m}p^{∥b_{ε|x}∥}q^{∥b_{ε|y}∥}
= r^{k′+icodes σ_{ε|x}}s^{m′+icodes σ_{ε|y}}

× p^{icomaj σ_{ε|x}+∥λ∥}q^{icomaj σ_{ε|y}+∥θ∥}

= r^{k′}s^{m′}p^{∥λ∥}q^{∥θ∥}ψ(σ; ε; r, s, p, q).

On en tire

(6.2) ∑_{k≥0,m≥0} r^{k}s^{m} ∑_{b∈Mot(k,m)} φ(b; ε; p, q)

= ∑_{{k′≥0, \atop m′≥0}} r^{k′}s^{m′} ∑_{{λ∈MD_{α}(k′), \atop θ∈MD_{β}(m′)}} p^{∥λ∥}q^{∥θ∥} ∑_{σ∈PC(ε)} ψ(σ; ε; r, s, p, q)

= e_{p}^{α}(r) e_{q}^{β}(s) ∑_{σ∈PC(ε)} ψ(σ; ε; r, s, p, q),

à cause de (6.1).

7. La seconde bijection.

Il y a juste quelques modifications à apporter à la description de la première bijection pour obtenir la construction de la seconde.

Proposition 7.1. Le mot ε étant donné, ainsi que des entiers positifs K et M, il existe une bijection qui envoie tout mot B ∈ Mot(ε; K, M) sur un quintuplet (K′, M′, Σ, Λ, Θ) satisfaisant les propriétés suivantes:

(i) Σ ∈ PC(ε); K = K′ + ides Σ_{ε|x}; M = M′ + ides Σ_{ε|y}; (ii) Λ ∈ MD_{α}(K′), Θ ∈ MD_{β}(M′), où α = ℓ(ε|x), β = ℓ(ε|y); (iii) ∥B_{ε|x}∥ = imaj Σ_{ε|x} + ∥Λ∥; ∥B_{ε|y}∥ = imaj Σ_{ε|y} + ∥Θ∥. (iv) i est une ε-montée stricte de B ssi i est une ε-descente de Σ.

De même, nous donnons la construction de cette bijection à l’aide d’un exemple. On prend le même mot ε, puis K = 8, M = 6, B = 4 7 1 0 4 6 3 3 5 ∈ Mot(ε; 8, 6).

Dans la première et la deuxième étape, on définit Σ et C comme σ et c dans la construction du paragraphe précédent, mais on remplace partout “à droite” par “à gauche” et réciproquement. La troisième étape est identique. On obtient

\begin{matrix}ε = \\ B = \\ Σ = \\ C ∘ Σ = \\ B − C ∘ Σ = \end{matrix} (\begin{matrix}1 & & 2 & & 3 & 4 & & 5 & & 6 & 7 & 8 & & 9 \\ x & & x & & y & y & & y & & y & x & x & & x \\ 4 & • & 7 & • & 1 & 0 & • & 4 & • & 6 & 3 & 3 & • & 5 & • \\ 7 & • & 5 & • & 3 & 4 & • & 2 & • & 1 & 8 & 9 & • & 6 & • \\ 0 & & 1 & & 0 & 0 & & 1 & & 2 & 0 & 0 & & 1 \\ 4 & & 6 & & 1 & 0 & & 3 & & 4 & 3 & 3 & & 4 \end{matrix}) ,

où l’on a indiqué aussi les ε-montées strictes pour B et les ε-descentes pour Σ par le symbole “•,” celles-ci apparaissant aux mêmes places.

De même, les mots croissants Λ et Θ sont définis comme les réarrangements croissants des lettres grasses (resp. des lettres maigres) du mot B − C ∘ Σ. Ici

Λ = 3 3 4 4 6  et  Θ = 0 1 3 4.

Enfin, on définit: K′ = K − ides Σ_{ε|x}, M′ = M − ides Σ_{ε|y}.

On vérifie les propriétés suivantes.

(i) On a ides Σ_{ε|x} = des Σ_{ε|x}^{−1} = 1 et ides Σ_{ε|y} = des Σ_{ε|y}^{−1} = 2 et donc K′ = 8 − 1 = 7 et M′ = 6 − 2 = 4.

(ii) Les mots croissants Λ et Θ ont leurs lettres au plus égales respectivement à K′ = 7 et à M′ = 4.

(iii) On a imaj Σ_{ε|x} = maj Σ_{ε|x}^{−1} = 2 et imaj Σ_{ε|y} = maj Σ_{ε|y}^{−1} = 3. Enfin, ∥B_{ε|x}∥ = 4 + 7 + 3 + 3 + 5 = 22 = 2 + (6 + 4 + 4 + 3 + 3) = imaj Σ_{ε|x} + ∥Λ∥ et ∥B_{ε|y}∥ = 1 + 0 + 4 + 6 = 11 = 3 + (4 + 3 + 1 + 0) = imaj Σ_{ε|y} + ∥Θ∥.

Pour chaque permutation Σ posons maintenant:

Ψ(Σ; ε; R, S, P, Q) = R^{ides Σ_{ε|x}}S^{ides Σ_{ε|y}}P^{imaj Σ_{ε|x}}Q^{imaj Σ_{ε|y}}.

Le même calcul que dans la section précédente, utilisant cette fois la Proposition 7.1, conduit à

R^{K}S^{M}φ(B; ε; P, Q) = R^{K′}S^{M′}P^{∥Λ∥}Q^{∥Θ∥}Ψ(Σ; ε; R, S, P, Q),

d’où l’on tire:

(7.1) ∑_{K≥0,M≥0} R^{K}S^{M} ∑_{B∈Mot(K,M)} φ(B; ε; P, Q)

= e_{P}^{α} (R) e_{Q}^{β}(S) ∑_{Σ∈PC(ε)} Ψ(Σ; ε; R, S, P, Q).

8. Le calcul de la première fonction génératrice.

Combinons maintenant le contenu des deux Propositions 6.1 et 7.1. On suppose donnés, d’abord le mot ε, contenant α lettres x et β lettres y, puis les suites d’entiers positifs

\begin{aligned}K & = (K_{1}, K_{2}, …, K_{L}), \\ M & = (M_{1}, M_{2}, …, M_{L}), \end{aligned}  \begin{aligned}k & = (k_{1}, k_{2}, …, k_{l}), \\ m & = (m_{1}, m_{2}, …, m_{l}). \end{aligned}

En outre, on désigne par Multimot(ε; \binom{K,M}{k,m}) l’ensemble des multimots w = (B_{1}, …, B_{L}, b_{1}, …, b_{l}), tels que tout B_{i} est dans Mot(ε; K_{i}, M_{i}) et tout b_{i} est dans Mot(ε; k_{i}, m_{i}). On peut donc appliquer à chaque b_{i} la bijection de la Proposition 6.1 et à chaque B_{i} celle de la Proposition 7.1. Notons σ_{i} (resp. Σ_{i}) la permutation compatible avec ε correspondant à b_{i} (resp. à B_{i}) par la première (resp. la seconde) bijection et posons

(8.1)  \underline{Σ} = (Σ_{1}, …, Σ_{L});  \underline{σ} = (σ_{1}, …, σ_{l});

\underline{Ψ}(\underline{Σ}, \underline{σ}, ε) = Ψ(Σ_{1}; ε; R_{1}, S_{1}, P_{1}, Q_{1}) … Ψ(Σ_{L}; ε; R_{L}, S_{L}, P_{L}, Q_{L}) × ψ(σ_{1}; ε; r_{1}, s_{1}, p_{1}, q_{1}) … ψ(σ_{l}; ε; r_{l}, s_{l}, p_{l}, q_{l}).

Introduisons les huit statistiques multivariées ides_{x}, ides_{y}, imaj_{x}, imaj_{x}, icodes_{x}, icodes_{y}, icomaj_{x}, icomaj_{y} comme:

R^{ides_{x}(\underline{Σ},ε)} = R_{1}^{ides Σ_{1 ε | x}} … R_{L}^{ides Σ_{L ε | x}}
⋯ = ⋯
q^{icomaj_{x}(\underline{σ},ε)} = q_{1}^{icomaj σ_{1 ε | y}} … q_{l}^{icomaj σ_{l ε | y}}

On peut encore écrire: (8.2) \underline{Ψ}(\underline{Σ}, \underline{σ}, ε) = R^{ides_{x}(\underline{Σ},ε)}S^{ides_{y}(\underline{Σ},ε)}P^{imaj_{x}(\underline{Σ},ε)}Q^{imaj_{y}(\underline{Σ},ε)}

× r^{icodes_{x}(\underline{σ},ε)}s^{icodes_{y}(\underline{σ},ε)}p^{icomaj_{x}(\underline{σ},ε)}q^{icomaj_{y}(\underline{σ},ε)}

D’autre part, les propriétés (iv) des deux Propositions 6.1 et 7.1 impliquent que i est une ε-montée commune à chaque b_{j} et une ε-montée stricte commune à chaque B_{j}, si et seulement si i est une ε-descente commune à chaque σ_{j} et à chaque Σ_{j}. Autrement dit, on a:

(8.3)  rise(w, ε) = ddes(\underline{Σ}, \underline{σ}, ε).

D ’après (6.2) et (7.1) et les définitions de φ et Φ données en (3.3) et (3.4), on en déduit (8.4) \begin{matrix}∑ \\ ( & {K,M \atop k,m} & ) \end{matrix} R^{K}S^{M}r^{k}s^{m} ∑ ; w∈Multimot(ε;\binom{K,M}{k,m}) t^{rise(w,ε)}Φ(w, ε)

= e_{P}^{α}(R) e_{Q}^{β}(S) e_{p}^{α}(r) e_{q}^{β}(s) ∑_{(\underline{Σ},\underline{σ})} t^{ddes(\underline{Σ},\underline{σ},ε)}X^{ℓ(ε|x)}Y^{ℓ(ε|y)}\underline{Ψ}(\underline{Σ}, \underline{σ}, ε),

où la dernière sommation est sur toutes les suites de permutations (8.1), compatibles avec ε.

Maintenant on peut sommer d’abord par rapport à tous les ε tels que ℓ(ε|x) = α et ℓ(ε|y) = β, puis par rapport à α ≥ 0 et à β ≥ 0. Le membre de gauche donne

(8.5)  \begin{matrix}∑ \\ ( & {K,M \atop k,m} & ) \end{matrix} R^{K}S^{M}r^{k}s^{m} ∑_{(w,ε)∈MMS\binom{K,M}{k,m}} t^{rise(w,ε)}Φ(w, ε),

où la seconde sommation est étendue à tous les multimots signés (w, ε) de MMS\binom{K,M}{k,m}.

Le membre de droite de (8.4) devient

∑_{α≥0, β≥0} e_{P}^{α}(R) e_{Q}^{β}(S) e_{p}^{α}(r) e_{q}^{β}(s)X^{α}Y^{β}W_{α,β},

où

W_{α,β} = W_{α,β}(t, R, S, P, Q, r, s, p, q) = ∑_{{(\underline{Σ},\underline{σ},ε) (comp.) \atop ℓ(ε|x)=α, ℓ(ε|y)=β}} t^{ddes(\underline{Σ},\underline{σ},ε)}\underline{Ψ}(\underline{Σ}, \underline{σ}, ε),

la sommation étant sur toutes les multipermutations signées compatibles (\underline{Σ}, \underline{σ}, ε) telles que ℓ(ε|x) = α et ℓ(ε|y) = β.

Récrivons l’expression (8.5) à l’aide de la seconde identité de la Proposition 4.1. On en déduit le résultat suivant.

Théorème 8.1. La fonction génératrice factorielle des multipermutations signées compatibles (\underline{Σ}, \underline{σ}, ε) par la suite de statistiques (voir (8.2))

(ddes, ides_{x}, ides_{y}, imaj_{x}, imaj_{y}, icodes_{x}, icodes_{y}, icomaj_{x}, icomaj_{y}), est donnée par

\begin{matrix}∑ \\ ( & {K,M \atop k,m} & ) \end{matrix} R^{K}S^{M}r^{k}s^{m} \frac{(1 − t) J_{k}^{K}((1 − t)X; P, p)}{−t + J_{k}^{K}((1 − t)X; P, p) J_{m}^{M}((1 − t)Y; Q, q)}

= ∑_{α≥0, β≥0}e_{P}^{α}(R) e_{Q}^{β}(S) e_{p}^{α}(r) e_{q}^{β}(s)X^{α}Y^{β} ∑_{{(\underline{Σ},\underline{σ},ε) (comp.) \atop ℓ(ε|x)=α, ℓ(ε|y)=β}} t^{ddes(\underline{Σ},\underline{σ},ε)}\underline{Ψ}(\underline{Σ}, \underline{σ}, ε).

Si l’on fait X = 0 dans la précédente identité, on obtient

(8.6) \begin{matrix}∑ \\ ( & {M \atop m} & ) \end{matrix} S^{M}s^{m} \frac{(1 − t)}{−t + J_{m}^{M}((1 − t)Y; Q, q)}

= ∑_{β≥0} e_{Q}^{β}(S) e_{q}^{β}(s)Y^{β} ∑_{(\underline{Σ},\underline{σ})} t^{ddes(\underline{Σ},\underline{σ})}\underline{Ψ}(\underline{Σ}, \underline{σ}).

La dernière sommation se fait cette fois sur toutes les multipermutations (\underline{Σ}, \underline{σ}) de longueur β. La statistique ddes(\underline{Σ}, \underline{σ}) est le nombre de descentes communes à toutes les permutations Σ_{1}, …, Σ_{L}, σ_{1}, …, σ_{l}. Enfin,

\underline{Ψ}(\underline{Σ}, \underline{σ}) = S^{ides \underline{Σ}} s^{icodes \underline{σ}} Q^{imaj \underline{Σ}} q^{icomaj \underline{σ}},

où, naturellement,

S^{ides \underline{Σ}} = S_{1}^{ides Σ_{1}} … S_{L}^{ides Σ_{L}},
⋯ = ⋯
q^{icomaj \underline{Σ}} = q_{1}^{icomaj σ_{1}} … q_{l}^{icomaj σ_{l}}.

L’identité (8.6) avec cette dernière interprétation globalise en une formule toutes les identités obtenues par Fedou et Rawlings [FeRa94, FeRa95] dans leur calcul de la statistique “ddes” sur les suites de permutations.

L’identité du Théorème 8.1 est l’analogue fini de la fonction génératrice factorielle des multipermutations signées: “analogue fini” voulant dire que les fonction de Bessel sous-jacentes sont toutes à paramètres finis. Si les paramètres ne sont plus finis, on ne peut plus considérer une série en les paramètres \binom{K,M}{k,m} comme dans l’identité du Théorème 8.1. On part alors de cette identité et on la multiplie successivement par (1−R_{1}) et l’on fait R = 1, …, puis par (1 − R_{L}) et l’on fait R_{L} = 1, jusqu’à multiplier par (1 − s_{l}) et faire s_{l} = 1. On obtient l’identité

(8.7) \frac{(1 − t) J((1 − t)X; P, p)}{−t + J((1 − t)X; P, p) J((1 − t)Y; Q, q)}

= ∑_{α≥0, β≥0} \frac{1}{(P; P)_{α}} \frac{1}{(Q; Q)_{β}} \frac{1}{(p; p)_{α}} \frac{1}{(q; q)_{β}}

× X^{α}Y^{β} ∑_{{(\underline{Σ},\underline{σ},ε) (comp.) \atop ℓ(ε|x)=α, ℓ(ε|y)=β}} t^{ddes(\underline{Σ},\underline{σ},ε)}\underline{Ψ}′(\underline{Σ}, \underline{σ}, ε),

où le monôme \underline{Ψ}′(\underline{Σ}, \underline{σ}, ε) est simplement la spécialisation de \underline{Ψ}(\underline{Σ}, \underline{σ}, ε) lorsque toutes les variables R_{i}, S_{i}, r_{i}, s_{i} sont égales à 1. Autrement dit, avec les notations (8.2)

\underline{Ψ}′(\underline{Σ}, \underline{σ}, ε) = P^{imaj_{x}(\underline{Σ},ε)}Q^{imaj_{y}(\underline{Σ},ε)}p^{icomaj_{x}(\underline{σ},ε)}q^{icomaj_{y}(\underline{σ},ε)}.

Dans (8.7) la fonction génératrice sous-jacente est sur les seules multipermutations signées compatibles. On peut en déduire une expression pour la fonction génératrice de toutes les multipermutations signées, en réduisant le nombre des variables. Ceci fait l’objet du paragraphe suivant.

9. Fonction génératrice de toutes les multipermutations signées

Partons de (8.7) et prenons P = Q, p = q, c’est-à-dire P_{1} = Q_{1}, …, P_{L} = Q_{L}, p_{1} = q_{1}, …, p_{l} = q_{l}. Posons également pour chaque multipermutation signée compatible (\underline{Σ}, \underline{σ}, ε)

imaj(\underline{Σ}, ε) = imaj_{x}(\underline{Σ}, ε) + imaj_{y}(\underline{Σ}, ε)
icomaj(\underline{σ}, ε) = icomaj_{x}(\underline{σ}, ε) + icomaj_{y}(\underline{σ}, ε),

soit imaj(Σ_{i}, ε) = imaj Σ_{i ε|x} + imaj Σ_{i ε|y} (i = 1, …, L) et icomaj(σ_{i}, ε) = icomaj Σ_{i ε|x}+icomaj Σ_{i ε|y} (i = 1, …, l), ce qui est conforme à la définition donnée au paragraphe 5, puisque toutes les permutations signées (Σ_{i}, ε) et (σ_{i}, ε) considérées sont compatibles.

Conservant les seules variables Q_{1}, …, Q_{L}, q_{1}, …, q_{l}, on voit que le nouveau monôme \underline{Ψ}′(\underline{Σ}, \underline{σ}, ε) est égal à

(9.1)  \underline{Ψ}′′(\underline{Σ}, \underline{σ}, ε) = Q^{imaj(\underline{Σ},ε)}q^{icomaj(\underline{σ},ε)}.

Posons

W_{α,β} = ∑_{{(\underline{Σ},\underline{σ},ε) (comp.) \atop ℓ(ε|x)=α, ℓ(ε|y)=β}} t^{ddes(\underline{Σ},\underline{σ},ε)}Q^{imaj(\underline{Σ},ε)}q^{icomaj(\underline{σ},ε)}

Une manipulation banale sur les q-séries permet alors de transformer le membre de droite de l’identité (8.7) et d’écrire cette identité sous la forme

(9.2) \frac{(1 − t) J((1 − t)X; Q, q)}{−t + J((1 − t)X; Q, q) J((1 − t)Y; Q, q)}

= ∑_{n≥0} \frac{1}{(Q; Q)_{n}(q; q)_{n}} W′_{n}(X, Y, t, Q, q)

où l’expression

(9.3) W′_{n}(X, Y, t, Q, q) = ∑_{0≤α≤n} X^{α}Y^{n−α}\left[{n \atop α}\right]_{Q} \left[{n \atop α}\right]_{q} W_{α,n−α}

est un polynôme à coefficients entiers positifs. On retrouve l’identité (1.1) démontrée avec d’autres techniques dans notre premier article et pour une autre suite de statistiques.

Théorème 9.1. Le polynôme W′_{n}(X, Y, t, Q, q) apparaissant dans (9.2) est le polynôme générateur des multipermutations signées (\underline{Σ}, \underline{σ}, ε) de longueur n par le 5-vecteur (ℓ(ε|x), ℓ(ε|y), ddes, imaj, icomaj). En d’autres termes,

W′_{n}(X, Y, t, Q, q) = ∑_{(\underline{Σ},\underline{σ},ε)} X^{ℓ(ε|x)}Y^{ℓ(ε|y)}t^{ddes(\underline{Σ},\underline{σ},ε)}Q^{imaj(\underline{Σ},ε)}q^{icomaj(\underline{σ},ε)},

où la somme est sur toutes les multipermutations signées (\underline{Σ}, \underline{σ}, ε) de longueur n.

Nous ne reproduisons pas la démonstration. On peut la calquer de la démonstration de la Proposition 2.1 de notre premier article.

Posons

(9.4) W_{n}(X, Y, t, Q, q)

= ∑_{(\underline{Σ},\underline{σ},ε)} X^{ℓ(ε|x)}Y^{ℓ(ε|y)}t^{ddes(\underline{Σ},\underline{σ},ε)}Q^{inv(\underline{Σ},ε)}q^{coinv(\underline{σ},ε)} .

Dans notre premier article nous avions démontré que l’identité (9.2) était encore vraie si l’on remplaçait le polynôme W′_{n} par W_{n}. Nous obtenions ainsi une autre interprétation combinatoire du développement du rapport des fonctions de Bessel apparaissant dans le membre de gauche de (9.2). Dans le dernier paragraphe de cet article, nous donnons une démonstration “bijective” de ce résultat.

10. L’interprétation en termes de nombre d’inversions

Il s’agit de démontrer que le polynôme W_{n}(X, Y, t, Q, q) défini dans (9.4) et le polynôme W′_{n}(X, Y, t, Q, q) apparaissant dans l’énoncé du Théorème 9.1 sont identiques.

On pourrait partir de l’identité de la Proposition 4.1, et définir des bijections analogues à celles qui ont été construites dans les sections 6 et 7 et établir que la fraction (9.2) est la fonction génératrice factorielle des polynômes W_{n}. Nous préférons établir le résultat à l’aide d’une bijection directe.

Proposition 10.1. Il existe une bijection Ψ : (\underline{Σ}, \underline{σ}, ε) ↦ (\underline{Σ}′, \underline{σ}′, ε′) de l’ensemble des multipermutations signées de longueur n sur elle-même, ayant les propriétés suivantes:

(i) ℓ(ε|x) = ℓ(ε′|x); (ii) ddes(\underline{Σ}, \underline{σ}, ε) = ddes(\underline{Σ}′, \underline{σ}′, ε′); (iii) imaj(\underline{Σ}, ε) = inv(\underline{Σ}′, ε′) et icomaj(\underline{σ}, ε) = coinv(\underline{σ}′, ε′).

Démonstration. L’ingrédient principal de cette bijection est la seconde transformation fondamentale. Nous ne rappelons pas sa construction, mais renvoyons le lecteur au chapitre 10 du livre de Lothaire [Lo83]. Notons Γ cette transformation. Par ailleurs, pour tout mot w = x_{1}x_{2} … x_{m}, où les lettres appartiennent à un alphabet totalement ordonné, la ligne de route “ligne w” de w est définie comme l’ensemble des entiers i tels que 1 ≤ i ≤ m−1 et x_{i} > x_{i+1}, de sorte que “maj w” est simplement la somme des éléments de cette ligne de route.

Soit maintenant π une bijection d’un ensemble fini I d’entiers sur un ensemble fini d’entiers. Posons

I = {i_{1} < i_{2} < ⋯ < i_{k}}, π(I) = {j_{1} < j_{2} < ⋯ < j_{k}},

et présentons π comme une matrice à deux lignes (\begin{matrix}i_{1} & … & i_{k} \\ π(i_{1}) & … & π(i_{k}) \end{matrix}), où

les éléments de la première ligne sont rangés en ordre croissant. Notons i l’opération qui consiste à envoyer toute bijection sur son inverse et considérons la chaîne

(\begin{matrix}i_{1} & … & i_{k} \\ π(i_{1}) & … & π(i_{k}) \end{matrix}) \underrightarrow{i} (\begin{matrix}j_{1} & … & j_{k} \\ π^{−1}(j_{1}) & … & π^{−1}(j_{k}) \end{matrix})

\underrightarrow{Γ} (\begin{matrix}j_{1} & … & j_{k} \\ y_{1} & … & y_{k} \end{matrix}) \underrightarrow{i} (\begin{matrix}i_{1} & … & i_{k} \\ π′(i_{1}) & … & π′(i_{k}) \end{matrix}) ,

qu’on va récrire:

π \underrightarrow{i} π^{−1} \underrightarrow{Γ} Γ(π^{−1}) \underrightarrow{i} π′.

Comme prouvé dans [FoSc78], Γ envoie le mot π^{−1}(j_{1}) … π^{−1}(j_{k}) sur un réarrangement y_{1} … y_{k} de ce mot. C’est la seconde ligne de la troisième matrice ci-dessus. De plus, cette bijection Γ a la propriété:

maj(π^{−1}(j_{1}) … π^{−1}(j_{k})) = inv(y_{1} … y_{k}),

ce qui entraîne (10.1) maj π^{−1} = inv π′ et comaj π^{−1} = coinv π′.

Comme prouvé dans [FoSc78], elle conserve, de plus, la ligne de route de l’inverse. Par conséquent, la ligne de route de l’inverse de π^{−1} est égale à la ligne de route de l’inverse de Γ(π^{−1}), c’est-à-dire,

(10.2)  ligne π = ligne π′.

Soit maintenant un triplet (\underline{Σ}, \underline{σ}, ε) = ((Σ_{1}, …, Σ_{L}), (σ_{1}, …, σ_{l}), ε). On note I le sous-ensemble de [ n] des entiers i tels que ε(i) = x. On pose, tout d’abord, ε′ = ε. Ensuite, on applique à la restriction à I et à I^{c} de chaque permutation Σ_{i}, σ_{i} la transformation précédente π ↦ π′.

On construit ainsi des permutations Σ′_{i} et σ′_{i}, toutes définies par leurs restrictions à I et à I^{c}.

Les trois propriétés (i), (ii), (iii) exigées sont bien satisfaites: la propriété (i) est triviale; la propriété (ii) résulte de la propriété (10.2) de la transformation π ↦ π′. Enfin, pour chaque permutation Σ de la suite \underline{Σ}, on a d’abord

inv(Σ_{ε|y}, Σ_{ε|x}) = inv(Σ′_{ε|y}, Σ′_{ε|x}) et inv(σ_{ε|y}, σ_{ε|x}) = inv(σ′_{ε|y}, σ′_{ε|x}). Ensuite, d’après (2.2),

imaj(Σ, ε) = maj Σ_{ε|x}^{−1} + maj Σ_{ε|y}^{−1} + inv(Σ_{ε|y}, Σ_{ε|x})
= inv Σ′_{ε|x} + inv Σ′_{ε|y} + inv(Σ′_{ε|y}, Σ′_{ε|x}) = inv(Σ′, ε) ;
icomaj(σ, ε) = comaj σ_{ε|x}^{−1} + comaj σ_{ε|y}^{−1} + inv(σ_{ε|y}, σ_{I})
= coinv σ′_{ε|x} + coinv σ′_{ε|y} + inv(σ′_{ε|y}, σ′_{ε|x}) = coinv(σ, ε).

Bibliographie

[An76] George E. Andrews. — The Theory of Partitions. — London, Addison-Wesley, 1976 (Encyclopedia of Math. and Its Appl., 2).

[Ca76] L. Carlitz, R. Scoville and T. Vaughan. — Enumeration of pairs of permutations,

Discrete Math., vol. 14, 1976, p. 215–239.

[ClFo95] Robert J. Clarke and Dominique Foata. — Eulerian Calculus, II: An Extension of Han’s Fundamental Transformation, Europ. J. Combinatorics, vol. 16, 1995, p. 221–252.

[Ehr93] Leon Ehrenpreis. — Function Theory for Rogers-Ramanujan-like Partition Identities, Contemporary Math., vol. 143, 1993, p. 259–320.

[FeRa94] J.-M. Fedou and D. Rawlings. — More Statistics on Permutations Pairs, Electronic J. Combinatorics, vol. 1, 1994, R11, 17 pp.

[FeRa95] J.-M. Fedou and D. Rawlings. — Adjacencies in words, Advances in Appl. Math.,

vol. 16, 1995, p. 206–218.

[Fo95] Dominique Foata. — Les distributions Euler-Mahoniennes sur les mots, Discrete Math., vol. 139, 1995, p. 167–188.

[Fo79] Dominique Foata. — A Noncommutative Version of the Matrix Inversion For-

mula, Adv. in Math., vol. 31, 1979, p. 330–349.

[FoHa96] Dominique Foata et Guo-Niu Han. — Calcul basique des permutations signées, I: longueur et nombre d’inversions, Strasbourg, 18 p., 1996.

[FoHa96a] Dominique Foata et Guo-Niu Han. — Table des spécialisations des distributions sur les multipermutations signées, available at

http://cartan.u-strasbg.fr/∼guoniu/papers/table.html.

[FoKr95] Dominique Foata and Christian Krattenthaler. — Graphical Major Indices, II, Séminaire Lotharingien de Combinatoire, 34k, 16 pp.

[FoSc78] Dominique Foata and Marcel-Paul Schützenberger. — Major Index and Inversion number of Permutations, Math. Nachr., vol. 83, 1978, p. 143–159.

[FoZe95] Dominique Foata and Doron Zeilberger. — Graphical Major Indices, à paraître dans J. of Computational and Applied Math., 1995.

[GaRa90] George Gasper and Mizan Rahman. — Basic Hypergeometric Series. — London, Cambridge Univ. Press, 1990 (Encyclopedia of Math. and Its Appl., 35).

[GoJa83] I.P. Goulden and D.M. Jackson. — Combinatorial Enumeration. — New York, John Wiley, 1983.

[HuWi75] J. P. Hutchinson and H.S. Wilf. — On Eulerian circuits and words with prescribed

adjacency patterns, J. Combinatorial Theory A, vol. 18, 1975, p. 80–87.

[Lo83] M. Lothaire. — Combinatorics on words. — Reading, Addison-Wesley, 1983 (Encyclopedia of Math. and its Appl., 17).

[Mac13] 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., vol. 35, 1913, p. 314–321.

[Re93] V. Reiner. — Signed permutation statistics, Europ. J. Combinatorics, vol. 14, 1993, p. 553–567.

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

[St76] Richard P. Stanley. — Binomial posets, Möbius inversion, and permutation enumeration, J. Combinatorial Theory Ser. A, vol. 20, 1976, p. 336–356.

[St86] Richard P. Stanley. — Enumerative Combinatorics, vol. 1. — Monterey, Calif.,

Wadsworth and Brooks/Cole, 1986.

[Stem92] John Stembridge. — Eulerian numbers, tableaux, and the Betti numbers of a

toric variety, Discrete Math., vol. 99, 1992, p. 307–320.

[Vi86] Xavier Gérard Viennot. — Heaps of pieces, I: basic definitions and combinatorial lemmas, in Combinatoire Énumérative [G. Labelle and P. Leroux, eds. Montréal, 1985]. — Lecture Notes in Math., 1234, Berlin, Springer-Verlag, 1986.