COMMUTATION ET RÉARRANGEMENTS,

HIER ET AUJOURD’HUI

PAR

Dominique FOATA

en hommage à Pierre CARTIER

1. Introduction. — On ne s’étonnera pas de trouver le nom de Pierre CARTIER associé aux problèmes de nature combinatoire ou algorithmique. Plusieurs de ses exposés au Séminaire Bourbaki ont porté sur ces sujets. Déjà en 1962 (cf. [Ca62]), il expliquait les incidences de l’identité de Spitzer dans les fluctuations de sommes de variables aléatoires ; plus récemment (cf. [Ca80, Ca82, Ca91]), il traitait d’arrangements d’hyperplans, d’algèbre classique avec le renouveau de l’étude des fonctions symétriques et enfin des travaux de ZEILBERGER sur la démonstration “automatique” des identités hypergéométriques.

Plus étonnant est de trouver son nom associé au parallélisme. En fait, comme il sera expliqué ici, la base théorique de cette discipline a pris sa source dans le mémoire “Problèmes combinatoires de commutation et réarrangements,” que CARTIER et moi-même avions rédigé à la fin des années soixante [CaFo79]. J’ai repris une partie de ce titre ici, car, dernièrement, les techniques développées dans ce mémoire ont été reprises par le jeune Guo-Niu HAN dans une étude de statistiques bivariées sur une classe de réarrangements de mots, lui permettant notamment de prouver une conjecture de DENERT sur l’évaluation de la fonction zêta d’ordres héréditaires.

Le but de cet article est de montrer comment et dans quels domaines les problèmes de commutation sont apparus et quelles sont les techniques qui ont été utilisées pour les résoudre, enfin comment HAN [Ha92] s’est servi de ces techniques de commutation pour prouver la conjecture de DENERT.

D. FOATA

2. Parallélisme. — Nous reprenons ici l’exemple traité par Volker DIEKERT [Die] dans son traité sur la combinatoire des traces. Considérons une base de données composée d’un ensemble de données, supposées entières, x, y, z, … et d’un ensemble de transactions pouvant être exécutées simultanément ou non : a, b, c, … Ces transactions agissent sur chaque base de la façon suivante :

(a) x := x+y;  (b) x := w+x;  (c) y := y+z;  (d) w := 2y+z;
(e) z := y + 2z;  (f) x := w + x + y;  (g) x := w + x + 2y.

Les transactions qui ne peuvent être exécutées simultanément sont celles qui contiennent des variables en commun, par exemple (a) et (b). On peut donc bâtir un diagramme de dépendance entre ces transactions, comme indiqué dans la figure :

[figure: a; b; f; g; c; d; e]

Deux suites de transactions conduisant aux mêmes opérations sur les données sont dites équivalentes. Par exemple, les deux suites p = adbcafg et p′ = dacbafg sont équivalentes, puisque l’on peut faire simultanément les transactions a et d, d’une part, et b et c, d’autre part. Durant les années 70, les spécialistes du parallélisme étudiant le comportement non-séquentiel de systèmes concurrents ont donc cherché un modèle mathématique permettant de manipuler non plus ces suites de transactions, mais les classes d’équivalence de telles suites, qu’ils ont appelées traces. Ils ont cherché à représenter les traces par des graphes orientés. Si une trace est de longueur n, c’est-à-dire si elle est composée de suites de longueur n, on lui associe un graphe de n sommets v_{1}, v_{2}, …, v_{n}, dont les étiquettes sont prises dans l’ensemble des transactions ; de plus, on convient de joindre le sommet v_{i} au sommet v_{j} par un arc, si i < j et si les étiquettes de v_{i} et v_{j} sont dépendantes. Par exemple, pour p = adbcafg, on obtient le graphe dit de dépendance :

[figure: d; c; a; b; a; f; g]

COMMUTATION ET RÉARRANGEMENTS

Il est clair que le graphe de dépendance caractérise la trace. Il suggère, de plus, un moyen de faire exécuter les transactions en parallèle : on exécute, d’abord les transactions qui sont minimales dans le graphe de dépendance, puis retirant celles-ci du graphe, celles qui sont minimales dans le graphe résultant et ainsi de suite. Pour le graphe de dépendance cidessus on obtient une suite en parallèle de cinq ensembles de transactions, à savoir :

{a, d} {c, b} {a} {f} {g}.

On va voir, dans un instant, que chaque trace est caractérisée par une telle suite.

3. Monoïdes soumis à des relations de commutation. — Pour rendre compte des manipulations ci-dessus, on introduit un couple (X, D), où X est un ensemble non-vide, appelé alphabet et où D est une relation sur X, qui est réflexive et symétrique. On forme ensuite le monoïde libre X^{∗} engendré par X, composé de tous les mots w = x_{1}x_{2} … x_{m}, où les x_{i} sont des éléments de X. L’opération sur X^{∗} est le produit de juxtaposition des mots. On suppose l’existence d’un mot vide noté ε.

Posons I = X × X \ D et notons ≡_{I} la relation d’équivalence sur X^{∗} engendrée par les couples de la forme (uxyv, uyxv), où u et v sont des mots de X^{∗} et où (x, y) ∈ I. Cette relation d’équivalence est compatible avec le produit dans X^{∗}. Le monoïde quotient X^{∗}/ ≡_{I} est appelé monoïde libre partiellement commutatif ou monoïde des traces, ou encore monoïde soumis à des relations de commutation. On le note M(X, D).

Désignons par [x] la classe d’équivalence d’une lettre x de X. L’application x ↦ [x] est injective et M(X, D) est engendré par l’ensemble des éléments de la forme [x]

On dit qu’une partie F de X est un pas élémentaire, si elle est finie, non-vide, et si deux de ses éléments commutent toujours. On pose dans ce cas [F] = ∏_{x∈F} [x]. Comme tous les éléments de F commutent, la notation [F] définit bien une trace.

Le fait que toute trace est caractérisée par son graphe de dépendance est exprimé dans le théorème suivant.

Théorème 1. — Toute trace s’exprime, de façon unique, comme un produit dans M(X, D), de pas élémentaires [F_{1}] … [F_{r}] (r ≥ 0) tels que pour tout i = 2, …, r et tout b ∈ F_{i}, il existe un a ∈ F_{i−1} satisfaisant (a, b) ∈ D.

Les monoïdes libres partiellement commutatifs sont l’objet de nombreuses études dans les milieux de l’informatique théorique. Le précédent théorème, par exemple, a été popularisé par les spécialistes du parallélisme (cf. [Maz77], [Du86], [Di90]). La notion de commutation partielle a été récemment exploitée par DUCHAMP et KROB [DuKr90] pour introduire les groupes libres partiellement commutatifs, les algèbres de Lie partiellement commutatives, l’algèbre libre partiellement commutative. Pourtant, lorsque ces objets ont été introduits par CARTIER-FOATA [CaFo69], rien ne laissait prévoir une telle popularité. Il s’agissait de dégager l’outil mathématique qui sous-tendait les problèmes de réarrangement de suites et l’établissement de certaines identités d’inversion. Le précédent théorème, par exemple, permet immédiatement d’établir le résultat suivant :

Théorème 2. — Dans l’algèbre ℤ⟨⟨M⟩⟩ des séries formelles du monoïde des traces M = M(X, D), l’inverse de la série caractéristique ∑ t (t ∈ M) est donné par la série 1 + ∑(−1)^{|F |}[F], où F varie dans l’ensemble des pas élémentaires.

A son tour, le précédent théorème a permis de trouver des versions noncommutatives au “Master Theorem” de MACMAHON qui s’énonce comme suit :

Théorème 3. — Soient X_{1}, X_{2}, …, X_{n} n variables qui commutent et B = (b(i, j)) (1 ≤ i, j ≤ n) une matrice à coefficients dans un anneau. Pour tout monôme h = X_{1}^{c_{1}} … X_{n}^{c_{n}} notons ν(h) le coefficient du monôme h dans le développement de

(∑_{j} b(1, j)X_{j})^{c_{1}} … (∑_{j} b(n, j)X_{j})^{c_{n}}.

On a alors l’identité :

| \begin{matrix}1 − b(1, 1)X_{1} & … & −b(1, n)X_{n} \\ … & … & … \\ −b(n, 1)X_{1} & … & 1 − b(n, n)X_{n} \end{matrix} |^{−1} = ∑ hν(h).

Naturellement ce théorème 3 peut se démontrer de bien des façons, et CARTIER dans un séminaire à Strasbourg en 1971 [Ca71] en avait donné neuf démonstrations. Cependant, MACMAHON l’utilisant pour démontrer un résultat statistique sur les suites de nombres, résultat qu’on pouvait établir par d’autres techniques, il importait de voir si ces techniques ne pouvaient pas permettre de trouver aussi des extensions non-commutatives du Master Theorem de MacMahon (cf. [CaFo69]).

4. Réarrangements de suites. — Supposons que l’alphabet X est totalement ordonné. A tout mot croissant u = y_{1}y_{2} … y_{m} on fait correspondre la classe R(u) de tous les réarrangements du mot u, c’està-dire l’ensemble de tous les mots de la forme y_{i_{1}}y_{i_{2}} … y_{i_{m}}, où i_{1}i_{2} … i_{m} est une permutation de 12 … n. Si w = x_{1}x_{2} … x_{m} est un mot de cette classe, son réarrangement croissant, à savoir u lui-même, est encore noté \overline{w} = u. Les statistiques suivantes sont classiques :

des w = |{i | x_{i} > x_{i+1}}| ; exc w = |{i | x_{i} > y_{i}}| ;
maj w = ∑{i | x_{i} > x_{i+1}}; inv w = |{i < j | x_{i} > x_{j}}| .

Les statistiques “des,” “exc,” “maj” et “inv” sont traditionnellement appelées nombre de descentes, nombre d’excédances, indice majeur, nombre d’inversions.

Le théorème suivant est dû à MACMAHON (cf. [CaFo69] :

Théorème 4. — Dans toute classe de réarrangements R(u), pour tout nombre k ≥ 0, il y a autant de mots w tels que exc w = k que de mots w′ tels que des w′ = k.

Ce théorème suppose donc que pour toute classe R(u) on doit pouvoir construire une bijection Φ de R(u) sur elle-même satisfaisant la propriété

exc w = des Φ(w),

identiquement.

Une telle bijection est donnée dans le mémoire de CARTIER-FOATA [CaFo69] et repose sur les propriétés des monoïdes de traces. C’est même à cause de la recherche de cette bijection que ces monoïdes ont été introduits. On s’y prend comme suit.

On part de l’alphabet X ×X, les lettres de l’alphabet étant représentées par des matrices à deux lignes x = ({x′ \atop x} ). La relation de dépendance que l’on s’impose est constituée par l’ensemble des bilettres (x = ({x′ \atop x} ), y = ({y′ \atop y} )) telles que x′ = y′. Autrement dit, deux bi-lettres commutent si et seulement si leurs lettres sur la ligne du haut sont différentes. Le monoïde soumis à ces relations de commutation est appelé monoïde des flots et noté F (X). Comme précédemment, la classe contenant le bi-mot w = ({w′ \atop w} ) est notée [w] = [{w′ \atop w} ]. Lorsque le mot w′ est un réarrangement du mot w, la classe d’équivalence [{w′ \atop w} ] est appelée circuit. Il est clair que l’ensemble C(X) de tous les circuits est un sous-monoïde de F (X), appelé monoïde des circuits.

Pour tout mot w = x_{1}x_{2} … x_{m} de X^{∗}, on note δw le cyclage circulaire δw = x_{2}x_{3} … x_{m}x_{1}. Le mot w est dit dominé, si sa première lettre, notée pre(w), est strictement supérieure à toutes ses autres lettres. Un circuit c est dominé, s’il contient un bimot de la forme

w = \binom{δw}{w} ,

avec w dominé. Tout circuit dominé contient un et un seul bimot de cette forme, appelé représentant canonique du circuit dominé. On pose alors pre(c) = pre(w).

Soient x, y deux lettres de X, [c] = [ \begin{matrix}w′ \\ w \end{matrix} ] = [ \begin{matrix}x′_{1} x′_{2} … x′_{m} \\ x_{1} x_{2} … x_{m} \end{matrix} ] un circuit.

On note exc_{x,y}(c) le nombre d’indice i tels que 1 ≤ i ≤ m et x′_{i} = x, x_{i} = y. On note également des_{x,y}(w) le nombre d’indices i tels que 1 ≤ i ≤ m − 1 et x_{i} = y, x_{i+1} = x. Autrement dit, exc_{x,y}(c) est le nombre d’occurrences de bilettres (verticales) [{x \atop y}] dans c et des_{x,y}(w) le nombre de facteurs yx dans w :

[c] = [ \begin{matrix}… x … \\ … y … \end{matrix} ] = [ \begin{matrix}… & … & … \\ … yx … \end{matrix} ]

Pour permettre un parallèle avec le monoïde de Han qui sera introduit plus loin, on va numéroter les propriétés utiles du monoïde des circuits 1_{c}, 2_{c}, …

Propriété 1_{c}. — Tout circuit c a un et un seul représentant de la forme [\overline{w} ; w ], où \overline{w} est le réarrangement croissant de w.

Propriété 2_{c}. — Tout circuit non vide c admet une factorisation unique de la forme

c = d^{1}d^{2} … d^{r},

où les facteurs d^{i} sont des circuits dominés avec la condition

pre(d^{1}) ≤ pre(d^{2}) ≤ ⋯ ≤ pre(d^{r}).

Propriété 3_{c}. — Si c est un circuit dominé, dont le représentant canonique est ({δw \atop w} ), on a pour tout couple (x, y) tel que x < y la propriété

exc_{x,y}(c) = des_{x,y}(w).

Propirété 4_{c}. — Soit c = d^{1}d^{2} … d^{r} la factorisation (unique) d’un circuit c en circuits dominés (cf. PROPRI^{}ÉT^{}É 2_{c}), dont les mots de la seconde ligne sont u^{1}, u^{2}, …, u^{r}. Alors pour tout x < y on a :

des_{x,y}(u^{1}u^{2} … u^{r}) = des_{x,y}(u^{1}) + des_{x,y}(u^{2}) + ⋯ + des_{x,y}(u^{r}).

La construction de la bijection w ↦ Φ(w) est faite alors comme suit : on part d’un mot w auquel on associe, de façon forcément unique, le circuit [\overline{w} ; w ]. Ce circuit se factorise, d’après la PROPRI^{}ÉT^{}É 2_{c} en un produit de circuits dominés d^{1}d^{2} … d^{r}. Chaque circuit d^{i} dominé a un et un seul représentant ({δu^{i} \atop u^{i}} ). On définit alors Φ(w) comme étant le produit de juxtaposition

Φ(w) = u^{1}u^{2} … u^{r}.

Exemple. — Par exemple, partons du mot

w = 3 1 5 1 4 2 2 6 6 7 2 6 1 5

dont le réarrangement croissant est :

\overline{w} = 1 1 1 2 2 2 3 4 5 5 6 6 6 7.

D’après la PROPRI^{}ÉT^{}É 1_{c}, il lui correspond un unique circuit

\left[{\overline{w} \atop w}\right] = [ \begin{matrix}1 & 1 & 1 & 2 & 2 & 2 & 2 & 4 & 5 & 5 & 6 & 6 & 6 & 7 \\ 3 & 1 & 5 & 1 & 4 & 2 & 2 & 6 & 6 & 7 & 2 & 6 & 1 & 5 \end{matrix} ] .

La factorisation de ce circuit en circuits dominés s’obtient en extrayant ceux-ci de la droite vers la gauche, comme indiqué ci-dessous :

[ \begin{matrix}1 & 1 & 1 & 2 & 2 & 2 & 3 & 4 & 5 & 6 & 6 & 6 \\ 3 & 1 & 5 & 1 & 4 & 2 & 2 & 6 & 6 & 2 & 6 & 1 \end{matrix} ] [ \begin{matrix}5 & 7 \\ 7 & 5 \end{matrix} ]
[ \begin{matrix}1 & 1 & 2 & 2 & 2 & 3 & 4 & 6 & 6 \\ 3 & 1 & 1 & 4 & 2 & 2 & 6 & 2 & 6 \end{matrix} ] [ \begin{matrix}5 & 1 & 6 \\ 6 & 5 & 1 \end{matrix} ] [ \begin{matrix}5 & 7 \\ 7 & 5 \end{matrix} ]
[ \begin{matrix}1 & 1 & 2 & 2 & 2 & 3 & 4 & 6 \\ 3 & 1 & 1 & 4 & 2 & 2 & 6 & 2 \end{matrix} ] [ \begin{matrix}6 \\ 6 \end{matrix} ] [ \begin{matrix}5 & 1 & 6 \\ 6 & 5 & 1 \end{matrix} ] [ \begin{matrix}5 & 7 \\ 7 & 5 \end{matrix} ]
[ \begin{matrix}1 & 1 & 2 & 3 \\ 3 & 1 & 1 & 2 \end{matrix} ] [ \begin{matrix}4 & 2 & 2 & 6 \\ 6 & 4 & 2 & 2 \end{matrix} ] [ \begin{matrix}6 \\ 6 \end{matrix} ] [ \begin{matrix}5 & 1 & 6 \\ 6 & 5 & 1 \end{matrix} ] [ \begin{matrix}5 & 7 \\ 7 & 5 \end{matrix} ]

La juxtaposition des mots du bas de chaque circuit dominé fournit le mot

Φ(w) = 3 1 1 2 6 4 2 2 6 6 5 1 7 5,

dont les descentes successives 31, 64, 42, 65, 51, 75 correspondent aux excédances apparaissant en gras dans les différentes expression du circuit

[\overline{w} ; w ].

A l’aide de la construction précédente, on obtient donc bien une bijection Φ de R(u) sur elle-même satisfaisant la propriété

exc w = des Φ(w),

identiquement (cf. CARTIER-FOATA [CaFo69]).

5. Les distributions Euler-mahoniennes. — Les statistiques “des” et “maj” ont été définies sur les mots (au début de la section 4). La distribution jointe de ces deux statistiques sur une classe de réarrangements de mots quelconques est connue depuis MACMAHON (1916). Notons R(m) la classe des réarrangements du mot 1^{m_{1}}2^{m_{2}} … r^{m_{r}} et A_{m}(t, q) le polynôme générateur du couple (des, maj) sur la classe R(m). Autrement dit,

A_{m}(t, q) = ∑_{w} t^{des w}q^{maj w} (w ∈ R(m)).

Utilisons aussi les notations classiques de la q-factorielle montante :

\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}

et des q-coefficients multinomiaux :

\left[{m_{1} + m_{2} + … + m_{r} \atop m_{1}, m_{2}, …, m_{r}}\right] = \frac{(q; q)_{m_{1}+m_{2}+···+m_{r}}}{(q; q)_{m_{1}}(q; q)_{m_{2}} … (q; q)_{m_{r}}} .

Posons également |m| = m_{1} + m_{2} + … + m_{r} et u^{m} = u_{1}^{m_{1}}u_{2}^{m_{2}} … u_{r}^{m_{r}}. On sait, depuis MACMAHON que “maj” a la distribution q-multinomiale sur R(m) :

A_{m}(t = 1, q) = \left[{m_{1} + m_{2} + … + m_{n} \atop m_{1}, m_{2}, …, m_{n}}\right] (w ∈ R(m)),

identité qu’on peut récrire :

∑_{m} A_{m}(t = 1, q)\frac{u^{m}}{(q; q)_{|m|}} = \frac{1}{(u_{1}; q)_{∞} … (u_{r}; q)_{∞}} ;

et la distribution du couple (des, maj) sur R(m) n’est autre que la “textension” de cette identité :

∑_{m} A_{m}(t, q)\frac{u^{m}}{(q; q)_{1+|m|}} = ∑_{s≥0} \frac{t^{s}}{(u_{1}; q)_{s+1} … (u_{r}; q)_{s+1}} .

Ces deux dernières identités peuvent s’établir directement à partir de la formule de Cauchy

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

sur les produits des fonctions de Schur (cf. [Fo92]). On peut également trouver des formules de récurrence pour les coefficients du polynôme A_{m}(t, q) (cf. RAWLINGS [Ra79]). En résumé, on a plusieurs formes analytiques pour la distribution de (des, maj) sur toute classe de réarrangements.

On dit qu’un couple de statistiques défini sur R(m) est Euler-mahonien, s’il a même distribution que le couple (des, maj) sur R(m). Comme “exc” et “des” ont aussi même distribution sur toute classe R(m), d’après la section précédente, il restait donc à imaginer la définition d’une statistique, disons “den,” ayant même distribution que “maj,” telle que le couple (exc, den) soit Euler-mahonien.

Il est curieux de constater que depuis MACMAHON ou même depuis la construction de la première transformation fondamentale Φ décrite dans la section 4, personne ne se soit intéressé à imaginer une telle statistique. Il a fallu attendre DENERT, [Den90] qui, en 1990, se proposant de calculer la fonction zeta d’un R-ordre héréditaire dans des algèbres centrales simples, a été amenée à introduire une nouvelle statistique sur les mots, plus tard appelée “den.” Elle a constaté pour les premières valeurs de n que le couple (exc, den) était Euler-mahonien sur le groupe symétrique 𝔖_{n} et a fait la conjecture que le résultat devait se prolonger sur toute classe de réarrangements R(m).

6. La conjecture de Denert. — La définition de la statistique “den” (revue par HAN [Han92]) est mieux comprise, si on introduit l’intervalle cyclique

]]x, y]] = \{ \begin{matrix}]x, y] & si x ≤ y, \\ [1, y] + ]x, n] & si x > y; \end{matrix}

Soit alors w = x_{1}x_{2} … x_{m} un mot, soit \overline{w} = x′_{1}x′_{2} … x′_{m} son réarrangement croissant. On pose alors

den w = ∑_{1≤k≤m} |{i ≤ k − 1 : x_{i} ∈]]x_{k}, x′_{k}]]} |.

Par exemple, pour le mot w suivant

\binom{\overline{w}}{w} = ( \begin{matrix}1 & 1 & 1 & 2 & 2 & 2 & 2 & 4 & 5 & 5 & 6 & 6 & 6 & 7 \\ 3 & 1 & 2 & 1 & 2 & 4 & 6 & 2 & 6 & 5 & 6 & 1 & 7 & 5 \end{matrix} )
0 0 2 1 0 4 5 2 7 0 0 9 12 4

on obtient : den w = 46.

Pour une permutation σ = σ(1)σ(2) … σ(n), la statistique den σ est simplement

den σ = ∑_{1≤k≤m} |{i ≤ k − 1 : σ(i) ∈]]σ(k), k]]} |.

Géométriquement, le coefficient de rang k dans la sommation ci-dessus est le nombre de points du graphe de σ contenus dans le rectangle ABCD, lorsque σ(k) ≤ k, et dans les rectangles ABCD et EF GH, lorsque σ(k) > k, comme indiqué dans la figure ci-dessus.

[figure: k−1; k; σ(k); σ(k)+1; •; A; B; D; C; σ(k) ≤ k; k−1; k; σ(k); σ(k)+1; n; •; A; B; D; C; E; F; H; G; σ(k) > k]

Le théorème suivant fut conjecturé par DENERT dans une forme différente, mais équivalente.

Théorème. — Le couple de statistiques (exc, den) a même distribution que (des, maj) sur toute classe de réarrangements R(m) de mots.

Lorsque R(m) = 𝔖_{n}, à savoir le groupe des permutations d’ordre n, le théorème a été prouvé par FOATA et ZEILBERGER [FoZe90]. Le théorème pour une classe R(m) quelconque est dû à Han [Han91]. Ce dernier a eu aussi le mérite de donner la bonne définition de “den” dans le cas général (définition qui a été rappelée plus haut) et, de façon plus essentielle, de construire une nouvelle transformation bijective Φ_{3} de R(m) sur elle-même satisfaisant :

(des, maj)(w) = (exc, den)(Φ_{3}(w))

identiquement. C’est la construction de cette transformation que nous nous proposons de décrire dans la section suivante.

7. La transformation fondamentale de Han. — Soient x, y, a, b quatre lettres appartenant à l’intervalle [n] = {1, 2, …, n}. On dit que les lettres a et b sont voisines par rapport à x et y, si elles appartiennent au même intervalle cyclique ]]y, x]], ou à son complémentaire ; dans le cas contraire, on dit qu’elles sont en face.

On ne s’impose plus des règles de commutation, sur l’ensemble des bilettres, mais des règles (de grammaire). On forme ce que les informaticiens appellent un système semi-Thue sur l’ensemble X × X, où X est supposé être ici l’ensemble des entiers ℕ, en posant :

( \begin{matrix}x & y \\ a & b \end{matrix} ) ⇒ \{ \begin{matrix}( \begin{matrix}y & x \\ a & b \end{matrix} ) , & si a et b sont voisines ; \\ ( \begin{matrix}y & x \\ b & a \end{matrix} ) , & si a et b sont en face. \end{matrix}

Par exemple, pour x = 6 et y = 4, les lettres 4 et 8 sont voisines, puisque ]]y, x]] =]]4, 6]] = {5, 6} et que 4 et 8 appartiennent tous deux au complémentaire de cet ensemble. Au contraire, 4 et 6 sont en face. On a donc

( \begin{matrix}6 & 4 \\ 4 & 8 \end{matrix} ) ⇒ ( \begin{matrix}4 & 6 \\ 4 & 8 \end{matrix} )  et  ( \begin{matrix}6 & 4 \\ 6 & 4 \end{matrix} ) ⇒ ( \begin{matrix}4 & 6 \\ 4 & 6 \end{matrix} ) .

Ces règles peuvent être prolongées à l’ensemble des bimots : on a w ⇒ w′, si w = ulu′ et w′ = uru′, pour certains bimots u, u′, l, r et l ⇒ r. La fermeture “≡” symétrique, réflexive et transitive de cette relation définit un monoïde quotient H(X) = (X × X)^{∗}/≡. Pour ce monoïde, on reprend la même terminologie que pour le monoïde sur (X × X)^{∗} défini par des relations de commutation : flots, circuits, … Quand on applique les règles précédentes l ⇒ r à un bimot w = ({w′ \atop w} ), la nature des règles veut que le bimot obtenu, disons v = ({v′ \atop v} ) est tel que v′ (resp. v) est un réarrangement de w′ (resp. w). Par ailleurs, par application de ces mêmes règles, on peut toujours amener le mot du haut à être un mot croissant. La difficulté vient du fait que dans une classe, il peut y avoir plusieurs bimots ({v′ \atop v} ), dont le mot du haut v′ est croissant.

Dans une première étape, on étend la définition de “exc” et “den” aux bimots

w = ( \begin{matrix}v \\ w \end{matrix} ) = ( \begin{matrix}v_{1} v_{2} … v_{m} \\ w_{1} w_{2} … v_{m} \end{matrix} )

où v est un réarrangement (quelconque) de w, en posant :

exc w = |{i : 1 ≤ i ≤ m, w_{i} > v_{i}}|;
den w = ∑_{1≤k≤m} |{i ≤ k − 1 : w_{i} ∈]]w_{k}, v_{k}]]} |.

La construction de HAN repose sur les deux propriétés suivantes :

Propriété 1. — Les statistiques exc et den sont invariantes dans chaque classe du monoïde de Han. Autrement dit, si w ≡ w′, alors (exc, den)(w) = (exc, den)(w′).

Propriété 2. — Si un bimot est un produit de juxtaposition de circuits dominés

w = \binom{v^{1}}{w^{1}} \binom{v^{2}}{w^{2}} … \binom{v^{r}}{w^{r}}

tels que

pre(w^{1}) ≤ pre(w^{2}) ≤ ⋯ ≤ pre(w^{r}),

alors (des, maj)(w) = (exc, den)(w).

La construction de la transformation de Han va alors consister, partant d’un mot w, à lui associer un bimot w tel que (exc, den)(w) = (exc, den)(w). Par définition même de ces statistiques, il suffit de prendre w = (\overline{w} ; w ), où \overline{w} est le réarrangement croissant de w. Il suffit, ensuite, de trouver dans la classe d’équivalence de w un bimot w̃ qui soit un produit croissant (au sens de la propriété 2) de bimots dominés :

w̃ = \binom{v^{1}}{w^{1}} \binom{v^{2}}{w^{2}} … \binom{v^{r}}{w^{r}} ,

et de montrer que le passage de w à w̃ est bien bijectif. La bijection cherchée est alors donnée par w ⟼ w̃ = w^{1}w^{2} … w^{r}. Cette construction est illustrée dans l’exemple suivant.

\binom{\overline{w}}{w} = ( \begin{matrix}1 & 1 & 1 & 2 & 2 & 2 & 2 & 4 & 5 & 5 & 6 & 6 & 6 & 7 \\ 3 & 1 & 2 & 1 & 2 & 4 & 6 & 2 & 6 & 5 & 6 & 1 & 7 & 5 \end{matrix} )
6 5 6
6 5 1
6 5 6
5 1 7
1 1 1 2 2 2 3 4 5 6 6 6 3 1 2 1 2 4 6 2 6 6 5 1 ( \begin{matrix}5 & 7 \\ 7 & 5 \end{matrix} )

\begin{matrix}· & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & · & · & · & · & · & · & · \end{matrix}

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

∗  ∗ ∗  ∗ ∗  ∗  exc w̃ = 6 = exc w
0 0 0 1  4 4 0 3  0  7 5 9  9 4 den w̃ = 46 = den w
•  • •  • •  •  des w̃ = 6
1  5 6  10 11  13  maj w̃ = 46

BIBLIOGRAPHIE

[Ca62] CARTIER (Pierre). — 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.

[Ca71] CARTIER (Pierre). — La série génératrice exponentielle : applications probabilistes et algébriques, Publications de l’I.R.M.A. Strasbourg, 68 pages, 1971/1972.

[Ca80] CARTIER (Pierre). — 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] CARTIER (Pierre). — 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.

[Ca91] CARTIER (Pierre). — 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.

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

[Den90] DENERT (M.). — The genus zeta function of hereditary orders in central simple algebras over global fields, Math. Comp., t. 54, 1990, p. 449-465.

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

[Du86] DUBOC (C.). — Commutations dans les monoïdes libres : un cadre théorique pour l’étude du parallélisme, thèse, Faculté des Sciences de l’Université de Rouen, 1986.

[DuKr90] DUCHAMP (D.) and KROB (D.). — Free partially commutative structures, à

paraître dans J. of Algebra.

[Fo92] FOATA (Dominique). — Les distributions Euler-Mahoniennes sur les mots, à

paraître dans Discrete Math.

[FoZe90] FOATA (Dominique) and ZEILBERGER (Doron). — Denert’s Permutation Statistic Is Indeed Euler-Mahonian, Studies in Appl. Math., t. 83, 1990, p. 31–59.

[Han91] HAN (Guo-Niu). — Calcul Denertien, thèse doctorat Strasbourg. — Publ. I.R.M.A. Strasbourg, 476/TS-29, 1991.

[Maz87] MAZURKIEWICZ (A.). — Trace Theory, Petri Nets, Applications and Relationship to other Models of Concurrency [W. Brauer, ed. ], p. 279–324. — Berlin, Springer-Verlag, 1987 (Lecture Notes in Computer Science, 255).

[Ra79] RAWLINGS (Don). — Permutation and Multipermutation Statistics, Ph. D. thesis, Univ. Calif. San Diego. — Publ. I.R.M.A. Strasbourg, 49/P-23, 1979.

Dominique Foata,

I.R.M.A. et département de mathématique, C.N.R.S. et Université Louis-Pasteur, 7, rue René-Descartes, F-67084 Strasbourg Cedex.

email : foata@math.u-strasbg.fr