Commutation and Rearrangements

An electronic reedition of the monograph

Problèmes combinatoires de commutation et réarrangements

by P. Cartier, D. Foata

with three new appendices by

D. Foata, B. Lass and Ch. Krattenthaler

Foreword

The monograph “Problèmes combinatoires de commutation and réarrangements” was originally published as no. 85 in the Springer-Verlag Lecture Notes in Mathematics Series, back in 1969. The algebraic and combinatorial techniques developed there have since been used in various branches of mathematics and also computer science. The notion of partially commutative monoid, that was first introduced for extending the MacMahon Master Theorem to the noncommutative case, has been used in other contexts. In particular, it has provided an appropriate mathematical model for the study of computer parallelism. The fundamental result deals with an inversion formula, that has been expressed in different algebraic structures, originally the algebra of a partially commutative monoid.

It was then appropriate, with this electronic reedition of the monograph, to have three appendices which could illustrate how that fundamental inversion formula was implemented in other environments, explicitly and also implicitly.

In the fist appendix (“Inversions de Möbius”) it is shown how to go from the Möbius inversion formula for a partially commutative monoid to the Möbius formula for a locally finite partially ordered set, and conversely.

In the second appendix Bodo Lass shows that by means of a simple specialization of the variables the fundamental inversion formula provides a noncommutative version of the celebrated chromatic polynomial identity for graphs : (−1)^{|V |}χ_{G}(−1) = a(G).

The third appendix, written by Christian Krattenthaler, presents Viennot’s theory of heaps of pieces, a theory that has been very fruitful in the combinatorial theory of orthogonal polynomials and in the calculation of multivariable generating functions for polyominoes. The equivalence of the theory of heaps and of partially commutative monoids is explicitly established.

COMMUTATION AND REARRANGEMENTS

P. Cartier, D. Foata : Problèmes combinatoires de commutation et réarrangements, 54 pages.

D. Foata : Inversions de Möbius, 5 pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 55

B. Lass : Le polynôme chromatique, 2 pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . p. 61

Ch. Krattenthaler : The theory of heaps and the Cartier-Foata monoid, 11 pages . . . . . . . . p. 63

Lecture Notes in Mathematics

A collection of informal reports and seminars Edited by A. Dold, Heidelberg and B. Eckmann, Zürich Series : Institut de Mathématique, Université de Strasbourg Adviser : P. A. Meyer

85

P. Cartier • D. Foata

Université de Strasbourg

Problèmes combinatoires de commutation et réarrangements

Springer-Verlag Berlin • Heidelberg • New York 1969

The present volume is a 2005 TEX-reproduction of the original text that was originally published in the Springer-Verlag Lecture Notes in Mathematics Series in 1969.

TABLE DES MATIÈRES

Introduction ............................................................. 1

CHAPITRE PREMIER. Monoïdes définis par des relations de commutation ............................................................ 5

1. Rappels sur les monoïdes libres ................................. 5
2. Construction de L(Z; C) ........................................ 6
3. Structure de L(Z; C) ............................................ 7
4. Un exemple ...................................................... 9
CHAPITRE 2. Fonction de Möbius d’un monoïde .................. 11
1. Décompositions .................................................. 11
2. Formule d’inversion de Möbius ................................. 12
3. Fonction de Möbius du monoïde L(Z; C) ...................... 13
4. Cas particuliers .................................................. 13
CHAPITRE 3. Circuits dans un graphe ............................... 15
1. Définitions ....................................................... 15
2. Structure des flots ............................................... 16
3. Structure des circuits ............................................ 17
4. Cycles ............................................................ 18
5. Relation avec les chemins ....................................... 19
6. Décomposition descendante d’un circuit ....................... 21
CHAPITRE 4. Réarrangements de suites ............................. 24
1. Monoïde des réarrangements .................................... 24
2. Décomposition d’un réarrangement en cycles .................. 25
3. Monoïde d’intercalement ........................................ 26
4. Décomposition descendante d’un mot .......................... 29
5. Une méthode de réarrangement ................................. 30
CHAPITRE 5. Sur le ^{⟨⟨}Master Theorem^{⟩⟩} de MacMahon ......... 33
1. Une généralisation non commutative du ^{⟨⟨}Master Theorem^{⟩⟩} . 33
2. Une autre généralisation du théorème de MacMahon ......... 35

CHAPITRE 6. Relations entre coefficients binomiaux ............. 37
1. Description du graphe ........................................... 37
2. Étude des circuits pairs ......................................... 37
3. Étude des circuits impairs ...................................... 38
4. Autres identités .................................................. 39
5. Utilisation du ^{⟨⟨}Master Theorem^{⟩⟩} de MacMahon.............. 40
Formulaire ............................................................ 43
CHAPITRE 7. Applications probabilistes ............................ 45
1. Identité de Spitzer ............................................... 45
2. Propriétés du permanent ........................................ 47
3. Fonctions caractéristiques de certaines variables aléatoires .... 49
Bibliographie ............................................................ 52
Index des principales notations ...................................... 53

INTRODUCTION

Dans sa thèse [1], l’un d’entre nous a étudié les problèmes combinatoires liés aux réarrangements de suites finies et à la décomposition en cycles de ⟨⟨permutations avec répétitions^{⟩⟩}. Nous reprenons ici ces questions par des méthodes nouvelles : la nouveauté principale est l’introduction du monoïde des circuits sur un un graphe et, comme cas particulier, celle des monoïdes de réarrangements. Nous pouvons ainsi donner des démonstrations assez intuitives de plusieurs théorèmes de factorisation ; on obtient deux bijections distinctes de l’ensemble des mots sur l’ensemble des réarrangements, dont la composition redonne un théorème de réarrangement, sans recourir aux constructions élaborées dans [1]. Nous examinerons maintenant les principaux thèmes de ce travail.

A. Fonction de Möbius

Le but des chapitres I et II est d’établir l’identité générale

(1)  ( ∑_{i_{1},...,i_{r}}(−1)^{r} T_{i_{1}} ⋯ T_{i_{r}})^{−1} = ∑_{j_{1},...,j_{s}} T_{j_{1}} ⋯ T_{j_{s}},

dont la signification est la suivante : on considère des séries formelles à coefficients entiers en des indéterminées T_{i} auxquelles on impose certaines relations de commutation T_{i}T_{j} = T_{j}T_{i} (éventuellement aucune ou toutes). Le membre de gauche comporte une sommation sur tous les monômes distincts formés de lettres distinctes commutant deux à deux et celui de droite comporte une sommation sur tous les monômes distincts (si plusieurs monômes se trouvent être égaux en vertu des relations de commutation imposées, on ne prend que l’un d’entre eux dans la sommation). En spécialisant au cas où les indéterminées ne commutent jamais ou au contraire commutent toujours, on retrouve les identités connues

(2)  (1 − ∑_{i=1}^{n} T_{i})^{−1} = ∑_{r=0}^{∞} ∑_{i_{1},...,i_{r}} T_{i_{1}} ⋯ T_{i_{r}};

(3)  ((1 − T_{1}) ⋯ (1 − T_{n}))^{−1} = ∑_{α_{1},...,α_{n}} T_{1}^{α_{1}} ⋯ T_{n}^{α_{n}}.

L’établissement de (1) se fait en deux étapes. Considérons un monoïde M dans lequel tout élément n’a qu’un nombre fini de décompositions en produit (d’un nombre quelconque de facteurs). On peut alors former des séries formelles ∑_{x∈M} a_{x} ·x à coefficients entiers par exemple. Nous montrons qu’il existe une fonction μ_{M} (fonction de Möbius de M) telle que

(4)  ( ∑_{x∈M} μ_{M}(x) · x)^{−1} = ∑_{x∈M} x;

cette relation équivaut à ∑_{yz=x} μ_{M}(y) = 0 pour x ≠ 1 et μ_{M}(1) = 1.

Lorsque M est l’ensemble des entiers strictement positifs, avec la multiplication pour opération, la fonction μ_{M} est la fonction de Möbius usuelle ([2], p. 234) et la relation (4) équivaut à l’identité connue

(5)  (∑_{n=1}^{∞} μ(n) · n^{−s})^{−1} = ∑_{n=1}^{∞} n^{−s}.

Il reste à expliciter la fonction μ_{M} pour certains monoïdes. Pour cela, nous étudions au chapitre I les monoïdes engendrés par des générateurs T_{i} soumis à certaines relations de commutation. Le résultat principal est le théorème 1.2 qui résout le problème des mots pour de tels monoïdes, en indiquant une famille réduite et un algorithme pour la réduction à la forme réduite.

B. Flots et cycles sur un graphe

Le chapitre 3 est consacré à une généralisation non commutative de l’homologie. Nous considérons un graphe orienté G (variété combinatoire orientée de dimension 1) ; les simplexes de dimension 0 sont appelés sommets et ceux de dimension 1 arêtes. On suppose pour simplifier qu’il n’y a qu’un nombre fini de sommets et d’arêtes. Pour i = 0, 1, on note C_{i} le groupe commutatif libre engendré par les simplexes de dimension i, appelé classiquement groupe des i-chaînes ; l’opérateur bord ∂ : C_{1} → C_{0} est caractérisé par ∂(a) = t − s pour toute arête a joignant le sommet s au sommet t. Le premier groupe d’homologie H_{1} du graphe G est le noyau de ∂.

Pour tout sommet s, soit Ĉ(s) le groupe libre engendré par les arêtes d’origine s; notons aussi Ĉ_{1} le produit de tous ces groupes Ĉ(s). Il existe un homomorphisme canonique surjectif π : Ĉ_{1} → C_{1}, dont le noyau est le groupe des commutateurs de Ĉ_{1}. Le groupe Ĥ_{1} = π^{−1}(H_{1}) mérite le nom de premier groupe d’homologie non commutatif de G.

En fait, nous ne nous intéressons qu’au sous-monoïde F de Ĉ_{1} engendré par les arêtes, dont les éléments sont appelés flots. Les éléments de F ∩Ĥ_{1} sont appelés circuits. Les résultats essentiels sont deux théorèmes de décomposition d’un circuit. Le théorème 3.5 affirme que le monoïde des circuits est du type envisagé au chapitre I : les générateurs sont des cycles ^{⟨⟨}géométriques^{⟩⟩} et deux cycles commutent si et seulement s’ils n’ont aucun sommet en commun. Ce résultat précise et généralise les théorèmes usuels de décomposition d’un ^{⟨⟨}cycle algébrique^{⟩⟩} en ^{⟨⟨}cycles géométriques^{⟩⟩}. La proposition 3.10 fournit une décomposition d’un circuit en lacets. La méthode de démonstration s’explique facilement dans le langage imagé des labyrinthes. On dispose d’un labyrinthe, dont tous les couloirs sont à sens unique ; de plus, pour chaque carrefour, on a établi un ordre de préséance entre les couloirs partant de ce carrefour (par exemple de la gauche vers la droite à partir d’un d’entre eux) ; enfin, on suppose remplie la condition bien connue d’Euler : il y a autant de couloirs aboutissant à un carrefour que de couloirs qui en partent. Partant d’un carrefour déterminé, on voyage selon la règle dite de Tarry : à chaque carrefour, choisir pour en ressortir le premier des couloirs non encore parcourus. On retourne certainement au point de départ par cette règle, après avoir exploré tout ou partie du labyrinthe ; si tout n’est pas exploré, on peut visiter le reste en recommençant par une méthode analogue.

C. Applications

Au chapitre IV, nous appliquons les résultats précédents au cas d’un graphe G ayant la propriété suivante : quels que soient les sommets s et t, il existe une arête et une seule joignant s à t. On suppose l’ensemble X des sommets totalement ordonné.

Un mot formé de n lettres distinctes dans X est spécifié par la donnée de l’ensemble de ces lettres et de la permutation qui amène ces lettres de l’ordre croissant à l’ordre dans le mot. La décomposition d’une permutation en cycles fournit donc une décomposition d’un mot formé de lettres distinctes en mots cycliques. Nous généralisons ceci à tous les mots grâce à la décomposition en cycles des réarrangements (qui sont des circuits dans G). En interprétant convenablement le produit des circuits, nous retrouvons le monoïde d’intercalement déjà introduit dans [1] ; nous obtenons très facilement les résultats le concernant.

MacMahon a fait grand usage du résultat suivant qu’il a baptisé ^{⟨⟨}Master Theorem^{⟩⟩} [3, page 97] :

Soient X_{1}, …, X_{n} des indéterminées commutatives, b_{ij} des nombres réels et

Y_{i} = ∑_{j=1}^{n} b_{ij}X_{j}.

Pour toute suite de n entiers positifs α_{1}, …, α_{n}, le coefficient du monôme X_{1}^{α_{1}} ⋯ X_{n}^{α_{n}} dans le polynôme Y_{1}^{α_{1}} ⋯ Y_{n}^{α_{n}} est égal au coefficient du même monôme dans le développement en série formelle de l’inverse du déterminant

| \begin{matrix}1 − b_{1,1}X_{1} & − b_{1,2}X_{2} & … & − b_{1,n}X_{n} \\ − b_{2,1}X_{1} & 1 − b_{2,2}X_{2} & … & − b_{2,n}X_{n} \\ ⋮ & ⋮ & ... & ⋮ \\ − b_{n,1}X_{1} & − b_{n,2}X_{2} & … & 1 − b_{n,n}X_{n} \end{matrix} | .

La démonstration de MacMahon est valable dans tout anneau commutatif. Nous montrons au chapitre V que le résultat reste valable dans un anneau quelconque, pourvu que b_{ij} commute à b_{i′j′}, pour i ≠ i′ (théorème 5.1). En fait, sous cette forme, le théorème de MacMahon équivaut à la détermination de la fonction de Möbius du monoïde des circuits sur le graphe G. Par les mêmes méthodes, nous obtenons dans la proposition 5.2 une autre généralisation du ^{⟨⟨}Master Theorem^{⟩⟩}, déjà établie par d’autres moyens dans [1].

Un autre résultat de MacMahon est le suivant [3, page 186] : pour toute permutation σ de {1, 2, …, n}, soit ν(σ) le nombre des entiers i tels que 1 ≤ i ≤ n − 1 et σ(i) > i et soit ξ(σ) le nombre des entiers i tels que 1 ≤ i ≤ n − 1 et σ(i + 1) > σ(i). Pour tout entier m ≥ 0, il y a autant de permutations σ avec ν(σ) = m que de permutations σ avec ξ(σ) = m. En fait, on peut exhiber une bijection Φ de l’ensemble des permutations sur luimême telle que ξ = ν ∘Φ. Nous construisons au chapitre IV une telle bijection dans le cas des ^{⟨⟨}permutations avec répétitions^{⟩⟩} (ou réarrangements) ; cette bijection a déjà été introduite dans [1], mais nous obtenons ici très facilement ses propriétés.

Le chapitre VI est consacré à certaines identités entre coefficients binomiaux. Nous employons une méthode uniforme qui consiste à compter de deux manières différentes certains circuits dans un graphe à trois sommets. Dans le cas des circuits de longueur paire, nous retrouvons les identités de Dixon, Fjeldstad ou Foata [1, chapitre 10]. Dans le cas des circuits de longueur impaire, nous obtenons toute une série de nouvelles identités.

Au chapitre VII, nous appliquons enfin les résultats combinatoires précédents à la détermination des fonctions caractéristiques de certaines variables aléatoires. Nous obtenons une identité tout à fait analogue à celle de Spitzer [5] ; ces résultats généralisent ceux du chapitre 9 de [1].

C’est un fait connu que l’on explique facilement à un ami une méthode combinatoire sur un exemple explicite et qu’une rédaction suivant les canons mathématiques usuels est souvent lourde et obscure. Nous n’espérons pas que ce travail échappe à la règle commune, mais nous souhaitons l’avoir rendu un peu plus attrayant par la discussion d’exemples. La fonction de Möbius a été généralisée dans une autre direction par Rota [4] ; ses résultats ne recoupent pratiquement pas les nôtres. D. E. Knuth, du California Institute of Technology, nous a appris par lettre qu’il a obtenu les mêmes identités entre coefficients binomiaux que nous, par une méthode à peu près identique. Enfin, nous remercions Schützenberger et Verdier pour les nombreuses suggestions qu’ils nous ont faites et qui sont à l’origine de plusieurs des questions étudiées ici.

Strasbourg, le 15 juin 1968

P. CARTIER, D. FOATA

CHAPITRE PREMIER

MONOÏDES DÉFINIS

PAR DES RELATIONS DE COMMUTATION

1. Rappels sur les monoïdes libres

Soit Z un ensemble non vide, dont les éléments seront appelés lettres. Un mot est une suite finie w = z_{1} ⋯ z_{m} de lettres ; l’entier m ≥ 1 est appelé la longueur du mot w. On convient qu’il existe aussi un mot vide, noté 1, de longueur 0 et qui n’a aucune lettre. Si w = z_{1} ⋯ z_{m} et w′ = z′_{1} ⋯ z′_{n} sont deux mots non vides, leur produit w′′ = ww′ = w · w′ est obtenu par juxtaposition de w et w′, c’est-à-dire que l’on a w′′ = z′′_{1} ⋯ z′′_{m+n} avec z′′_{i} = z_{i} pour 1 ≤ i ≤ m et z′′_{i} = z′_{i−m} pour m + 1 ≤ i ≤ m + n. On convient que w · 1 = 1 · w = w pour tout mot w. Pour cette opération, l’ensemble des mots est un monoïde,(^{1}) noté Mo(Z) et appelé monoïde libre construit sur Z.

On note Ab(Z) l’ensemble des fonctions à valeurs entières positives f sur Z, telles que l’ensemble {z ∈ Z | f(z) ≠ 0} soit fini. La somme f + g de deux éléments f et g de Ab(Z) est la fonction définie par (f + g)(z) = f(z) + g(z) pour tout z ∈ Z. Pour cette addition, Ab(Z) est un monoïde commutatif appelé le monoïde commutatif libre construit sur Z.

Pour tout z ∈ Z, on définit un élément ϵ_{z} de Ab(Z) par ϵ_{z}(z) = 1 et ϵ_{z}(z′) = 0 pour z′ distinct de z. Pour tout mot w = z_{1} ⋯ z_{m}, on note ϵ(w) l’élément ϵ_{z_{1}} + ⋯ + ϵ_{z_{m}} de Ab(Z). L’application ϵ est homomorphisme (^{2}) de Mo(Z) sur Ab(Z). On dit qu’un mot w′ = z′_{1} ⋯ z′_{n} est un réarrangement de w = z_{1} ⋯ z_{m} si l’on a ϵ(w) = ϵ(w′) ; il revient au même de dire que toute lettre z intervient un même nombre de fois dans w et dans w′, ou encore qu’on a m = n et qu’il existe une permutation σ de {1, 2, ⋯, m} avec z′_{i} = z_{σ(i)} pour 1 ≤ i ≤ m.

(^{1}) Un monoïde est un ensemble muni d’une multiplication associative, avec élément unité.

Si M est un monoïde, un sous-monoïde est une partie de M stable par multiplication et contenant l’élément unité de M.

(^{2}) Soient M et M′ deux monoïdes, dont on note 1 les éléments unités. Un homomorphisme de M sur M′ est une application f de M dans M′ telle que f(xy) = f(x)f(y) et f(1) = 1.

2. Construction de L(Z; C)

Soient Z un ensemble et C une partie de Z×Z; on suppose que, pour (z, z′) dans C, on a z ≠ z′ et (z′, z) ∈ C. On dit que deux mots w et w′ sont C-adja-cents s’il existe deux mots u et v et un couple (z, z′) dans C avec w = uzz′v et w′ = uz′zv; on dit que les mots w et w′ sont C-équivalents s’ils sont égaux ou s’il existe une suite de mots w_{0}, w_{1}, …, w_{p} telle que w_{0} = w, w_{p} = w′ et w_{i−1} et w_{i} soient C-adjacents pour 1 ≤ i ≤ p. On définit ainsi une relation d’équivalence R_{C} dans Mo(Z), compatible avec la multiplication ; le monoïde quotient Mo(Z)/R_{C} sera noté L(Z; C), son élément neutre sera noté 1 et la classe de C-équivalence d’une lettre z sera notée [z]. L’application z ↦ [z] est injective et L(Z; C) est engendré par l’ensemble des éléments de la forme [z]. On dira que deux lettres z et z′ commutent si l’on a [z] · [z′] = [z′] · [z] dans L(Z; C) ; l’ensemble C se compose alors des couples de lettres distinctes qui commutent.

Soient M un monoïde, (x_{i})_{i∈I} une famille d’éléments de M et C une partie de I × I telle que (i, j) ∈ C entraîne i ≠ j et (j, i) ∈ C. On dit que M est engendré par l’ensemble des x_{i} (i ∈ I) soumis aux relations de commutation x_{i}x_{j} = x_{j}x_{i} pour (i, j) ∈ C s’il existe un isomorphisme φ : L(I; C) → M tel que φ[i] = x_{i} pour tout i ∈ I.

Lemme 1.1. — Soient M un monoïde et f une application de Z dans M ; on suppose que pour (z, z′) dans C, les éléments f(z) et f(z′) de M commutent. Il existe alors un homomorphisme \overline{f} de L(Z; C) dans M et un seul, tel que f(z) = \overline{f}([z]) pour toute lettre z.

Si w = z_{1} ⋯ z_{m} et w′ = z′_{1} ⋯ z′_{m} sont deux mots C-équivalents, on a f(z_{1}) ⋯ f(z_{m}) = f(z′_{1}) ⋯ f(z′_{m}) : cela résulte de l’hypothèse sur f lorsque w et w′ sont C-adjacents et le cas général se déduit de là de proche en proche. Il existe donc une application \overline{f} de L(Z; C) dans M définie par \overline{f}([z_{1}] ⋯ [z_{m}]) = f(z_{1}) ⋯ f(z_{m}) et \overline{f} répond à la question posée.

Comme Ab(Z) est commutatif, le lemme 1.1 assure l’existence d’un homomorphisme π de L(Z; C) dans Ab(Z) tel que π([z]) = ϵ_{z} pour toute lettre z; si l’on note λ l’homomorphisme de Mo(Z) dans L(Z; C) défini par λ(z_{1} ⋯ z_{m}) = [z_{1}] ⋯ [z_{m}], on a ϵ = π ∘ λ, d’où le diagramme commutatif

[figure: Mo(Z); Ab(Z); ϵ; λ; π; L(Z; C)]

Le lemme 1.1 démontre aussi l’existence d’une application ι de L(Z; C) dans lui-même caractérisée par les formules

(1)  ι(1) = 1, ι([z]) = [z], ι(uv) = ι(v)ι(u)

3. STRUCTURE DE L(Z; C) 7

pour toute lettre z et u, v dans L(Z; C). On a ι([z_{1}] ⋯ [z_{m}]) = [z_{m}] ⋯ [z_{1}], d’où

(2)  ι(ι(u)) = u pour tout u dans L(Z; C).

On dit que ι est l’involution dans L(Z; C).

3. Structure de L(Z; C)

On dit qu’une partie F de Z est commutative si elle est finie, non vide et si deux de ses éléments commutent toujours ; on pose dans ce cas [F] = ∏_{z∈F}[z].

On pose aussi [∅] = 1. On dit qu’une lettre z est liée à une partie F de Z si l’on a z ∈ F ou s’il existe une lettre dans F qui ne commute pas à z. Si F et F′ sont deux parties de Z, on dit que F est contiguë à F′ si toute lettre de F′ est liée à F ; on appelle V -suite toute suite (F_{1}, …, F_{r}) de parties commutatives de Z, telle que F_{i} soit contiguë à F_{i+1} pour 1 ≤ i ≤ r − 1 et l’on convient d’une V -suite vide notée o.

Théorème 1.2. — Tout élément u de L(Z; C) admet une V -décomposi-tion, c’est-à-dire une V -suite (F_{1}, …, F_{r}) telle que u = [F_{1}] ⋯ [F_{r}] ; celle-ci est unique.

(A) Existence d’une V -décomposition :

Pour toute V -suite s = (F_{1}, …, F_{r}), on pose p(s) = [F_{1}] ⋯ [F_{r}] avec la convention p(o) = 1. De plus, pour toute V -suite s = (F_{1}, …, F_{r}) et toute lettre z, nous définirons une suite s·z de parties de Z par les règles suivantes :

(1) Si z est liée à F_{r}, on pose s · z = (F_{1}, …, F_{r}, {z}) (cas particulier o · z = {z}).

(2) Si z n’est pas liée à F_{r}, notons j le plus petit des entiers compris entre 1 et r et tels que z ne soit liée à aucune des parties F_{k} pour j ≤ k ≤ r. On pose alors s · z = (F′_{1}, …, F′_{r}) avec F′_{i} = F_{i} pour i ≠ j et F′_{j} = F_{j} ∪ {z}.

Si une lettre z est liée à une partie F de Z, elle est liée à toute partie de Z contenant F ; si, au contraire, z n’est pas liée à une partie commutative F, alors F · {z} est commutative. Ces remarques prouvent que s · z est une V -suite pour toute V -suite s. De plus, on a la relation

(3)  p(s · z) = p(s) · [z];

cette relation est évidente dans le cas (1). Dans le cas (2), la lettre z n’est pas liée à F_{j}, F_{j+1}, …, F_{r}, donc [z] commute à [F_{j+1}] ⋯ [F_{r}] et l’on a [F_{j}] · [z] = [F_{j} ∪ {z}] car z ∉ F_{j}; on en déduit [F_{j}] · [F_{j+1}] ⋯ [F_{r}] · [z] = [F_{j} ∪ {z}] · [F_{j+1}] ⋯ [F_{r}], d’où encore (3).

Soit alors u = [z_{1}] ⋯ [z_{m}] un élément de L(Z; C) ; on pose

s = (⋯ ((o · z_{1}) · z_{2}) · . . . · z_{m}).

De p(o) = 1 et de la formule (3), on déduit par récurrence sur m la relation p(s) = u, c’est-à-dire que s est une V -décomposition de u.

(B) Unicité d’une V -décomposition :

Soient s = (F_{1}, …, F_{r}) une V -suite non vide et z_{1}, z_{2} deux lettres distinctes qui commutent. Soit n ∈ {1, 2}; lorsque z_{n} n’est pas liée à F_{r}, on notera j_{n} le plus petit des entiers compris entre 1 et r et tels que z_{n} ne soit liée à aucune des parties F_{k} pour j_{n} ≤ k ≤ r. Par application des règles (1) et (2) qui définissent s · z, on obient facilement le tableau suivant.

z_{1} liée à F_{r} z_{2} liée à F_{r}  (s · z_{1}) · z_{2}
oui  oui  (F_{1}, …, F_{r}, {z_{1}, z_{2}})
oui  non  (F_{1}, …, F_{j_{2}} ∪ {z_{2}}, …, F_{r}, {z_{1}})
non  oui  (F_{1}, …, F_{j_{1}} ∪ {z_{1}}, …, F_{r}, {z_{2}})
non  non  \{ \begin{matrix}j_{1} = j_{2} & (F_{1}, …, F_{j_{1}} ∪ \{z_{1}, z_{2}\}, …, F_{r}) \\ j_{1} ≠ j_{2} & (F′_{1}, …, F′_{r}) avec F′_{i} = F_{i} \end{matrix}

pour i ∉ {j_{1}, j_{2}}

F′_{j_{n}} = F_{j_{n}} ∪ {z_{n}} pour z ∈ {1, 2}.

Comme z_{2} n’est pas liée à {z_{1}}, on a par ailleurs (o · z_{1}) · z_{2} = {z_{1}, z_{2}}. Il résulte alors du tableau précédent que l’on a dans tous les cas précédents la relation

(4)  (s · z_{1}) · z_{2} = (s · z_{2}) · z_{1} pour toute V -suite s.

Soient w = z_{1} ⋯ z_{m} et w′ = z′_{1} ⋯ z′_{m} deux mots. Si w et w′ sont Cadjacents, la formule (4) entraîne (⋯ (o·z_{1})· . . . ·z_{m}) = (⋯ (o·z′_{1})· . . . ·z′_{m}) et la même conclusion subsiste évidemment si w et w′ sont seulement supposés C-équivalents. Il existe donc une application q de L(Z; C) dans l’ensemble des V -suites définie par

(5)  q([z_{1}] ⋯ [z_{m}]) = (⋯ ((o · z_{1}) · z_{2}) · . . . · z_{m}).

Soit u un élément de L(Z; C). Nous allons montrer que toute V - décomposition s = (F_{1}, …, F_{r}) de u est égale à q(u). Nous raisonnerons par récurrence sur r, le cas r = 0 étant trivial (il correspond à u = 1 et q(u) = s = o). Si l’on pose v = [F_{1}] ⋯ [F_{r−1}] et F_{r} = {z_{1}, …, z_{m}}, on a q(v) = (F_{1}, …, F_{r−1}) par hypothèse de récurrence et u = v · [z_{1}] ⋯ [z_{m}], d’où q(u) = (F_{1}, …, F_{r−1})·z_{1} · . . . ·z_{m}; comme z_{1} est liée à F_{r−1} et que z_{j+1} n’est pas liée à {z_{1}, …, z_{j}} pour 1 ≤ j ≤ m − 1, une application répétée des règles (1) et (2) donne q(u) = (F_{1}, …, F_{r}).

Corollaire 1.3. — La multiplication dans le monoïde L(Z; C) est simplifiable.

Soient z une lettre, t un élément de L(Z; C) et (H_{1}, …, H_{s}) la V - décomposition de t. Supposons qu’il existe un élément u de L(Z; C), de V - décomposition (F_{1}, …, F_{r}), tel que t = u · [z] ; nous dirons qu’on est dans le cas (1) ou dans le cas (2) selon que z est liée à F_{r} ou non. Dans le cas (1), on a r = s − 1 et H_{s} = {z}. Dans le cas (2), soit j le plus petit des entiers compris entre 1 et r tels que z ne soit pas liée à F_{k} pour j ≤ k ≤ r; on a alors s = r et si j < r, on a H_{s} = F_{r} et comme z n’est pas liée à F_{r}, on a z ∉ H_{s}; si, au contraire, on a j = r, on a z ∉ F_{r} et H_{s} = F_{r} ∪ {z}; quel que soit j, on a donc H_{s} ≠ {z}.

On peut donc conclure que l’on est dans le cas (1) ou (2) selon que H_{s} est égal à {z} ou non. Dans le cas (1), on a u = [H_{1}] ⋯ [H_{s−1}] ; dans le cas (2), j est le plus grand des entiers ℓ compris entre 1 et r tels que z ∈ H_{ℓ} et l’on a u = [H_{1}] ⋯ [H_{j−1}][H_{j} \ {z}][H_{j+1}] ⋯ [H_{r}]. Il existe donc au plus un élément u de L(Z; C) tel que t = u · [z].

Soient alors u, u′ et v des éléments de L(Z; C). Comme u · [z] = u′ · [z] entraîne u = u′ pour toute lettre z, une récurrence sur la longueur de v montre que uv = u′v entraîne u = u′. Par ailleurs, de vu = vu′, on déduit ι(u)ι(v) = ι(vu) = ι(vu′) = ι(u′)ι(v), d’où ι(u) = ι(u′) en simplifiant par ι(v) ; finalement, on a u = u′ d’après la formule (2) du n^{o} 2.

Corollaire 1.4. — Soient u un élément de L(Z; C) distinct de 1, (F_{1}, …, F_{r}) sa V -décomposition et F une partie commutative de Z. Pour qu’il existe v dans L(Z; C) avec u = [F] · v, il faut et il suffit que l’on ait F ⊂ F_{1}.

Lorsque F est contenue dans F_{1}, on a u = [F] · v avec v = [F_{1} \ F] · [F_{2}]. · · · .[F_{r}]. Posons Φ(1) = ∅; pour tout élément v ≠ 1 de L(Z; C), notons Φ(v) le premier élément de sa V -décomposition. D’après la partie (A) de la démonstration du théorème 1.2, on a Φ(v · [z]) ⊃ Φ(v) pour tout v dans L(Z; C) et toute lettre z; par récurrence sur la longueur de v′, on en déduit Φ(vv′) ⊃ Φ(v) pour v, v′ dans L(Z; C). Enfin, on a Φ([F]) = F pour toute partie commutative F. S’il existe v dans L(Z; C) avec u = [F] · v, on a donc F = Φ([F]) ⊂ Φ(u) = F_{1}.

4. Un exemple

Pour simplifier l’écriture, on écrira une suite (w_{1}, …, w_{p}) de mots sous la forme w_{1} | w_{2} | ⋯ | w_{p}. Par exemple, l’écriture a b c | d d c a | b b | c désigne la suite des mots w_{1} = abc, w_{2} = ddca, w_{3} = bb, w_{4} = c; on dit que la suite précédente est une décomposition du mot w_{1}w_{2}w_{3}w_{4} = abcddcabbc.

Supposons l’ensemble Z totalement ordonné. A toute partie commutative F on associera le mot formé en rangeant les éléments de F par ordre croissant. Si (F_{1}, …, F_{r}) est la V -décomposition d’un élément de L(Z; C), on l’écrira sous la forme w_{1} | w_{2} | ⋯ | w_{r} où w_{j} est le mot associé à F_{j}.

On est donc amené à considérer des mots coupés en compartiments par des barres |. Une lettre a le droit de se déplacer vers la gauche de deux manières différentes :

(a) à l’intérieur de son compartiment, elle peut sauter toutes les lettres qui lui sont strictement supérieures dans l’ordre de Z;

(b) elle peut sauter dans le compartiment immédiatement à sa gauche si elle est distincte des lettres dudit compartiment et commute avec elles.

Une V -suite correspond ainsi à un mot compartimenté dans lequel aucune lettre n’a le droit de se déplacer. Pour déterminer la V -décomposition d’un élément u = [z_{1}] ⋯ [z_{m}], on détermine successivement les V -décompositions des éléments u_{j} = [z_{1}] ⋯ [z_{j}] pour 1 ≤ j ≤ m. Ayant la V -décomposition de u_{j}, on ajoute z_{j+1} à droite ; si z_{j+1} est égale à une lettre du dernier compartiment, ou ne commute pas avec toutes les lettres dudit compartiment, on crée un nouveau compartiment à droite pour elle. Sinon, on la déplace le plus loin possible vers la gauche.

Pour un exemple, considérons un ensemble Z à cinq éléments a, b, c, d, e, ordonné par a < b < c < d < e; l’ensemble C ⊂ Z × Z se compose des cases non barrées dans le tableau suivant.

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

On considère l’élément u = λ(a b c c d a b c b c e d) de L(Z; C) ; on a alors u_{1} = λ(a), u_{2} = λ(ab), … et si v_{j} est la V -décomposition de u_{j}, on a le tableau suivant :

\begin{aligned}v_{1} & = a \\ v_{2} & = a | b \\ v_{3} & = a c | b \\ v_{4} & = a c | b c \\ v_{5} & = a c | b c | d \\ v_{6} & = a c | b c | d | a \end{aligned}  \begin{aligned}v_{7} & = a c | b c | d | a | b \\ v_{8} & = a c | b c | c d | a | b \\ v_{9} & = a c | b c | c d | a | b | b \\ v_{10} & = a c | b c | c d | a c | b | b \\ v_{11} & = a c | b c | c d | a c | b e | b \\ v_{12} & = a c | b c | c d | a c | b e | b | d. \end{aligned}

Finalement, la V -décomposition de u est a c | b c | c d | a c | b e | b | d.

CHAPITRE II

FONCTION DE MÖBIUS D’UN MONOÏDE

1. Décompositions

On note M un monoïde, 1 son élément unité et M^{∗} l’ensemble des éléments distincts de 1 dans M. On appelle décomposition d’un élément x de M toute suite finie s = (x_{1}, …, x_{q}) d’éléments de M^{∗} telle que x = x_{1} ⋯ x_{q}; l’entier q ≥ 1 s’appelle le degré de la décomposition s. On admet par convention une décomposition vide de 1, de degré 0. Dans ce n^{o} et le suivant, on suppose que tout élément de M n’admet qu’un nombre fini de décompositions. (^{3})

Lemme 2.1. — L’élément 1 n’admet que la décomposition vide.

Il n’existe aucune décomposition de degré 1 de 1. Supposons qu’il existe un entier q ≥ 2 et des éléments x_{1}, …, x_{q} de M^{∗} tels que 1 = x_{1} ⋯ x_{q}; si l’on pose a = x_{1} et b = x_{2} ⋯ x_{q}, on a a ≠ 1 et ab = 1, d’où b ≠ 1. Pour tout entier m ≥ 1, on a alors 1 = (ab)^{m} d’où une décomposition de degré 2m de 1. Il existe donc une infinité de décompositions de 1, contrairement aux hypothèses faites.

Pour tout élément x de M, on note d(x) le nombre des décompositions de x, puis d_{+}(x) celui des décompositions de degré pair et d_{−}(x) celui des décompositions de degré impair. On a évidemment les relations

(1)  d(x) = d_{+}(x) + d_{−}(x), d(1) = d_{+}(1) = 1, d_{−}(1) = 0.

La fonction de Möbius du monoïde M est définie par μ_{M}(x) = d_{+}(x)−d_{−}(x) ; en particulier, on a μ_{M}(1) = 1.

(^{3}) Cette hypothèse équivaut à la conjonction des ceux conditions :

(a) Pour tout x ∈ M, il n’existe qu’un nombre fini de couples (y, z) avec x = yz.

(b) Pour tout x ∈ M, il existe un entier q ≥ 1 tel qu’il n’y ait aucune décomposition de longueur strictement supérieure à q de x.

L’exemple d’un groupe à deux éléments montre que la seconde condition n’est pas conséquence de la première.

2. Formule d’inversion de Möbius

On note A l’ensemble des fonctions à valeurs entières sur M. (^{4}) Nous munirons A de la structure d’anneau dont les opérations sont données par les règles

(2)  (f + g)(x) = f(x) + g(x);
(3)  (fg)(x) = ∑_{x_{1}x_{2}=x} f(x_{1}) · g(x_{2}).

L’élément unité de l’anneau A est la fonction ϵ définie par ϵ(1) = 1 et ϵ(x) = 0 pour x ≠ 1. Dans (3), la somme est étendue à tous les couples (x_{1}, x_{2}) tels que x_{1}x_{2} = x, à savoir les couples (x, 1), (1, x) et les décompositions de degré 2 de x. D’après le lemme 2.1, on a donc

(4)  (fg)(1) = f(1)g(1) pour f, g dans A.

Lemme 2.2. — Soit ζ la fonction constante égale à 1 sur M. On a les relations

(5) ζ d_{+} = d_{+} ζ = d, ζ d_{−} = d_{−} ζ = d − ϵ,
(6)  ζ μ_{M} = μ_{M} ζ = ϵ.

Comme on a ζ(1) = d(1) = d_{+}(1) = ϵ(1) = 1 et d_{−}(1) = 0, la formule (4) montre que les fonctions ζd_{+}, d_{+}ζ et d prennent la valeur 1 en 1 et que ζd_{−}, d_{−}ζ et d − ϵ s’annulent en 1. Soit x dans M^{∗}; on a

(7)  (d_{+} ζ)(x) = ∑_{yz=x} d_{+}(y) = d_{+}(x) + ∑_{z≠1, yz=x} d_{+}(y).

La première somme dans (7) représente le nombre des suites (y_{1}, …, y_{q}, y, z) avec q pair, y_{1}, …, y_{q}, z dans M^{∗}, y = y_{1} ⋯ y_{q} et x = yz; c’est aussi le nombre des décompositions (y_{1}, …, y_{q}, z) de degré impair de x, d’où (d_{+} ζ)(x) = d_{+}(x) + d_{−}(x) = d(x). On établit de manière analogue les relations (ζ d_{+})(x) = (ζ d_{−})(x) = (d_{−} ζ)(x) = d(x) pour x ∈ M^{∗}. On a donc prouvé les formules (5) et l’on en déduit immédiatement (6) par différence.

Lemme 2.3 (Formule d’inversion de Möbius). — Soient f et g deux fonctions à valeurs entières (^{5}) sur M. Les relations suivantes sont équivalentes :

(8)  ∑_{x_{1}x_{2}=x} g(x_{2}) = f(x) pour tout x ∈ M;
(9)  ∑_{x_{1}x_{2}=x} μ_{M}(x_{1})f(x_{2}) = g(x) pour tout x ∈ M.

La relation (8) s’écrit ζ g = f et (9) s’écrit μ_{M}f = g; elles sont donc équivalentes puisque ζμ_{M} = μ_{M}ζ = ϵ et ϵf = f, ϵg = g.

(^{4}) On pourrait plus généralement considérer des fonctions sur M à valeurs dans un anneau commutatif K avec élément unité. On obtient ainsi l’algèbre large du monoïde M à coefficients dans l’anneau K (cf. Bourbaki, Alg. II, 2^{ième} édition, § 7, n^{o} 10).

(^{5}) La même conclusion reste valable pour des fonctions f et g sur M à valeurs dans un groupe commutatif.

3. Fonction de Möbius du monoïde L(Z; C)

Nous allons d’abord montrer que, dans le monoïde L(Z; C) défini au chapitre 1.2, tout élément n’a qu’un nombre fini de décompositions ; nous utiliserons pour cela l’homomorphisme π de L(Z; C) dans Ab(Z). Soient f dans Ab(Z) et z_{1}, …, z_{p} les éléments z de Z tels que f(z) ≠ 0 ; on pose m_{i} = f(z_{i}) pour 1 ≤ i ≤ p et m = m_{1} + ⋯ + m_{p}. Les éléments u de L(Z; C) tels que π(u) = f sont de la forme [t_{1}] ⋯ [t_{m}] avec t_{1}, …, t_{m} dans Z, la lettre z_{i} apparaissant m_{i} fois dans le mot t_{1} ⋯ t_{m} pour 1 ≤ i ≤ p; par suite π^{−1}(f) est fini pour tout f ∈ L(Z; C). Soient alors u dans L(Z; C) et f = π(u) ; pour toute décomposition (u_{1}, …, u_{q}) de u dans L(Z; C), la suite (π(u_{1}), …, π(u_{q})) est une décomposition de f dans Ab(Z) ; comme f n’a qu’un nombre fini de décompositions dans Ab(Z) et que pour f_{1}, …, f_{q} données, il n’y a qu’un nombre fini de solutions du système π(u_{1}) = f_{1}, …, π(u_{q}) = f_{q}, l’élément u n’a qu’un nombre fini de décompositions dans L(Z; C).

Dans toute la suite, nous notons |F | le nombre d’éléments d’un ensemble fini F.

Théorème 2.4. — La fonction de Möbius du monoïde L(Z; C) est la fonction μ donnée par μ([F]) = (−1)^{|F |} pour toute partie commutative F de Z et μ(u) = 0 dans les autres cas.

Soit μ la fonction sur L(Z; C) définie dans l’énoncé et soit ζ la fonction constante égale à 1 sur L(Z; C). Soient u un élément de L(Z; C) et (F_{1}, …, F_{r}) sa V -décomposition ; d’après les corollaires 1.3 et 1.4, les couples (F, v) où la partie commutative F de Z et v dans L(Z; C) satisfont à [F] · v = u sont les couples (F, [F_{1} \ F] · [F_{2}] ⋯ [F_{r}]) avec F ⊂ F_{1}. On a donc (μζ)(u) = ∑_{F ⊂F_{1}}(−1)^{|F |}; si u = 1, on a F_{1} = ∅ et la somme précédente vaut 1 ;

sinon, notons n le cardinal de F_{1}, d’où (μζ)(u) = ∑_{r=0}^{n}(−1)^{r}\binom{n}{r} = (1−1)^{n} = 0.

On a donc prouvé μζ = ϵ; si μ′ est la fonction de Möbius de L(Z; C), on a alors μ′ = ϵμ′ = (μζ)μ′ = μ(ζμ′) = μϵ = μ.

4. Cas particuliers

(a) Lorsque C est vide, le monoïde L(Z; C) se réduit à Mo(Z), les parties commmutatives ont un élément et l’on a μ(z) = −1 pour tout lettre z, puis μ(1) = 1 et μ(w) = 0 pour tout mot de longueur supérieure ou égale à 2. Supposons en particulier que z soit un ensemble fini à n éléments T_{1}, …, T_{n}; l’application f ↦ ∑_{w∈Mo(Z)} f(w) · w est un isomorphisme de l’anneau A

défini au n^{o} 2 (pour M = Mo(Z)) sur l’anneau des séries formelles non commutatives à coefficients entiers en T_{1}, …, T_{n}. A la fonction ζ correspond

la série ∑_{w} w = ∑_{r=0}^{∞} ∑_{i_{1},...,i_{r}=1}^{n} T_{i_{1}} ⋯ T_{i_{r}} ; à la fonction μ correspond la série

1 − ∑_{i=1}^{n} T_{i}, d’où l’identité ∑_{w} w = (1 − T_{1} − ⋯ − T_{n})^{−1}.

(b) Supposons maintenant que C se compose de tous les couples d’éléments distincts de Z. L’application π est un isomorphisme de L(Z; C) sur Ab(Z), qui nous permettra d’identifier ces deux monoïdes. Toute partie finie non vide F de Z est commutative et [F] est la fonction égale à 1 sur F et à 0 sur Z \ F. Le théorème 2.4 détermine donc la fonction de Möbius sur Ab(Z) ; lorsque Z est l’ensemble des nombres premiers, l’application f ↦ ∏_{p∈Z} p^{f(p)}

est un isomorphisme de Ab(Z) sur le monoïde multiplicatif des entiers n ≥ 1 et l’on retrouve les résultats connus sur la fonction de Möbius proprement dite.

Particularisons encore en supposant que Z a n éléments T_{1}, …, T_{n}. L’anneau A défini au n^{o} 2 pour M = Ab(Z) est isomorphe à l’anneau ℤ[[T_{1}, …, T_{n}]] des séries formelles commutatives à coefficients entiers en T_{1}, …, T_{n}, la fonction f correspondant à la série

∑_{α_{1},...,α_{n}≥0} f(α_{1}, …, α_{n})T_{1}^{α_{1}} ⋯ T_{n}^{α_{n}}.

La fonction ζ correspond à

∑_{α_{1},...,α_{n}≥0} T_{1}^{α_{1}} ⋯ T_{n}^{α_{n}}

et μ à

∑_{F ⊂{1,...,n}}(−1)^{|F |} ∏_{j∈F} T_{j} = ∏_{i=1}^{n}(1 − T_{i}).

Supposant toujours Z fini, on peut appliquer la formule d’inversion de Möbius à deux fonctions f et g nulles sur les éléments de Ab(Z) qui ne sont pas de la forme [F] avec F ⊂ Z. On retrouve le résultat connu : si f et g sont deux fonctions définies sur l’ensemble des parties d’un ensemble fini Z, les relations ∑_{F′⊂F} f(F′) = g(F) et ∑_{F′⊂F}(−1)^{−|F′|}g(F \ F′) = f(F)

sont équivalentes (principe d’inclusion et d’exclusion).

CHAPITRE 3

CIRCUITS DANS UN GRAPHE

1. Définitions

Un graphe orienté G est un quadruplet (S, A, σ, β) où S et A sont deux ensembles et σ, β deux applications de A dans S. Les éléments de S sont appelés les sommets et ceux de A les arêtes du graphe G; si a est une arête, le sommet σ(a) est appelé sa source et le sommet β(a) son but ; on dit aussi que l’arête a joint le sommet s au sommet t si l’on a σ(a) = s et β(a) = t.

Un flot dans G est une famille (f_{s,i})_{s∈S, 1≤i≤h(s)} ayant les propriétés suivantes :

(a) h est une fonction sur S à valeurs entières positives ;

(b) l’ensemble Φ des sommets s tels que h(s) ≠ 0 est fini ;

(c) pour tout s ∈ Φ et tout entier i avec 1 ≤ i ≤ h(s), l’élément f_{s,i} est une arête de source s.

Soient f = (f_{s,i})_{s∈S, 1≤i≤h(s)} et f′ = (f′_{s,i})_{s∈S, 1≤i≤h′(s)} deux flots ; leur produit ff′ est le flot f′′ = (f′′_{s,i})_{s∈S, 1≤i≤h”(s)} défini par

(1)  h′′(s) = h(s) + h′(s);
(2)  f′′_{s,i} = \{ \begin{matrix}f_{s,i} & pour 1 ≤ i ≤ h(s) ; \\ f′_{s,i−h(s)} & pour h(s) + 1 ≤ i ≤ h(s) + h′(s). \end{matrix}

L’ensemble des flots est un monoïde, ayant pour unité le flot correspondant à h = 0.

Soit f = (f_{s,i})_{s∈S, 1≤i≤h(s)} un flot. L’entier ∑_{s∈S} h(s) s’appelle la longueur

du flot. De plus, la matrice d’incidence N(f) = (n_{s,t})_{s,t∈S} est définie ainsi : si s et t sont deux sommets, l’entier n_{s,t} est le nombre d’entiers i tels que 1 ≤ i ≤ h(s) et β(f_{s,i}) = t (autrement dit, le nombre d’arêtes du flot joignant s à t). On a évidemment

(3)  ∑_{t∈S} n_{s,t} = h(s);

si l’on a aussi

(4)  ∑_{s∈S} n_{s,t} = h(t) (pour tout t ∈ S),

on dit que f est un circuit. La formule N(ff′) = N(f) + N(f′) montre que si f et f′ sont des flots et si deux des trois flots f, f′, ff′ sont des circuits, le troisième est aussi un circuit. En particulier, les circuits forment un sous-monoïde du monoïde des flots.

Remarque 3.1. — Pour tout sommet s, soit T_{s} le monoïde libre construit sur l’ensemble des arêtes de source s. Soit le monoïde produit ∏_{s∈S} T_{s}. Le

monoïde des flots est par définition le sous-monoïde de T formé des familles (t_{s})_{s∈S} telles que l’ensemble {s | t_{s} ≠ 1} soit fini. Comme la multiplication est simplifiable dans un monoïde libre, elle l’est dans le monoïde des flots et a fortiori dans le sous-monoïde des circuits. Ce dernier cas est aussi une conséquence du théorème 3.3 et du corollaire 1.3.

2. Structure des flots

Soient a une arête et \overline{s} sa source ; le flot b(a) est par définition le flot (f_{s,i})_{s∈S, 1≤i≤h(s)} tel que h(\overline{s}) = 1, h(s) = 0 pour s ≠ \overline{s} et f_{\overline{s},i} = a. Il est immédiat que b(a) et b(a′) commutent si les arêtes a et a′ ont des sources distinctes. De plus, un flot quelconque f = (f_{s,i})_{s∈S, 1≤i≤h(s)} peut se mettre sous forme de produit (^{6})

(5)  f = ∏_{s∈S} ∏_{i=1}^{h(s)} b(f_{s,i}).

On dit qu’un flot f = (f_{s,i})_{s∈S, 1≤i≤h(s)} est simple si h ne prend que les valeurs 0 et 1 ; il revient au même de dire que f est de la forme ∏_{s∈Φ} b(a_{s})

où Φ est un ensemble fini de sommets et où l’arête a_{s} est de source s pour tout s ∈ Φ ; l’ensemble Φ s’appelle le support du flot simple f.

Lemme 3.2. — Soit f un flot. Il existe une suite (f_{1}, …, f_{m}) de flots simples et une seule, telle que f = f_{1} ⋯ f_{m} et que le support de f_{i} contienne celui de f_{i+1} pour 1 ≤ i ≤ m − 1.

Représentons f sous la forme (5) et notons m le plus grand des entiers h(s). Pour 1 ≤ i ≤ m, soit Φ_{i} l’ensemble des sommets s tels que h(s) ≥ i et soit f_{i} le flot simple ∏_{s∈Φ_{i}} b(f_{s,i}). Il est immédiat que (f_{1}, …, f_{m}) est la suite cherchée.

Théorème 3.3. Le monoïde des flots sur le graphe G est engendré par l’ensemble des flots b(a) (pour a ∈ A), soumis aux relations de commutation b(a)·b(a′) = b(a′)·b(a) pour tous les couples d’arêtes a et a′ ayant des sources distinctes.

(^{6}) Pour tout sommet s, posons u(s) = ∏_{i=1}^{h(s)} b(f_{s,i}). Les flots u(s) commutent deux à deux et il existe une partie finie S′ de S telle que u(s) = 1 pour tout s ∈ S \ S′. Le produit ∏_{s∈S} u(s) est donc défini sans ambiguïté.

Soit C l’ensemble des couples d’arêtes (a, a′) telles que σ(a) ≠ σ(a′). Lorsque (a, a′) appartient à C, on a b(a) · b(a′) = b(a′) · b(a), donc l’application b se prolonge en un homomorphisme b′ de L(A; C) dans le monoïde des flots. Avec les notations de 1.3, les parties commutatives de A sont de la forme F = {a_{s} | s ∈ Φ} où Φ est un ensemble fini de sommets et a_{s} une arête de source s pour tout s ∈ Φ ; de plus, on a b′[F] = ∏_{s∈Φ} b(a_{s}). Enfin, si F et F′ sont deux parties commutatives de A, la partie F est contiguë à F′ si et seulement si le support de b′[F] contient celui de b′[F′]. Par suite, l’homomorphisme b′ transforme la V -décomposition d’un élément u de L(A; C) en la décomposition du lemme 3.2 du flot b′(u). Le théorème 1.2 sur les V -décompositions entraîne donc que b′ est bijectif.

3. Structure des circuits

Soient Φ un ensemble fini non vide de sommets, u une permutation de Φ et pour tout s ∈ Φ, soit a_{s} une arête joignant s à u(s) ; notons a la famille (a_{s})_{s∈Φ} ; on posera c(Φ, u, a) = ∏_{s∈Φ} b(a_{s}). Par abus de notation, nous écrirons parfois c(Φ, u, a_{s}) au lieu de c(Φ, u, a). Du fait que u est une permutation de Φ, on obtient là un circuit simple ; de plus, tout circuit simple s’obtient ainsi d’une manière et d’une seule. On dira que le circuit simple c(Φ, u, a) est contigu au circuit simple c(Φ′, u′, a′) si, pour tout sommet s′ ∈ Φ′, il existe un entier m ≥ 1 avec u^{′m}(s′) ∈ Φ.

Proposition 3.4. — Soit f un circuit. Il existe une suite (f_{1}, …, f_{m}) de circuits simples et une seule, telle que f = f_{1} ⋯ f_{m} et que f_{i} soit contigu à f_{i+1} pour 1 ≤ i ≤ m − 1.

(A) Existence de la décomposition :

Nous raisonnerons par récurrence sur la longueur ℓ de f, le cas ℓ = 0 étant trivial. Supposons donc ℓ ≥ 1 et l’existence d’une décomposition prouvée pour les circuits de longueur inférieure à ℓ.

Posons f = (f_{s,i})_{s∈S, 1≤i≤h(s)} et notons Σ l’ensemble des sommets s tels que h(s) ≠ 0. Si une arête f_{s,i} joint s à t, on a n_{s,t} ≥ 1 ; comme f est un circuit, on a h(t) = ∑_{s′} n_{s′,t} d’où h(t) ≥ 1 et finalement t ∈ Σ. Il existe donc une application v de Σ dans lui-même telle que l’arête f_{s,1} joigne s à v(s).

La suite des ensembles finis Σ, v(Σ), v^{2}(Σ), … est décroissante ; il existe donc un entier m_{0} ≥ 0 et une partie non vide Φ de Σ tels que v^{m}(Σ) = Φ pour m ≥ m_{0}. De plus, v induit une permutation u de Φ et par suite f_{1} = ∏_{s∈Φ} b(f_{s,1}) est un circuit simple. Il existe un circuit f′ tel que f = f_{1}f′ et comme f′ est de longueur strictement inférieure à ℓ, il existe par l’hypothèse de récurrence des circuits simples f_{2}, …, f_{m} tels que f′ = f_{2} ⋯ f_{m} et que f_{i} soit contigu à f_{i+1} pour 2 ≤ i ≤ m − 1. Il reste donc à prouver que f_{1} est contigu à f_{2}.

Posons f_{2} = c(Φ′, u′, a′) ; comme f = f_{1}f_{2} ⋯ f_{m}, il est clair que l’on a a′_{s} = f_{s,1}, d’où u′(s) = v(s) pour s ∈ Φ′ ∩ Φ^{c}. (^{7}) Pour tout s dans Φ′ ∩ Φ^{c}, il existe un entier m ≥ 1 tel que les sommets s, v(s), …, v^{m−1}(s) appartiennent à Φ′∩Φ^{c} et que v^{m}(s) appartienne à Φ : cela résulte aussitôt de la construction de Φ. On a alors v^{i+1}(s) = u′(v^{i}(s)) pour i ∈ {0, 1, …, m−1}, d’où u^{′m}(s) = v^{m}(s) ∈ Φ. On a donc prouvé que f_{1} est contigu à f_{2}.

(^{7}) Si U est une partie de S, on note U^{c} son complémentaire dans S.

(B) Unicité de la décomposition :

En raisonnant par récurrence sur la longueur de f, on se ramène à prouver l’assertion suivante : soient g_{1}, …, g_{n} des circuits simples tels que f = g_{1} ⋯ g_{n} et que g_{j} soit contigu à g_{j+1} pour 1 ≤ j ≤ n − 1. On a alors g_{1} = f_{1} (noter que la multiplication est simplifiable dans le monoïde des circuits d’après la remarque 3.1).

Sous les hypothèses précédentes, posons g_{j} = c(Φ_{j}, u_{j}, a_{s,j}) et Ψ_{j} = Φ_{j} ∩ (Φ_{1} ∪ ⋯ ∪ Φ_{j−1})^{c} pour 1 ≤ j ≤ n. La relation f = g_{1} ⋯ g_{n} entraîne Σ = Φ_{1} ∪ ⋯ ∪ Φ_{n} = Ψ_{1} ∪ ⋯ ∪ Ψ_{n} et f_{s,1} = a_{s,j}, d’où v(s) = u_{j}(s), pour 1 ≤ j ≤ n et s ∈ Ψ_{j}. Soit s ∈ Φ_{j} (avec 2 ≤ j ≤ n) ; comme g_{j−1} est contigu à g_{j}, il existe un entier m ≥ 0 tel que (u_{j})^{m}(s) ∈ Φ_{j−1} ; si l’on note μ le plus petit des entiers positifs m tels que (u_{j})^{m}(s) appartienne à Φ_{1} ∪ ⋯ ∪ Φ_{j−1}, on a (u_{j})^{μ}(s) = v^{μ}(s), d’où v^{μ}(s) ∈ Φ_{1} ∪ ⋯ ∪ Φ_{j−1}, on a (u_{j})^{μ}(s) = v^{μ}(s), d’où v^{μ}(s) ∈ Φ_{1} ∪ ⋯ ∪ Φ_{j−1}. Ce résultat entraîne que, pour tout s ∈ Σ, il existe un entier m(s) ≥ 0 avec v^{m(s)}(s) ∈ Φ_{1}. Or, on a v(Φ_{1}) = Φ_{1} car v coïncide sur Φ_{1} avec la permutation u_{1} de Φ_{1} ; pour tout entier m ≥ 0, on a donc Φ_{1} = v^{m}(Φ_{1}) ⊂ v^{m}(Σ), d’où Φ_{1} ⊂ Φ = ⋂_{m≥0} v^{m}(Σ). Par ailleurs Σ est

fini et pour m ≥ sup m(s), on a v^{m}(s) ∈ Φ_{1} pour tout s ∈ Σ, d’où Φ ⊂ Φ_{1}.

On a donc prouvé Φ = Φ_{1} ; comme on a aussi f_{s,1} = a_{s,1} pour tout s ∈ Φ_{1}, on a g_{1} = f_{1}.

4. Cycles

On dit qu’un flot est un cycle s’il existe des sommets distincts s_{1}, …, s_{m} et des arêtes a_{1}, …, a_{m} tels que z = b(a_{1}) ⋯ b(a_{m}) et que a_{1} joigne s_{1} à s_{2}, a_{2} joigne s_{2} à s_{3}, …, a_{m−1} joigne s_{m−1} à s_{m} et a_{m} joigne s_{m} à s_{1}. Lorsqu’il y a au plus une arête de source et de but donnés, on pourra représenter sans ambiguïté le cycle précédent par la notation [s_{1} ⋯ s_{m}] où n’interviennent que les sommets des cycles.

On notera Z l’ensemble des cycles et D l’ensemble des couples de cycles n’ayant aucun sommet en commun ; il est immédiat que l’on a

(6)  zz′ = z′z pour (z, z′) ∈ D.

De plus, les cycles ne sont autres que les circuits simples de la forme c(Φ, u, a) où u est une permutation circulaire de Φ. La décomposition usuelle d’une permutation en cycles montre alors que tout circuit simple s’écrit de manière unique sous la forme [T] = ∏_{z∈T} z, où T est une partie finie non vide de Z telle que (z, z′) ∈ D pour z, z′ distincts dans T. Si [T′] est un autre circuit simple, il est immédiat que [T] est contigu à [T′] si et seulement si, pour tout z′ ∈ T′, il existe z ∈ T avec (z, z′) ∉ D.

D’après la relation (6), il existe un homomorphisme φ de L(Z; D) dans le monoïde des circuits qui applique tout cycle sur lui-même. Les remarques précédentes montrent que φ transforme la V -décomposition d’un élément u de L(Z; D) en la décomposition du circuit φ(u) décrite dans la proposition 3.4. Le théorème 1.2 sur les V -décompositions et la proposition 3.4 entraînent alors le théorème suivant.

Théorème 3.5. — Le monoïde des circuits sur le graphe G est engendré par l’ensemble des cycles soumis aux relations de commutation zz′ = z′z pour tous les couples de cycles z et z′ n’ayant aucun sommet en commun.

Remarque 3.6. — Le théorème précédent permet de déterminer facilement la fonction de Möbius μ du monoïde des circuits. En effet, utilisant le théorème 2.4, on voit d’abord que l’on a μ(z_{1} ⋯ z_{r}) = (−1)^{r} si z_{1}, …, z_{r} sont des cycles n’ayant deux à deux aucun sommet en commun et que l’on a μ(f) = 0 si le circuit f n’est pas de la forme précédente. Or la signature d’une permutation circulaire portant sur n éléments est égale à (−1)^{n+1}. Utilisant la décompositon d’un circuit simple en cycles, on obtient le résultat définitif suivant.

(a) Si le circuit f est simple, de la forme f = c(Φ, u, a), on a μ(f) = ϵ · (−1)^{|Φ|} où ϵ est la signature de la permutation u.

(b) Si le circuit f n’est pas simple, on a μ(f) = 0.

5. Relation avec les chemins

Nous allons d’abord rappeler les définitions usuelles. A tout sommet s on fait par convention correspondre un chemin e_{s} de longueur 0 et l’on pose σ(e_{s}) = β(e_{s}) = s. Pour tout entier m ≥ 1, un chemin de longueur m est une suite c = (a_{1}, …, a_{m}) d’arêtes telles que β(a_{i}) = σ(a_{i+1}) pour 1 ≤ i ≤ m−1 ; il existe alors des sommets s_{0}, s_{1}, …, s_{m} tels que a_{i} joigne s_{i−1} à s_{i} pour 1 ≤ i ≤ m; on dit que s_{0}, s_{1}, …, s_{m} sont les sommets de c et que s_{0} est la source σ(c) et s_{m} le but β(c) de c. On dit aussi que c joint s_{0} à s_{m}.

Le produit des chemins est défini de la manière suivante : soient s, t et u des sommets, c un chemin joignant s à t et c′ un chemin joignant t à u. Si c est de longueur 0, on pose cc′ = c′; si c′ est de longueur 0, on pose cc′ = c; si c = (a_{1}, …, a_{m}) et c′ = (a′_{1}, …, a′_{n}) sont de longueur non nulle, la suite (a_{1}, …, a_{m}, a′_{1}, …, a′_{n}) est un chemin noté cc′. Dans tous les cas, cc′ joint s à u et sa longueur est la somme des longueurs de c et c′. Les chemins de longueur 1 sont des arêtes et un chemin c = (a_{1}, …, a_{m}) n’est autre que le produit a_{1} ⋯ a_{m}.

Soit s un sommet. Un lacet de source s est un chemin joignant s à s. Pour la multiplication précédemment définie, les lacets de source s forment un monoïde, d’élément unité e_{s}. Soit c un lacet de source s, de sommets s_{0}, s_{1}, …, s_{m} (avec s_{0} = s_{m} = s) ; on dit que c est irréductible si l’on a m ≥ 1 et s_{i} ≠ s pour 1 ≤ i ≤ m−1. Tout lacet de source s s’écrit de manière unique sous la forme c_{1} ⋯ c_{p}, où c_{1}, …, c_{p} sont des lacets irréductibles : il suffit pour le voir de couper un lacet aux endroits où il repasse en s.

A tout chemin c = a_{1} ⋯ a_{m}, nous ferons correspondre le flot b(c) = b(a_{1}) ⋯ b(a_{m}). On voit immédiatement que b(c) est un circuit si c est un lacet et que l’on a b(cc′) = b(c) · b(c′) lorsque le produit des chemins c et c′ est défini. De plus b(e_{t}) est le flot nul pour tout sommet t.

Proposition 3.7. — Soit f = (f_{s,i})_{s∈S,1≤i≤h(s)} un flot et t un sommet. On note C_{t} l’ensemble des chemins c de source t pour lesquels le flot b(c) divise f à gauche. (^{8}) Il existe un chemin γ = α_{1} ⋯ α_{μ} et un seul tel que C_{t} se compose des chemins γ_{m} = α_{1} ⋯ α_{m} pour m ∈ {0, 1, …, μ}.

Notons ℓ la longueur de f. Pour tout chemin c, le flot b(c) a même longueur que c; il en résulte que tout chemin c tel que b(c) divise f à gauche est de longueur au plus égale à ℓ. De plus, on a e_{t} ∈ C_{t} donc C_{t} n’est pas vide. Il existe donc dans C_{t} un chemin de longueur maximale. Si γ = α_{1} ⋯ α_{μ} est un tel chemin, nous poserons γ_{m} = α_{1} ⋯ α_{m} pour m ∈ {0, 1, …, μ}. Il est clair que chacun des chemins γ_{0}, γ_{1}, …, γ_{μ} appartient à C_{t} et la proposition 3.7 résulte alors du lemme suivant.

Lemme 3.8. — Pour tout entier m ≥ 0 il existe au plus un chemin de longueur m dans C_{t}.

Soient c un chemin de longueur m, a_{1}, …, a_{m} ses arêtes et s_{0}, s_{1}, …, s_{m} ses sommets. Pour tout sommet s, on note k(s) le nombre de fois que s apparaît dans la suite s_{0}, s_{1}, …, s_{m−1} et l’on range sous forme d’une suite strictement croissante (u(s, 1), …, u(s, k(s)) les entiers i tels que 1 ≤ i ≤ m et s_{i−1} = s. Soit i un entier compris entre 0 et m − 1 ; il existe un entier k_{i} et un seul tel que 1 ≤ k_{i} ≤ k(s_{i}) et u(s_{i}, k_{i}) = i + 1 et k_{i} représente le nombre de fois que le sommet s_{i} apparaît dans la suite s_{0}, s_{1}, …, s_{i}. On a

(7)  f = ∏_{s∈S} ∏_{i=1}^{h(s)} b(f_{s,i})

(8)  b(c) = ∏_{s∈S} ∏_{j=1}^{k(s)} b(a_{u(s,j)})

et par suite, le flot b(c) divise à gauche le flot f si et seulement si l’on a k(s) ≤ h(s) et a_{u(s,j)} = f_{s,j} pour j ∈ {1, …, k(s)}, quel que soit le sommet s. Ces conditions équivalent à

(9)  a_{i+1} = f_{s_{i},k_{i}}  pour 0 ≤ i ≤ m − 1

et entraînent

(10)  s_{i+1} = β(f_{s_{i},k_{i}}) pour 0 ≤ i ≤ m − 1.

(^{8}) Nous disons que f′ divise f à gauche s’il existe f′ avec f = f′f′′.

Comme on a s_{0} = t et k_{0} = 1 et que k_{i} ne dépend que des sommets s_{0}, s_{1}, …, s_{i}, les formules récurrentes (9) et (10) montrent qu’il existe au plus un chemin c de longueur m dans C_{t}.

Propositon 3.9. — On conserve les notations de 3.7 et l’on suppose que f est un circuit et que h(t) est non nul. Le chemin γ est alors un lacet et il existe dans C_{t} un lacet irréductible et un seul.

Pour montrer que γ est un lacet, nous raisonnerons par l’absurde en montrant que, si un chemin c de longueur m appartient à C_{t} et n’est pas un lacet, il existe dans C_{t} un chemin de longueur m + 1.

Soient donc a_{1}, …, a_{m} les arêtes et s_{0}, s_{1}, …, s_{m} les sommets de c. Pour tout sommet s ≠ s_{m}, notons k(s) le nombre de fois que s apparaît dans

la suite s_{0}, s_{1}, …, s_{m−1} et posons u(s) = ∏_{i=1}^{k(s)} b(f_{s,i}). Par ailleurs, notons k

le nombre de fois que s_{m} apparaît dans la suite s_{0}, s_{1}, …, s_{m−1} et rangeons sous forme d’une suite strictement croissante i_{1}, …, i_{k} les entiers i tels que 1 ≤ i ≤ m − 1 et s_{i} = s_{m}. On a alors

(11)  b(c) = ∏_{s≠s_{m}} u(s) · ∏_{r=1}^{k} b(f_{s_{m},r})

(le second terme disparaît si k = 0 et l’on a s_{0} ≠ s_{m}).

Par ailleurs, notons (n′_{s,s′}) la matrice d’incidence de b(c) et (n_{s,s′}) celle de f. Comme b(c) divise f, on a n′_{s,s′} ≤ n_{s,s′} et comme f est un circuit, on a ∑_{s∈S} n_{s,s′} = h(s′). Or les arêtes a_{i_{1}}, a_{i_{2}}, …, a_{i_{k}}, a_{m} ont pour but le sommet s_{m}, d’où k + 1 ≤ ∑_{s∈S} n′_{s,s_{m}} ≤ ∑_{s∈S} n_{s,s_{m}} = h(s_{m}). L’arête a_{m+1} = f_{s_{m},k+1} est donc définie et la formule (11) prouve que le flot b(c · a_{m+1}) = b(c) · b(a_{m+1}) divise à gauche f. Par conséquent, le chemin a_{1} ⋯ a_{m}a_{m+1} de longueur m + 1 appartient à C_{t}.

On a donc prouvé que γ est un lacet. Comme on a h(t) ≥ 1, l’arête f_{t,1} appartient à C_{t}, d’où μ ≥ 1. Le lacet γ se décompose de manière unique en un produit de lacets irréductibles c_{1} ⋯ c_{p} (avec p ≥ 1). Soit c un lacet irréductible de source t. Pour que c appartienne à C_{t}, il faut et il suffit qu’il eixste un lacet c′ de source t avec cc′ = γ = c_{1} ⋯ c_{p}, ce qui équivaut à c = c_{1}.

6. Décomposition descendante d’un circuit

On suppose dans ce n^{o} que l’ensemble S des sommets du graphe G est totalement ordonné. On appelle décomposition descendante d’un circuit f toute suite (c_{1}, …, c_{p}) de lacets irréductibles qui possède les propriétés suivantes :

(a) on a f = b(c_{1}) ⋯ b(c_{p}) ;

(b) on a σ(c_{1}) ≥ ⋯ ≥ σ(c_{p}) ;

(c) pour i ∈ {1, …, p}, la source σ(c_{i}) est le plus grand sommet du lacet c_{i}.

Posons f = (f_{s,i})_{s∈S, 1≤i≤h(s)} ; la formule f = b(c_{1}) ⋯ b(c_{p}) montre que l’on a h(s) ≠ 0 si et seulement si s est un sommet de l’un des lacets c_{1}, …, c_{p}; il résulte alors de (b) et (c) que l’on a s ≤ σ(c_{1}) pour tout sommet s tel que h(s) ≠ 0.

Proposition 3.10. — Tout circuit f possède une décomposition descendante et une seule.

Nous noterons ℓ la longueur de f et nous supposerons ℓ ≠ 0, le cas ℓ = 0 étant trivial. Nous noterons N l’ensemble des sommets s tels que h(s) ≠ 0 ; il est fini, donc possède un plus grand éléments s_{1}.

(A) Unicité de la décomposition descendante :

Raisonnant par récurrence sur ℓ, il suffit d’établir l’assertion suivante : si (c_{1}, …, c_{p}) et (c′_{1}, …, c′_{p′}) sont des décompositions descendantes de f, on a c_{1} = c′_{1}. Sous l’hypothèse faite, les lacets irréductibles c_{1} et c′_{1} sont tels que b(c_{1}) et b(c′_{1}) divisent à gauche f; la remarque précédant la proposition 3.10 montre que c_{1} et c′_{1} ont tous deux pour source le sommet s_{1} ; on a donc c_{1} = c′_{1} d’après la proposition 3.9.

(B) Existence de la décomposition descendante :

Comme on a h(s_{1}) ≠ 0, il existe un lacet irréductible c_{1} de source s_{1} et un circuit f′ tels que f = b(c_{1}) · f′. Comme f′ est de longueur strictement inférieure à ℓ, on peut admettre par hypothèse de récurrence que f′ possède une décomposition descendante (c_{2}, …, c_{p}). On a f′ = b(c_{2}) ⋯ b(c_{p}), d’où f = b(c_{1})b(c_{2}) ⋯ b(c_{p}). Les sommets de c_{1} appartenant à N, la source s_{1} = σ(c_{1}) de c_{1} est le plus grand des sommets de c_{1} ; comme σ(c_{2}) ∈ N, on a σ(c_{1}) = s_{1} ≥ σ(c_{2}) et par suite (c_{1}, c_{2}, …, c_{p}) est une décomposition descendante de f.

Exemple 3.11. — Nous considérons le graphe G de sommets 1, 2, 3, 4, 5, 6 avec l’ordre naturel sur les sommets et dont les arêtes sont figurées sur le dessin ci-après ; on considère sur G le flot f représenté aussi sur le même dessin. La décomposition descendante de f est égale à (c_{1}, …, c_{7}) avec le tableau suivant donnant les arêtes et les sommets de ces lacets et le code de la figure.

6. DÉCOMPOSITION DESCENDANTE D’UN CIRCUIT 23

CHAPITRE IV

RÉARRANGEMENTS DE SUITES

Dans tout ce chapitre, on note X un ensemble ; à partir du n^{o} 3, on suppose que X est totalement ordonné. Dans les exemples, X est l’ensemble des entiers, avec l’ordre naturel.

1. Monoïde des réarrangements

Les constructions de ce n^{o} s’obtiennent en appliquant les constructions générales du chapitre III au graphe G = (S, A, σ, β) associé de la manière suivante à X : on a S = X, A = X × X, σ(x, y) = x et β(x, y) = y pour x, y dans X. De manière plus imagée, X est l’ensemble des sommets du graphe G; quels que soient les sommets x et y, il existe une arête unique a_{x,y} joignant x à y.

Un flot est une application f de X dans Mo(X) telle que l’ensemble {x ∈ X | f(x) ≠ 1} soit fini. Le produit de deux flots f et f′ est défini par (ff′)(x) = f(x) · f′(x) pour tout x dans X. L’ensemble des flots, avec cette multiplication, est un monoïde noté F (X). Si f est un flot et x, y des éléments de X, on note θ_{x}(f) la longueur du mot f(x) et n_{x,y}(f) le nombre de fois que la lettre y intervient dans le mot f(x). On a alors les relations

(1)  θ_{x}(f) = ∑_{y∈X} n_{x,y}(f)
(2)  θ_{x}(ff′) = θ_{x}(f) + θ_{x}(f′)
(3)  n_{x,y}(ff′) = n_{x,y}(f) + n_{x,y}(f′),

où f et f′ sont deux flots et x, y deux éléments de X. Pour tout flot f, l’application x ↦ θ_{x}(f) est un élément de Ab(X) et θ est un homomorphisme de F (X) dans Ab(X).

Les circuits, que nous préférons appeler ici réarrangements, sont les flots f satisfaisant à la relation

(4)  θ_{y}(f) = ∑_{x∈X} n_{x,y}(f) (pour tout y ∈ X);

cette relation équivaut à la suivante

(5)  θ(f) = ∑_{x∈X} ϵ(f(x)).

Les réarrangements forment un sous-monoïde Q(X) de F (X) ; on l’appelle monoïde des rérrangements.

Soient w = x_{1} ⋯ x_{m} et w′ = x′_{1} ⋯ x′_{m} deux mots de même longueur ; on

note \binom{w}{w′} le flot ∏_{i=1}^{m} b(a_{x′_{i},x_{i}}) où b(a) est le flot associé à une arête a. C’est un

flot f ainsi défini : pour tout x ∈ X, soient i_{1}, …, i_{p} les entiers i tels que 1 ≤ i ≤ m et x′_{i} = x, rangés par ordre croissant ; on a alors f(x) = x_{i_{1}} ⋯ x_{i_{p}}. Cette définition entraîne les propriétés suivantes :

(a) Tout flot est de la forme \binom{w}{w′} et l’on a \binom{w_{1}}{w′_{1}}\binom{w_{2}}{w′_{2}} = \binom{w_{1}w_{2}}{w′_{1}w′_{2}}.

(b) On a \binom{x_{1}···x_{m}}{x′_{1}···x′_{m}} = \binom{y_{1}···y_{n}}{y′_{1}···y′_{n}} si et seulement si l’on a m = n et s’il existe une permutation de {1, 2, …, m} telle que y_{i} = x_{σ(i)}, y′_{i} = x′_{σ(i)} et tel que i < j, x′_{i} = x′_{j} entraînent σ(i) < σ(j).

(c) Soit f = \binom{x_{1}···x_{m}}{x′_{1}···x′_{m}}; pour x, y dans X, l’entier n_{x,y}(f) est le nombre des entiers i tels que 1 ≤ i ≤ m et x′_{i} = x, x_{i} = y. D’après (1), θ_{x}(f) est donc le nombre de fois que la lettre x intervient dans le mot x′_{1} ⋯ x′_{m}; autrement dit, on a la relation

(6)  θ\binom{w}{w′} = ϵ(w′).

(d) Le monoïde des flots F (X) est engendré par les éléments \binom{x}{x′} (pour x, x′ dans X) soumis aux relations de commutation \binom{x}{x′}\binom{y}{y′} = \binom{y}{y′}\binom{x}{x′} pour x′ ≠ y′ (voir le théorème 3.3).

(e) Le flot \binom{w}{w′} est un réarrangement si et seulement si le mot w′ est un réarrangement du mot w (ce qui justifie la terminologie adoptée).

Soient Ω un monoïde commutatif, noté additivement et c une application de X × X dans Ω. Pour tout flot f, l’ensemble des couples (x, y) tels que n_{x,y}(f) ≠ 0 est fini ; on peut donc poser

(7)  n_{c}(f) = ∑_{x,y} n_{x,y}(f) · c(x, y).

Il est immédiat que n_{c} est un homomorphisme de F (X) dans Ω ; de plus, on a

(8)  n_{c}\binom{x_{1}···x_{m}}{x′_{1}···x′_{m}} = ∑_{i=1}^{m} c(x′_{i}, x_{i}).

2. Décomposition d’un réarrangement en cycles

La donnée d’un circuit simple f équivaut à celle d’une partie finie F de X et d’une permutation σ de F ; on a f = ∏_{x∈F} b(a_{x,σ(x)}). Si x_{1}, …, x_{m} sont

les éléments de F, on peut encore écrire f = \binom{σ(x_{1})···σ(x_{m})}{x_{1} ··· x_{m}} et la notation des réarrangements est donc en accord avec la notation usuelle des permutations.

Pour tout mot w = x_{1} ⋯ x_{m}, on pose

(9)  γ w = x_{2}x_{3} ⋯ x_{m}x_{1};

les cycles sont alors les réarrangements de la forme [w] = \binom{γ w}{w} où w est un mot formé de lettres distinctes et l’on a [w] = [w′] si et seulement s’il existe un entier positif i avec w′ = γ^{i}w.

En traduisant le théorème 3.5, on obtient le résultat suivant qui généralise la décomposition bien connue d’une permutation en produit de cycles.

Proposition 4.1.

(a) Tout réarrangement est produit d’une suite finie de cycles.

(b) Étant données deux décompositions d’un même réarrangement en produit de suites finies de cycles, on passe de la première à la seconde par une suite finie de transformations élémentaires consistant à permuter dans un produit deux cycles consécutifs qui n’ont aucune lettre en commun.

La démonstration de la proposition 3.4 fournit un algorithme effectif pour la décomposition en cycles d’un réarrangement f = \binom{w}{w′}. On pose f_{1} = f et l’on forme une suite de lettres y_{1}, …, y_{q} de la manière suivante :

(a) y_{1} est la première lettre de w′;

(b) lorsque y_{i} est déjà définie, on choisit pour y_{i+1} la lettre la plus à gauche de w parmi celles qui se trouvent au-dessus d’une lettre de w′ égale à y_{i}; on entoure la colonne correspondante ;

(c) on arrête la procédure la première fois qu’on obtient une lettre y_{q} égale à l’une des lettres précédentes, par exemple y_{q} = y_{p} avec 1 ≤ p < q.

On pose alors z_{1} = [y_{p}y_{p+1} ⋯ y_{q−1}] et l’on supprime dans f_{1} les colonnes entourées dont la lettre inférieure est y_{p}, y_{p+1}, …, ou y_{q−1}. On obtient ainsi un réarrangement f_{2} tel que f_{1} = z_{1}f_{2} et l’on recommence avec f_{2} la procédure précédente.

Exemple 4.2. — On part du réarrangement f = (\begin{matrix}3 & 5 & 4 & 2 & 4 & 1 & 2 & 2 & 1 & 3 \\ 1 & 1 & 2 & 2 & 2 & 3 & 3 & 4 & 4 & 5 \end{matrix}). On

a, en indiquant dans la deuxième colonne la suite y_{1} ⋯ \overline{y_{p} ⋯ y_{q}}

f_{1} = ((\overline{3} \underline{1}) 5 4 2 4 1 2 2 2 (\overline{1} \underline{3}) \begin{matrix}2 & 2 & 1 & 3 \\ 3 & 4 & 4 & 5 \end{matrix} )  ⟶ \overline{1 3 1}  z_{1} = [1 3]
f_{2} = ((\overline{5} \underline{1}) (\overline{4} \underline{2})2 4 2 2 (\overline{2} \underline{3}) (\overline{2} \underline{4}) {1 \atop 4} (\overline{3} \underline{5})) ⟶ 1 5 3 \overline{2 4 2} z_{2} = [2 4]
f_{3} = ((\overline{5} \underline{1}) (\overline{2} \underline{2}){4 \atop 2} (\overline{2} \underline{3}) {1 \atop 4} (\overline{3} \underline{5}))  ⟶ 1 5 3 \overline{2 2} z_{3} = [2]
f_{4} = ((\overline{5} \underline{1}) (\overline{4} \underline{2}) (\overline{2} \underline{3}) (\overline{1} \underline{4}) (\overline{3} \underline{5}))  ⟶ \overline{1 5 3 2 4 1} z_{4} = [1 5 3 2 4],

d’où la décomposition en cycles

f = [1 3] · [2 4] · [2] · [1 5 3 2 4].

3. Monoïde d’intercalement

On rappelle que l’ensemble X est désormais supposé totalement ordonné. On dit qu’un mot x_{1} ⋯ x_{m} est croissant si l’on a x_{1} ≤ x_{2} ≤ ⋯ ≤ x_{m}. Soit w un mot ; parmi les réarrangements de x, il en est un seul qui soit croissant et qu’on notera \overline{w}. De manière plus explicite, soient s_{1}, …, s_{p} les lettres intervenant dans w, rangées par ordre croissant et soit α(i) la multiplicité

de s_{i} dans w; on a alors \overline{w} = ∏_{i=1}^{p} s_{i}^{α(i)}. On posera aussi Γ(w) = \binom{w}{\overline{w}}; comme

le mot w est de longueur α(1)+⋯+α(p), on peut le décomposer de manière unique sous la forme w = w_{1} ⋯ w_{p} où le mot w_{i} est de longueur α(i) ; dans ces conditions, le flot h = Γ(w) est défini par h(s_{i}) = w_{i} pour 1 ≤ i ≤ p et h(x) = 1 pour x ∉ {s_{1}, …, s_{p}}.

Par ailleurs, pour tout réarrangement f, on pose Π(f) = ∏_{x∈X} f(x) ; ce produit se calcule ainsi : si F est une partie finie de X telle que f(x) = 1 pour x ∈ X \ F, rangée sous forme d’une suite croissante x_{1}, …, x_{q}, on a Π(f) = f(x_{1}) ⋯ f(x_{q}).

On a donc défini deux applications

Γ : Mo(X) → Q(X) et Π : Q(X) → Mo(X).

Proposition 4.3. — Les applications Γ et Π sont des bijections réciproques.

Les remarques précédentes montrent que l’on a Π(Γ(w)) = w pour tout mot w. Montrons par ailleurs qu’on a Γ(Π(f)) = f pour tout réarrangement f. Rangeons sous forme d’une suite croissante x_{1}, …, x_{q} l’ensemble des x ∈ X tels que f(x) ≠ 1 et notons α(i) la longueur du mot w_{i} = f(x_{i}) ; enfin posons w = w_{1} ⋯ w_{q} et w′ = x_{1}^{α(1)} ⋯ x_{q}^{α(q)}. Il est immédiat que l’on a w = Π(f) et f = \binom{w}{w′}; comme f est un réarrangement, le mot croissant w′ est un réarrangement du mot w, d’où w′ = \overline{w} et f = \binom{w}{\overline{w}} = Γ(Π(f)).

Comme Γ et Π sont des bijections réciproques, la formule w τ w′ = Π(Γ(w) · Γ(w′)) définit un nouveau produit dans Mo(X), distinct en général du produit de juxtaposition et appelé produit d’intercalement. Pour ce produit, l’ensemble des mots est un nouveau monoïde, qu’on appellera monoïde d’intercalement et qu’on notera Q′(X). Par construction, Π est un isomorphisme de monoïde de Q(X) sur Q′(X) et Γ est l’isomorphisme réciproque.

Proposition 4.4. — Soient w et w′ deux mots, s_{1}, …, s_{p} les lettres intervenant dans w ou w′ rangées par ordre croissant, α(i) (resp. α′(i)) la multiplicité de s_{i} dans w (resp. w′). Décomposons w en w_{1} ⋯ w_{p} et w′ en w′_{1} ⋯ w′_{p} de sorte que w_{i} soit de longueur α(i) et w′_{i} de longueur α′(i) pour 1 ≤ i ≤ p. On a alors w τ w′ = w_{1}w′_{1}w_{2}w′_{2} ⋯ w_{p}w′_{p}.

Le réarrangement croissant de w est s_{1}^{α(1)} ⋯ s_{p}^{α(p)} et celui de w′ est s_{1}^{α′(1)} ⋯ s_{p}^{α′(p)}. Le mot f = Γ(w) est donc défini par f(s_{i}) = w_{i} pour 1 ≤ i ≤ p et f(x) = 1 pour x ∉ {s_{1}, …, s_{p}}; de même, f′ = Γ(w′) est défini par f′(s_{i}) = w′_{i} pour 1 ≤ i ≤ p et f′(x) = 1 lorsque x ∉ {s_{1}, …, s_{p}}.

On a alors w τ w′ = Π(ff′) = ∏_{i=1}^{p}(ff′)(s_{i}) = ∏_{i=1}^{p} w_{i}w′_{i}.

Exemple 4.5. — Pour w = 1 3 5 2 1 4 3 1 2 1 1 3 et w′ = 1 2 3 5 4 3 2 1 1 1 on a les valeurs suivantes de α(i) et α′(i) :

\begin{matrix}i & 1 2 3 4 5 \\ α(i) & 5 2 3 1 1 \\ α′(i) & 4 2 2 1 1 \end{matrix}

d’où les partages

w = 1 3 5 2 1 | 4 3 | 1 2 1 | 1 | 3 et w′ = 1 2 3 5 | 4 3 | 2 1 | 1 | 1 et le produit d’intercalement

w τ w′ = 1 3 5 2 1 1 2 3 5 | 4 3 4 3 | 1 2 1 2 1 | 1 1 | 3 1.

Exemple 4.6. — Soit à calculer le produit w = w_{1} τ w_{2} τ w_{3} avec w_{1} = 1 3 5 1 2 4, w_{2} = 1 1 1 2, w_{3} = 5 4 3 2 1, ce qui donne les réarrangements croissants \overline{w}_{1} = 1 1 2 3 4 5, \overline{w}_{2} = 1 1 1 2, \overline{w}_{3} = 1 2 3 4 5. On a alors

Γ(w) = Γ(w_{1})Γ(w_{2})Γ(w_{3}) = (\begin{matrix}1 & 3 & 5 & 1 & 2 & 4 & 1 & 1 & 1 & 2 & 5 & 4 & 3 & 2 & 1 \\ 1 & 1 & 2 & 3 & 4 & 5 & 1 & 1 & 1 & 2 & 1 & 2 & 3 & 4 & 5 \end{matrix})

et après permutation des colonnes, on a

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

et finalement w = 1 3 1 1 1 5 5 2 4 1 3 2 2 4 1.

La bijection Γ permet de transporter à Q′(X) certaines fonctions définies sur Q(X) au n^{o} 1. Tout d’abord, on a

(10)  θ(Γ(w)) = ϵ(w) pour tout mot w;

en effet, on a θ(Γ(w)) = θ\binom{w}{\overline{w}} d’après (6) et comme \overline{w} est un réarrangement de w, on a ϵ(\overline{w}) = ϵ(w). On pose par ailleurs

(11)  ν_{x,y}(w) = n_{x,y}(Γ(w))

pour tout mot w = x_{1} ⋯ x_{m}; si \overline{w} = \overline{x}_{1} ⋯ \overline{x}_{m} est le réarrangement croissant de w, l’entier ν_{x,y}(w) est le nombre d’entiers i tels que 1 ≤ i ≤ m et \overline{x}_{i} = x, x_{i} = y. Enfin, si c est une application de X × X dans un monoïde commutatif Ω, on pose ν_{c}(w) = n_{c}(Γ(w)) pour tout mot w; avec les notations précédentes, on a

(12)  ν_{c}(w) = ∑_{i=1}^{m} c(\overline{x}_{i}, x_{i})

d’après la formule (8).

Remarque 4.7. — On pourrait définir directement le produit d’intercalement w τ w′ de deux mots par la proposition 4.4 ; il n’est pas difficile de montrer directement que ce produit est associatif et admet pour élément neutre le mot 1. C’est la voie suivie dans [1] (voir page 103).

4. Décomposition descendante d’un mot

Soit w = x_{1} ⋯ x_{m} un mot. On appelle lettre finale de w l’élément F w = x_{m} de X; on dit que w est dominé si l’on a w ≠ 1 et x_{i} < x_{m} pour 1 ≤ i < m et l’on dit que l’indice i ∈ {1, 2, …, m} est saillant si l’on a x_{i} ≥ x_{j} pour i ≤ j ≤ m. On appelle décomposition descendante de w toute suite (w_{1}, w_{2}, …, w_{p}) de mots dominés telle que w = w_{1}w_{2} ⋯ w_{p} et F w_{1} ≥ F w_{2} ≥ ⋯ ≥ F w_{p}.

Proposition 4.8. — Tout mot admet une décomposition descendante et une seule.

Si w est un mot et si n_{1}, …, n_{p} sont des entiers positifs dont la somme est égale à la longueur de w, il existe une décomposition w = w_{1} ⋯ w_{p} de w et une seule telle que w_{i} soit de longueur n_{i} pour 1 ≤ i ≤ p. Comme le dernier indice d’un mot est saillant, il suffit de prouver le lemme suivant.

Lemme 4.9. — Soient w = x_{1} ⋯ x_{m}, w_{1}, …, w_{p} des mots de longueur non nulle tels que w = w_{1} ⋯ w_{p}; on note ℓ_{k} la longueur de w_{k} et l’on pose

j_{k} = ∑_{r=1}^{k} ℓ_{r} pour 1 ≤ k ≤ p. Pour que (w_{1}, …, w_{p}) soit une décomposition

descendante de w, il faut et il suffit que les indices saillants de w soient j_{1}, …, j_{p}.

Supposons d’abord que (w_{1}, …, w_{p}) soit une décomposition descendante de w. Comme w_{1} est dominé, aucun indice i tel que 1 ≤ i < j_{1} ne peut être saillant ; de plus, il est immédiat que l’indice j_{p} = m est saillant. Soient alors k et i des entiers tels que 1 ≤ k < p et j_{k} < i ≤ m; il existe un entier k′ tel que k ≤ k′ < p et j_{k′} < i ≤ j_{k′+1} ; comme le mot w_{k′+1} est dominé, on a x_{i} ≤ x_{j′_{k}+1} = F w_{k′+1} ≤ F w_{k} = x_{j_{k}}; ceci prouve que j_{k} est saillant. En particulier, si l’on a j_{k′} < i < j_{k′+1}, alors x_{i} < x_{j_{k′+1}} et l’indice i n’est donc pas saillant. On a prouvé que les indices saillants sont j_{1}, …, j_{p}.

Supposons réciproquement que les indices saillants de w soient j_{1}, …, j_{p}. Pour tout entier k tel que 1 ≤ k < p, on a j_{k} < j_{k+1} et comme j_{k} est saillant, on a F w_{k} = x_{j_{k}} ≥ x_{j_{k+1}} = F w_{k+1}. Montrons que chacun des mots w_{k} est dominé. Puisque l’indice i′ = j_{k} − 1 n’est pas saillant lorsque j_{k} − j_{k−1} > 1, on a dans ce cas x_{i′} < x_{j_{k}}. Il nous suffit donc de montrer que l’hypothèse j_{k−1} < i < j_{k} et x_{i′} < x_{j_{k}} pour i < i′ < j_{k} entraîne x_{i} < x_{j_{k}}. Or comme j_{k} est saillant, on a x_{j_{k}} ≥ x_{r} pour j_{k} ≤ r ≤ m et comme i n’est pas saillant, il existe s avec i < s ≤ m et x_{i} < x_{s}; dans les deux cas i < s < j_{k} et j_{k} ≤ s ≤ m, on a x_{s} ≤ x_{j_{k}}, d’où x_{i} < x_{j_{k}}. (On a posé j_{0} = 0.)

Soit w = x_{1} ⋯ x_{m} un mot. Nous noterons Δ(w) le flot \binom{γw_{1} ··· γw_{p}}{w_{1} ··· w_{p}} où (w_{1}, …, w_{p}) est la décomposition descendante de w; comme γw_{j} est un réarrangement de w_{j}, on voit que Δ(w) est un réarrangement. Par ailleurs, étant donnés x et y dans X, nous noterons ξ_{x,y}(w) le nombre d’entiers i tels que 1 ≤ i ≤ m − 1, x_{i} = x et x_{i+1} = y. Enfin, si c est une application de X × X dans un monoïde commutatif Ω, nous poserons ξ_{c}(w) = 0 si m est égal à 0 ou 1 et

(13)  ξ_{c}(w) = c(x_{1}, x_{2}) + c(x_{2}, x_{3}) + ⋯ + c(x_{m−1}, x_{m})

si m ≥ 2.

Proposition 4.10. — L’application Δ est une bijection de Mo(X) sur Q(X). De plus, pour tout mot w, on a les relations

θ(Δ(w)) = ϵ(w), n_{x,y}(Δ(w)) = ξ_{x,y}(w)

si x < y et n_{c}(Δ(w)) = ξ_{c}(w) si l’applicatioon c de X × X dans Ω est telle que c(x, y) = 0 pour x ≥ y.

(a) Pour tout mot dominé w = x_{1} ⋯ x_{m}, notons c(w) le lacet de sommets x_{m}x_{1}x_{2} ⋯ x_{m} dans le graphe G associé à X. Il est immédiat que le circuit b(c(w)) (voir chapitre III.5) est égal à \binom{γw}{w} et que l’application w ↦ c(w) induit une bijection de l’ensemble des mots dominés sur l’ensemble des lacets irréductibles dont la source est le plus grand sommet. Avec ces notations, on a Δ(w) = b(c(w_{1})) ⋯ b(c(w_{p})) si (w_{1}, …, w_{p}) est la décomposition descendante de w; comme la source du lacet c(w_{j}) est la dernière lettre de F w_{j} de w_{j} et que l’on a F w_{1} ≥ ⋯ ≥ F w_{p}, l’application Δ de Mo(X) dans Q(X) transforme la décomposition descendante d’un mot en la décompositin descendante du circuit correspondant. La proposition 3.10 montre alors que Δ est bijective.

(b) Soit w = x_{1} ⋯ x_{m} un mot ; on note (w_{1}, …, w_{p}) la décomposition descendante de w et j_{1}, …, j_{p} les indices saillants de w; enfin, on note x′ = x′_{1} ⋯ x′_{m} le réarrangement γw_{1} ⋯ γw_{p} de w. L’orsque l’indice i ∈ {1, 2, …, m} est distinct de j_{1}, …, j_{p}, on a x′_{i} = x_{i+1} ; par ailleurs, pour k ∈ {1, 2, …, p}, on a

x′_{j_{k}} = x_{j_{k−1}+1} ≤ x_{j_{k}}

car le mot w_{k} est dominé (on fait la convention j_{0} = 0) ; si de plus, on a k ≠ p, on a x_{j_{k}+1} ≤ x_{j_{k}} car l’indice j_{k} est saillant. Soient alors x, y dans X avec x < y; les remarques précédentes montrent que l’on a x_{i} = x, x′_{i} = y si et seulement si l’on a x_{i} = x, x_{i+1} = y (et ceci ne peut avoir lieu pour i dans \{j_{1}, …, j_{p}\}). Comme on a Δ(w) = \binom{w′}{w}, la propriété (c) du n^{o} 1 montre que l’on a n_{x,y}(Δ(w)) = ξ_{x,y}(w) lorsque x < y.

(c) Enfin, soit c une application de X ×X dans un monoïde commutatif Ω telle que c(x, y) = 0 lorsque x ≥ y. On a alors n_{c}(f) = ∑_{x<y} n_{x,y}(f) · c(x, y) pour tout réarrangement f et ξ_{c}(w) = ∑_{x<y} ξ_{x,y}(w)·c(x, y) pour tout mot w. Le résultat de l’alinéa (b) entraîne alors n_{c}(Δ(w)) = ξ_{c}(w) pour tout mot w. La formule θ(Δ(w)) = ϵ(w) résulte de (6).

5. Une méthode de réarrangement

Dans les numéros précédents, nous avons décrit deux bijections

Γ : Mo → Q(X), Δ : Mo(X) → Q(x);

par composition, on en déduit une permutation Φ = Γ^{−1} ∘ Δ de l’ensemble Mo(X) des mots. On peut l’expliciter ainsi : soit w = x_{1} ⋯ x_{m} un mot ; notons s_{1}, …, s_{q} les lettres intervenant dans w, rangées par ordre croissant, α(i) la multiplicité de s_{i} dans w et β(i) = α(1) + ⋯ + α(i) (avec la convention β(0) = 0). Notons \overline{w} = \overline{x}_{1} ⋯ \overline{x}_{m} le réarrangement croissant s_{1}^{α(1)} ⋯ s_{q}^{α(q)} de w et σ la permutation de l’ensemble {1, 2, …, m} qui satisfasse à \overline{x}_{i} = x_{σ(i)} pour 1 ≤ i ≤ m et qui soit croissante sur chacun des intervalles [β(j − 1) + 1, β(j)] pour 1 ≤ j ≤ q. Par ailleurs, soit (w_{1}, …, w_{q}) la décomposition descendante de w; on pose γw_{1} ⋯ γw_{p} = y_{1} ⋯ y_{m}; on a alors Φ(w) = y_{σ(1)} ⋯ y_{σ(m)}.

Théorème 4.11. — Soient w = x_{1} ⋯ x_{m} un mot, \overline{w} = \overline{x}_{1} ⋯ \overline{x}_{m} son réarrangement croissant et x′ = x′_{1} ⋯ x′_{m} le mot Φ(w). Alors

(a) Le mot w′ est un réarrangement de w.

(b) Si x et y sont deux éléments de X tels que x < y, le nombre ν_{x,y}(w′) des entiers i tels que 1 ≤ i ≤ m et \overline{x}_{i} = x, x′_{i} = y est égal au nombre ξ_{x,y}(w) des entiers i tels que 1 ≤ i < m et x_{i} = x, x_{i+1} = y.

(c) Soit c une application de X × X dans un monoïde commutatif Ω, telle que c(x, y) = 0 pour x ≥ y. On a

(14)  ∑_{i=1}^{m−1} c(\overline{x}_{i}, x′_{i}) = ∑_{i=1}^{m−1} c(x_{i}, x_{i+1}).

On a Δ(w) = Γ(w′). D’après les formules (10) et (11) et la proposition 4.10, on a ϵ(w) = θ(Δ(w)) = θ(Γ(w′)) = ϵ(w′) et ξ_{x,y}(w) = n_{x,y}(Δ(w)) = n_{x,y}(Γ(w′)) = ν_{x,y}(w′) pour x < y. Ceci prouve (a) et (b). On a aussi

∑_{i=1}^{m} c(\overline{x}_{i}, x′_{i}) = ν_{c}(w′) = n_{c}(Γ(w′)) = n_{c}(Δ(w)) = ξ_{c}(w) = ∑_{i=1}^{m−1} c(x_{i}, x_{i+1})

d’après les formules (12) et (13) et la proposition 4.10 ; comme on a \overline{x}_{m} ≥ x′_{m}, on a aussi c(\overline{x}_{m}, x′_{m}) = 0, d’où immédiatement la formule (14).

Soient x = x_{1} ⋯ x_{m} un mot et \overline{w} = \overline{x}_{1} ⋯ \overline{x}_{m} son réarrangement croissant. On note ν(w) le nombre des entiers i tels que 1 ≤ i ≤ m et \overline{x}_{i} < x_{i} et ξ(w) le nombre des entiers i tels que 1 ≤ i ≤ m − 1 et x_{i} < x_{i+1}. On a

ν(w) = ∑_{x<y} ν_{x,y}(w), ξ(w) = ∑_{x<y} ξ_{x,y}(w)

et le théorème 4.11 entraîne ξ(w) = ν(Φ(w)). On en déduit le résultat suivant, dû à MacMahon [3, page 186].

Corollaire 4.12. — Soient w un mot et r un entier positif. Parmi les réarrangements w′ de w, il y en a autant pour lesquels on a ν(w′) = r que pour lesquels on a ξ(w′) = r.

Exemple 4.13. — Pour déterminer les indices saillants d’un mot w = x_{1} ⋯ x_{m}, le plus simple est de déterminer le mot ŵ = y_{1} ⋯ y_{m} défini par y_{i} = max{x_{i}, x_{i+1}, …, x_{m}}; un indice i est saillant si et seulement si l’on a x_{i} = y_{i}. Considérons par exemple le mot

w = \overline{4 \underline{6}} \underline{6} 5 4 4 3 \overline{1 2 \underline{6}} 2 2 \overline{1 3 \underline{4}} \underline{3} 2 \overline{1 2 \underline{3}} 1 \overline{1 \underline{2}}
d’où  ŵ = 6 6 6 6 6 6 6 6 6 6 4 4 4 4 4 3 3 3 3 3 2 2 2,

ce qui permet de déterminer les indices saillants (soulignés). La décomposition descendante s’obtient en coupant w après chaque indice saillant, soit

w = 4 6 | 6 | 5 4 4 3 1 2 6 | 2 2 1 3 4 | 3 | 2 1 2 3 | 1 1 2 ;

on en déduit

Δ(w) = ( \begin{matrix}6 & 4 \\ 4 & 6 \end{matrix} | {6 \atop 6} | \begin{matrix}4 & 4 & 3 & 1 & 2 & 6 & 5 \\ 5 & 4 & 4 & 3 & 1 & 2 & 6 \end{matrix} | 2 1 3 4 2 2 2 1 3 4 | \begin{matrix}3 \\ 3 \end{matrix} | 1 2 3 2 2 1 2 3 | \begin{matrix}1 & 2 & 1 \\ 1 & 1 & 2 \end{matrix} ) ,

d’où après permutation des colonnes

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

et finalement

\begin{matrix}w′ = Φ(w) = \\ \overline{w} = \end{matrix}(\overline{2} \underline{1})(\overline{3} \underline{1})(\overline{2} \underline{1}){1 \atop 1}(\overline{2} \underline{1})(\overline{6} \underline{2})2 1 1 2 2 1(\overline{3} \underline{2})1 1 2 3(\overline{4} \underline{3})3 2 3 3(\overline{6} \underline{4})\begin{matrix}4 & 3 & 2 & 4 & 4 & 6 & 5 \\ 4 & 4 & 4 & 5 & 6 & 6 & 6. \end{matrix}

On a entouré les paires montantes (\overline{x}_{i}, x′_{i}) avec \overline{x}_{i} < x′_{i} et coché sur w les paires montantes (x_{i}, x_{i+1}) avec x_{i} < x_{i+1}.

Enfin, voici les matrices

N(w′) = (ν_{x,y}(w′))_{x,y∈X} et Ξ(w) = (ξ_{x,y}(w))_{x,y∈X} :

N(w′) = ( \begin{matrix}1 & 3 & 1 & 0 & 0 & 0 \\ 3 & 1 & 1 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 \end{matrix} ) Ξ(w) = ( \begin{matrix}1 & 3 & 1 & 0 & 0 & 0 \\ 2 & 1 & 1 & 0 & 0 & 1 \\ 2 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 1 \end{matrix} )

dont les parties au-dessus de la diagonale principale coïncident. On a

ν(w′) = ξ(w) = 8.

CHAPITRE V

SUR LE “MASTER THEOREM” DE MACMAHON

1. Une généralisation non commutative du “Master Theorem”

On note A un anneau avec élément unité, non nécessairement commutatif. Bien que l’anneau A ne soit pas commutatif, on peut définir le déterminant d’une matrice carrée T = (t_{i,j})_{1≤i,j≤n} à coefficients dans A par la formule usuelle

(1)  det T = ∑_{σ∈𝔖_{n}} ε_{σ} ∏_{i=1}^{n} t_{i,σ(i)}.

On rappelle que 𝔖_{n} est l’ensemble des permutations de l’ensemble {1,2,…,n} et ε_{σ} est la signature de la permutation σ. Par ailleurs, on note I_{n} la matrice unité d’ordre n et A_{n} l’anneau des séries formelles à coefficidents dans A en des indéterminées commutatives X_{1}, …, X_{n}. Le théorème suivant se réduit au ^{⟨⟨}Master Theorem^{⟩⟩} lorsque l’anneau A est supposé commutatif.

Théorème 5.1. — Soit X la matrice diagonale d’éléments X_{1}, …, X_{n} et soit B = (b_{ij}) une matrice carrée d’ordre n à coefficients dans A. On suppose que b_{ij} commute à b_{i′j′} lorsque i et i′ sont distincts. On pose Y_{i} = ∑_{j=1}^{n}b_{ij}X_{j} pour i ∈ {1, 2, …, n}.

Quels que soient les entiers positifs α(1), …, α(n), le coefficient t_{α(1),...,α(n)} du monôme X_{1}^{α(1)} ⋯ X_{n}^{α(n)} dans le produit Y_{1}^{α(1)} ⋯ Y_{n}^{α(n)} est égal au coefficient du même monôme dans la série formelle det(I_{n}−B·X)^{−1}.

Nous noterons Q le monoïde des réarrangements construit sur l’ensemble {1, 2, …, n} (voir IV.1) et μ la fonction de Möbius de Q. Vu l’hypothèse de commutativité faite sur les éléments de la matrice B, il existe un homomorphisme u de Q dans le monoïde multiplicatif Ω de l’anneau A_{n}, tel que

(2)  u\binom{j_{1}···j_{p}}{i_{1}···i_{p}} = ∏_{i=1}^{p} b_{i_{k}j_{k}}X_{j_{k}}.

(A) Calcul de la série t = ∑_{α(1),...,α(n)} t_{α(1),...,α(n)} X_{1}^{α(1)} ⋯ X_{n}^{α(n)} :

Soient α(1), …, α(n) des entiers positifs. Pour i ∈ {1, 2, …, n}, on a

(3)  Y_{i}^{α(i)} = ∑_{j_{1},...,j_{α(i)}}b_{ij_{1}} ⋯ b_{ij_{α(i)}} X_{j_{1}} ⋯ X_{j_{α(i)}};

posons p = α(1) + ⋯ + α(n) et notons i_{1}, …, i_{p} la suite croissante où 1 apparaît α(1) fois, 2 apparaît α(2) fois, …, et où n apparaît α(n) fois. Multipliant les égalités (3) membre à membre, on obtient

(3)  Y_{1}^{α(1)} ⋯ Y_{n}^{α(n)} = ∑_{j_{1},...,j_{n}} b_{i_{1}j_{1}} ⋯ b_{i_{p}j_{p}} X_{j_{1}} ⋯ X_{j_{p}},

où les entiers j_{1}, …, j_{p} prennent indépendamment les valeurs 1, 2, …, n. On obtient le produit t_{α(1),...,α(n)}X_{1}^{α(1)} ⋯ X_{n}^{α(n)} en ne conservant dans la somme précédente que les termes pour lesquels chacun des entiers i ∈ {1, 2, …, n} apparaît α(i) fois dans la suite j_{1}, …, j_{p}.

On a donc

(4)  t_{α(1),...,α(n)}X_{1}^{α(1)} ⋯ X_{n}^{α(n)} = ∑ u\binom{j_{1} ... j_{p}}{i_{1} ... i_{p}}

où la sommation est étendue à tous les systèmes i_{1}, …, i_{p}, j_{1}, …, j_{p} satisfaisant aux deux conditions suivantes :

(a) la suite i_{1}, …, i_{p} est croissante ;

(b) chacun des entiers i ∈ {1, …, n} apparaît α(i) fois dans chacune des suites i_{1}, …, i_{p} et j_{1}, …, j_{p}.

Si l’on somme sur les suites (α(1), …, α(n)) de n entiers positifs, on obtient une fois et une seule tout élément de Q, d’où

(5)  t = ∑_{f∈Q} u(f).

(B) Calcul de la série d = det(I_{n} − B · X) :

Soit U = (u_{ij}) une matrice carrée d’ordre n; pour toute partie H de l’ensemble {1, 2, …, n}, soit D_{H} le déterminant de la matrice obtenue en supprimant de U les lignes et les colonnes dont les indices n’appartiennent pas à H; on a alors

(6)  det(I_{n} − U) = ∑_{r=0}^{n}(−1)^{r} ∑_{|H|=r} D_{H}.

Cette formule est bien connue lorsque les éléments de U commutent deux à deux et la démonstration usuelle s’étend immédiatement au cas général. Appliquons ceci au cas de la matrice U = B ·X d’éléments u_{ij} = b_{ij}X_{j}; pour toute partie H avec |H| = r, on a

(7)  D_{H} = ∑_{σ∈𝔖_{r}} ε_{σ} ∏_{i∈H} u_{i,σ(i)} = ∑_{σ∈𝔖_{r}} ε_{σ} u(∏_{i∈H} \binom{σ(i)}{i}).

Lorsque σ parcourt le groupe symétrique 𝔖_{r}, l’élément ∏_{i∈H} \binom{σ(i)}{i} parcourt

l’ensemble des circuits simples de support H; d’après la remarque 3.6, μ(f) est égal à (−1)^{r} · ε_{σ} lorsque f est de la forme précédente et l’on a μ(f) = 0 si le circuit f n’est pas simple. De (6) et (7), on déduit facilement

(8)  d = ∑_{f∈Q} μ(f) · u(f).

2. UNE AUTRE GÉNÉRALISATION DU THÉORÈME DE MACMAHON 35

(C) Fin de la démonstration :

Rappelons qu’on a u(f′)·u(f′′) = u(f′f′′) pour f′, f′′ dans Q. Des formules (5) et (8), on déduit alors

d t = ∑_{f′,f′′} μ(f′) · u(f′)u(f′′) = ∑_{f} u(f) ∑_{f′f′′=f} μ(f′).

Par définition de la fonction de Möbius μ de Q, on a par ailleurs

∑_{f′f′′=f} μ(f′) = \{ \begin{matrix}1, & si f = 1 ; \\ 0, & si f ≠ 1 ; \end{matrix}

d’où immédiatement d t = u(1) = 1. La démonstration de la formule t d = 1 est analogue.

2. Une autre généralisation du théorème de MacMahon

Dans ce n^{o}, on note A un anneau commutatif avec élément unité. On introduit des indéterminées non commutatives ξ_{1}, …, ξ_{n} et des séries formelles à coefficients dans A en ces indéterminées. Rappelons qu’une telle série s’écrit de manière unique sous la forme h = ∑_{w} a_{w} · w où w parcourt l’ensemble des mots en ξ_{1}, …, ξ_{n}; de manière explicite, on a

(10)  h = ∑_{r=0}^{∞} ∑_{i_{1},...,i_{r}=1}^{∞} a_{i_{1},...,i_{r}} ξ_{i_{1}} ⋯ ξ_{i_{r}}.

On a défini au chapitre IV.3 le produit d’intercalement w τ w′ pour deux mots w et w′; on étend cette définition au cas des séries en posant

(11) (∑_{w} a′_{w} · w) τ (∑_{w} a′′_{w} · w) = ∑_{w′w′′} a′_{w′}a′′_{w′′}(w′ τ w′′)

= ∑_{w}( ∑_{w′τw′′=w} a′_{w′}a′′_{w′′}).w.

Pour cette multiplication, les séries formelles en ξ_{1}, …, ξ_{n} forment un anneau A_{n}^{τ}.

Soit B = (b_{ij}) une matrice carrée d’ordre n à éléments dans A. Nous lui associerons les deux séries

(12) t^{τ} = ∑_{r=0}^{∞} ∑_{k_{1},...,k_{r}} b_{ℓ_{1}k_{1}} ⋯ b_{ℓ_{r}k_{r}} ξ_{k_{1}} ⋯ ξ_{k_{r}}

(où ℓ_{1}, …, ℓ_{r} désigne le réarrangement croissant de k_{1}, …, k_{r}) et

(13) d^{τ} = ∑_{r=0}^{n}(−1)^{r} ∑_{i_{1}<···<i_{r}} ∑_{σ∈𝔖_{r}} ε_{σ} b_{i_{1},σ(i_{1})} ⋯ b_{i_{r},σ(i_{r})} ξ_{σ(i_{1})} ⋯ ξ_{σ(i_{r})}.

Proposition 5.2. — Les séries t^{τ} et d^{τ} sont inverses dans l’anneau A_{n}^{τ}. On note Q le monoïde des réarrangements et Q′ le monoïde d’intercalement

construits sur l’ensemble {1, 2, …, n} (voir chap. IV.1 et IV.3). Comme au n^{o} précédent, on construit un homomorphisme v de Q dans le monoïde multiplicatif Ω de l’anneau A par la formule

(14)  v\binom{j_{1}···j_{p}}{i_{1}···i_{p}} = ∏_{k=1}^{p} b_{i_{k},j_{k}}.

En tenant compte de l’isomorphisme Γ de Q′ sur Q défini au chapitre IV.3, on obtient un homomorphisme b = v ∘ Γ de Q′ dans Ω ; si w = k_{1} ⋯ k_{r} est un mot et si ℓ_{1} ⋯ ℓ_{r} est son réarrangement croissant, on a

(15)  b(w) = b_{ℓ_{1}k_{1}} ⋯ b_{ℓ_{r}k_{r}}.

La forme de la fonction de Möbius de Q (voir remarque 3.6) et la formule précédente permettent de mettre les séries t^{τ} et d^{τ} sous la forme

(16)  t^{τ} = ∑_{w∈Q′} b(w) · w
(17)  d^{τ} = ∑_{w∈Q′} b(w)μ(w) · w.

Comme on a b(w′ τ w′′) = b(w′) · b(w′′), la formule t^{τ} d^{τ} = d^{τ} t^{τ} = 1 résulte de (16) et (17) par un raisonnement analogue à celui de la partie (C) de la démonstration du théorème 5.1.

Soit A_{n} l’anneau des séries formelles à coefficients dans A en des indéterminées commutatives X_{1}, …, X_{n}. Pour toute série formelle h ∈ A_{n}^{τ}, soit ε_{n}(h) la série obtenue par substitution de X_{1} à ξ_{1}, …, X_{n} à ξ_{n}; alors ε_{n} est un homomorphisme d’anneaux de A_{n}^{τ} dans A_{n}. Il est immédiat que ε_{n} transforme les séries t^{τ} et d^{τ} en les séries t et d du n^{o} 1. La relation t^{τ} d^{τ} = d^{τ} t^{τ} = 1 entraîne donc la relation td = dt = 1, qui n’est autre que le théorème de MacMahon. C’est en ce sens que la proposition 5.2 généralise le théorème de MacMahon.

CHAPITRE VI

RELATIONS ENTRE COEFFICIENTS BINOMIAUX

1. Description du graphe

Le graphe G a trois sommets numérotés 1, 2, 3 et des arêtes a_{ij} joignant le sommet i au sommet j pour i ≠ j. On voit immédiatement qu’il y a cinq cycles

c_{1} = [12], c_{2} = [13], c_{3} = [23], c_{4} = [123], c_{5} = [132].

Deux cycles distincts ayant toujours un sommet en commun, un circuit f dans G s’écrit de manière unique sous la forme f = c_{i_{1}} ⋯ c_{i_{m}} avec 1 ≤ i_{k} ≤ 5 pour 1 ≤ k ≤ m. On note ε_{k}(f) le nombre de fois que le cycle c_{k} apparaît dans le circuit f; la parité d’un circuit f est par définition celle de sa longueur, autrement dit celle de l’entier ε_{4}(f) + ε_{5}(f) car les cycles c_{1}, c_{2} et c_{3} sont de longueur paire.

Soit f un circuit ; la matrice d’incidence N(f) de f est égale à ∑_{k=1}^{5} ε_{k}(f)·I_{k},

où I_{k} est la matrice d’incidence de c_{k}. Les matrices I_{k} sont données dans la table suivante, où les points représentent des zéros :

I_{1} = ( \begin{matrix}· & 1 & · \\ 1 & · & · \\ · & · & · \end{matrix} ) I_{2} = ( \begin{matrix}· & · & 1 \\ · & · & · \\ 1 & · & · \end{matrix} ) I_{3} = ( \begin{matrix}· & · & · \\ · & · & 1 \\ · & 1 & · \end{matrix} )

I_{4} = ( \begin{matrix}· & 1 & · \\ · & · & 1 \\ 1 & · & · \end{matrix} ) I_{5} = ( \begin{matrix}· & · & 1 \\ 1 & · & · \\ · & 1 & · \end{matrix} ) .

2. Étude des circuits pairs

Les multiplicités ε_{k} = ε_{k}(f) (pour 1 ≤ k ≤ 5) d’un circuit pair sont des entiers positifs tels que ε_{4} + ε_{5} soit pair. Il est immédiat qu’un tel système d’entiers s’écrit de manière unique sous la forme

(1) ε_{1} = c − n, ε_{2} = b − n, ε_{3} = a − n,

(2) ε_{4} = n + k, ε_{5} = n − k, où les entiers a, b, c, n, k sont assujettis aux relations

(3) |k| ≤ n ≤ p, où p est le plus petit des trois sommets a, b, c. La matrice d’incidence

N(f) = ∑_{i=1}^{5} ε_{i} · I_{i} est alors de la forme

N = ( \begin{matrix}0 & c + k & b − k \\ c − k & 0 & b − k \\ b + k & a − k & 0 \end{matrix} );

on notera que n n’intervient pas explicitement dans la matrice précédente ; de

plus, on a M = S+k·V où S est la matrice symétrique ( \begin{matrix}0 & c & b \\ c & 0 & a \\ b & a & 0 \end{matrix} ) et V = I_{4}−I_{5}

la matrice antisymétrique ( \begin{matrix}0 & 1 & −1 \\ −1 & 0 & 1 \\ 1 & −1 & 0 \end{matrix} ), ce qui indique la signification des entiers a, b, c, k.

L’identité (A) du formulaire s’obtient en évaluant de deux manières différentes le nombre N des circuits f tels que N(f) = M. Rappelons qu’un circuit correspondant à la matrice M s’obtient en attachant à chacun des sommets une suite finie d’arêtes ayant ce sommet pour source ; la suite des arêtes attachées au sommet 1 doit faire intervenir c + k fois l’arête a_{12} et b − k fois l’arête a_{13} et il y a donc \binom{b+c}{c+k} choix possibles. (^{8}) Raisonnant de manière analogue pour les sommets 2 et 3, on trouve

(5)  N = \binom{b + c}{c + k}\binom{c + a}{a + k}\binom{a + b}{b + k}.

Par ailleurs, vu l’unicité de la décomposition d’un circuit en cycles, le nombre des circuits qui font intervenir ε_{i} fois le cycle c_{i} pour 1 ≤ i ≤ 5 est égal à (ε_{1} +ε_{2} +ε_{3} +ε_{4} +ε_{5})!/(ε_{1}! ε_{2}! ε_{3}! ε_{4}! ε_{5}!) ; si l’on évalue les ε_{i} conformément aux formules (1) et (2) et qu’on somme sur l’entier n soumis à la condition (3), on trouve

(6)  N = ∑_{n=|k|}^{p} \frac{(a + b + c − n)!}{(a − n)! (b − n)! (c − n)! (n + k)! (n − k)!}

et la comparaison de (5) et (6) établit la formule (A).

3. Étude des circuits impairs

L’entier ε_{4} + ε_{5} étant cette fois impair, il faut remplacer les formules (2) et (3) par les suivantes :

(2′) ε_{4} = n + k, ε_{5} = n − k + 1, (3′) κ ≤ n ≤ p avec κ = max{−k, k − 1} et p = min{a, b, c}.

(^{8}) Le nombre de suites faisant intervenir α_{1} fois x_{1}, …, α_{p} fois x_{p} est égal à (α_{1} + ⋯ + α_{p})!/(α_{1}! ⋯ α_{p}!). On note \binom{m}{n} le coefficient binomial m!/((m − n)! n!).

La matrice d’incidence N(f) = ∑_{i=1}^{5} ε_{i} · I_{i} prend alors la forme

(4′)  M′ = ( \begin{matrix}0 & c + k & b − k + 1 \\ c − k + 1 & 0 & a + k \\ b + k & a − k + 1 & 0 \end{matrix} );

l’évaluation directe du nombre N′ des circuits f tels que N(f) = M′ conduit à la formule

(5′)  N′ = \binom{b + c + 1}{c + k}\binom{c + a + 1}{a + k}\binom{a + b + 1}{b + k}

tandis que l’utilisation de la décomposition d’un circuit en produit de cycles conduit à l’évaluation

(6′)  N′ = ∑_{n=κ}^{p} \frac{(a + b + c − n + 1)!}{(a − n)! (b − n)! (c − n)! (n + k)! (n − k + 1)!}.

La comparaison de ces deux résultats établit la formule (A′).

4. Autres identités

Montrons d’abord comment la formule (A) entraîne toutes celles du cas pair ; nous commencerons par (B). Nous considérons l’ensemble I des couples (k, n) d’entiers satisfaisant aux inégalités |k| ≤ n ≤ p, c’est-à-dire les points de coordonnées entières du triangle ABC ci-après :

[figure: n; B; p; C; −p; A; p; k]

Pour toute fonction f sur I, on a la formule de sommation

(7)  ∑_{(k,n)∈I} f(k, n) = ∑_{k=−p}^{p} ∑_{n=|k|}^{p} f(k, n) = ∑_{n=0}^{p} ∑_{k=−n}^{n} f(k, n).

Posons en particulier

f(k, n) = \frac{(a + b + c − n)!}{(a − n)! (b − n)! (c − n)!} \frac{u^{p+k}}{(n + k)!} \frac{v^{p−k}}{(n − k)!};

La formule du binôme entraîne

(uv)^{p−n} \frac{(u + v)^{2n}}{(2n)!} = ∑_{k=−n}^{n} \frac{u^{p+k}}{(n + k)!} \frac{v^{p−k}}{(n − k)!},

et le second membre de (B) est donc égal à ∑_{n=0}^{p} ∑_{k=−n}^{n} f(k, n). D’autre

part, la formule (A) montre que le premier membre de (B) est égal à

∑_{k=−p}^{p} ∑_{n=|k|}^{p} f(k, n), d’où (B) d’après (7).

Il est clair que (C) est le cas particulier u = v = 1 de (B). Si l’on fait u = 1 et v = −1, on a (u+v)^{2n} = 0 pour n > 0 et le second membre de (B) se réduit au seul terme pour lequel n = 0, lui-même égal à (−1)^{p}(a + b + c)!/(a! b! c!) ; la formule (D) est donc le cas particulier u = 1, v = −1 de (B). Si l’on fait a = b = c = q et k = ℓ−q, d’où p = q, dans (A) et qu’on remplace l’indice de sommation n par q − m, on obtient (E) ; on déduit (F) de (B) par les mêmes transformations. Enfin (G) s’obtient en faisant u = v = 1 dans (F) et (H) est le cas particulier a = b = c = q de (D).

Les formules du cas impair se déduisent de (A′) de manière analogue ; seules (D′′) et (H′) méritent un nouvel examen. Remplaçons u par 1 + t et v par −1 dans (B′) ; on obtient une égalité de la forme

(8)  ∑_{k=−p}^{p+1} r_{k}(−1)^{k+1}(1 + t)^{p+k} = ∑_{n=0}^{p} s_{n}(−1)^{n}(1 + t)^{p−n} \frac{t^{2n+1}}{(2n + 1)!}

avec

r_{k} = \binom{b + c + 1}{c + k}\binom{c + a + 1}{a + k}\binom{a + b + 1}{b + k} et s_{n} = \frac{(a + b + c − n + 1)!}{(a − n)! (b − n)! (c − n)!}.

Le coefficient de t dans le polynôme (1 + t)^{p+k} est égal à p + k et les termes du second membre de (8) avec n > 0 sont divisibles par t^{3} et ne contribuent donc pas au coefficient de t. Prenant le coefficient de t dans les deux membres de (8), on obtient

(9)  ∑_{k=−p}^{p+1} r_{k}(−1)^{k+1}(p + k) = s_{0};

faisant t = 0 dans (8), on obtient par ailleurs ∑_{k=−p}^{p+1}(−1)^{k+1}r_{k} = 0, d’où

finalement ∑_{k=−p}^{p+1}(−1)^{k+1}k r_{k} = s_{0}, ce qui n’est autre que (D′′). On démontre

de manière analogue (H′) en faisant u = 1 + t et v = −1 dans (F′) et en égalant les coefficients de t dans les deux membres de l’égalité obtenue ainsi.

5. Utilisation du “Master Theorem” de MacMahon

Nous allons montrer comment déduire les relations (B) et (B′) du

théorème de MacMahon appliqué à la matrice ( \begin{matrix}0 & s & t \\ t & 0 & s \\ s & t & 0 \end{matrix} ) où s et t sont deux

indéterminées. Notons a, b, c des entiers positifs et p le plus petit de ces entiers. Nous noterons X_{1}, X_{2} et X_{3} de nouvelles indéterminées, P le polynôme

(sX_{2} + tX_{3})^{b+c}(sX_{3} + tX_{1})^{c+a}(sX_{1} + tX_{2})^{a+b}

et D le déterminant de la matrice

( \begin{matrix}1 & −sX_{2} & −tX_{3} \\ −tX_{1} & 1 & −sX_{3} \\ −sX_{1} & −tX_{2} & 1 \end{matrix} ) .

Enfin, nous noterons U le coefficient du monôme X_{1}^{b+c}X_{2}^{c+a}X_{3}^{a+b} dans P et V le coefficient du même monôme dans la série formelle D^{−1}.

(a) Calcul de U : en utilisant la formule du binôme, on développe f sous la forme

F = ∑_{λ=−c}^{b} \binom{b + c}{c + λ}(sX_{2})^{c+λ}(tX_{3})^{b−λ} ∑_{μ=−a}^{c} \binom{c + a}{a + μ}(sX_{3})^{a+μ}(tX_{1})^{c−μ}

× ∑_{ν=−b}^{a} \binom{a + b}{b + ν}(sX_{1})^{b+ν}(tX_{2})^{a−ν}

= ∑_{λ,μ,ν} \binom{b + c}{c + λ}\binom{c + a}{a + μ}\binom{a + b}{b + ν}s^{(a+b+c)+(λ+μ+ν)}t^{(a+b+c)−(λ+μ+ν)}

× X_{1}^{b+c−μ+ν}X_{2}^{c+a−ν+λ}X_{3}^{a+b−λ+μ}.

On obtient le coefficient U de X_{1}^{b+c}X_{2}^{c+a}X_{3}^{a+b} en faisant la somme de tous les termes pour lesquels λ = μ = ν sont égaux à un entier k tel que −p ≤ k ≤ p, d’où

(10)  U = ∑_{k=−p}^{p} \binom{b + c}{c + k}\binom{c + a}{a + k}\binom{a + b}{b + k} s^{a+b+c+3k} t^{a+b+c−3k}.

(b) Calcul de V : on trouve immédiatement

D = 1 − stX_{2}X_{3} − stX_{3}X_{1} − stX_{1}X_{2} − (s^{3} + t^{3})X_{1}X_{2}X_{3} = 1 − H

d’où par la formule du binôme

D^{−1} = ∑_{m=0}^{∞} H^{m} = ∑_{α,β,γ,δ≥0}\frac{(α + β + γ + δ)!}{α! β! γ! δ!}(stX_{2}X_{3})^{α}(stX_{3}X_{1})^{β}(stX_{1}X_{2})^{γ}

× (s^{3} + t^{3})^{δ}(X_{1}X_{2}X_{3})^{δ}

= ∑_{α,β,γ,δ≥0}\frac{(α + β + γ + δ)!}{α! β! γ! δ!}(st)^{α+β+γ}(s^{3} + t^{3})^{δ}X_{1}^{β+γ+δ}X_{2}^{γ+α+δ}X_{3}^{α+β+δ}.

Or les nombres entiers positifs solutions du système d’équations linéaires

\begin{aligned}β + γ + δ & = b + c \\ γ + α + δ & = c + a \\ α + β + δ & = a + b \end{aligned}

sont donnés par α = a − n, β = b − n, γ = c − n, δ = 2n où n parcourt l’ensemble des entiers compris entre 0 et p. On conclut alors

(11)  V = ∑_{n=0}^{p} \frac{(a + b + c − n)!}{(a − n)! (b − n)! (c − n)!}(st)^{a+b+c−3n} \frac{(s^{3} + t^{3})^{2n}}{(2n)!} .

(c) Démonstration de (B) : le théorème de MacMahon fournit l’égalilté U = V. Si l’on remplace s^{3} par u et t^{3} par v dans l’égalité

(st)^{3p−(a+b+c)}U = (st)^{3p−(a+b+c)}V,

on obtient immédiatement (B).

La démonstration de (B′) s’obtient de manière analogue par la considération des coefficients du monôme X_{1}^{b+c+1}X_{2}^{c+a+1}X_{3}^{a+b+1} dans le polynôme

Q = (sX_{2} + tX_{3})^{b+c+1}(sX_{3} + tX_{1})^{c+a+1}(sX_{1} + tX_{2})^{a+b+1}

et dans la série formelle D^{−1}.

FORMULAIRE 43

FORMULAIRE

Dans tout ce formulaire, on note q, a, b et c des entiers positifs et l’on pose p = min{a, b, c}.

I. Cas pair.

(A) \binom{b + c}{c + k}\binom{c + a}{a + k}\binom{a + b}{b + k}

= ∑_{n=|k|}^{p} \frac{(a + b + c − n)!}{(a − n)! (b − n)! (c − n)! (n + k)! (n − k)!} lorsque |k| ≤ p.

(B) ∑_{k=−p}^{p} \binom{b + c}{c + k}\binom{c + a}{a + k}\binom{a + b}{b + k}u^{p+k}v^{p−k}

= ∑_{n=0}^{p} \frac{(a + b + c − n)!}{(a − n)! (b − n)! (c − n)!}(uv)^{p−n} \frac{(u + v)^{2n}}{(2n)!} [Foata 1965]

(C) ∑_{k=−p}^{p} \binom{b + c}{c + k}\binom{c + a}{a + k}\binom{a + b}{b + k} = ∑_{n=0}^{p} \frac{(a + b + c − n)!}{(a − n)! (b − n)! (c − n)!} \frac{2^{2n}}{(2n)!}

(D) ∑_{k=−p}^{p}(−1)^{k}\binom{b + c}{c + k}\binom{c + a}{a + k}\binom{a + b}{b + k} = \frac{(a + b + c)!}{a! b! c!} [Fjeldstad 1954]

(E) \binom{2q}{ℓ}^{3} = ∑_{m=0}^{ℓ} \frac{(2q + m)!}{(m!)^{3} (ℓ − m)! (2q − ℓ − m)!} si 0 ≤ ℓ ≤ 2q

(F) ∑_{ℓ=0}^{2q} \binom{2q}{ℓ}^{3}u^{ℓ}v^{2q−ℓ} = ∑_{m=0}^{ℓ} \frac{(2q + m)!}{(m!)^{3} (2q − 2m)!}(uv)^{m}(u + v)^{2q−2m}

[MacMahon 1915]

(G) ∑_{ℓ=0}^{2q} \binom{2q}{ℓ}^{3} = ∑_{m=0}^{ℓ} \frac{(2q + m)!}{(m!)^{3} (2q − 2m)!}2^{2q−2m} [MacMahon 1915]

(H) ∑_{ℓ=0}^{2q}(−1)^{ℓ}\binom{2q}{ℓ}^{3} = (−1)^{q} \frac{(3q)!}{(q!)^{3}} [Dixon 1890]

II. Cas impair :

(A′) \binom{b + c + 1}{c + k}\binom{c + a + 1}{a + k}\binom{a + b + 1}{b + k}

= ∑_{n=κ}^{p} \frac{(a + b + c − n + 1)!}{(a − n)! (b − n)! (c − n)! (n + k)! (n − k + 1)!}

lorsque κ = max{−k, k − 1} est majoré par p.

(B′) ∑_{k=−p}^{p+1} \binom{b + c + 1}{c + k}\binom{c + a + 1}{a + k}\binom{a + b + 1}{b + k}u^{p+k}v^{p−k+1}

= ∑_{n=0}^{p} \frac{(a + b + c − n + 1)!}{(a − n)! (b − n)! (c − n)!}(uv)^{p−n} \frac{(u + v)^{2n+1}}{(2n + 1)!}

(C′) ∑_{k=−p}^{p+1} \binom{b + c + 1}{c + k}\binom{c + a + 1}{a + k}\binom{a + b + 1}{b + k}

= ∑_{n=0}^{p} \frac{(a + b + c − n + 1)!}{(a − n)! (b − n)! (c − n)!} \frac{2^{2n+1}}{(2n + 1)!}

(D′) ∑_{k=−p}^{p+1}(−1)^{k}\binom{b + c + 1}{c + k}\binom{c + a + 1}{a + k}\binom{a + b + 1}{b + k} = 0

(D′′) ∑_{k=−p}^{p+1}(−1)^{k+1}k\binom{b + c + 1}{c + k}\binom{c + a + 1}{a + k}\binom{a + b + 1}{b + k}= \frac{(a + b + c + 1)!}{a! b! c!}

(E′) \binom{2q + 1}{ℓ}^{3} = ∑_{m=0}^{ℓ} \frac{(2q + m + 1)!}{(m!)^{3} (ℓ − m)! (2q − ℓ − m + 1)!} si 0 ≤ ℓ ≤ q

(F′) ∑_{ℓ=0}^{2q+1} \binom{2q + 1}{ℓ}^{3}u^{ℓ}v^{2q−ℓ+1}

= ∑_{m=0}^{ℓ} \frac{(2q + m + 1)!}{(m!)^{3} (2q − 2m + 1)!}(uv)^{m}(u + v)^{2q−2m+1}

(G′) ∑_{ℓ=0}^{2q+1} \binom{2q + 1}{ℓ}^{3} = ∑_{m=0}^{ℓ} \frac{(2q + m + 1)!}{(m!)^{3} (2q − 2m + 1)!}2^{2q−2m+1}

(H′) ∑_{ℓ=0}^{2q+1}(−1)^{ℓ+1}ℓ \binom{2q + 1}{ℓ}^{3} = (−1)^{q} \frac{(3q + 1)!}{(q!)^{3}}.

CHAPITRE VII

APPLICATIONS PROBABILISTES

1. Identité de Spitzer

Nus considèrerons dans la suite des séries formelles à coefficients complexes en une indéterminée t. Si U est une telle série, sans terme constant, son

exponentielle est la série exp U = ∑_{m=0}^{∞} U^{m}/m! La formule du binôme montre immédiatement que l’on a

(1)  exp(U + V) = (exp U) · (exp V).

De plus, pour toute série V sans terme constant, il existe une série U sans

terme constant telle que V = ∑_{m=1}^{∞} U^{m}/m! = (exp U) − 1 et une seule : ceci

résulte des théorèmes usuels sur la résolution “d’équations formelles.” On en déduit que l’application exponentielle est une bijection de l’ensemble des séries sans terme constant, sur l’ensemble des séries de terme constant 1. L’application réciproque est appelée logarithme ; on note log V le logarithme de V.

Ces généralités étant rappelées, considérons deux suites

(a_{n})_{n≥1} = (a_{1}, a_{2}, …) et (b_{n})_{n≥1} = (b_{1}, b_{2}, …)

de nombres complexes. On dit qu’elles satisfont à l’identité de Spitzer si l’on a

(2) 1 + ∑_{n=1}^{∞} a_{n} t^{n} = exp ∑_{k=1}^{∞} \frac{b_{k}}{k} t^{k}.

D’après ce qui précède, la correspondance (a_{n})_{n≥1} ↔ (b_{n})_{n≥1} exprimée par cette identité est bijective.

On peut donner une forme récurrente plus simple à cette relation. Notons U′ la dérivée d’une série U; on sait que la dérivée de exp U est U′·exp U. Posons alors

A = 1 + ∑_{n=1}^{∞} a_{n} t^{n}, B = ∑_{k=1}^{∞} \frac{b_{k}}{k} t^{k}.

La relation (2) s’écrit A = exp B, d’où tA′ = tB′ · exp B = A · (tB′) ; or

on a tA′ = ∑_{n=1}^{∞} na_{n}t^{n} et tB′ = ∑_{k=1}^{∞} b_{k}t^{k}; en prenant le coefficient de t^{n} dans l’identité tA′ = A · (tB′), on trouve

(3)  na_{n} = b_{n} + ∑_{k=1}^{n−1} a_{k} · b_{n−k} (n ≥ 1).

La suite (b_{n})_{n≥1} étant donnée, les relations (3) pour n = 1, 2, … déterminent de manière unique la suite (a_{n})_{n≥1} par récurrence. Autrement dit, la relation de Spitzer équivaut au système des relations (3).

Notre but est maintenant de calculer explicitement le coefficient a_{n} en fonction de b_{1}, …, b_{n} (pour n ≥ 1 donné). On a B = B_{1} + B_{2} avec

B_{1} = b_{1}t + \frac{b_{2}}{2} t^{2} + ⋯ + \frac{b_{n}}{n} t^{n}, B_{2} = ∑_{k=n+1}^{∞} \frac{b_{k}}{k} t^{k}.

Comme la série B_{2} est divisible par t^{n+1}, il en est de même de la série

(exp B_{2}) − 1 = ∑_{m=1}^{∞}(B_{2})^{m}/m! et a fortiori de

(exp B_{1})((exp B_{2}) − 1) = (exp B_{1})(exp B_{2}) − exp B_{1} = exp B − exp B_{1}.

Le coefficient de t^{n} dans exp B est donc le même que dans exp B_{1} ; or on a

exp B_{1} = exp(b_{1}t + \frac{b_{2}}{2} t^{2} + ⋯ + \frac{b_{n}}{n} t^{n})

= ∏_{k=1}^{n} exp \frac{b_{k}}{k} t^{k}

= ∏_{k=1}^{n} ∑_{m=0}^{∞} \frac{1}{m!}(\frac{b_{k}}{k} )^{m}t^{km}

= ∑_{m_{1},...,m_{n}} ∏_{k=1}^{n} \frac{1}{m_{k}!}(\frac{b_{k}}{k} )^{m_{k}}t^{km_{k}}.

Finalement, on a

(4)  a_{n} = ∑ \frac{b_{1}^{m_{1}} ⋯ b_{n}^{m_{n}}}{m_{1}! ⋯ m_{n}! 1^{m_{1}}2^{m_{2}} ⋯ n^{m_{n}}} ,

la sommation étant étendue à toutes les suites (m_{1}, …, m_{n}) de n entiers positifs satisfaisant à 1m_{1} + 2m_{2} + ⋯ + m_{n} = n.

Avant d’énoncer la proposition 7.1, il nous faudra introduire quelques notations. On note ℂ l’ensemble des nombres complexes ; pour tout entier n ≥ 1, on note 𝔖_{n} l’ensemble des permutations de {1, 2, …, n} et γ_{n} la permutation circulaire d’ordre n définie par

(5)  γ_{n}(i) = \{ \begin{matrix}i + 1, & si 1 ≤ i ≤ n − 1 ; \\ 1, & si i = n. \end{matrix}

Enfin, si σ ∈ 𝔖_{m} et τ ∈ 𝔖_{n}, on note σ ⊕ τ l’élément ρ de 𝔖_{m+n} défini par

(6)  ρ(i) = \{ \begin{matrix}σ(i), & si 1 ≤ i ≤ m; \\ m + τ(i − m), & si m + 1 ≤ i ≤ m + n. \end{matrix}

Proposition 7.1. — On suppose donnée une suite de fonctions h_{n} : 𝔖_{n} → ℂ (pour n ≥ 1) satisfaisant aux relations :

(a) on a h_{n}(τστ^{−1}) = h_{n}(σ) pour σ, τ dans 𝔖_{n};

(b) on a h_{m+n}(σ ⊕ τ) = h_{m}(σ) · h_{n}(τ) pour σ ∈ 𝔖_{m} et τ ∈ 𝔖_{n}. Posons a_{n} = (1/n!) ∑_{σ∈𝔖_{n}} h_{n}(σ) et b_{n} = h_{n}(γ_{n}). L’identité de Spitzer est satisfaite pour les suites (a_{n})_{n≥1} et (b_{n})_{n≥1}.

Soit σ ∈ 𝔖_{n}; supposons que σ se décompose en p cycles de longueurs respectives n_{1}, …, n_{p}. Il est bien connu qu’il existe τ ∈ 𝔖_{n} tel que

τστ^{−1} = γ_{n_{1}} ⊕ ⋯ ⊕ γ_{n_{p}};

d’après les hypothèses (a) et (b), on a alors

h_{n}(σ) = h_{n}(τστ^{−1}) = h_{n_{1}}(γ_{n_{1}}) ⋯ h_{n_{p}}(γ_{n_{p}}) = b_{n_{1}} ⋯ b_{n_{p}}.

Autrement dit, si σ comporte m_{k} cycles de longueur k pour k = 1, 2, …, n, on a h_{n}(σ) = b_{1}^{m_{1}} ⋯ b_{k}^{m_{k}}. Il est bien connu qu’il existe dans 𝔖_{n} un nombre égal à n!/(m_{1}! ⋯ m_{n}! 1^{m_{1}} ⋯ n^{m_{n}}) permutations ayant m_{k} cycles de longueur k pour k = 1, 2, …, n. On a alors

a_{n} = \frac{1}{n!} ∑_{σ∈𝔖_{n}} h_{n}(σ) = \frac{1}{n!} ∑ \frac{n!}{m_{1}! ⋯ m_{n}! 1^{m_{1}} ⋯ n^{m_{n}}} b_{1}^{m_{1}} ⋯ b_{n}^{m_{n}},

c’est-à-dire que la relation (4) est satisfaite.

Remarque 7.2. — Si l’on pose h_{n}(σ) = 1 pour tout n ≥ 1 et tout σ ∈ 𝔖_{n}, les conditions (a) et (b) de la proposition 7.1 sont remplies. On a dans ce cas a_{n} = b_{n} = 1, d’où

1 + ∑_{n=1}^{∞} t^{n} = exp ∑_{k=1}^{∞} \frac{t^{k}}{k} .

Le premier membre est l’inverse de 1 − t; changeant t en −t, puis prenant le logarithme de l’inverse des deux membres (on a (exp U)^{−1} = exp(−U) ), on retrouve l’identité bien connue

log(1 + t) = ∑_{k=1}^{∞}(−1)^{k−1} \frac{t^{k}}{k} .

2. Propriétés du permanent

Rappelons d’abord la définition du permanent Per(a_{ij}) d’une matrice carrée complexe (a_{ij})_{1≤i,j≤n} : c’est le nombre

∑_{σ∈𝔖_{n}} ∏_{i=1}^{n} a_{i,σ(i)}.

Cette définition ne diffère de celle du déterminant que par l’omission des signes ±.

Dans la suite de ce n^{o}, on note X un ensemble totalement ordonné et u une fonction à valeurs complexes sur X × X. (^{10})

Lemme 7.3. — Pour x_{1}, …, x_{n} dans X, posons

(7)  h_{n}(x_{1}, …, x_{n}) = ∏_{i=1}^{n} u(\overline{x}_{i}, x_{i}),

où \overline{x}_{1} ⋯ \overline{x}_{n} est le réarrangement croissant de x_{1} ⋯ x_{n}. On a alors

(8)  ∑_{σ∈𝔖_{n}} h_{n}(x_{σ(1)}, …, x_{σ(n)}) = Per(u(x_{i}, x_{j}))_{1≤i,j≤n}.

Notons a(x_{1}, …, x_{n}) le premier membre de (8) et b(x_{1}, …, x_{n}) le second. Soit τ ∈ 𝔖_{n}; on a

b(x_{τ(1)}, …, x_{τ(n)}) = ∑_{σ∈𝔖_{n}} ∏_{i=1}^{n} u(x_{τ(i)}, x_{τσ(i)})

= ∑_{σ∈𝔖_{n}} ∏_{i=1}^{n} u(x_{j}, x_{τστ^{−1}(j)})

= ∑_{σ∈𝔖_{n}} ∏_{i=1}^{n} u(x_{j}, x_{σ(j)})

= b(x_{1}, …, x_{n}).

Autrement dit, la fonction de n variables b est symétrique ; comme il en est évidemment de même de a, il suffit d’établir la formule (8) lorsque la suite (x_{1}, …, x_{n}) est croissante. Mais dans ce cas, pour tout σ ∈ 𝔖_{n}, le mot x_{1} ⋯ x_{n} est le réarrangement croissant de x_{σ(1)} ⋯ x_{σ(n)}, d’où

h_{n}(x_{σ(1)}, …, x_{σ(n)}) = ∏_{i=1}^{n} u(x_{i}, x_{σ(i)});

en sommant sur σ, on trouve immédiatement (8).

Lemme 7.4. — On suppose que l’on a n ≥ 2 et u(x, y) = 1 lorsque x ≥ y. Pour x_{1}, …, x_{n} dans X, posons

(9)  k_{n}(x_{1}, …, k_{n}) = ∏_{i=1}^{n−1} u(x_{i}, x_{i+1}).

On a alors

(10)  ∑_{σ∈𝔖_{n}} k_{n}(x_{σ(1)}, …, x_{σ(n)}) = Per(u(x_{i}, x_{j}))_{1≤i,j≤n}.

(^{10}) La définition du permanent conserve un sens pour des matrices à coefficients dans un anneau commutatif quelconque. On peut généraliser de manière analogue les lemmes 7.3 et 7.4.

En raisonnant comme dans le lemme précédent, on voit qu’il suffit de prouver l’identité (10) dans le cas d’une suite croissante (x_{1}, …, x_{n}). Posons alors a_{ij} = u(x_{i}, x_{j}) pour 1 ≤ i, j ≤ n d’où a_{ij} = 1 lorsque i ≥ j. On est donc ramené à prouver la relation

(11)  ∑_{σ∈𝔖_{n}} ∏_{i=1}^{n−1} a_{σ(i),σ(i+1)} = ∑_{σ∈𝔖_{n}} ∏_{i=1}^{n−1} a_{i,σ(i)}

(noter que l’on a n ≥ σ(n) d’où a_{n,σ(n)} = 1).

Or les réarrantements du mot 12 ⋯ n sont les suites σ(1)σ(2) ⋯ σ(n) où σ parcourt 𝔖_{n}. Appliquons le théorème 4.11, (c) au cas où X = {1, 2, …, n}, où Ω est le monoïde multiplicatif des nombres complexes et c(i, j) = a_{ij}. On en déduit qu’il existe une bijection Φ : σ ↦ σ′ de 𝔖_{n} sur lui-même telle que

(12)  ∏_{i=1}^{n−1} a_{σ(i),σ(i+1)} = ∏_{i=1}^{n−1} a_{i,σ′(i)} (σ ∈ 𝔖_{n}).

Sommant sur σ (ou, ce qui revient au même, sur σ′), on déduit immédiatement (11) de (12).

3. Fonctions caractéristiques de certaines variables aléatoires

Dans ce n^{o}, on note (ξ_{n})_{n≥1} une suite de variables aléatoires indépendantes de même loi sur un espace probabilisé (Ω, 𝔉, P) ; on note 𝔼[τ] l’espérance d’une variable aléatoire τ définie sur (Ω, 𝔉, P). On rappelle que ℝ est l’ensemble des nombres réels.

Lemme 7.5. — Soit u une fonction borélienne et bornée sur ℝ^{2}, à valeurs complexes. Pour tout entier n ≥ 1, posons

a_{n} = \frac{1}{n!}𝔼[Per(u(ξ_{i}, ξ_{j}))_{1≤i,j≤n}]
b_{n} = 𝔼[u(ξ_{1}, ξ_{2}) ⋯ u(ξ_{n−1}, ξ_{n})u(ξ_{n}, ξ_{1})].

Les suites (a_{n})_{n≥1} et (b_{n})_{n≥1} satisfont à l’identité de Spitzer.

Pour tout entier n ≥ 1 et tout σ ∈ 𝔖_{n}, posons

h_{n}(σ) = 𝔼[∏_{i=1}^{n} u(ξ, ξ_{σ(i)})].

Il est clair qu’on a

a_{n} = \frac{1}{n!} ∑_{σ∈𝔖_{n}} h_{n}(σ), b_{n} = h_{n}(γ_{n});

il suffit donc de prouver que les fonctions h_{n} satisfont aux hypothèses (a) et (b) de la proposition 7.1.

(a) Soient d’abord σ et τ dans 𝔖_{n}; définissons une fonction borélienne et bornée v sur ℝ^{n} par

v(x_{1}, …, x_{n}) = ∏_{i=1}^{n}u(x_{i}, x_{σ(i)}).

On a

v(x_{τ(1)}, …, v_{τ(n)}) = ∏_{i=1}^{n} u(x_{τ(j)}, x_{τσ(j)})

= ∏_{i=1}^{n} u(x_{i}, x_{τστ^{−1}(i)})

(la première égalité par substitution dans la définition de v, la seconde par le changement j = τ^{−1}(i)). On en déduit

h_{n}(σ) = 𝔼[v(ξ_{1}, …, ξ_{n})]
h_{n}(τστ^{−1}) = 𝔼[v(ξ_{τ(1)}, …, ξ_{τ(n)})];

mais le vecteur aléatoire (ξ_{1}, …, ξ_{n}) est à composantes indépendantes de même loi et sa loi est invariante par permutation des coordonnées ; les variables aléatoires v(ξ_{n}, …, ξ_{n}) et v(ξ_{τ(1)}, …, ξ_{τ(n)}) ont donc même espérance. En conclusion, on a h_{n}(τστ^{−1}) = h_{n}(σ).

(b) Soient σ ∈ 𝔖_{m} et τ ∈ 𝔖_{n}; posons ρ = σ ⊕ τ. On a

h_{m+n}(ρ) = 𝔼[∏_{i=1}^{m} u(ξ_{i}, ξ_{σ(i)}) · ∏_{j=1}^{n} u(ξ_{m+j}, ξ_{m+τ(j)})]

h_{m}(σ) = 𝔼[∏_{i=1}^{m} u(ξ_{i}, ξ_{σ(i)})]

h_{n}(τ) = 𝔼[∏_{j=1}^{n} u(ξ_{j}, ξ_{τ(j)})];

mais les hypothèses faites sur la suite (ξ_{n})_{n≥1} entraînent que les vecteurs aléatoires (ξ_{1}, …, ξ_{m}) et (ξ_{m+1}, …, ξ_{m+n}) sont indépendants et que le vecteur aléatoire (ξ_{m_{1}}, …, ξ_{m+n}) a même loi que (ξ_{1}, …, ξ_{m}). La formule h_{m+n}(ρ) = h_{m}(σ) · h_{n}(τ) est alors immédiate.

Avant d’énoncer les deux thèorèmes fondamentaux de ce chapitre, nous introduirons quelques notations supplémentaires. On note b une fonction borélienne sur ℝ^{2}, à valeurs réelles. Pour tout entier n ≥ 1, on note \overline{ξ}_{1}^{(n)}, …, \overline{ξ}_{n}^{(n)} le réarrangement croissant de la suite ξ_{1}, …, ξ_{n}; (^{11}) on pose

(13)  η_{n} = ∑_{i=1}^{n} b(\overline{ξ}_{i}^{(n)}, ξ_{i})

(14)  ζ_{n} = ∑_{i=1}^{n−1} b(ξ_{i}, ξ_{i+1})
(15)  θ_{n} = ζ + b(ξ_{n}, ξ_{1}).

(^{11}) Autrement dit, pour tout ω ∈ Ω, la suite \overline{ξ}_{1}^{(n)}(ω), …, \overline{ξ}_{n}^{(n)}(ω) est le réarrangement croissant de la suite ξ_{1}(ω), …, ξ_{n}(ω).

Enfin, si ξ est une variable aléatoire réelle et q un nombre réel, on pose

(16)  φ_{ξ}(q) = 𝔼[e^{iqξ}]

(φ_{ξ} est la fonction caractéristique de ξ).

Théorème 7.6. — Soit q un nombre réel. Pour tout entier n ≥ 1, on pose a_{n} = φ_{η_{n}}(q) et b_{n} = φ_{θ_{n}}(q). Alors les suites (a_{n})_{n≥1} et (b_{n})_{n≥1} satisfont à l’identité de Spitzer.

Théorème 7.7. — Supposons que l’on ait b(x, y) = 0 lorsque x ≥ y. Alors les variables aléatoires η_{n} et ζ_{n} ont même loi.

Posons u(x, y) = e^{iqb(x,y)} ; la fonction u sur ℝ^{2} est borélienne et de module 1, donc bornée. On définit h_{n} comme dans le lemme 7.3, d’où

a_{n} = 𝔼[∏_{i=1}^{n} u(\overline{ξ}_{i}^{(n)}, ξ_{i})] = 𝔼[h_{n}(ξ_{1}, …, ξ_{n})];

comme le vecteur aléatoire (ξ_{1}, …, ξ_{n}) est symétrique, on a donc

a_{n} = \frac{1}{n!}[ ∑_{σ∈𝔖_{n}} h_{n}(ξ_{σ(1)}, …, ξ_{σ(n)})].

Le lemme 7.3 entraîne

a_{n} = \frac{1}{n!}𝔼[Per(u(ξ_{i}, ξ_{j}))_{1≤i,j≤n}];

comme on a évidemment b_{n} = 𝔼[u(ξ_{1}, ξ_{2})u(ξ_{2}, ξ_{3}) ⋯ u(ξ_{n−1}, ξ_{n})u(ξ_{n}, ξ_{1})],

le lemme 7.5 montre que les suites (a_{n})_{n≥1} et (b_{n})_{n≥1} satisfont à l’identité de Spitzer. Ceci démontre le théorème 7.6.

Supposons maintenant que l’on ait b(x, y) = 0 pour x ≥ y; posons encore u(x, y) = e^{iqb(x,y)}, d’où u(x, y) = 1 pour x ≥ y. Enfin posons

a′_{n} = φ_{ζ_{n}}(q) = 𝔼[∏_{i=1}^{n−1} u(ξ_{i}, ξ_{i+1})].

En raisonnant comme précédemment, mais en utilisant le lemme 7.4 en place du lemme 7.3, on voit que les suites (a′_{n})_{n≥1} et (b_{n})_{n≥1} satisfont à l’identité de Spitzer. On a donc a′_{n} = a_{n}, c’est-à-dire φ_{ζ_{n}}(q) = φ_{η_{n}}(q) pour tout n ≥ 1 et tout nombre réel q. Autrement dit, les variables aléatoires ζ_{n} et η_{n} ont même fonction caractéristique, donc même loi. Ceci démontre le théorème 7.7.

Exemple 7.8. — Soit [c, d] un intervalle fini, le cas particulier c = d n’étant pas dépourvu d’intérêt. Définissons la fonction b sur ℝ^{2} par

b(x, y) = \{ \begin{matrix}1, & si x < c et y > d; \\ 0, & sinon. \end{matrix}

Il est clair qu’on a b(x, y) = 0 lorsque x ≥ y. La signification des variables η_{n} et ζ_{n} est facile à élucider dans ce cas :

(a) si N est le nombre aléatoire d’indices i tels que 1 ≤ i ≤ n et ξ_{i} < c, alors η_{n} est le nombre aléatoire d’indices j tels que 1 ≤ j ≤ N et ξ_{h} > d. Ceci s’interprète aisément en termes de méthode d’échantillonnage.

(b) ζ_{n} est le nombre aléatoire d’indice i tels que 1 ≤ i ≤ n − 1, ξ_{i} < c et ξ_{i+1} > d; on peut l’appeler le nombre des traversées croissantes de l’intervalle [c, d].

Ces deux variables aléatoires prennent les valeurs 0, 1, 2, …, n − 1 ; le théorème 7.7 entraîne qu’elles ont même loi.

BIBLIOGRAPHIE

[1] Foata (D.). — Étude algébrique de certains problèmes d’Analyse Combinatoire et du Calcul des Probabilités, Publ. Inst. Statist. Univ. Paris, t. 14, 1965, p. 81–241.

[2] Hardy (G. H.) et Wright (E. M.). — An Introduction to the Theory of Numbers. 4^{ième} édition, Oxford Univ. Press, 1960.

[3] MacMahon (P. A.). — Combinatory Analysis, 1. — Cambridge Univ. Press, 1915 (réimpression : Chelsea Publ. Co., New York, 1960).

[4] Rota (G.-C.). — On the Foundations of Combinatorial Theory I. Theory of Möbius Functions, Z. Wahrscheinlichkeitstheorie, t. 2, 1964, p. 340–368.

[5] Spitzer (F.). — A combinatorial lemma and its appllication to probability theory, Trans. Amer. Math. Soc., t. 82, 1956, p. 323–339.

INDEX DES PRINCIPALES NOTATIONS (Une référence telle que IV.3 renvoie au n^{o} 3 du chapitre IV.)

Symbole  Référence Signification
Mo(Z)  I.1  Monoïde libre construit sur Z.
Ab(Z)  I.1  Monoïde commutatif libre construit sur Z.
ϵ  I.1  Homomorphisme canonique de Mo(Z) dans Ab(Z).
L(Z; C)  I.2  Monoïde défini par des relations de commutation.
π  I.2  Homomorphisme canonique de L(Z; C) dans Ab(Z).
λ  I.2  Homomorphisme canonique de Mo(Z) dans L(Z; C).
ι  I.2  Involution de L(Z; C).
[z]  I.2  Élément de L(Z; C) correspondant à z ∈ Z.
[F]  I.2  Produit des éléments [z] pour z parcourant la

partie commutative F.

μ_{M}  II.1  Fonction de Möbius du monoïde M.
|F |  II.3  Nombre d’éléments d’un ensemble fini F.
σ(a)  III.1  Source de l’arête a.
β(a)  III.1  But de l’arête a.
N(f)  III.1  Matrice d’incidence du flot f.
b(a)  III.2  Flot associé à l’arête a.
σ(c)  III.5  Source du chemin c.
β(c)  III.5  But du chemin c.
b(c)  III.5  Flot associé au chemin c.
F (X)  IV.1  Monoïde des flots sur l’ensemble X.
Q(X)  IV.1  Monoïde des réarrangements construit sur X.
θ  IV.1  Homomorphisme canonique de F (X) dans Ab(X).
n_{x,y}(f)  IV.1  Multiciplicité du couple (x, y) dans le flot f.
\binom{w}{w′}  IV.1  Réarrangement défini par les mots w et w′.
n_{c}  IV.1  Homomorphisme de F (X) dans Ω associé

à l’application c de X × X dans Ω.

γw  IV.2  Mot déduit de w par permutation circulaire.
[w]  IV.2  Cycle associé à un mot w sans lettres répétées.
\overline{w}  IV.3  Réarrangement croissant du mot w.
Q′(X)  IV.3  Monoïde d’intercalement construit sur l’ensemble

totalement ordonné X.

Γ  IV.3  Isomomorphisme de Q′(X) sur Q(X) défini

par Γ(w) = \binom{w}{\overline{w}}.

Π  IV.3  Isomorphisme réciproque de Γ.
w τ w′  IV.3  Produit d’intercalement des mots w et w′.
ν_{x,y}(w)  IV.3  Nombre des paires (\overline{x}_{i}, x_{i}) égales à (x, y)

où w = x_{1} ⋯ x_{m} et \overline{w} = \overline{x}_{1} ⋯ \overline{x}_{m}.

ν_{c} IV.3 Homomorphisme de Q′(X) dans Ω associé

à l’application c de X × X dans Ω.

ξ_{x,y}(w) IV.4 Nombre de couples (x_{i}, x_{i+1}) égaux à

(x, y) où w = x_{1} ⋯ x_{m}.

ξ_{c}(w) IV.4 Somme c(x_{1}, x_{2}) + ⋯ + c(x_{m−1}, x_{m}) pour

w = x_{1} ⋯ x_{m} et une application c de X ×X dans Ω.

F w  IV.4  Dernière lettre du mot w.
Δ  IV.4  Bijection de Mo(X) sur Q(X) définie par

Δ(w) = \binom{γw_{1}···γw_{p}}{w_{1}···w_{p}} si (w_{1}, …, w_{p}) est la décomposition descendante de w.

Φ  IV.5  Permutation Γ^{−1} ∘ Δ de Mo(X).
ν(w)  IV.5  Nombre des indices i avec \overline{x}_{i} < x_{i} où

w = x_{1} ⋯ x_{m} et \overline{w} = \overline{x}_{1} ⋯ \overline{x}_{m}.

ξ(w) IV.5 Nombre des indices i tels que x_{i} < x_{i+1}

pour le mot w = x_{1} ⋯ x_{m}.

γ_{n}  VII.1  Permutation circulaire de 12 ⋯ n.
σ ⊕ τ  VII.1  Permutation (\begin{matrix}σ(1) & ⋯ & σ(m) & m + τ(1) & ⋯ & m + τ(n) \\ 1 & ⋯ & m & m + 1 & ⋯ & m + n \end{matrix}).
Per(a_{i,j})  VII.2  Permanent de la matrice carrée (a_{ij}).
(ξ_{n})_{n≥1}  VII.3  Une suite de variables aléatoires indépendantes

et de même loi.

\overline{ξ}_{1}^{(n)}, …, \overline{ξ}_{n}^{(n)} VII.3  Réarrangement croissant de ξ_{1}, …, ξ_{n}.
b  VII.3  Fonction borélienne de deux variables réelles.
γ_{n}, ζ_{n}, θ_{n}  VII.3  Variables aléatoires déduites de ξ_{1}, …, ξ_{n} et n.

Notations générales

ℤ : ensemble des nombres entiers.
ℝ : ensemble des nombres réels.
ℂ : ensemble des nombres complexes.
𝔖_{n} : ensemble des permutations de l’ensemble {1, 2, …, n}.

INVERSIONS DE MÖBIUS (^{1})

Dominique Foata

La formule d’inversion de Möbius, comme le soulignait fort justement le professeur Temperley lors de la Rencontre d’Aberdeen (6-12 juillet 1975), n’est en fait qu’une sublimation du principe d’inclusion-exclusion. Chacun sait bien que le plus difficile dans les applications est de calculer la fonction de Möbius sous-jacente et à l’exception de quelques cas simples, ce calcul ne dérive pas des principes, mais reste une affaire d’ingéniosité et d’expérience.

La formule d’inversion, de façon habituelle (cf., par exemple, Rota (1964)), est présentée dans le cadre des ensembles ordonnés localement finis (“locally finite partially ordered sets”). Dans Cartier-Foata (1969, chap. 2), on trouve une définition de fonction de Möbius des monoïdes à factorisation finie. Le but de cette note est de montrer la connexion entre ces deux présentations.

En aucun cas, je ne veux faire ici œuvre originale : mon but est simplement de montrer qu’il n’y a qu’une “théorie” de l’inversion de Möbius. Le cadre choisi pour présenter la formule d’inversion est au fond accessoire et ne peut être qu’une structure algébrique rudimentaire. En fait, la proposition 1 cidessous doit être attribuée à Rota (1972) et la proposition 2 à Schützenberger (1974) dans des communications privées avec l’auteur.

1. Ensembles ordonnés

La construction de la fonction de Möbius pour les ensembles ordonnés est très clairement exposée dans Rota (1964). Soit P un ensemble ordonné localement fini, c’est-à-dire que si x ≤ y, il n’y a qu’un nombre fini de z ∈ P tels que x ≤ z ≤ y. On forme l’ensemble R(P × P) des fonctions réelles de deux variables x et y, où x et y sont dans P, ayant les propriétés suivantes :

(i) f(x, y) = 0 si x ≰ y; (ii) f(x, x) est, pour tout x ∈ P, une constante qui ne dépend que de f.(^{2})

L’ensemble R(P × P) est muni d’une structure d’algèbre associative sur le corps des réels – on l’appellera désormais l’algèbre d’incidence de P – en prenant pour somme f + g et produit fg de deux éléments f, g de R(P × P), les fonctions définies par

(f + g)(x, y) = f(x, y) + g(x, y);
(fg)(x, y) = ∑_{x≤z≤y} f(x, z)g(z, y);

(^{1}) The present text was written on the occasion of the Science Research Council Rencontre, Aberdeen, July 6–12 1975 and had never been published since.

(^{2}) La restriction (ii) n’est en général pas imposée. Elle est ici mentionnée par commodité.

On se persuadera que les fonction ξ_{P} et μ_{P} définies ci-après appartiennent bien à R(P ×P).

pour tout x, y dans P. L’algèbre R(P × P) a un élément unité δ (la fonction de Kronecker). On distingue enfin une application ξ_{P} définie par

ξ_{P} (x, y) = \{ \begin{matrix}1, & si x ≤ y; \\ 0, & autrement. \end{matrix}

La fonction de Möbius μ_{P} de P n’est autre que l’inverse (on démontre qu’il existe !) de ξ_{P} dans A(P ×P). Autrement dit, μ_{P} est la fonction satisfaisant à

ξ_{P} μ_{P} = μ_{P} ξ_{P} = δ.

2. Monoïdes à factorisation finie

Soit maintenant M un monoïde, c’est-à-dire un ensemble muni d’une opération associative (qu’on notera multiplicativement), admettant un élément unité (qu’on notera 1). Le monoïde M peut ou non contenir un élément zéro, noté 0, tel que 0 · x = x · 0 = 0 pour tout x dans M. On note M^{+} l’ensemble des éléments non nuls de M.

On appelle décomposition d’un élément x de M toute suite finie s = (x_{1}, …, x_{q}) d’éléments de M, différents de 0 et de 1, telle que x = x_{1} ⋯ x_{q}. L’entier q s’appelle le degré de la décomposition s. On admet, par convention, une décomposition vide de 1, de degré 0. On dit que le monoïde M est à factorisation finie, si tout élément de M^{+} n’admet qu’un nombre fini de décompositions.

Soit R(M) l’ensemble des fonctions réelles sur M^{+}. On munit R(M) d’une structure d’algèbre associative en posant

(f + g)(x) = f(x) + g(x);
(fg)(x) = ∑_{x_{1}x_{2}=x} f(x_{1})g(x_{2}).

Dans la seconde règle ci-dessus, la sommation est étendue à tous les couples (x_{1}, x_{2}) tels que x_{1}x_{2} = x, en particulier, aux couples (1, x) et (x, 1). On dira encore que R(M) est l’algèbre d’incidence de M. De même, on distingue deux éléments ξ_{M} et ϵ_{M} dans R(M), définis par ξ_{m}(x) = 1 pour tout x dans M^{+} et ϵ_{M}(x) = 1 ou 0 suivant que x = 1 ou x ≠ 0, 1.

3. Formules d’inversion

La formule d’inversion de Möbius dans le cas des ensembles ordonnés est la suivante : soient f et g deux fonctions réelles d’une variable x courant dans un ensemble ordonné P et p un élément de P. Alors les relations suivantes sont équivalentes :

g(x) = ∑_{p≤y≤x} f(y),  pour tout x dans P ;
f(x) = ∑_{p≤y≤x} g(y)μ_{P} (y, x), pour tout x dans P.

Dans le cas des monoïdes à factorisation finie, la formule d’inversion de Möbius est une identité dans l’algèbre d’incidence R(M) du monoïde M (cf. Cartier-Foata (1969), p. 20). Soient f et g deux fonctions réelles sur M^{+}. On a l’équivalence entre les deux formules

g(x) = ∑_{x_{1}x_{2}=x} f(x_{2}),  pour tout x dans M^{+} ;
f(x) = ∑_{x_{1}x_{2}=x} μ_{M}(x_{1})g(x_{2}), pour tout x dans M^{+}.

Un dernier rapprochement entre μ_{P} et μ_{M}. Dans le cas des ensembles ordonnés, on détermine μ_{P} par récurrence au moyen des formules μ_{P} (x, x) = 1 et

μ_{P} (x, y) = − ∑_{x≤z≤y, z≠y} μ_{P} (x, z),

en utilisant le fait qu’il n’y a qu’un ensemble fini de z tels que x ≤ z ≤ y.

Dans le cas des monoïdes, la fonction de Möbius μ_{M} est donnée en chaque point x par l’argument suivant. Pour tout x dans M^{+} on note d_{+}(x) (resp. d_{−}(x)) le nombre de décompositions de x de degré pair (resp. impair). Alors

μ_{M}(x) = d_{+}(x) − d_{−}(x)

pour tout x dans M.

4. Algèbres d’incidence des monoïdes

Voyons maintenant comment le calcul de toute fonction de Möbius d’un ensemble ordonné peut être ramené au calcul d’une fonction de Möbius d’un monoïde à factorisation finie.

Proposition 1. — Soit R(P × P) l’algèbre d’incidence d’un ensemble ordonné localement fini P. Alors il existe un monoïde à factorisation finie M tel que son algèbre d’incidence R(M) soit isomorphie à R(P × P).

Démonstration. — Soit J l’ensemble des couples (x, y) d’éléments de P tels que x ≤ y et x ≠ y. Soient encore deux éléments que nous noterons 0 et 1 n’appartenant pas à P. On munit l’ensemble M = {0, 1} ∪ J d’une structure de monoïde en posant

(∗)

0 · m = m · 0 = 0,  pour tout m dans M;
1 · m = m · 1 = m,  pour tout m dans M^{+} = M \ {0};

et pour (x, y) , (z, t) dans J

(∗∗)  (x, y) · (z, t) = \{ \begin{matrix}(x, t), & si y = z; \\ 0, & sinon. \end{matrix}

La multiplication ainsi définie est évidemment associative. Si (x, y) est dans J, il n’admet qu’un nombre fini de décompositions, puisque le segment [x, y] = {z ∈ P : x ≤ z ≤ y} est fini. Le monoïde M est donc à factorisation finie.

Soit maintenant f ∈ R(P × P). On définit la fonction réelle f_{M} sur M^{+} par les relations

(i)  f_{M}(1) = f(x, x),  pour un élément x quelconque de P ;
(ii)  f_{M}(x, y) = f(x, y),  pour x < y.

Montrons que l’application f ↦ f_{M} est un isomorphisme de R(P × P) sur R(M). Le caractère bijectif de f ↦ f_{M} est évident d’après les relations (i) et (ii) et la relation (f + g)_{M} = f_{M} + g_{M} est triviale. Reste à vérifier : (fg)_{M} = f_{M}g_{M}. Or, pour x < y, on a

(fg)_{M}(x, y) = ∑_{x≤z≤y} f(x, z)g(z, y)

= ∑_{x<z<y} f(x, z)g(z, y) + f(x, x)g(x, y) + f(x, y)g(y, y)

= ∑ f_{M}(x_{1}, y_{1})g_{M}(x_{2}, y_{2}) + f_{M}(1)g_{M}(x, y) + f_{M}(x, y)g_{M}(1),

où la sommation est étendue à l’ensemble des paires de couples (x_{1}, y_{1}), (x_{2}, y_{2}) tels que (x_{1}, y_{1}) · (x_{2}, y_{2}) = (x, y). D’où

(fg)_{M} = (f_{M}g_{M})(x, y).

Enfin, pour tout x dans P,

(fg)_{M}(1) = (fg)(x, x)
= f(x, x)g(x, x) = f_{M}(1)g_{M}(1)
= (f_{M}g_{M})(1).

Corollaire. — Soit M le monoïde associé à l’ensemble ordonné P par les relations (∗) et (∗∗). On a alors

μ_{P} (x, y) = μ_{M}(x, y)

pour tout couple (x, y) tel que x ≤ y.

En effet, μ_{M} est l’image de μ_{P} par l’isomomorphisme f ↦ f_{M}.

5. Algèbres d’incidence des ensembles ordonnés

Réciproquement, on peut ramener le calcul de la fonction de Möbius d’un monoïde à factorisation finie M à celui de la fonction de Möbius d’un ensemble ordonné P. Il y a cependant une restriction à imposer sur le monoïde M. On dit qu’un monoïde M est simplifiable (à droite) si pour x, u, v dans M avec x ≠ 0 on a : [xu = xv] ⇒ [u = v]. Supposons M simplifiable. Si u, x, y sont dans M et si y = xu, l’élément u est défini de façon unique. On peut donc poser

u = y/x et ainsi y = x (y/x).

Compte tenu de cette restriction, on a le résultat suivant.

Proposition 2. — Soit R(M) l’algèbre d’incidence d’un monoïde à factoorisation finie et simplifiable. Alors il existe un ensemble ordonné localement fini P tel que son algèbre d’incidence R(P ×P) soit isomorphe à R(M).

Démonstration. — L’ensemble ordonné P qu’on va associer à M est la paire (M, ≤), où “≤” est l’ordre défini par

x ≤ y si y = xu pour un certain u dans M.

On définit de cette façon un ordre sur M, car si y = xu et y = zv, on a z = xuv; d’où x ≤ y et y ≤ z entraînent x ≤ y. De plus, cet ordre est localement fini, car si l’on a x ≤ y ≤ z, on a aussi z = yv pour un certain v, où encore (y, v) est une décomposition de degré 2 de z. Comme il n’y a qu’un nombre fini de décompositions de z, il n’y a donc qu’un nombre fini d’éléments y satisfaisant à x ≤ y ≤ z. Comme on a supposé M simplifiable, il existe un et un seul élément noté y/x tel que y = x(y/x) lorsque x ≤ y.

Soit f une fonction appartenant à R(M). On pose alors pour x, y dans M

f_{P} (x, y) = \{ \begin{matrix}f(y/x), & si x ≤ y; \\ 0, & sinon. \end{matrix}

Comme précédemment on peut vérifier que f ↦ f_{P} est bijectif et linéaire. Soient f et g deux éléments de R(M). On a pour x ≤ y

(fg)_{P} (x, y) = (fg)(y/x) = ∑_{u_{1}u_{2}=y/x} f(u_{1})g(u_{2})

= ∑_{x≤y≤z} f(z/x)g(y/z)

= ∑_{x≤y≤z} f_{P} (x, z)g_{P} (z, y) = (f_{P} g_{P})(x, y).

La fonction de Möbius μ_{P} de l’ensemble P = (M, ≤) est alors donnée par

μ_{P} (x, y) = μ_{M}(y/x), lorsque x ≤ y.

Bibliographie

Pierre Cartier, Dominique Foata (1969). — Problèmes combinatoires de commutation et réarrangements. — Lecture Notes in Math., no. 85, Springer-Verlag, Berlin. Gian-Carlo Rota (1964). — On the Foundations of Combinatorial Theory I. Theory of Möbius Inversion, Z. Wahrscheinlichkeitstheorie, 2, p. 340–368. Gian-Carlo Rota (1972). — Communication privée. Marcel-Paul Schützenberger (1974). — Communication privée.

Retyped with TEX, December 10, 2005.

Institut Lothaire 1, rue Murner 67000 Strasbourg, France

60 LE POLYNÔME CHROMATIQUE

Bodo LASS

Institut Camille Jordan (UMR 5208 du CNRS) Université Claude Bernard – Lyon 1 Bâtiment Doyen Jean Braconnier (101) 43, Boulevard du 11 Novembre 1918 F-69622 Villeurbanne Cedex

                       Courriel : lass@math.univ-lyon1.fr

Regardons la toute première identité dans Cartier-Foata ([1], p. 1, formule (1)) (ou bien le théorème 2.4, p. 13) et associons un graphe (simple) G = (V, E) à cette identité : chaque sommet v ∈ V correspond à une variable T_{v} et chaque arête {u, v} ∈ E correspond, de façon bijective, à deux variables T_{u}, T_{v} qui ne commutent pas. Par conséquent, les monômes formés de lettres distinctes commutant deux à deux correspondent aux ensembles de sommets qui ne contiennent aucune arête : on les appelle indépendants.

Imposons maintenant les relations supplémentaires T_{v}^{2} = 0 pour tout v ∈ V ainsi que T_{u}T_{v} = T_{v}T_{u} pour toute arète {u, v} ∈ E (pour travailler avec l’algèbre commutative des fonctions d’ensembles ℤ[T_{v}]/⟨T_{v}^{2}⟩, v ∈ V). L’identité (1) devient alors

[1 + ∑_{∅⊂I⊆V, I indépendant} (−1)^{|I|} ∏_{v∈I} T_{v}]^{−1} = 1 + ∑_{∅⊂V′⊆V} a(G[V′]) ∏_{v∈V′} T_{v},

où a(G[V′]) est le nombre d’orientations acycliques du graphe G[V′] qui contient toutes les arêtes ayant leurs deux extrémités dans V′ ⊆ V. En effet, les monômes distincts formés des lettres non-commutatives T_{v}, v ∈ V′, correspondaient aux orientations acycliques du graphe G[V′].

On appelle une coloration des sommets de G régulière si et seulement si les deux extrémités de chaque arête obtiennent des couleurs différentes. Notons χ_{G}(λ) le nombre de ces colorations avec λ couleurs. Puisque χ_{G}(λ) compte les partitions de V en λ ensembles indépendants, nous avons l’identité (voir Tutte [3])

1 + ∑_{∅⊂V′⊆V} χ_{G[V′]}(λ) ∏_{v∈V′} T_{v} = [1 + ∑_{∅⊂I⊆V, I indépendant} ∏_{v∈I} T_{v}]^{λ}

= 1 + ∑_{k=1}^{|V |} \binom{λ}{k}[ ∑_{∅⊂I⊆V, I indépendant} ∏_{v∈I} T_{v}]^{k},

puisque k > |V | implique [∑_{∅⊂I⊆V, I indépendant} ∏_{v∈I} T_{v}]^{k} = 0 dans l’algèbre commutative des fonctions d’ensembles ℤ[T_{v}]/⟨T_{v}^{2}⟩, v ∈ V. En particulier, χ_{G}(λ) est un polynôme : le polynôme chromatique.

En remplaçant chaque variable T_{v} par −T_{v} nous voyons donc que l’identité (1) (ou bien le théorème 2.4) est une généralisation non-commu-tative de l’identité (−1)^{|V |}χ_{G}(−1) = a(G) (voir Stanley [4]).

Une autre généralisation peut être obtenue en associant à chaque arête {u, v} l’hyperplan x_{u} = x_{v} dans l’espace ℝ^{|V |}. Les orientations acycliques de G correspondent alors aux régions de cet arrangement d’hyperplans. En fait, la formule (−1)^{|V |}χ_{G}(−1) = a(G) se généralise non seulement aux arrangements d’hyperplans (voir Winder [4]) mais encore aux matroïdes orientés.

BIBLIOGRAPHIE

[1] Pierre Cartier, Dominique Foata. — Problèmes combinatoires de commutation et réarrangements. — Lecture Notes in Math. 85, Springer-Verlag, Berlin, 1969; electronically reedited 2006.

[2] R. P. Stanley. — Acyclic orientations of graphs, Discrete Math., t. 5, 1973, p. 171-178.

[3] W. T. Tutte. — On dichromatic polynomials, J. Combin. Theory, t. 2, 1967, p. 301-320.

[4] R. O. Winder. — Partitions of N-space by hyperplanes, SIAM J. Appl. Math., t. 14, 1966, p. 811-818.