DESCENTES DES DÉRANGEMENTS ET MOTS CIRCULAIRES(*)

Jacques DÉSARMÉNIEN (**) ET Michelle WACHS (***)

R^{}ÉSUM^{}É. — Au moyen de deux bijections, dues à Macdonald et à Gessel, nous établissons que l’ensemble des descentes des dérangements et l’ensemble des reculs d’une classe de permutations caractérisée par la suite de ses montées et descentes ont même distribution.

ABSTRACT. — Using two bijections by Macdonald and Gessel, we show that the set of the descents of derangements and the set of the descents of the inverse of permutations characterized by their up-down sequences have the same distribution.

Introduction

Dans un précédent article, l’un des auteurs [2] a montré que l’ensemble des permutations débutant par un nombre impair de descentes est en bijection avec l’ensemble des dérangements et fournit un cadre intéressant pour expliquer des formules classiques de récurrence sur le nombre de dérangements. De plus, cet ensemble se prête bien à des q-extensions, et donne naissance à une famille de fonctions symétriques d’un type déjà connu (cf. [1], [4], [6]). Gessel, dans un travail non publié [7], a effectué le q-dénombrement des dérangements par indice majeur, qui apparaît être identique au q-dénombrement par indice majeur inverse des permutations que nous avions étudiées. En fait, une investigation plus poussée a conduit à la constatation suivante, énoncée dans [3], que les distributions des ensembles des descentes des dérangements et des ensembles des reculs des permutations débutant par un nombre impair de descentes coïncident. Ceci est évidemment un résultat plus fort que la simple égalité de deux q-séries.

Malheureusement, le travail de Gessel ci-dessus mentionné ne contient aucune démonstration, et c’est au cours d’une conversation avec l’une de nous qu’il a indiqué son idée de départ. Ceci a permis, non seulement de reconstituer les démonstrations du travail de Gessel (ce qui a été fait dans [10]), mais aussi de montrer qu’il a découvert un outil susceptible d’autres utilisations.

(*) Soutien par le P.R.C. Mathématiques et Informatique.

(**) Département d’informatique, I.U.T. Strasbourg III, 72, route du Rhin, F-67400 Illkirch-Graffenstaden.

(***) Department of mathematics, University of Miami, Coral Gables, FL 33124, U.S.A.

En particulier il permet d’établir l’égale distribution des ensembles introduits plus haut.

Par ailleurs, diverses démonstrations bijectives de ce résultat ont été établies par l’un des auteurs (cf. [11]), qui doivent être incluses dans une rédaction définitive de ce travail.

1. Le problème

Nous allons ici donner les définitions et notations qui seront utilisées dans toute la suite.

Tout d’abord, si [n] = {1, 2, …, n} et E est une partie de [n−1], on dira que la suite s = s_{1}, s_{2}, …, s_{n} d’entiers strictement positifs est compatible avec E, ce que nous noterons s ⊥ E, si :

\begin{matrix}i : s_{1} ≥ s_{2} ≥ ⋯ ≥ s_{n} > 0; \\ ii : i ∈ E ⇒ s_{i} > s_{i+1}. \end{matrix}

Nous aurons à considérer un ensemble X = {x_{1}, x_{2}, …} d’indéterminées commutatives. Le poids de la suite s est le produit w(s) = x_{s_{1}}x_{s_{2}} ⋯ x_{s_{n}}.

Soit maintenant σ ∈ 𝔖_{n} une permutation de [n]. Un entier i ∈ [n − 1] est une descente (resp. montée) de σ si σ_{i} > σ_{i+1} (resp. σ_{i} < σ_{i+1}). Un recul de σ est une descente de σ^{−1}. Notons des σ et rec σ respectivement les ensembles des descentes et des reculs de σ.

La forme (“up-down sequence”) de σ est la suite de longueur n−1 dont le i-ième symbole est M ou D selon que i est une montée ou une descente de σ.

Si la décomposition en produit de cycles est constituée de cycles de longueur λ_{1}, λ_{2}, …, λ_{k} on dira que la partition λ de n est le type (“cycle structure”) de σ.

Nous aurons à considérer deux ensemble de permutations : l’un, classique, est celui des dérangements, ou permutations sans point fixe, noté 𝔇_{n}, dont le nombre d’éléments est d_{n}; l’autre, introduit dans [2], est l’ensemble 𝔎_{n} des permutations dont la forme débute par un nombre impair de D; le nombre de ses éléments est k_{n}. On sait déjà que d_{n} = k_{n}. Nous allons montrer un résultat plus fort, en considérant les ensembles 𝔇_{n}^{E} et 𝔎_{n}^{E} d’éléments de 𝔇_{n} et de 𝔎_{n} dont l’ensemble des descentes pour 𝔇_{n} et des reculs pour 𝔎_{n} est un ensemble E donné. (Il serait possible de ne s’intéresser qu’aux ensembles de reculs : leur distribution est identique à celle des descentes sur 𝔇_{n}; c’est pour des raisons historiques que nous avons maintenu cette distinction.) Notons respectivement d_{n}^{E} et k_{n}^{E} le nombre de leurs éléments. Le résultat nouveau et principal de cet article est le suivant.

Théorème 1. — Quel que soit E, on a l’égalité d_{n}^{E} = k_{n}^{E}.

2. Les fonctions de Schur

Pour tous détails complémentaires, on renvoie à [8]. Soient μ/λ une forme gauche d’ordre n. Un tableau semi-standard de forme μ/λ est une application T de μ/λ dans l’ensemble des entiers strictement positifs telle que les indices vont en décroissant strictement de bas en haut dans les colonnes et en décroissant au sens large de gauche à droite dans les lignes. Par exemple,

2 1 3 3 1 5 8 6 2

est un tableau semi-standard de forme 5332/22.

Le poids de T est le produit w(T) des indéterminées de X dont les indices figurent dans T. Un tel tableau définit un ordre total ⪯ sur les points de la forme μ/λ en convenant que (i, j) ≺ (i′, j′) si T (i, j) > T (i′, j′) ou T (i, j) = T (i′, j′) et i ≤ i′. En plaçant l’entier k sur le point (i, j) de μ/λ s’il est le k-ième dans l’ordre ainsi défini, on obtient un tableau standard Θ de forme μ/λ, contenant tous les entiers de 1 à l’ordre n de Θ avec croissance stricte suivant les lignes et les colonnes.

Un recul d’un tableau standard Θ est un entier i ∈ [n − 1] tel que i + 1 apparaisse à gauche ou au dessus de i dans Θ.

Si T est un tableau semi-standard et Θ le tableau standard associé, on voit aisément que la suite décroissante des éléments de T est compatible avec l’ensemble rec Θ des reculs de Θ. On a même le résultat suivant (cf. [4]).

Proposition 2. — Il y a une bijection entre l’ensemble des tableaux semi-standard T de forme μ/λ et l’ensemble des couples (Θ, s) constitués d’un tableau standard de forme μ/λ et d’une suite compatible avec rec Θ. De plus, les poids de T et de s sont égaux.

Le couple (Θ, s) associé au tableau semi-standard de l’exemple précédent est :

Θ = 6 8 4 5 9 3 1 2 7 s = 865332211 ;

on a indiqué en gras les reculs de Θ ainsi que les éléments de s dont l’indice est un recul de Θ.

La fonction de Schur S_{μ/λ}(X) est la somme des poids de tous les tableaux semi-standard de forme μ/λ. C’est une fonction symétrique. La proposition précédente peut donc être récrite comme suit.

Proposition 3. — La fonction de Schur vaut :

S_{μ/λ}(X) = ∑_{Θ} ∑_{s⊥rec Θ} w(s),

la somme étant étendue aux tableaux standard Θ de forme μ/λ.

À partir de cette proposition, on peut faire le lien entre fonction de Schur et q-dénombrement des tableaux standard par somme de leurs reculs (l’indice majeur inverse, cf. [4, 9]).

Le cas qui nous intéressera spécialement est celui où la forme μ/λ est un ruban connexe (cf. [1]), c’est à dire que tout point de la forme μ/λ a un prédécesseur situé à gauche ou au dessus et un successeur à droite ou au dessous, sauf deux points, l’origine qui n’a pas de prédécesseur et l’extrémité qui n’a pas de successeur. Un tableau standard dont la forme est un ruban connexe peut être vu comme la permutation obtenue en lisant le tableau ligne après ligne ; la forme de la permutation est alors identifiée au ruban et les reculs du tableau sont ceux de la permutation.

Un cas particulier est celui où le ruban est une partition contenant une seule part. La fonction de Schur est alors la fonction élémentaire complète S_{n}(X).

Proposition 4. — Lorsque ρ et ρ′ sont deux rubans, le produit des fonctions de Schur S_{ρ}(X) et S_{ρ′}(X) se décompose en somme de deux fonctions de Schur elles-mêmes associées à des rubans :

S_{ρ}(X)S_{ρ′}(X) = S_{ρ→ρ′}(X) + S_{ρ↓ρ′}(X),

où ρ → ρ′ et ρ ↓ ρ′ sont obtenus en plaçant l’origine de ρ′ respectivement à droite et en dessous de l’extrémité de ρ.

Cette décomposition se voit très simplement en examinant les tableaux semi-standard.

Par exemple,

S_{× ×}(X)S_{\begin{matrix}× \\ × & × \end{matrix}}(X) = S_{\begin{aligned}× & × & × \\ & & × & × \end{aligned}}(X) + S_{\begin{aligned}× & × \\ & × \\ & × & × \end{aligned}}(X).

Un corollaire de la proposition précédente permet de développer S_{1}(X)^{n}.

Proposition 5. — On a la formule :

S_{1}(X)^{n} = ∑_{σ∈𝔖_{n}} ∑_{s⊥rec σ} w(s).

Nous en arrivons maintenant aux permutations dans 𝔎_{n}. La forme du tableau standard associé à un élément de 𝔎_{n} commence donc par un nombre impair de pas verticaux, c’est à dire que la première colonne du ruban est de longueur paire. Appelons K_{n}(X) la fonction symétrique somme des poids des tableaux semi-standard dont la forme est un tel ruban de longueur n. En somme,

K_{n}(X) = ∑_{σ∈𝔎_{n}} ∑_{s⊥rec σ} w(s).

Par exemple,

K_{4}(X) = S_{\begin{matrix}× \\ × & × & × \end{matrix}}(X) + S_{\begin{aligned}× \\ × & × \\ & × \end{aligned}}(X) + S_{\begin{matrix}× \\ × \\ × \\ × \end{matrix}}(X).

Partant d’un ruban quelconque, il existe une et une seule façon d’en enlever, à partir de son origine, une bande horizontale de manière à laisser un ruban qui commence par un nombre impair de pas verticaux. Par exemple,

\begin{aligned}× & × \\ & × \\ & × & × \end{aligned} = × × ↓ \begin{matrix}× \\ × & × \end{matrix} et \begin{aligned}× & × \\ & × & × & × \end{aligned} = × → \begin{matrix}× \\ × & × & × \end{matrix}.

En tenant compte de la proposition précédente, cette remarque se traduit par la proposition suivante, qu’on peut comparer à la formule d’inclusion-exclusion donnant le nombre de dérangements.

Proposition 6. — La suite de fonctions symétriques K_{n}(X) est donnée par la récurrence :

\begin{aligned}i & : K_{0}(X) = 1; \\ ii & : S_{1}(X)^{n} = ∑_{0≤k≤n} S_{k}(X)K_{n−k}(X), n ≥ 1. \end{aligned}

3. La factorisation de Lyndon

Un mot de Lyndon de longueur n est un mot c = c_{1}c_{2} ⋯ c_{n} dont les lettres sont des entiers strictement positifs et qui est strictement plus petit (pour l’ordre lexicographique) que toutes ses permutations circulaires. Le poids d’un mot est le produit des indéterminées de X dont les indices apparaissent dans le mot.

Le résultat suivant, dû à Lyndon (cf. [8]), est un classique, bien connu des informaticiens.

Proposition 7. — Tout mot w se factorise de manière unique en produit de concaténation de mots de Lyndon w^{1}w^{2} ⋯ w^{k} qui, dans cet ordre, vont en décroissant lexicographiquement.

Considérons par exemple le mot suivant, de longueur 9 : w = 321231212. On trouve la décomposition de Lyndon de w en isolant successivement les facteurs droits minimaux de w ([8], prop. 5.1.6 p. 67). Les facteurs de w sont donc : w = 3 2 123 12 12.

Les longueurs des facteurs de Lyndon d’un mot w de longueur n constituent une partition λ de n, appelée type de w. Le type du mot de l’exemple précédent est λ = 32211.

Exposons maintenant la construction de Gessel [7, 10]. Partons de la décomposition de Lyndon d’un mot w = w^{1}w^{2} ⋯ w^{k}. À la i-ième lettre de w qui apparaît dans le mot de Lyndon w^{r}, associons le mot p(i) infini obtenu en lisant circulairement w^{r} à partir de la i-ième lettre de p. Le mot w définit alors un ordre total ⪯ sur ses n positions comme suit : i ≺ j si p(i) est plus grand que p(j) pour l’ordre lexicographique, ou si p(i) = p(j) et i < j. Soit τ le mot qui à i associe sa position dans l’ordre ⪯. On peut à son tour factoriser τ en produit de mots de Lyndon pour l’ordre inverse de l’ordre naturel. Chacun des facteurs peut alors être considéré comme un cycle d’une permutation σ de type λ dont l’écriture en produit de cycles est σ = σ^{1}σ2 ⋯ σ^{k}. Cette dernière partie n’est autre que la “transformation fondamentale de Foata” (cf. [5], p. 15).

On peut alors montrer que la suite décroissante des entiers qui figurent dans w est compatible avec l’ensemble des σ des descentes de σ, d’où le théorème qui suit.

Proposition 8. — Il y a une bijection entre l’ensemble des mots w de type λ et l’ensemble des couples (σ, s) constitués d’une permutation σ ∈ 𝔖_{n} de type λ et d’une suite s compatible avec des σ. De plus, les poids de w et de s sont égaux.

Cette construction est illustrée par la continuation de l’exemple précédent. Soit

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

où l’on a indiqué dans la première ligne les indices i et dans la deuxième les facteurs de Lyndon de w; le type de w est λ = 32211.

Pour ce mot,

p(1) = 333333 … p(2) = 222222 …
p(3) = 123123 … p(4) = 231231 …
p(5) = 312312 … p(6) = 121212 …
p(7) = 212121 … p(8) = 121212 …
p(9) = 212121 …

L’ordre sur les positions de p est donc :

1 ≺ 5 ≺ 4 ≺ 2 ≺ 7 ≺ 9 ≺ 3 ≺ 6 ≺ 8.

Par conséquent,

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

On en déduit la décomposition de σ en produit de cycles :

σ = (1)(4)(732)(85)(96),

soit, en indiquant simultanément les descentes de σ et les éléments correspondants de s en gras :

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

On remarque que la bijection inverse de celle décrite consiste à écrire les cycles de σ avec leur plus grand élément en tête et par ordre croissant de ce plus grand élément, ce qui donne τ, puis à remplacer dans τ l’entier k par le k-ième élément de la suite s.

Si λ est une partition de n, notons P_{λ}(X) la somme des poids de toutes les mots de type λ. D’après la proposition 8 :

P_{λ}(X) = ∑_{σ} ∑_{s⊥des σ} w(s),

où la première somme est sur les permutations de type λ. Un développement analogue à celui mentionné après la proposition 3 permet de faire le lien entre les fonctions symétriques P_{λ}(X) et le q-dénombrement des permutations de type donné. L’évaluation de P_{λ}(X) peut se faire au moyen de la formule d’énumération de Pólya (cf. [7, 10]).

La somme des poids de tous les mots de longueur n est évidemment égale à S_{1}(X)^{n}. Avec la proposition 8, on trouve donc :

S_{1}(X)^{n} = ∑_{σ∈𝔖_{n}} ∑_{s⊥des σ} w(s) = ∑_{λ} P_{λ}(X),

la dernière somme étant étendue à toutes les partitions de n.

Le produit de deux fonctions P se fait simplement lorsque leurs types n’ont aucune part en commun, en prenant la réunion des types :

P_{3111}(X)P_{422}(X) = P_{4322111}(X).

Cette propriété se voit directement sur les mots, en intercalant leurs facteurs de Lyndon respectifs. La situation est moins simple lorsque les types ont des parts en commun. Par exemple, il est clair que P_{1}(X) = S_{1}(X) ; d’autre part, un mot de type 111… est en fait une suite faiblement décroissante d’entiers. Par conséquent, P_{1^{k}}(X) = S_{k}(X), la fonction symétrique élémentaire complète.

Appelons maintenant D_{n}(X) la somme des P_{λ}(X) dont le type ne contient pas de parts égales à 1. En d’autres termes, les permutations associées σ de la proposition 8 sont des dérangements, soit :

D_{n}(X) = ∑_{σ∈𝔇_{n}} ∑_{s⊥des σ} w(s).

Toute partition résulte, d’une manière unique, de la réunion d’une partition sans parts égales à 1 et d’une partition dont toutes les parts sont égales à 1. Dans ce cas, les types n’ont pas de part en commun, ce qui, compte tenu de la convention D_{0}(X) = 1 nous donne la proposition suivante.

Proposition 9. — La suite de fonctions symétriques D_{n}(X) est donnée par la récurrence :

\begin{aligned}i & : D_{0}(X) = 1; \\ ii & : S_{1}(X)^{n} = ∑_{0≤k≤n} S_{k}(X)D_{n−k}(X), n ≥ 1. \end{aligned}

4. Le résultat principal

Comme corollaire aux propositions 6 et 9, on a bien entendu :

Proposition 10. — Les fonctions symétriques K_{n}(X) et D_{n}(X) sont égales.

Partons de la définition de D_{n}(X) :

D_{n}(X) = ∑_{σ∈𝔇_{n}} ∑_{s⊥des σ} w(s)

= ∑_{E⊂[n−1]} ∑_{σ∈𝔇_{n}^{E}} ∑_{s⊥E} w(s)

= ∑_{E⊂[n−1]} d_{n}^{E} ∑_{s⊥E} w(s).

Il en est de même pour K_{n}(X). On a donc :

(*)  ∑_{E⊂[n−1]}(d_{n}^{E} − k_{n}^{E})W (E) = 0,

où, pour simplifier, on a posé :

W (E) = ∑_{s⊥E} w(s).

Écrivons les monômes de degré n en X par ordre décroissant des indices des indéterminées, et ordonnons ces monômes ainsi écrits par ordre lexicographique. Soit maintenant E = {i_{1}, i_{2}, …, i_{k}} ⊂ [n − 1]. Le plus petit monôme qui apparaît dans W (E), appelé son terme dominant, est :

x_{k+1}^{i_{1}}x_{k}^{i_{2}−i_{1}}⋯ x_{2}^{i_{k}−i_{k−1}}x_{1}^{n−i_{k}},

correspondant à la suite s constante sauf pour les indices de E, où la décroissance est d’une unité. Par exemple, aux ensembles E = ∅, {1}, {2}, {1, 2} et {1, 3} correspondent les termes dominants respectifs :

x_{1}^{n}, x_{2}x_{1}^{n−1}, x_{2}^{2}x_{1}^{n−2}, x_{3}x_{2}x_{1}^{n−2} et x_{3}x_{2}^{2}x_{1}^{n−3}.

En supposant les ensembles E ordonnés par taille croissante puis par ordre lexicographique de leurs éléments lorsqu’ils ont même taille, le lemme suivant est donc vrai.

Lemme 11. — L’application qui à E associe son terme dominant est strictement croissante.

L’identité (*) implique donc, par l’argument triangulaire habituel, que le coefficient de W (E) est nul pour tout E, ce qui est exactement le théorème 1.

BIBLIOGRAPHIE

[1] D^{}ÉSARM^{}ÉNIEN (Jacques). — Fonctions symétriques associées à des suites classiques de nombres, Ann. scient. École normale supérieure, t. 16, 1983, p. 271–304.

[2] D^{}ÉSARM^{}ÉNIEN (Jacques). — Une autre interprétation du nombre de dérangements, Séminaire Lotharingien de combinatoire, B08a, 1983.

[3] D^{}ÉSARM^{}ÉNIEN (Jacques). — Une autre interprétation…, conférence prononcée au 28^{e} Colloque des sciences mathématiques du Québec, Université du Québec à Montréal, 31 octobre 1987.

[4] D^{}ÉSARM^{}ÉNIEN (Jacques) et FOATA (Dominique). — Fonctions symétriques et séries hypergéométriques basiques multivariées, Bull. Soc. math. France, t. 113, 1985, p. 3–22.

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

[6] FOATA (Dominique) et SCH^{}ÜTZENBERGER (Marcel-Paul). — Major index and inversion number of permutations, Math. Nachr., t. 83, 1978, p. 143–159.

[7] GESSEL (Ira). — Note non publiée.

[8] LOTHAIRE (M.). — Combinatorics on words. — Reading, Addison-Wesley (Encyclopedia of Mathematics and its Applications, vol. 17), 1983.

[9] MACDONALD (Ian G.). — Symmetric functions and Hall polynomials. — Oxford, Clarendon Press, 1979.

[10] WACHS (Michelle). — Communication orale.

[11] WACHS (Michelle). — Communications écrites.