UNE NOUVELLE TRANSFORMATION POUR LES STATISTIQUES EULER-MAHONIENNES ENSEMBLISTES

Dominique Foata et Guo-Niu Han (^{∗})

EN HOMMAGE À PIERRE CARTIER, POLYMATH, LOTHARINGIEN D’HONNEUR

Abstract. The construction of a bijection of the symmetric group onto itself is given that has the property of mapping a pair of set-statistics onto another pair. As a consequence, it is shown that a pair of Euler-mahonian statistics has a symmetric distribution.

Résumé. On donne la construction d’une bijection du groupe symétrique sur lui-même, qui a la propriété d’envoyer un couple de statistiques ensemblistes sur un autre couple. Comme conséquence, on montre qu’un couple de statistiques Euler-mahoniennes a une distribution symétrique.

Avant-propos

Nous sommes heureux de dédier le présent article de Combinatoire à Pierre Cartier, qui, dès les années soixante, a attiré l’attention de la communauté mathématique sur la renaissance de cette discipline ; témoin son exposé de 1962 au Séminaire Bourbaki (cf. [Ca62]) sur l’identité exponentielle de Spitzer [Sp56] et ses applications aux fluctuations de sommes de variables aléatoires. Tout au long de sa carrière, il est resté attentif à tous les développements importants (cf. [Ca80, Ca82, Ca91]), en particulier au renouveau de l’étude des fonctions symétriques initialisé par Schützenberger [Sc77] et à la révolution philosophique que constitue la démonstration “automatique” des identités hypergéométriques due à Zeilberger [Ze90]. Il a lui-même contribué à cette discipline dans plusieurs travaux (cf. [CaFo69, Ca72, Ca90, Ca00]). Notons enfin que le mémoire sur les commutations [CaFo69] a donné un cadre mathématique utile aux problèmes de parallélisme (cf. Diekert [Di90]) et a fourni une version non-commutative à l’identité fondamentale du polynôme chromatique [St73] (cf. Lass [La01]).

DOMINIQUE FOATA ET GUO-NIU HAN

La construction donnée ci-dessous d’une nouvelle transformation sur le groupe symétrique s’inscrit dans ce cadre de recherche, où les propriétés des statistiques définies sur ce groupe (comme le nombre de descentes, la longueur, l’indice majeur, …) sont systématiquement explorées et étendues à certains groupes de Coxeter (cf. [AR01, ABR01, Br94, FH97, Re93a, Re93b, Re93c, Re95a, Re95b, StE93, St76, StJ92]). Il s’agit, en particulier, de trouver les expressions analytiques des séries génératrices de ces statistiques ; si on ne peut le faire directement, il s’agit alors de construire des bijections sur ces groupes qui permettent de ramener le calcul à des cas classiques connus. Chemin faisant, la construction de ces bijections fait apparaître des propriétés nouvelles sur ces groupes.

(^{∗}) Ce travail de recherche a pu être effectué grâce au soutien financier du contrat européen “Algebraic Combinatorics”, no. RTN2-2001-00059.

1. Introduction

Appelons ligne de route d’une permutation σ = σ(1)σ(2) … σ(n) (écrite comme un mot en les lettres 1, 2, …, n), l’ensemble, noté Ligne σ, de tous les entiers i tels que 1 ≤ i ≤ n − 1 et σ(i) > σ(i + 1). [Certains auteurs parlent d’ensemble de descentes (“descent set”) et adoptent la notation D(σ) ou DES σ) (cf. [AR01, Br94, Re95a, Re95b]).] La somme des éléments de Ligne σ est notée maj σ (l’indice majeur de σ).

Par ailleurs, la ligne inverse de route, Iligne σ, de σ, est définie comme l’ensemble de toutes les lettres σ(i), telles que la lettre égale à 1+σ(i) soit à la gauche de σ(i) dans le mot σ. Il est immédiat que la ligne inverse de route de σ n’est autre que la ligne de route de la permutation inverse σ^{−1}.

Rappelons que le codage par inversions (ou codage de Lehmer) (cf. [Le60]), Invcode σ, d’une permutation σ est défini comme le mot w = x_{1}x_{2} … x_{n}, de longueur n, tel que pour tout i = 1, 2, …, n, la lettre x_{i} est donnée par

(1.1)  x_{i} := #{j : 1 ≤ j ≤ i − 1, σ(j) > σ(i)}.

Par construction-même, on a :

(1.2)  0 ≤ x_{i} ≤ i − 1  (1 ≤ i ≤ n).

Un mot w = x_{1}x_{2} … x_{n}, dont les lettres sont des entiers satisfaisant les inégalités (1.2) est dit sous-excédent. On note SE_{n} l’ensemble des mots sous-excédents de longueur n. On définit la ligne des montées, Rise w, d’un mot quelconque (en particulier d’un mot sous-excédent) w = x_{1}x_{2} … x_{n}, comme l’ensemble des indices i tels que 1 ≤ i ≤ n − 1 et x_{i} < x_{i+1}.

Il est évident que “Invcode” est une bijection de S_{n} sur SE_{n}. Une autre telle bijection est le maj-codage “Majcode”, que l’on peut définir, par récurrence, de la façon suivante : le maj-codage de la permutation 1 est 0. Soient σ une permutation d’ordre n ≥ 2 et σ^{−} la permutation déduite de σ par suppression de la lettre n dans σ. Si x_{1}x_{2} … x_{n−1} est le maj-codage de σ^{−}, alors on définit Majcode σ := x_{1}x_{2} … x_{n−1}x_{n}, avec x_{n} := maj σ − maj σ^{−}. Une autre définition de “Majcode” par étiquetage est proposée au paragraphe 5.

TRANSFORMATION POUR STATISTIQUES ENSEMBLISTES

Le but de cet article est de démontrer qu’il existe une bijection ϕ : σ ↦ τ du groupe symétrique S_{n} sur lui-même et surtout de construire une telle bijection, telle que le diagramme suivant soit commutatif :

[figure: w′; B; Rise; Majcode; Iligne; τ; σ; ϕ; (1.3); w; A; Rise; Invcode; Ligne; w, w′ ∈ SE_{n};; σ, τ ∈ S_{n};; A, B ⊂ {1, 2, …, n − 1}.]

On en déduit le résultat suivant.

Théorème 1.1. Il existe une bijection ϕ qui satisfait :

(1.4)  (Ligne, Iligne) σ = (Rise ∘ Invcode, Rise ∘ Majcode) ϕ(σ).

Le lecteur souhaitant lire tout de suite la construction de la bijection ϕ est invité à se reporter au paragraphe 4, où deux descriptions en sont données. Il doit seulement se rappeler la définition de Majcode et, pour chaque entier i tel que 1 ≤ i ≤ n, utiliser la bijection croissante de {1, …, i − 1, i + 1, …, n} sur {1, 2, …, n − 1} notée réd_{i} (“réd” pour “réduite”) et la bijection inverse réd_{i}^{−1}.

En plus des statistiques “Ligne”, “Iligne” et “Rise” déjà définies, introduisons une quatrième statistique ensembliste “Eul”, dite valeur Eulérienne, qui associe à tout mot sous-excédent w = x_{1}x_{2} … x_{n} un sousensemble, Eul w, de {1, 2, …, n − 1}. Si n = 1, on pose Eul 0 := ∅; si n ≥ 2 et si l’on pose w′ := x_{1}x_{2} … x_{n−1}, de sorte que w′ ∈ SE_{n−1} et w = w′x_{n}, on peut poser, par récurrence, Eul w′ := {y_{k} < y_{k−1} < ⋯ < y_{1}} ⊂ {1, 2, …, n − 2}. Notons alors {z_{k+1} < z_{k+2} < ⋯ < z_{n−1} = n − 1} l’ensemble complémentaire {1, 2, …, n − 1} \ Eul w′. Si k ≥ x_{n} ≥ 0, on définit :

(1.5) Eul w′x_{n} := {y_{k}, y_{k−1}, …, y_{x_{n}+1}, y_{x_{n}} + 1, …, y_{2} + 1, y_{1} + 1}.

En particulier Eul w′0 = Eul w′.

Posons, par commodité, y_{k+1} := 0 et y_{0} := n. Si n − 1 ≥ x_{n} ≥ k + 1, il existe un entier unique p tel que y_{p+1} < z_{x_{n}} < y_{p}. En particulier, x_{n} ≥ k + 1 ≥ p + 1. On définit alors :

(1.6)  Eul w′x_{n} := {y_{k}, …, y_{p+1}, x_{n} − p, y_{p} + 1, …, y_{1} + 1}.

Exemple. On a successivement : Eul(0, 0) = ∅; Eul(0, 0, 1) = {1}; Eul(0, 0, 1, 0) = {1}; Eul(0, 0, 1, 0, 3) = {1, 3}; Eul(0, 0, 1, 0, 3, 1) = {1, 4}. Avec w′ = 0, 0, 1, 0, 3, 1, on obtient Eul w′0 = {1, 4}; Eul w′1 = {1, 5}; Eul w′2 = {2, 5}; Eul w′3 = {1, 2, 5}; Eul w′4 = {1, 3, 5}; Eul w′5 = {1, 4, 5} et Eul w′6 = {1, 4, 6}.

Par définition-même du codage par inversions (cf., par exemple, [Lo02], Proposition 11.4.2), on a, pour toute permutation σ,

(1.7)  Ligne σ = Rise ∘ Invcode σ.

On peut vérifier également (voir § 5) que l’on a :

(1.8)  Ligne σ = Eul ∘ Majcode σ.

Désignons par i la bijection définie sur S_{n}, qui envoie toute permutation sur son inverse i σ := σ^{−1} et formons la chaîne

(1.9)

i  ϕ  Majcode  Invcode^{−1}
σ′ ↦ σ ↦ τ  ↦  w′  ↦  τ′
S_{n}  S_{n}  S_{n}  SE_{n}  S_{n}

De (1.4), (1.7) et (1.8), résultent, d’une part, les identités

(1.10) \begin{matrix}Ligne σ′ & = & Iligne σ & = & Rise ∘ Majcode τ & = & Rise w′ & = & Ligne τ′; \\ Iligne σ′ & = & Ligne σ & = & Ligne τ & = & Eul w′ & = & Eul ∘ Invcode τ′, \end{matrix}

d’autre part, le théorème suivant.

Théorème 1.2. Les couples de statistiques ensemblistes (Ligne, Iligne), (Rise ∘Majcode, Ligne), (Ligne, Eul∘Invcode) sur S_{n}, ainsi que (Rise, Eul) sur SE_{n} ont même distribution.

Le plan de l’article est le suivant. Dans le prochain paragraphe, nous donnons les applications du Théorème 1.1 à l’étude des statistiques numériques Euler-Mahoniennes. Dans le paragraphe 3, nous expliquons la démarche naturelle qui mène à la construction de la bijection du Théorème 1.1, qui est, elle, décrite dans le paragraphe 4. Les propriétés de cette bijection reposent sur une analyse fine du majcodage, qui est explicitée dans le paragraphe 5. Le paragraphe suivant contient un lemme fondamental sur les lignes de montée. Dans le paragraphe 8, nous calculons le polynôme générateur des permutations, de ligne de route fixée, par un couple Euler-Mahonien de statistiques. Pour terminer, nous donnons un exemple numérique, qui illustre, d’une part, la construction de la bijection ϕ, d’autre part, le calcul de toutes les statistiques utilisées.

2. Statistiques Euler-Mahoniennes

Si “Stat” est une statistique ensembliste, comme les quatre statistiques précédemment introduites, on forme les deux statistiques numériques # Stat et Σ Stat, telles que # Stat w (resp. Σ Stat w) est définie comme le cardinal de (resp. la somme des éléments dans) Stat w.

Avec “Ligne”, on retrouve des := # Ligne (le nombre de descentes) et maj := Σ Ligne (l’indice majeur). Avec “Iligne”, on pose traditionnellement ides := # Iligne, imaj := Σ Iligne. On introduit, en plus, les quatre statistiques définies sur SE_{n} : # Eul, Σ Eul, # Rise, Σ Rise. D’après la définition de la valeur Eulérienne donnée en (1.5) et (1.6), on observe que si w = x_{1}x_{2} … x_{n} ∈ SE_{n}, alors

(2.1)  Σ Eul w = x_{1} + x_{2} + ⋯ + x_{n},

une statistique que l’on note plus volontiers tot w (“tot” pour “total”). Quant à la statistique # Eul, que l’on note simplement “eul”, elle a déjà été introduite dans [Ha90] : soit w = x_{1}x_{2} … x_{n} un mot sousexcédent. Si n = 1, on pose eul w = 0 ; si n ≥ 2 et si l’on pose w′ := x_{1}x_{2} … x_{n−1} ∈ SE_{n−1}, de sorte que w = w′x_{n}, alors

(2.2)  eul(w′x_{n}) := \{ \begin{matrix}eul w′, & si x_{n} ≤ eul w′; \\ 1 + eul w′, & si x_{n} ≥ 1 + eul w′. \end{matrix}

On peut encore voir que eul w est la longueur du plus long sous-mot x_{i_{1}}x_{i_{2}} … x_{i_{k}} (1 ≤ i_{1} < i_{2} < ⋯ < i_{k}) tel que 1 ≤ x_{i_{1}}, 2 ≤ x_{i_{2}}, …, k ≤ x_{i_{k}}.

Soit inv σ le nombre d’inversions de la permutation σ. Par définitionmême de Invcode, on a immédiatement :

(2.3)  Σ Eul ∘ Invcode = inv .

On dit qu’une statistique bivariée (f, g) est Euler-mahonienne, si f et g sont définies sur un ensemble fini E_{n}, de cardinal n! et si sa fonction génératrice ∑ t^{f(w)}q^{g(w)} (w ∈ E_{n}), écrite sous la forme A_{n}(t, q) = ∑_{k≥0} A_{n,k}(q)t^{k}, satisfait la relation de récurrence

(2.4)  A_{n,k}(q) = [k + 1]_{q} A_{n−1,k}(q) + q^{k} [n − k]_{q} A_{n−1,k−1}(q)

pour 1 ≤ k ≤ n − 1, avec les conditions initiales : A_{n,0}(q) = 1 et A_{n,k}(q) = 0 pour k ≥ n. Dans (2.4), on a posé [k]_{q} := 0 pour k = 0 et [k]_{q} := 1 + q + ⋯ + q^{k−1} pour k ≥ 1. Posons

(t; q)_{n} := \{ \begin{matrix}1, & si n = 0 ; \\ (1 − t)(1 − tq) ⋯ (1 − tq^{n−1}), & si n ≥ 1. \end{matrix}

De façon équivalente (l’équivalence est facile à voir), on peut dire que (f, g) est Euler-mahonienne si le polynôme A_{n}(t, q) satisfait l’identité

(2.5)  \frac{A_{n}(t, q)}{(t; q)_{n+1}} = ∑_{r≥0} t^{r} ( [r + 1]_{q})^{n}.

On sait depuis Carlitz [Ca54] que la statistique (des, maj), égale encore à (# Ligne, Σ Ligne), est Euler-mahonienne sur S_{n}. La proposition suivante résulte alors de (1.9) et de (1.10).

Proposition 2.1. Les couples (ides, imaj), (eul ∘ Invcode, inv) sur S_{n} et (eul, tot), (#Rise, ΣRise) sur SE_{n} sont des statistiques Euler-Mahoniennes.

Se reportant toujours à la chaîne (1.9) et à (1.10), on obtient, en plus, les propriétés suivantes

Propriété 2.2. La bijection σ′ ↦ τ′ de S_{n} sur S_{n} satisfait

(2.6)  (Ligne, ides, imaj) σ′ = (Ligne, eul ∘ Invcode, inv) τ′;
(2.7) (des, maj, ides, imaj) σ′ = (des, maj, eul ∘ Invcode, inv) τ′.

La statistique “eul ∘ Invcode” a été introduite par Skandera [Sk01] sous le nom de “st”. Il avait aussi conjecturé qu’il existait une bijection σ′ ↦ τ′ satisfaisant (2.7). On peut donc répondre positivement à sa conjecture.

Propriété 2.3. La bijection σ′ ↦ w′ de S_{n} sur SE_{n} satisfait

(2.8)  (Ligne, ides, imaj) σ′ = (Rise, eul, tot) w′;
(2.9)  (des, maj, ides, imaj) σ′ = (# Rise, Σ Rise, eul, tot) w′.

Posons

(u; q_{1}, q_{2})_{r+1,s+1} := ∏_{0≤i≤r,0≤j≤s}(1 − uq_{1}^{i}q_{2}^{j}).

Comme démontré dans [GG78] (voir aussi [Ra80], [DF86]), l’identité

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

définit une suite de polynômes (A_{n}(t_{1}, t_{2}, q_{1}, q_{2})) (n ≥ 0) qui sont les fonctions génératrices de S_{n} par le quadruplet (des, maj, ides, imaj). En d’autres termes, on a : A_{n}(t_{1}, t_{2}, q_{1}, q_{2}) = ∑_{σ∈S_{n}} t_{1}^{des σ}t_{2}^{ides σ}q_{1}^{maj σ}q_{2}^{imaj σ}. L’existence de la bijection σ′ ↦ w′ permet donc d’obtenir le résultat suivant, apparemment difficile à obtenir directement.

Théorème 2.4. La fonction génératrice factorielle des polynômes générateurs des ensembles SE_{n} de mots sous-excédants (n ≥ 0) par le quadruplet (# Rise, Σ Rise, eul, tot) est donnée par l’expression (2.10).

Pour tout couple d’entiers r, n ≥ 0, notons \left[{n \atop r}\right] le q-coefficient binomial défini par :

\left[{n \atop r}\right] := \{ \begin{matrix}\frac{(q; q)_{n}}{(q; q)_{n−r} (q; q)_{r}} , & si 0 ≤ r ≤ n; \\ 0, & autrement. \end{matrix}

Soit L = {ℓ_{1} < ⋯ < ℓ_{k}} un sous-ensemble de l’intervalle {1, 2, …, n − 1}. On pose ℓ_{0} := 0 et ℓ_{k+1} := n et on désigne par N_{r}(L, n) la matrice (k + 1) × (k + 1) :

N_{r}(L, n) = ( \begin{matrix}\left[{ℓ_{1}−ℓ_{0}+r \atop r}\right] & \left[{ℓ_{2}−ℓ_{0}+r \atop r}\right] & … & \left[{ℓ_{k}−ℓ_{0}+r \atop r}\right] & \left[{ℓ_{k+1}−ℓ_{0}+r \atop r}\right] \\ 1 & \left[{ℓ_{2}−ℓ_{1}+r \atop r}\right] & … & \left[{ℓ_{k}−ℓ_{1}+r \atop r}\right] & \left[{ℓ_{k+1}−ℓ_{1}+r \atop r}\right] \\ 0 & 1 & … & \left[{ℓ_{k}−ℓ_{2}+r \atop r}\right] & \left[{ℓ_{k+1}−ℓ_{2}+r \atop r}\right] \\ ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & … & 1 & \left[{ℓ_{k+1}−ℓ_{k}+r \atop r}\right] \end{matrix} ) .

En particulier, N_{r}(∅, n) = \left[{n+r \atop r}\right].

Il résulte des Propriétés 2.2 et 2.3 que pour tout sous-ensemble L de {1, 2, …, n − 1} on a les égalités :

∑_{σ∈S_{n},Ligne σ=L} t^{ides σ}q^{imaj σ} = ∑_{σ∈S_{n},Ligne σ=L} t^{eul ∘ Invcode σ}q^{inv σ} = ∑_{w∈SE_{n},Rise w=L} t^{eul w}q^{tot w}.

Désignons par A_{L}(t, q) ce polynôme. Dans le dernier paragraphe, on établit le résultat suivant, qui entraîne d’ailleurs l’identité (2.5).

Théorème 2.5. On a :

(2.11)  \frac{A_{L}(t, q)}{(t; q)_{n+1}} = ∑_{r≥0} t^{r} det N_{r}(L, n).

3. Comment construire la bijection ϕ?

La construction de ϕ nécessite une analyse fine des propriétés du maj-codage. On la définit par récurrence sur n. Si n ≥ 2 et si σ = σ(1)σ(2) … σ(n) est une permutation d’ordre n telle que σ(n) = i, on pose σ = σ′ i, où, par conséquent, σ′ := σ(1)σ(2) … σ(n − 1). Si la bijection ϕ a été construite pour les permutations d’ordre inférieur ou égal à (n − 1), on l’étend, de façon naturelle, aux permutations de la suite 1, …, (i − 1), (i + 1), …, n à l’aide de la bijection réd_{i} définie dans l’introduction. En effet, si l’on pose ϕ_{i} := réd_{i}^{−1} ∘ϕ ∘ réd_{i}, on définit

ϕ(σ) = ϕ(σ′ i) := γ_{i}(ϕ_{i}(σ′)) i,

où γ_{i} est un réarrangement de la permutation ϕ_{i}(σ′) qu’il faut préciser. Remarquons que cette définition de ϕ préserve la dernière lettre i.

La première étape de la construction de ϕ est donc de définir τ′ := γ_{i}(ϕ_{i}(σ′)), puis τ := τ′ i. Remarquons que ϕ∘réd_{i}(σ′) est une permutation de 1, 2, …, n − 1, alors que τ′ est une permutation de 1, …, (i − 1), (i + 1), …, n. Dans toute la suite, nous adoptons la convention : Majcode τ′ := Majcode ϕ ∘ réd_{i}(σ′). Si l’on désigne par x(1) … x(i − 1)x(i + 1) … x(n) le maj-codage de τ′, on définit aussi

(3.1)  Majcode_{i} τ′ := x(1) … x(i − 1) • x(i + 1) … x(n),

où le gros point “•”, placé dans la i^{ième} position, satisfait l’inégalité • < 0. Cette convention s’avèrera très utile dans la suite, car on montrera que l’on a, en fait,

(3.2)  Iligne σ = Rise ∘ Majcode_{i} τ′.

Pour n ≥ 2, on partitionne S_{n} en deux classes disjointes S′_{n} et S′′_{n}. La première classe est formée de toutes les permutations σ telle que σ(n − 1) < σ(n) ou telles que σ(n) = 1 et donc S′′_{n} se compose de toutes les permutations σ telles que σ(n − 1) > σ(n) ≥ 2. Pour les permutations σ appartenant à S′_{n}, le réarrangement γ_{i} est simplement l’application identique, de sorte que ϕ(σ) := ϕ_{i}(σ′) i.

Pour les permutations σ appartenant à S′′_{n}, on détermine toujours τ′ = ϕ_{i}(σ′) et τ = τ′ i, une permutation qui appartient encore à S′′_{n}. Le réarrangement γ_{i}, qu’il faut appliquer à τ′, peut être visualisé en se reportant à la Figure 1, où l’on a reproduit la partie droite du graphe de la permutation τ. La lettre τ(j) est la lettre la plus à droite de la permutation τ qui soit inférieure à τ(n) = i ≥ 2. Cette lettre existe et est bien définie pour n ≥ 3. Soient l la plus petite lettre entre τ(j) et i, puis L la seconde plus petite lettre, si elle existe ; sinon, on pose L := n + 1.

On forme alors les (L − i − 1) permutations

(3.3)  \begin{aligned}τ_{i+1} & := (i + 1, i + 2) ⋯ (l − 2, l − 1)(l − 1, l) τ \\ … & … \\ τ_{l−2} & := (l − 2, l − 1)(l − 1, l) τ \\ τ_{l−1} & := (l − 1, l) τ \\ τ_{l} & := τ \\ τ_{l+1} & := (l + 1, l) τ \\ τ_{l+2} & := (l + 2, l + 1)(l + 1, l) τ \\ … & … \\ τ_{L−1} & := (L − 1, L − 2) ⋯ (l + 2, l + 1)(l + 1, l) τ \end{aligned}

qui se déduisent de τ par application de ces produits de transpositions. Comme elles se terminent toutes par i, on pose τ_{k} := τ′_{k} i pour k = i + 1, i + 2, …, L − 1. La construction de ϕ utilise la propriété suivante.

[figure: •; •; •; •; •; •; •; •; j; τ(j) = τ′(j); n−1; n; l; L; i; L−1; l−1; i+1; }; E] Fig. 1

Proposition 3.1. Les permutation τ_{i+1}, …, τ_{L−1} ont toutes même ligne de route (que τ). Leurs maj-codages sont tous distincts et il existe une bijection, que l’on peut explicitement construire, ψ : l ↦ p de l’intervalle {i + 1, i + 2, …, L − 1} sur lui-même, telle que

(3.4)  Rise ∘ Majcode_{i} τ′_{l} = Rise ∘ Majcode τ_{p}.

Le fait que ces permutations aient même ligne de route est évident, puisque chaque transposition appliquée ne permute que deux entiers consécutifs, qui sont non-adjacents dans la permutation. Une fois qu’une bijection l ↦ p de l’ensemble {i + 1, …, L − 1} sur lui-même est définie, la bijection ϕ cherchée est simplement donnée par : ϕ(σ) = τ_{p}, où p = ψ(l). Compte-tenu de (3.2) et (3.4), elle a alors la propriété : Iligne σ = Rise ∘ Majcode ϕ(σ). Le réarrangement γ_{i} qu’il faut définir est donc γ_{i}(ϕ_{i}(σ′)) = τ′_{p}.

Exemple. Considérons la permutation τ = 6, 4, 8, 7, 2, 1, 9, 5, 3 qui appartient à S′′_{9}. L’extrémité droite de son graphe est représentée dans la Figure 2. Les L − i − 1 = 5 permutations du tableau (3.3) sont données par

Ligne τ_{k} = 1 3 4 5 7 8
τ_{4} = (4, 5) τ = 6, 5, 8, 7, 2, 1, 9, 4, 3
τ_{5} = τ = 6, 4, 8, 7, 2, 1, 9, 5, 3

τ_{6} = (6, 5) τ = 5, 4, 8, 7, 2, 1, 9, 6, 3
τ_{7} = (7, 6) (6, 5) τ = 5, 4, 8, 6, 2, 1, 9, 7, 3
τ_{8} = (8, 7) (7, 6) (6, 5) τ = 5, 4, 7, 6, 2, 1, 9, 8, 3

[figure: •; •; •; •; 1; L = 9; l = 5; i = 3] Fig. 2

Elles ont toutes la même ligne de route : 1, 3, 4, 5, 7, 8. En laissant tomber la lettre 3 de la fin, on obtient les permutations τ′_{k}. La détermination des Majcode_{3} τ′_{k} et des Majcode τ_{k} donne le tableau suivant, où la ligne des montées, Rise w, apparaît au-dessus de chaque code w.

Majcode_{3} τ′_{4} = 1 0, 1, 3 •, 4 0, 5 2, 3, 7 2, 8 5, 7 ; Majcode τ_{4} = 1 0, 1, 3 0, 3, 5 3, 4, 7 3, 8 6, 8 ;
Majcode_{3} τ′_{5} = 1 0, 1, 3 •, 2, 5 0, 3, 7 2, 8 5, 7 ; Majcode τ_{5} = 1 0, 1, 3 0, 4 2, 4, 4, 7 3, 8 6, 8 ;
Majcode_{3} τ′_{6} = 1 0, 1, 3 •, 4 2, 3, 6 0, 7 2, 8 5, 7 ; Majcode τ_{6} = 1 0, 1, 3 0, 4 2, 5 3, 5, 7 3, 8 6, 8 ;
Majcode_{3} τ′_{7} = 1 0, 1, 3 •, 4 2, 3, 2, 7 0, 8 5, 7 ; Majcode τ_{7} = 1 0, 1, 3 0, 4 2, 3, 6 2, 6, 8 6, 8 ;
Majcode_{3} τ′_{8} = 1 0, 1, 3 •, 4 2, 3, 6 2, 5, 8 0, 7 ; Majcode τ_{8} = 1 0, 1, 3 0, 4 2, 3, 6 2, 7 5, 8 7, 8.

On constate que les ensembles des lignes de montées des maj-codages des τ′_{k}, d’une part, et des lignes de montées des maj-codages des τ_{k}, d’autre part, sont identiques. Reste à définir la bonne bijection (cf. § 6). On verra qu’elle repose sur la propriété classique qui veut que si l’on part d’une permutation de 1, 2, …, n et si l’on insére dans cette permutation, dans les (n + 1) interstices possibles, un élément distinct de ces n entiers, disons i + 1/2 avec i ≥ 0 entier, l’ensemble des lignes de montées des (n + 1) réarrangements obtenus ne dépend pas de i, mais seulement de la permutation initiale.

On observe aussi les deux faits suivants :

on passe de Majcode_{i} τ′_{k} à Majcode_{i} τ_{k} en remplaçant le gros point par 0, le zéro reproduit en gras par (k − 1) et en augmentant d’une unité les nombres à la droite de ce zéro gras.

on passe de Majcode_{i} τ′_{k} à Majcode_{i} τ′_{k+1} en transposant le zéro reproduit en gras et la lettre suivante ;

Ces deux faits sont démontrés dans les Propositions 5.2 et 5.3.

4. Construction de la bijection ϕ

Cette construction fait appel à la réduction “réd_{i}” et au maj-codage, dont les définitions ont été données dans l’Introduction. Une autre définition du maj-codage par étiquetage sera donnée au paragraphe 5.

Description de la bijection ϕ. Soit σ ∈ S_{n}. Si n = 1 ou 2, on pose ϕ(σ) = σ. Si n ≥ 3, on pose i := σ(n), σ′ := σ(1)σ(2) … σ(n − 1) et on définit τ′ := réd_{i} ∘ϕ ∘ réd_{i}^{−1}(σ′) et τ := τ′ i.

Si τ(n − 1) < τ(n) ou si τ(n) = 1, on pose : ϕ(σ) := τ.

Si τ(n − 1) > τ(n) ≥ 2, on détermine le plus grand entier j tel que τ(j) < i, puis la plus petite lettre l de τ entre τ(j) et τ(n) et la seconde plus petite lettre L, aussi entre τ(j) et τ(n). Si cette seconde plus petite lettre n’existe pas, on pose : L := n + 1. (Voir Figure 1.)

Si i + 1 = L − 1, on pose aussi : ϕ(σ) := τ.

On forme alors Majcode_{i} τ′ := x(1) … x(i − 1) • x(i + 1) … x(n). Si l = i + 1 ou [si i + 2 ≤ l ≤ L − 2 et x(l − 1) ≥ x(l + 1)], on détermine le plus long facteur croissant strict x(l + 1)x(l + 2) … x(p) du mot x(l + 1)x(l + 2) … x(L − 1), de sorte que l’on a, ou bien p = L − 1, ou bien l + 1 ≤ p ≤ L − 2 et x(p) ≥ x(p + 1). On pose alors :

(4.1)  ψ(l) := p;
(4.2)  ϕ(σ) := τ_{p} = (p, p − 1) ⋯ (l + 2, l + 1)(l + 1, l) τ.

Si l = L − 1 ou [si i + 2 ≤ l ≤ L − 2 et x(l − 1) < x(l + 1)], on détermine le plus long facteur décroissant au sens large x(p)x(p + 1) … x(l − 1) de x(i + 1)x(i + 2) … x(l − 1), de sorte que l’on a, ou bien p = i + 1, ou bien i + 2 ≤ p ≤ l − 1 et x(p − 1) > x(p). On pose alors

(4.3)  ψ(l) := p;
(4.4)  ϕ(σ) := τ_{p} = (p, p + 1) ⋯ (l − 2, l − 1)(l − 1, l) τ.

Noter que l’on a deux expressions pour τ_{p} suivant que l + 1 ≤ p ≤ L − 1 ou i + 1 ≤ p ≤ l − 1.

Donnons encore une description algorithmique, qui permet une programmation informatique quasiment immédiate.

ALGORITHME–ϕ : une permutation σ = σ(1)σ(2) … σ(n) étant donnée, l’algorithme suivant fournit la permutation τ := ϕ(σ).

(ϕ 1) Si n = 1, RETURN la permutation 1.

(ϕ 2) On pose i := σ(n) ; σ′ := σ(1)σ(2) … σ(n − 1) ; τ′ := réd_{i}^{−1} ϕ réd_{i}(σ′) ; τ := τ′ i;

(ϕ 2.1) Si τ(n − 1) < i ou i = 1, RETURN τ;

(ϕ 2.2) On pose j := max{j′ : 1 ≤ j′ ≤ n − 1, τ(j′) < i}; E := {τ(j + 1), τ(j + 2), …, τ(n − 1)}; l := min E; L := min(E \ {l} ∪ {n + 1}) ; x := Majcode_{i} τ′ = x(1) … x(i − 1) • x(i + 1) … x(n) ;

(ϕ 2.2.1) Si i + 1 = L − 1, RETURN τ;

(ϕ 2.2.2) Si l = i + 1 ou si [ i + 2 ≤ l ≤ L − 2 et x(l − 1) ≥ x(l + 1) ], τ := (l, l + 1) τ; p := l + 1 ; Tant que [ x(p) < x(p + 1) et p ≤ L − 2 ], faire

{τ := (p, p + 1) τ; p := p + 1 ;}

RETURN τ;

(ϕ 2.2.3) Si l = L − 1 ou si [ i + 2 ≤ l ≤ L − 2 et x(l − 1) < x(l + 1) ], τ := (l, l − 1) τ; p := l − 1 ; Tant que [ x(p − 1) ≥ x(p) et p ≥ i + 2 ], faire

{τ := (p, p − 1) τ; p := p − 1 ;}

RETURN τ;

5. Propriétés du maj-codage

Rappelons la construction du maj-codage par étiquetage, tel qu’elle est bien exposée, par exemple, dans l’article de Rawlings [R81]. Soit σ une permutation d’ordre n. Si n = 1, on pose Majcode 1 = 0. Supposons n ≥ 2 et notons σ^{−} := σ^{−}(1)σ^{−}(2) … σ^{−}(n − 1) la permutation d’ordre (n − 1) déduite de la permutation σ = σ(1)σ(2) … σ(n) d’ordre n par suppression de la lettre n. Posons σ^{−}(0) = σ^{−}(n) := 0. Soit (d + 1) le nombre d’entiers i tels que 0 ≤ i ≤ n − 1 et σ^{−}(i) > σ^{−}(i + 1) (on a toujours σ^{−}(n − 1) > σ^{−}(n) = 0, de sorte que d ≥ 0).

En lisant le mot σ^{−}(0)σ^{−}(1) … σ^{−}(n − 1)σ^{−}(n) de la droite vers la gauche, on maj-étiquette 0, 1, …, d les (d + 1) successions de deux lettres σ^{−}(i)σ^{−}(i + 1) telles que σ^{−}(i) > σ^{−}(i + 1) (0 ≤ i ≤ n − 1). On lit ensuite le mot σ^{−}(0)σ^{−}(1) … σ^{−}(n − 1)σ^{−}(n) de la gauche vers la droite et on maj-étiquette (d + 1), (d + 2), …, (n − 1), les (n − 1 − d) successions restantes σ^{−}(i) < σ^{−}(i + 1). Or, on passe de σ^{−} à σ en insérant n dans l’une des successions σ^{−}(i)σ^{−}(i + 1) (0 ≤ i ≤ n − 1) (et en supprimant les lettres σ^{−}(0), σ^{−}(n)). Soit y la maj-étiquette de la succession où n est inséré. On pose alors

Majcode σ := w^{−} y,

où, par récurrence, w^{−} est le maj-codage de σ^{−}.

Nous supposons n ≥ 2 et nous nous servons de cette définition par étiquetage pour comparer les maj-codages des permutations τ′ et τ, où τ′ = τ′(1) … τ′(i − 1)τ′(i + 1) … τ′(n) est une permutation de 1, …, (i−1), (i+1), …, n et où τ est la permutation de 1, 2, …, n obtenue en juxtaposant la lettre i à la droite de τ′, soit τ := τ′ i. On note x(1)x(2) … x(i − 1)x(i + 1) … x(n) le maj-codage de τ′.

Proposition 5.1. Si τ′(n) < i et si

Majcode_{i} τ′ = x(1)x(2) … x(i − 1) • x(i + 1) … x(n),

alors

(5.1)  Majcode τ′ i = x(1)x(2) … x(i − 1) 0 x(i + 1) … x(n)

et les lettres x(i + 1), …, x(n) sont supérieures ou égales à 1.

Démonstration. La proposition est évidente pour i = n. Supposons 1 ≤ i ≤ n − 1 et notons Sub_{k} τ′ le sous-mot de τ′ réduit aux lettres de τ′, inférieures ou égales à k. Par définition du maj-codage, on a Majcode Sub_{i−1} τ′ = x(1)x(2) … x(i − 1) and Majcode Sub_{i} τ′i = x(1)x(2) … x(i − 1)0, puisque i est juxtaposé à la droite de Sub_{i−1} τ′.

Supposons qu’il existe un entier j tel que i + 1 ≤ j ≤ n et x(j) = 0 ; considérons le plus grand entier j ayant cette propriété. Par définition du maj-codage, la permutation τ′ aurait une dernière lettre égale à j > i. Ceci contredit l’hypothèse : τ′(n) < i. Ainsi tous les entiers x(i + 1), …, x(n) sont supérieurs ou égaux à 1.

Pour chaque j ≥ i + 1, on a Sub_{j−1}(τ′i) = (Sub_{j−1} τ′) i. Dans la construction du maj-codage de τ′ (resp. de τ′i), aucune lettre j ≥ i + 1 ne peut être insérée à la droite de Sub_{j−1} τ′ (resp. à la droite de Sub_{j−1} τ′ i ni juste avant la lettre finale i). Par conséquent, le maj-étiquetage des entiers i + 1, i + 2, …, n est identique pour τ′ et τ′ i.

Nous comparons maintenant les maj-codages de τ′ et τ = τ′ i lorsque τ appartient à S′′_{n}, c’est-à-dire lorsque τ(n − 1) > τ(n) ≥ 2. Les lettres l et L conservent les significations données dans la définition de ϕ ou dans la Figure 1.

Proposition 5.2. Si τ appartient à S′′_{n}, la comparaison des maj-codages de τ′ (deuxième ligne) et de τ (troisième ligne) est indiquée dans la table suivante :

\begin{matrix}1 & … & i−1 & i & i+1 & … & l−1 & l & l+1 & … & L−1 & … & n \\ x(1) & … & x(i−1) & • & x(i+1) & … & x(l−1) & 0 & x(l+1) & … & x(L−1) & … & x(n) \\ x(1) & … & x(i−1) & 0 & x(i+1) & … & x(l−1) & l−1 & \overline{x}(l+1) & … & \overline{x}(L−1) & … & \overline{x}(n) \end{matrix}

où \overline{x}(k) := 1+x(k). De plus, les lettres x(i+1), …, x(L−1) sont toutes au moins égales à 1 ; enfin, si L ≤ n, on a x(L) = L − 2 ou 0 ; si l + 1 ≤ L − 1, on a : x(l + 1) ≤ l − 2.

Démonstration. Le sous-mot Sub_{l−1} τ′ se termine par τ(j) < i (cf. Fig. 1). Il résulte de la Proposition 5.1 que le maj-codage de Sub_{l−1} τ vaut

x(1) … x(i − 1) 0 x(i + 1) … x(l − 1)

et les lettres x(i + 1), …, x(l − 1) sont toutes plus grandes que 1. Lorsque l’on construit le maj-codage de τ, la lettre l est insérée dans la montée la plus à droite τ(j) < i = τ(n). On crée ainsi une nouvelle descente, qui obtient la maj-étiquette 1. Comme cette descente la plus à droite n’apparaît pas dans τ′, chaque lettre m ≥ l + 1 obtient une maj-étiquette r+1 dans le maj-codage de τ, chaque fois qu’elle obtient la maj-étiquette r dans τ′.

Maintenant, ou bien L = n + 1, ou bien L ≤ n et cette lettre se trouve à droite de τ′(j) dans τ′. On a donc x(L) = L − 2 ou 0. Supposons enfin i + 1 < L − 1. Lors de la construction du maj-codage de τ′, la lettre (l + 1) n’a pas été insérée dans la montée la plus à droite τ′(j) < i, qui a la maj-étiquette (l − 1). On a donc x(l + 1) ≤ l − 2.

Proposition 5.3. Si τ = τ′ i appartient à S′′_{n} et si l + 1 ≤ L − 1, la comparaison des maj-codages de τ′ (deuxième ligne) et de υ′ := (l, l+1) τ′ (troisième ligne) est donnée dans la table :

\begin{matrix}1 & … & i−1 & i & i+1 & … & l−1 & l & l+1 & … & L−1 & … & n \\ x(1) & … & x(i−1) & • & x(i+1) & … & x(l−1) & 0 & x(l+1) & … & x(L−1) & … & x(n) \\ x(1) & … & x(i−1) & • & x(i+1) & … & x(l−1) & x(l+1) & 0 & … & x(L−1) & … & x(n) \end{matrix}

Démonstration. Il existe deux mots w_{1}, w_{2}, avec w_{2} non-vide, tels que

Sub_{l+1} τ′ = w_{1} (l + 1) w_{2} l et Sub_{l} υ′ = w_{1} l w_{2}.

Comme l’insertion de l dans Sub_{l−1} τ′ crée une montée, de maj-étiquette maxima, le maj-étiquetage de (l + 1) dans Sub_{l} τ′ et celui de l dans Sub_{l−1} υ′ sont identiques, tous deux égaux à x(l + 1). Par ailleurs, la maj-étiquette de (l + 1) dans υ′ est 0.

De même, le maj-codage de (l − 1, l) τ′ vaut

\begin{matrix}1 & … & i−1 & i & i+1 & … & l−2 & l−1 & l & … & L−1 & … & n \\ x(1) & … & x(i−1) & • & x(i+1) & … & x(l−2) & 0 & x(l+1) & … & x(L−1) & … & x(n) \end{matrix}

et celui de (i + 1, i + 2) ⋯ (l − 2, l − 1)(l − 1, l) τ′

1 … i−1 i i+1 i+2 … l  l+1 … L−1 … n
x(1) … x(i−1) • 0 x(i+1) … x(l−1) x(l+1) … x(L−1) … x(n)

que l’on récrit désormais :

y(1) … y(i−1) • 0 y(i+2) … y(l) y(l+1) … y(L−1) … y(n)

Utilisant cette nouvelle expression et conservant les notations (2.3), on obtient ainsi le résultat suivant.

Proposition 5.4. Les maj-codages des permutations τ′_{i+1}, …, τ′_{l−1}, τ′_{l}, τ′_{l+1}, …, τ′_{L−1} sont donnés par les lignes de la matrice

1 … i−1 i i+1 … l−1  l  l+1 … L−1 … n
y(1) … y(i−1) • 0 … y(l−1) y(l) y(l+1) … y(L−1) … y(n)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
y(1) … y(i−1) • y(i+2) … 0  y(l) y(l+1) … y(L−1) … y(n)
y(1) … y(i−1) • y(i+2) … y(l)  0 y(l+1) … y(L−1) … y(n)
y(1) … y(i−1) • y(i+2) … y(l) y(l+1) 0 … y(L−1) … y(n)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
y(1) … y(i−1) • y(i+2) … y(l) y(l+1) y(l+2) … 0 … y(n)

tandis que les maj-codages des permutations τ_{i+1}, …, τ_{l−1}, τ_{l}, τ_{l+1}, …, τ_{L−1} sont donnés par les lignes de la matrice

1 … i−1 i i+1 … l−1  l  l+1 … L−1 … n
y(1) … y(i−1) 0 i … \overline{y}(l−1) \overline{y}(l) \overline{y}(l+1) … \overline{y}(L−1) … \overline{y}(n)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
y(1) … y(i−1) 0 y(i+2) … l−2 \overline{y}(l) \overline{y}(l+1) … \overline{y}(L−1) … \overline{y}(n)
y(1) … y(i−1) 0 y(i+2) … y(l) l−1 \overline{y}(l+1) … \overline{y}(L−1) … \overline{y}(n)
y(1) … y(i−1) 0 y(i+2) … y(l) y(l+1) l … \overline{y}(L−1) … \overline{y}(n)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
y(1) … y(i−1) 0 y(i+2) … y(l) y(l+1) y(l+2) … L − 2 … \overline{y}(n)

De plus, on a les inégalités suivantes :

(5.2) 1 ≤ y(i + 2) ≤ i − 1, 1 ≤ y(i + 3) ≤ i, …, 1 ≤ y(L − 1) ≤ L − 4; (5.3) y(L) = 0 ou y(L) = L − 2.

6. La correspondance entre lignes de montées

Se reportant à l’énoncé de la Proposition 5.4, nous nous proposons de montrer qu’à toute ligne du premier tableau correspond biunivoquement une ligne du second tableau ayant même ligne de route. Observons, tout d’abord, qu’avec la convention • < 0 et l’inégalité 1 ≤ y(i + 2), il y a une descente en position i − 1 et une montée en i dans toutes les lignes des deux tableaux.

Supposons L ≤ n. Si y(L) = 0, alors y(L − 1) ou 0 ≥ y(L) dans le premier tableau et \overline{y}(L − 1) ou L − 2 ≥ 1 = \overline{y}(L) dans le second tableau, puisque i ≤ 2 entraîne L ≥ 3. Ainsi toutes les lignes des deux tableaux ont une descente en position L − 1. Si y(L) = L − 2, alors y(L − 2) < y(L), d’après (5.2) et donc \overline{y}(L − 2) < \overline{y}(L). Par ailleurs, 0 ≤ y(L) et L − 2 < L − 1 = \overline{y}(L), toujours d’après (5.2). Toutes les lignes des deux tableaux ont alors une montée en position L − 1.

Il suffit donc de définir une bijection entre les lignes du premier et du second tableau réduites aux colonnes d’indices i + 1, i + 2, …, L − 1. D’après (5.2), on a y(i + 2) ≤ i − 1, d’où i ≥ \overline{y}(i + 2). De même, pour i + 3 ≤ l ≤ L − 2, on a y(l) ≤ l − 3 et y(l + 1) ≤ l − 2, d’où y(l) < l − 1 et l − 1 ≥ \overline{y}(l + 1). Enfin, y(L − 1) < L − 2. Il en résulte qu’il suffit de définir une bijection, qui conserve la ligne de montées, entre les lignes notées B′_{i+1}, …, B′_{L−1} et B_{i+1}, …, B_{L−1}, des matrices bordées

B′ :=  ( \begin{matrix}i + 1 & i + 2 & … & L − 2 & L − 1 \\ i + 1 & 0 & y(i + 2) & … & y(L − 2) & y(L − 1) \\ i + 2 & y(i + 2) & 0 & … & y(L − 2) & y(L − 1) \\ … & . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . \\ L − 2 & y(i + 2) & y(i + 3) & … & 0 & y(L − 1) \\ L − 1 & y(i + 2) & y(i + 3) & … & y(L − 1) & 0 \end{matrix} )

B :=  ( \begin{matrix}i + 1 & i + 2 & … & L − 2 & L − 1 \\ i + 1 & ∞ & y(i + 2) & … & y(L − 2) & y(L − 1) \\ i + 2 & y(i + 2) & ∞ & … & y(L − 2) & y(L − 1) \\ … & . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . \\ L − 2 & y(i + 2) & y(i + 3) & … & ∞ & y(L − 1) \\ L − 1 & y(i + 2) & y(i + 3) & … & y(L − 1) & ∞ \end{matrix} )

où on a supprimé les barres sur les lettres, devenues inutiles pour la seule comparaison des lignes de montées et aussi remplacé les coefficients diagonaux dans la seconde matrice par le symbole ∞.

Pour obtenir les lignes de la matrice B′ (resp. B), on part du mot y(i + 2)y(i + 3) … y(L − 1) et on insère la lettre 0 (resp. ∞) dans les différents (L − i − 1) interstices. Ceci implique, en particulier, que les lignes des matrice B′ et B ont des lignes de montées distinctes.

La construction de la bijection s’inspire du principe bien connu pour les permutations, qui veut que si l’on insère une lettre quelconque, mais distincte de toutes les lettres présentes, dans les (L − i − 1) interstices, on obtient toujours le même ensemble de lignes de montées pour les (L−i−1) mots ainsi formés.

On définit alors des lettres soulignées, que l’on entrelace avec les entiers de la façon suivante :

\underline{0} = 0 < 1 < \underline{1} < 2 < \underline{2} < ⋯ < L − 3 < \underline{L − 3} < L − 2 < \underline{L − 2} = ∞.

Soit w a \underline{m} b w′ la ligne déduite de B′_{l} par le remplacement du 0 par \underline{m} et où le symbole −∞ a été mis en début et en fin de ligne, de sorte que les lettres a et b sont toujours définies et les mots w, w′ éventuellement vides.

On pose alors

δ(w a \underline{m} b w′) = \{ \begin{matrix}w a m + 1 \underline{m + 1} b w′, & si a, b ≠ m + 1 ; \\ w a m + 1 \underline{m + 1} w′, & si a ≠ b = m + 1 ; \\ w \underline{m + 1} m + 1 b w′, & si b ≠ a = m + 1 ; \\ w m + 1 m + 1 \underline{m + 1} w′, & si a = b = m + 1. \end{matrix}

Il est immédiat que la transformation δ préserve la ligne des montées et est bijective. La bijection ψ : l ↦ p est simplement donnée par :

(6.1)  ψ(l) = p si et seulement si δ^{L−2}(B′_{l}) = B_{p}.

Exemple. Prenons i = 2, L = 9 et B′_{i+1} = B′_{3} = 0, 1, 4, 4, 5, 1, de sorte que B′_{5} = 1, 4, 0, 4, 5, 1. On obtient :

δ^{3}(B′_{5}) = 1, 4, \underline{3}, 4, 5, 1
δ^{4}(B′_{5}) = 1, 4, 4, \underline{4}, 5, 1
δ^{5}(B′_{5}) = 1, 4, 4, 5, \underline{5}, 1
δ^{7}(B′_{5}) = 1, 4, 4, 5, \underline{7}, 1 = B_{7}.

d’où ψ(5) = 7. Avec cette bijection ψ bien définie, la Proposition 3.1 est démontrée. On peut vérifier que cette définition est exactement la même que celle donnée dans l’algorithme de ϕ au paragraphe 4.

7. Fin de la démonstration du Théorème 1.1

Reprenons la définition de ϕ donnée au paragraphe 3. On peut supposer n ≥ 3. Partant d’une permutation σ d’ordre n se terminant par σ(n) = i, on définit une permutation τ = τ′ i, se terminant aussi par la lettre i. Puisque, par induction, ϕ a été appliqué à la réduction de σ(1)σ(2) … σ(n − 1), on a aussi : σ(n − 1) = τ(n − 1). Par conséquent,

(7.1)  Ligne σ = Ligne τ.

D’autre part, Iligne σ = (réd_{i}^{−1} Iligne réd_{i} σ′) ∪ {i} \ {i − 1}, de plus, par récurrence, on a : Iligne réd_{i} σ′ = Rise ∘ Majcode(réd_{i} τ′). Comme i est aussi la dernière lettre de τ, on en déduit

Iligne σ = réd_{i}^{−1} Rise ∘ Majcode(réd_{i} τ′) ∪ {i} \ {i − 1}
= Rise ∘ Majcode_{i} τ′,

qui est la relation (3.2).

Si σ appartient à S′_{n} et se termine par i, alors ϕ(σ) = τ = τ′ i et naturellement Rise ∘ Majcode_{i} τ′ = Rise ∘ Majcode τ. La relation (1.4) est établie d’après (3.2) et (7.1).

Si σ appartient à S′′_{n}, on a ϕ(σ) = τ_{p}, où, avec les notations de la Proposition 3.1, on a τ_{l} := τ et p = ψ(l). La relation (1.4) résulte encore de (3.2) et (7.1) et du fait que τ_{p} a même ligne de route que τ.

Remarque. La transformation Ψ introduite dans [Fo68], définie sur toute classe de réarrangements de mots et à valeurs dans la même classe, satisfait imaj w = inv Ψ(w). Lorsqu’on la restreint au groupe symétrique, on sait (cf. [FS78]) qu’elle satisfait l’identité

(Ligne, imaj) σ = (Ligne, inv) Ψ(σ).

Posons w′′ := Invcode ∘Ψ(σ). On en déduit l’identité

(Ligne, imaj) σ = (Rise, tot) w′′,

mais, en général, ides σ ≠ eul w′′. La bijection σ′ ↦ w′ définie dans la Propriété 2.3 a donc une propriété supplémentaire.

8. Un calcul analytique

Établissons le Théorème 2.5, lorsque le polynôme A_{L}(t, q) est le polynôme générateur des permutations de ligne de route L par le couple (ides, imaj). On réadapte une technique de calcul de fonctions symétriques, que Désarménien (cf. [Lo02], chap. 11) a utilisée dans le cas t = 1.

Il est bien connu (voir, par exemple, [Lo02], p. 333) ou vite vérifié que l’on a :

\left[{ℓ + r \atop r}\right] = ∑_{r≥b_{1}≥···≥b_{ℓ}≥0} q^{b_{1}+···+b_{r}}.

Reprenons les notations de l’introduction, où L = {ℓ_{1}, …, ℓ_{k}} désigne un sous-ensemble de l’intervalle {1, 2, …, n − 1} et où ℓ_{0} := 0 et ℓ_{k+1} := n. Par ailleurs, désignons par W_{r}(L, n) l’ensemble des mots w = w_{1}w_{2} … w_{n}, de longueur n, dont les lettres sont des entiers positifs qui satisfont les inégalités

(∗)_{(L,n)} r ≥ w_{1} ≥ ⋯ ≥ w_{ℓ_{1}} ≥ 0; r ≥ w_{ℓ_{1}+1} ≥ ⋯ ≥ w_{ℓ_{2}} ≥ 0; …

r ≥ w_{ℓ_{k}+1} ≥ ⋯ ≥ w_{n} ≥ 0;

w_{ℓ_{1}} < w_{ℓ_{1}+1}, w_{ℓ_{2}} < w_{ℓ_{2}+1} , …, w_{ℓ_{k}} < w_{ℓ_{k}+1}.

Proposition 8.1. On a l’identité : ∑_{w∈W_{r}(L,n)} q^{tot w} = det N_{r}(L, n).

Démonstration. La proposition est évidemment vraie pour k = 1. Pour k ≥ 2, on développe le déterminant de N_{r}(L, n) suivant les éléments de la dernière ligne. Par récurrence, on obtient

det N_{r}(L, n) = det N_{r}(\{ℓ_{1}, …, ℓ_{k−1}\}, ℓ_{k})\left[{ℓ_{k+1} − ℓ_{k} + r \atop r}\right]

− det N_{r}({ℓ_{1}, …, ℓ_{k−1}}, n).

La proposition est ainsi prouvée, puisque le premier (resp. le second) terme du membre de droite est le polynôme générateur des mots w = w_{1}w_{2} … w_{n} satisfaisant les conditions (∗)_{(L,n)}, sauf éventuellement (resp. sauf expressément) la sous-condition w_{ℓ_{k}} < w_{ℓ_{k}+1}.

Nous appliquons maintenant aux mots de W_{r}(L, n) la bijection qui les envoie sur des couples (σ, s), où σ est une permutation de 1, 2, …, n, de ligne de route égale à L et où s = s_{1}s_{2} … s_{n} est un mot décroissant ayant les propriétés :

(8.1) r ≥ s_{1} ≥ s_{2} ≥ ⋯ ≥ s_{n} ≥ 0; Ligne σ = L; i ∈ Iligne σ ⇒ s_{i} > s_{i+1}.

Pour définir le couple (σ, s) correspondant à w = w_{1}w_{2} … x_{n} ∈ W_{r}(L, n), on procède comme suit : supposons que le réarrangement croissant de w soit de la forme i_{1}^{a_{1}} … i_{m}^{a_{m}}, avec i_{1} < ⋯ < i_{m} et a_{1} ≥ 1, …, a_{m} ≥ 1. On lit w de gauche à droite, en donnant les étiquettes 1, 2, …, a_{m} aux a_{m} lettres rencontrées égales à i_{m}; on continue, toujours de gauche à droite, en donnant les étiquettes a_{m}+1, …, a_{m}+a_{m−1} aux a_{m−1} lettres rencontrées égales à i_{m−1} et ainsi de suite. La lecture finale de ces étiquettes de gauche à droite fournit une permutation σ = σ(1)σ(2) … σ(n). Le mot s est simplement défini comme le réarrangement décroissant du mot w.

Exemple. Soient n = 9, r = 8, L = \{2, 5, 7\} et ( \begin{matrix}L \\ w \end{matrix} ) = ( \begin{matrix}& 2 & & & 5 & & 7 \\ 5 & 5 & 7 & 4 & 1 & 3 & 0 & 4 & 4 \end{matrix} )

un mot de N_{8}(L, 9). La permutation σ s’écrit ( \begin{matrix}L \\ σ \end{matrix} ) = ( \begin{matrix}& 2 & & & 5 & & 7 \\ 2 & 3 & 1 & 4 & 8 & 7 & 9 & 5 & 6 \end{matrix} )

et le mot s par ( \begin{matrix}Iligne σ \\ s \end{matrix} ) = ( \begin{matrix}1 & & & & & 6 & 7 \\ 7 & 5 & 5 & 4 & 4 & 4 & 3 & 1 & 0 \end{matrix} ). Les éléments de Iligne σ

ont été reproduits en gras.

On se persuade aisément que w ↦ (σ, s) est une bijection de W_{r}(L, n) sur les couples (σ, s) ayant la propriété (8.1). Une démonstration en est donnée par Désarménien (voir [Lo02], Théoréme 11.3.2), dans le cas où les lettres du mot w ne sont pas majorées par un entier r.

Compte tenu des Propriétés 2.2 et 2.3, pour démontrer le Théorème 2.5, il suffit d’établir la proposition suivante.

Proposition 8.2. On a :

\frac{∑_{σ, Ligne σ=L} t^{ides σ} q^{imaj σ}}{(t; q)_{n+1}} = ∑_{r≥0} t^{r} det N_{r}(L, n).

Démonstration. Là encore, c’est une technique déjà utilisée dans la théorie des fonctions symétriques qui conduit au résultat (voir [Lo02], pp. 371-372 pour la version dite non bornée et aussi [DF85], Théorème 4.1, ou encore [Ma95], p. 82, lorsque l’on manipule des tableaux). On part d’un couple (σ, s) ayant les propriétés (8.1) et on appelle d = d_{1}d_{2} … d_{n} le mot dont les lettres d_{i} sont définies par

d_{i} := \{ \begin{matrix}s_{i} − s_{i+1} − χ(i ∈ Iligne σ), & si 1 ≤ i ≤ n − 1 ; \\ s_{n}, & si i = n. \end{matrix}

On a alors d_{1} + ⋯ + d_{n} + ides σ = s_{1} ; on peut donc poser d_{0} := r − s_{1} ≥ 0 et ainsi d_{0}+d_{1}+⋯+d_{n}+ides σ = r. Par ailleurs, 1·d_{1}+2·d_{2}+⋯+n·d_{n}+ imaj σ = tot s. L’application (σ, s) ↦ (σ, (d_{0}, d_{1}, …, d_{n})) est une bijection des couples (σ, s) satisfaisant (8.1) sur les couples (σ, (d_{0}, d_{1}, …, d_{n})) tels que Ligne σ = L et où les entiers d_{0}, d_{1}, …, d_{n} sont positifs et satisfont d_{0} + d_{1} + ⋯ + d_{n} + ides σ = r. On en tire :

∑_{r≥0} t^{r} det N_{r}(L, n) = ∑_{r≥0} t^{r} ∑_{w∈W_{r}(L,n)} q^{tot w} = ∑_{r≥0} t^{r} ∑_{(σ,s)} q^{tot s}

= ∑_{r≥0} ∑_{σ} ∑_{d_{0},...,d_{n}} t^{d_{0}+···+d_{n}+ides σ}q^{1.d_{1}+···+n.d_{n}+imaj σ}

= ∑_{σ} t^{ides σ}q^{imaj σ} ∑_{r≥ides σ} ∑_{{d_{0}+···+d_{n} \atop =r−ides σ}} t^{d_{0}}(tq)^{d_{1}} ⋯ (tq^{n})^{d_{n}}

= ∑_{σ} t^{ides σ}q^{imaj σ} \frac{1}{(t; q)_{n+1}} .

Remarque. L’identité (2.11) a été ainsi démontrée lorsque le polynôme A_{L}(t, q) est le polynôme générateur suivant le couple (ides, imaj). La Propriété 2.2 permet de conclure que l’identité est encore vraie lorsque A_{L}(t, q) est le polynôme générateur suivant le couple (eul ∘ Invcode, inv). Nous ne proposons pas de méthode de calcul direct dans ce dernier cas, alors que la spécialisation de (2.11) pour t = 1, à savoir A_{L}(q)/(q; q)_{n} = det N, où N = (N_{i,j}) (1 ≤ i, j ≤ k + 1) est la matrice (k + 1) × (k + 1) donnée par

N_{i,j} := \{ \begin{matrix}1/(q; q)_{ℓ_{j}−ℓ_{i−1}}, & si i ≤ j; \\ 1, & si i = j + 1 ; \\ 0, & autrement ; \end{matrix}

peut être obtenue lorsque A_{L}(q) est, ou bien le polynôme générateur suivant “imaj”, ou bien suivant “inv” (cf. [Lo02], chap. 11). Notons encore que le calcul de A_{L}(q) suivant “inv” est aussi fait dans Stanley ([St86], p. 70) et qu’il q-généralise le vieux résultat de MacMahon ([Mac15], p. 190).

Remarquons, enfin, que si l’on somme l’identité de la Proposition 8.2, en remplaçant toutefois det N_{r}(L, n) par son expression de la Proposition 8.1, sur tous les sous-ensembles L ⊂ {1, …, n − 1}, on obtient, de nouveau, l’identité des polynômes q-Eulériens (2.5).

Un exemple numérique

La tableau suivant donne la construction complète de ϕ(σ) pour σ = 649821753 en utilisant l’algorithme-ϕ décrit dans la paragraphe 4. Il doit être lu colonne par colonne de la gauche vers la droite. On note que le calcul de ϕ(réd_{i}(σ′)) utilise la valeur obtenue dans la colonne suivante. On obtient ϕ(σ) = 658721943.

σ  649821753 53872164 4376215 436521 32541 2143 213  21
i  3  4  5  1  1  3  3  1
réd^{i}(σ′) 53872164 4376215 436521 32541 2143 213  21  1
ϕ(réd_{i}(σ′)) 53762184 4376215 436521 32541 2143 213  21  1
τ′  64872195 5387216 437621 43652 3254 214  21  2
τ  648721953 53872164 4376215 436521 32541 2143 213  21
\begin{matrix}τ(n−1) < i \\ ou i = 1? \end{matrix}  Non  Non  Oui  Oui Oui Non Oui Oui
(j, l, L)  (6, 5, 9) (6, 6, 9)  −  −  − (2, 3, 5) −  −
i+1=L−1?  Non  Non  −  −  −  Oui  −  −
x  01•203257 012•3025 −  −  −  −  −  −

RETURN par (ϕ2.2.3) (ϕ2.2.2) (ϕ2.1) (ϕ2.1) (ϕ2.1) (ϕ2.2.1) (ϕ2.1) (ϕ2.1)

ϕ(σ) =?τ  (45)τ (87)(76)τ  τ  τ  τ  τ  τ  τ
ϕ(σ)  658721943 53762184 4376215 436521 32541 2143 213  21

Calcul des statistiques utilisées. Pour σ = 649821753, on obtient :

w = Invcode σ = 0 1 0 1 4 5 2 4 6;
v = Majcode σ = 0 1 0 2 4 4 6 5 6;
Iligne σ = {1, 3, 5, 7, 8};
Rise w = Eul v = Ligne σ = {1, 3, 4, 5, 7, 8};
Eul w = {1, 3, 4, 7, 8}.

D’où

des σ = # Ligne σ = # Eul v = # Rise w = 6; maj σ = Σ Ligne σ = Σ Eul v = Σ Rise w = 28; ides σ = 5; imaj σ = 24; inv σ = tot w = Σ Eul w = 23; eul w = # Eul w = 5.

Le calcul suivant pour ϕ(σ) = 658721943 illustre l’identité (1.4).

Ligne ϕ(σ) = {1, 3, 4, 5, 7, 8} = Ligne σ;
t = Majcode ϕ(σ) = 0 1 0 3 3 4 3 6 8;
Rise t = {1, 3, 5, 7, 8} = Iligne σ.

Remerciements. Le premier auteur remercie Doron Zeilberger pour d’utiles discussions, qui sont à l’origine de cet article. Il remercie également Jean-Pierre Bourguignon, Michel Broué, François Digne, Guy Henniart, Bernhard Keller, Yvette Kosmann-Schwarzbach et Marc Rosso d’avoir organisé ce beau Colloque des 17 et 18 juin 2002 à Paris en l’honneur de Pierre Cartier.

Bibliographie

[AR01] Ron M. Adin and Yuval Roichman. — The flag major index and group actions on polynomial rings, Europ. J. Combin., vol. 22, 2001, p. 431–446.

[ABR01] Ron M. Adin, Francesco Brenti and Yuval Roichman. — Descent Numbers and Major Indices for the Hyperoctahedral Group, Adv. in Appl. Math., vol. 27, 2001, p. 210–224.

[Br94] Francesco Brenti. — q-Eulerian Polynomials Arising from Coxeter Groups, Europ. J. Combinatorics, vol. 15, 1994, p. 417–441.

[Ca54] L. Carlitz. — q-Bernouli and Eulerian numbers, Trans. Amer. Math. Soc., vol. 76, 1954, p. 332–350.

[Ca62] Pierre Cartier. — Fluctuations dans les suites de variables aléatoires indépendantes, Séminaire Bourbaki [Exposés 241–258, Paris. 1962/1963], exposé n^{o} 241, p. 241–01-18. — New York, Amsterdam, Benjamin, 1966.

[Ca72] Pierre Cartier. — On the structure of free Baxter algebras, Advances in Math., vol. 9, 1972, p. 253–265.

[Ca80] Pierre Cartier. — Arrangements d’hyperplans : un chapitre de géométrie combinatoire, Séminaire Bourbaki [Exposés 551–578, Paris. 1980/1981], exposé n^{o} 561, p. 561–01-22. — Berlin, Springer-Verlag, 1982 (Lecture Notes in Math., 901).

[Ca82] Pierre Cartier. — La théorie classique et moderne des fonctions symétriques, Séminaire Bourbaki [Exposés 597–600, Paris. 1982/1983], exposé n^{o} 597, p. 597– 01-24. — Paris, N. Bourbaki, 1983.

[Ca90] Pierre Cartier. — Nouvelles aventures au pays des q-analogues, Sém. Lothar.

Comb., B23a, 1990, 28 pages. [http ://www.mat.univie.ac.at/~slc].

[Ca91] Pierre Cartier. — Démonstration “automatique” d’identités et fonctions hypergéométriques [d’après Zeilberger], Séminaire Bourbaki [Exposés 745–749, Paris. 1991/1992], exposé n^{o} 746, p. 746–01-43. — Paris, N. Bourbaki, 1991.

[Ca00] Pierre Cartier. — Mathemagics, Sém. Lothar. Comb., B44d, 2000, 71 pages.

[http ://www.mat.univie.ac.at/~slc].

[CaFo69] Pierre Cartier et Dominique Foata. — Problèmes combinatoires de permutations et réarrangements. — Berlin, Springer-Verlag, 1969 (Lecture Notes in Math., 85).

[Di90] Volker Diekert. — Combinatorics on Traces. — Berlin, Springer-Verlag, 1990 (Lecture Notes in Computer Science, 454).

[DF85] Jacques Désarménien et Dominique Foata. — Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. Math. France, vol. 113, 1985, p. 3-22.

[Fo68] Dominique Foata. — On the Netto inversion number of a sequence, Proc. Amer. Math. Soc., vol. 19, 1968, p. 236–240.

[FH97] Dominique Foata et Guo-Niu Han. — Calcul basique des permutations signées, I : longueur et nombre d’inversions, Adv. in Appl. Math., vol. 18, 1997, p. 489–509.

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

[GG79] Adriano M. Garsia and Ira Gessel. — Permutations Statistics and Partitions, Adv. in Math., vol. 31, 1979, p. 288–305.

[Ha90] Guo-Niu Han. — Distribution Euler-mahonienne : une correspondance, C. R. Acad. Sci. Paris, vol. 310, 1990, p. 311–314.

[La01] Bodo Lass. — Calcul Combinatoire Ensembliste, Thèse Univ. Strasbourg, 2001. Prépubl. IRMA 2000/043, 147 pages.

[Le60] D. H. Lehmer. — Teaching combinatorial tricks to a computer, Proc. Sympos. Appl. Math., vol. 10, 1960, p. 179–193. Amer. Math. Soc., Providence, R.I.

[Lo02] M. Lothaire. — Algebraic Combinatorics on Words. — Cambridge Univ. Press, 2002 (Encyclopedia of Math. and its Appl., 90).

[Ma95] Ian G. Macdonald. — Symmetric Functions and Hall Polynomials, Second Edition. — Clarendon Press, Oxford, 1995.

[Mac15] P. A. MacMahon. — Combinatory Analysis, vol. 1. — Cambridge Univ. Press, 1915.

[Ra81] Don P. Rawlings. — Generalized Worpitzky identities with applications to permutation enumeration, Europ. J. Comb., vol. 2, 1981, p. 67-78.

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

[Re93b] V. Reiner. — Signed permutation statistics and cycle type, Europ. J. Combinatorics, vol. 14, 1993, p. 569–579.

[Re93c] V. Reiner. — Upper binomial posets and signed permutation statistics, Europ. J. Combinatorics, vol. 14, 1993, p. 581–588.

[Re95a] V. Reiner. — Descents and one-dimensional characters for classical Weyl groups, Discrete Math., vol. 140, 1995, p. 129–140.

[Re95b] V. Reiner. — The distribution of descents and length in a Coxeter group, Electronic J. Combinatorics, vol. 2, 1995, # R25.

[http ://www.emis.de/journals/EJC/].

[Sc77] M.-P. Schützenberger. — La correspondance de Robinson, Combinatoire et Représentation du Groupe Symétrique. [Actes Table Ronde Strasbourg. 1976], p. 59–113. Berlin, Springer-Verlag, 1977 (Lecture Notes in Math., 579).

[Sk01] Mark Skandera. — An Eulerian partner for inversions, Sém. Lothar. Combin.,

vol. 46, B46d, 2001, 19 pages. [http ://www.mat.univie.ac.at/~slc].

[Sp56] Frank Spitzer. — A combinatorial lemma and its applications to Probability Theory, Trans. Amer. Math. Soc., vol. 82, 1956, p. 323–339.

[St73] Richard P. Stanley. — Acyclic orientations of graphs, Discrete Math., vol. 5, 1973, p. 171–178.

[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. — Wadsworth & Brooks, 1986.

[StE94] Einar Steingrímsson. — Permutation Statistics of Indexed Permutations, Europ. J. Combinatorics, vol. 15, 1994, p. 187–205.

[StJ92] John Stembridge. — Eulerian numbers, tableaux, and the Betti numbers of a toric variety, Discrete Math., vol. 99, 1992, p. 307–320.

[Ze90] D. Zeilberger. — A holonomic system approach to special functions identities, J. Comput. and Appl. Math., vol. 32, 1990, p. 321–368.

Dominique Foata Département de mathématique Université Louis Pasteur 7, rue René-Descartes F-67084 Strasbourg, France

foata@math.u-strasbg.fr

Guo-Niu Han

I.R.M.A. UMR 7501

Université Louis Pasteur et CNRS 7, rue René-Descartes F-67084 Strasbourg, France

                         guoniu@math.u-strasbg.fr