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 Advisers : P. A. Meyer and M. Karoubi

138

Dominique Foata

Université de Strasbourg

Marcel-P. Schützenberger

Université de Paris

Théorie Géométrique des Polynômes Eulériens

Springer-Verlag Berlin · Heidelberg · New York 1970

1

TABLE DES MATIÈRES

CHAPITRE 0. Introduction et historique des nombres d’Euler .. 1
1. Bref historique sur les nombres d’Euler ........................ 1
2. Résumé du mémoire ............................................. 2

CHAPITRE PREMIER. Propriétés générales des systèmes d’excédances et de montées ............................................. 5

1. Excédances ....................................................... 5
2. Descentes et montées ............................................ 6
3. La transformation fondamentale ................................ 7
4. Relations entre les excédances et les descentes ................. 8
5. Applications aux permutations alternées ....................... 9
6. Relations entre les excédances et les montées .................. 10
7. Relations avec les permutations circulaires ..................... 11
8. Tableau des bijections utilisées ................................. 12
9. Notations générales .............................................. 12
CHAPITRE 2. Les polynômes eulériens .............................. 14
1. Interprétation des polynômes eulériens ......................... 14
2. Propriétés de symétrie .......................................... 15
3. Relations de récurrence ......................................... 16
4. Relations avec le ^{⟨⟨}problème de Simon Newcomb^{⟩⟩}............. 17
5. Relations avec les nombres de Stirling .......................... 18
6. Les identités de Worpitzky ...................................... 19
7. Table des polynômes eulériens .................................. 21
CHAPITRE 3. La formule exponentielle .............................. 23
1. La formule de Hurwitz .......................................... 23
2. Le composé partitionnel ......................................... 24
3. Une formule d’inversion pour les séries exponentielles ......... 26
4. Le composé partitionnel des applications ...................... 27
5. Applications ..................................................... 29
6. Une identité entre déterminants et permanents ................ 30
CHAPITRE 4. Fonctions génératrices polynômes eulériens ....... 32
1. Fonction génératrice exponentielle de ^{0}A_{n}(t), A_{n}(t) et B_{n}(t) . 32
2. Fonction génératrice exponentielle des polynômes ^{r}A_{n}(t) ...... 34
3. Autres interprétations des polynômes eulériens ................ 36

CHAPITRE 5. Les sommes alternées A_{n}(−1) et B_{n}(−1) ............ 38
1. Distribution du nombre des descentes sur 𝔖′_{n} ................. 38
2. Applications aux polynômes eulériens .......................... 40
3. Applications aux polynômes B_{n}(t) ............................. 40
4. Les développements de tg u et de 1/ cos u ...................... 42
5. Table des nombres d’Euler ...................................... 43
Bibliographie ............................................................ 46

CHAPITRE 0

INTRODUCTION ET HISTORIQUE DES NOMBRES D’EULER

1. Bref historique sur les nombres d’Euler

On sait depuis Euler que la relation

∑_{n≥0} A_{n}(t)\frac{u^{n}}{n!} = \frac{1 − t}{−t + exp(u(t − 1))}  (1)

définit des polynômes symétriques

A_{0}(t) = 1 et A_{n}(t) = t^{n−1}A_{n}(t^{−1}) = ∑_{0≤k≤n−1} A_{n,k}t^{k} (n ≥ 1),

de degré (n − 1), dont les coefficents A_{n,k} sont des entiers positifs de somme A_{n}(1) = n!

Worpitzky [31] a donné la formule

x^{n} = ∑_{0≤k≤n−1} A_{n,k}\binom{x + k}{n}  (2)

et Frobenius [13], qui a appelé les A_{n}(t) polynômes eulériens, a indiqué l’identité

A_{n}(t) = ∑_{0≤k≤n−1}(n − k)! (t − 1)^{k}S(n, n − k),  (3)

dans laquelle S(n, j) désigne le nombre de Stirling de seconde espèce, c’està-dire le nombre de partitions en j classes d’un ensemble de n éléments. Une bibliographie de cette question a été rassemblée par Carlitz [4].

De par ailleurs, les polynômes eulériens apparaissent dans divers problèmes d’énumération concernant le groupe symétrique 𝔖_{n} sur l’ensemble totalement ordonné [ n] = {1, 2, …, n} (= ∅ pour n = 0). Ainsi, d’après (1) la somme alternée (−1)^{p−1}A_{2p−1}(−1) est le coefficient de u^{2p−1}/(2p − 1)! dans le développement de tg u (voir chapitre V § 4 du présent article) et Désiré André [1], [2] (voir aussi [21], chap. 4) a découvert que ce dernier nombre est celui des permutations σ ∈ 𝔖_{2p−1} qui sont alternées, c’est-à-dire telles que pour chaque j ∈ [p − 1], on ait à la fois σ(2j) < σ(2j − 1) et σ(2j) < σ(2j + 1).

2 CHAPITRE 0 : INTRODUCTION ET HISTORIQUE DES NOMBRES D’EULER

MacMahon (19] a étudié le nombre A′_{n,k} des permutations σ ∈ 𝔖_{n} telles que j < σ(j) pour exactement k éléments j ∈ [ n] et en application de son ⟨⟨Master Theorem^{⟩⟩}, il a montré que A′_{n,k} est aussi le nombre des σ ∈ 𝔖_{n} qui possèdent k montées, c’est-à-dire qui satisfont à σ(j) < σ(j + 1) pour exactement k valeurs j ∈ [ n − 1 ]. Carlitz et Riordan [7] on reconnu que les A′_{n,k} sont précisément les ceofficients des polynômes eulériens et Riordan a généralisé ceux-ci au moyen de sa théorie des ^{⟨⟨}rook polynomials^{⟩⟩}. Appelons r-excédance de σ ∈ 𝔖_{n} tout j ∈ [ n] tel que j + r ≤ σ(j) (0 ≤ r) et soit rA_{n,k} le nombre des σ ∈ 𝔖_{n} ayant k r-excédances (^{1}A_{n,k} = A_{n,k}) ; Riordan, dans le dernier chapitre de son livre [20], considère avec des notations un peu différentes les polynômes

rA_{n}(t) = ∑_{0≤k}^{r}A_{n,k} t^{k}  (4)

et à leur sujet établit des extensions des formules (1) et (3). D’autres généralisations sont dues à Carlitz et son école ([5], [8], [10]).

Soit |Δ′Mσ| le nombre des montées de σ ∈ 𝔖_{n}. Roselle [25] a calculé le polynôme B_{n}(t) défini comme la somme de t^{|Δ′Mσ|} étendue au sousensemble G_{n} des σ ∈ 𝔖_{n} tels que 1 ≠ σ(1) et 1+σ(j) ≠ σ(j +1) pour chaque j ∈ [ n − 1 ]. Il note que B_{n}(1) est le nombre de permutations sans points fixes de 𝔖_{n} et il constate que la somme alternée (−1)^{p}B_{2p}(−1) est égale au coefficient de u^{2p}/(2p)! dans le développement de 1/ cos u, c’est-à-dire au 2p^{ième} nombre d’Euler. Or, on sait depuis longtemps que ce coefficient est le nombre des σ ∈ 𝔖_{2p} tels que σ(2p − 1) < 2p et σ(2j − 1) < σ(2j) > σ(2j + 1) (j ∈ [p − 1]) ([1], [14]), ceci étant d’ailleurs un cas particulier d’une formule plus générale due à Entringer [11] et dans une direction assez différente de la théorie des ^{⟨⟨}runs up and down^{⟩⟩} développée par David et Barton à des fins statistiques [3].

Enfin, dans la théorie dite du ^{⟨⟨}problème de Newcomb^{⟩⟩}, on considère au lieu de l’ensemble ordonné [ n] un ensemble préordonné quelconque X. Les énoncés y dépendent donc de façon cruciale de la structure de X, ce qui conduit à une problématique sensiblement différente, sauf si l’on réintroduit des hypothèses particulières sur X comme par exemple dans le cas des polynômes de Shanks [27], des polynômes de Poussin [22] ou dans celui de la ⟨⟨spécification (1^{r}(n − r))^{⟩⟩} qui fait apparaître directement les entiers ^{r}A_{n,k}. Hormis ce dernier cas, nous avons entièrement laissé de côté le problème de Newcomb qui nous eût entraîné fort loin des polynômes eulériens. Au demeurant, les mêmes techniques de base ont été employées récemment par l’un de nous [9] pour traiter le cas général et certaines de ses applications.

2. Résumé du mémoire

Les théorèmes qui viennent d’être rappelés ont été, en règle générale, établis en utilisant conjointement quelques propriétés géométriques (^{⟨⟨}combinatoires^{⟩⟩}) des permutations et les méthodes plus expéditives du calcul différentiel et intégral. En particulier, aucune connexion sauf la coïncidence de l’aboutissement de deux séries de calculs ne semble avoir été vue entre les sommes alternées A_{n}(−1) et B_{n}(−1) et la signification des polynômes A_{n}(t) et B_{n}(t) en termes d’excédances ou de montées.

Le but du présent mémoire est au contraire de développer la théorie géométrique sous-jacente et c’est de façon subsidiaire que nous en déduisons des identités entre séries ou polynômes. Nous nous sommes cependant attachés à toujours retrouver les résultats classiques. Dans de nombreux cas, cette approche évacue pratiquement tous les calculs : c’est ce qui se produit par exemple en ce qui concerne les formules reliant les polynômes eulériens et les nombres de Stirling. Dans d’autres cas, nous obtenons des séries d’identités nouvelles (par exemple les ^{⟨⟨}formules sommatoires^{⟩⟩} généralisant celle de Worpitzky données dans la section 6 du chapitre II ou le théorème 5.6). Les méthodes du chapitre III contiennent implicitement l’énumération du nombre des excédances pour les permutations dont les longueurs des cycles satisfont à des conditions de divisibilité données.

Plus important nous semble la démonstration du fait que toutes les identités classiques concernant les polynômes eulériens sont seulement la traduction de propriétés très simples des morphismes d’ensembles totalement ordonnés finis. Pour l’essentiel, elles dérivent soit de méthodes élémentaires courantes comme l’inversion de Möbius ou la formule exponentielle, soit d’une opération unique nouvelle σ ↦ σ̂ appelée ici transformation fondamentale, déjà introduite par l’un de nous [12] dans le cadre général du problème de Newcomb. Simultanément, les énoncés que nous proposons, expriment, en règle, des bijections entre ensembles. Ils sont donc plus riches que les identités énumératives classiques auxquelles ils se réduisent quand, en fin de calcul, on substitue à ces ensembles le nombre de leurs éléments.

Le chapitre I est consacré à l’étude détaillée des propriétés de la transformation fondamentale. Celle-ci est une bijection de 𝔖_{n} sur lui-même ayant la propriété que l’ensemble des ^{⟨⟨}excédances^{⟩⟩} de σ est envoyé, de façon biunivoque, sur celui des ^{⟨⟨}descentes^{⟩⟩} de σ̂. Elle permet ici d’établir que la distribution du nombre des excédances sur les permutations de 𝔖_{n} est la même que sur le sous-ensemble C_{n+1} des permutations circulaires de 𝔖_{n+1}. Ce résultat est étendu dans le paragraphe 4, où nous employons les bi-excédances (c’està-dire les j ∈ [ n] tels que j soit à la fois strictement plus petit que σ(j) et que σ^{−1}(j)) et les creux (c’est-à-dire les j ∈ [ n] tels que j soit à la fois strictement plus petit que σ(j − 1) et que σ(j + 1)) pour étudier les sommes alternées. Cette dualité pourrait être étendue à des constructions plus complexes sur lesquelles nous reviendrons peut-être dans un autre travail.

Dans le chapitre II, nous retrouvons et généralisons diverses formules de récurrence de Riordan et l’identité de Worpitzky, en application des résultats précédents et de la considérations des morphismes [ n] → [m], c’est-à-dire, puisque [ n] et [m] sont des ensembles totalement ordonnés des applications ϕ : [ n] → [m] telles que i ≤ j implique ϕ(i) ≤ ϕ(j).

Dans le chapitre III, nous croyons utile de donner d’abord une théorie systématique de la formule exponentielle classique de Cauchy exprimant le groupe symétrique en fonction des permutations circulaires. Cette formule est un cas particulier d’une constructuon très générale permettant de ramener divers problèmes d’énumération à un problème analogue sur une sous-famille ⟨⟨génératrice^{⟩⟩} constituée par des objets ^{⟨⟨}connexes^{⟩⟩}. Afin de clarifier ces notions, nous donnons quelques énoncés sous une forme qui permettrait de traiter les énumérations d’arborescences. Retournant aux permutations, une application de cette formule et des résultats du chapitre I nous permet d’obtenir dans le chapitre IV la fonction génératrice exponentielle du nombre des r-excédances pour les permutations ayant une composition en cycles donnée.

Dans le chapitre V, nous établissons un théorème sur la distribution du nombre des montées pour les permutations ayant un nombre de creux fixé. De façon plus explicite, soit 𝔖′_{n,k} l’ensemble des permutations σ ∈ 𝔖_{n} ayant k creux et telles que σ(1) = n (2 ≤ 2k ≤ n) ; alors le nombre de σ ∈ 𝔖′_{n,k} ayant j montées est donné par le coefficient binomial \binom{n−2k}{j} (0 ≤ j ≤ n−2k). Nous déduisons de ce résultat les expressions des sommes alternées A_{n}(−1) et B_{n}(−1) en fonction du nombre des permutations alternées. En particulier, les développements de tg u et 1/ cos u sont obtenus sans calcul à partir de l’expression des fonctions génératrices exponentielles des polynômes A_{n}(t) et B_{n}(t) données dans le chapitre IV.

Dans tout ce travail, étant donnés deux ensembles A et B finis et une application ϕ : A → B, nous appellerons ensemble pondéré l’application ϕ^{#} : B → ℕ définie pour chaque b ∈ B par ϕ^{#}(b) = card ϕ^{−1}(b). Par abus de notation, on désignera par ϕA l’ensemble pondéré ϕ^{#} et il sera commode d’identifier ϕA et ϕ^{#} à l’élément ∑{ϕ^{#}(b) : b ∈ B} du ℚ-module libre de base B.

Nous sommes reconnaissants au professeur J. Riordan de nous avoir fait bénéficier de ses conseils et de son érudition. La dactylographie de ce mémoire est due à Mlle Cler, du département de mathématique de Strasbourg, que nous tenons à remercier.

CHAPITRE PREMIER

PROPRIÉTÉS GÉNÉRALES DES SYSTÈMES D’EXCÉDANCES ET DE MONTÉES

1. Excédances

Dans tout ce chapitre, nous utilisons la notation x_{+} pour désigner la partie positive x_{+} = max{0, x} de tout x ∈ ℤ et pour σ ∈ 𝔖_{n}, nous désignons par σw le n-uple (ou vecteur) (σ(1), σ(2), …, σ(n)) ∈ ℕ^{n}. Par conséquent, σw = ∅ pour n = 0.

Définition 1.1. — Pour σ ∈ 𝔖_{n}, le système des 0-excédances de σ est le n-uple Eσ = (Eσ(1), Eσ(2), …, Eσ(n)) ∈ ℕ^{n}, où pour chaque k ∈ [ n], on pose

Eσ(k) = (σ(k) − (k − 1))_{+} .

Par exemple, avec n = 6 et σw = (6, 4, 1, 2, 5, 3), on a Eσ = ((6−0)_{+}, (4−1)_{+}, (1−2)_{+}, (2−3)_{+}, (5−4)_{+}, (3−5)_{+}) = (6, 3, 0, 0, 1, 0).

Définition 1.2. — Quelque soit l’entier p ≥ 1, on note Δ, Δ′ et Δ′′ les applications de ℕ^{p} dans ℕ^{p−1} envoyant respectivement chaque vecteur x = (x_{1}, x_{2}, …, x_{p}) ∈ ℕ^{p} sur

Δx = ((x_{1} − 1)_{+}, (x_{2} − 1)_{+}, …, (x_{p−1} − 1)_{+});
Δ′x = (x_{2}, x_{3}, …, x_{p});
Δ′′x = (x_{1}, x_{2}, …, x_{p−1}).

Il est immédiat que les trois opérateurs Δ, Δ′′, Δ′′ ainsi définis commutent deux à deux. Prenant le même exemple que ci-dessus, on obtient : Eσ = (6, 3, 0, 0, 1, 0) (= Δ^{0}Eσ = Δ^{′0}Eσ = Δ^{′′0}Eσ) ; ΔEσ = (5, 2, 0, 0, 0) ; Δ′Eσ = (3, 0, 0, 1, 0) ; Δ′′Eσ = (6, 3, 0, 0, 1) ; Δ^{2}Eσ = (4, 1, 0, 0) ; ΔΔ′Eσ = Δ′ΔEσ = (2, 0, 0, 0) ; Δ^{′2}Eσ = (0, 0, 1, 0), etc.

On notera que ΔEσ est simplement la suite

((σ(1) − 1)_{+}, (σ(2) − 2)_{+}, …, (σ(n − 1) − (n − 1))_{+})

et que plus généralement le vecteur Δ^{r}E décrit les r-excdances de σ mentionnées dans l’introduction. L’une des raisons motivant l’introduction de Δ′ est contenu dans le lemme 1.4 ci-dessous. L’opérateur Δ′′ permettra dans le deuxième chapitre de formuler une intéressante propriété de symétrie des polynômes eulériens (propriété 2.3).

6 CHAPITRE PREMIER : SYSTÈMES D’EXCÉDANCES ET DE MONTÉES

Remarque 1.3. — Pour σ ∈ 𝔖_{n} et k ∈ [ n], on a Eσ(k) = 1 si et seulement si (σ(k) − k + 1)_{+} = 1, c’est-à-dire si k = σ(k) est un point fixe de σ.

Lemme 1.4. — Soit ζ ∈ 𝔖_{n} la permutation circulaire envoyant n sur 1 et chaque k ≤ n − 1 sur k + 1 ou encore la permutation définie par ζw = (2, 3, …, n, 1). Pour chaque r ≥ 0 et chaque σ ∈ 𝔖_{n} on a

Δ^{′r}Eσ = Δ^{r}Eσζ^{r}.

Démonstration. — Posons σ′ = σζ^{r}. Pour chaque k ∈ [n−r], on a σ′(k) = σ(r + k). Donc on obtient Δ^{′r}Eσ(k) = Eσ(r + k) = (σ(r + k) + 1 − r − k)_{+} = (σ′(k) + 1 − k − r)_{+} = ((σ′(k) + 1 − k)_{+} − r)_{+} = Δ^{r}Eσ′(k).

Ce simple résultat a la conséquence immédiate suivante qui nous servira fréquemment par la suite.

Théorème 1.5. — Quelque soit le monôme Γ de degré r ≥ 0 en les applications Δ et Δ′, les ensembles pondérés Δ^{r}E𝔖_{n}, Δ^{′r}E𝔖_{n} et ΓE𝔖_{n} sont égaux.

Démonstration. — Puisque σ ↦ σζ^{r} est une bijection de 𝔖_{n} sur lui-même, l’égalité Δ^{r}E𝔖_{n} = Δ^{′r}E𝔖_{n} résulte immédiatement du lemme 1.4. Comme Δ et Δ′ commutent, on peut écire Γ = Δ^{s}Δ^{′r−s}, d’où ΓE𝔖_{n} = Δ^{r}E𝔖_{n}.

2. Descentes et montées

En parallèle avec les excédances, nous introduisons le système des 0descentes, Dσ, et des 0-montées, Mσ, de σ ∈ 𝔖_{n} par la définition suivante, dans laquelle on convient que σ(0) = σ^{−1}(0) = σ(n + 1) = 0.

Définition 1.6. — Pour σ ∈ 𝔖_{n}, on pose

Dσ = (Dσ(1), Dσ(2), …, Dσ(n)) ∈ ℕ^{n};
Mσ = (Mσ(1), Mσ(2), …, Mσ(n)) ∈ ℕ^{n};

où pour chaque k ∈ [ n]

Dσ(k) = (σ(−1 + σ^{−1}(k)) − (k − 1))_{+};
Mσ(k) = (σ(1 + σ^{−1}(k − 1)) − (k − 1))_{+}.

Par exemple, prenant encore σw = (6, 4, 1, 2, 5, 3), on obtient Dσ = ((4−0)_{+}, (1−1)_{+}, (5−2)_{+}, (6−3)_{+}, (2−4)_{+}, (0−5)_{+}) = (4, 0, 3, 3, 0, 0) Mσ = ((6−0)_{+}, (2−1)_{+}, (5−2)_{+}, (0−3)_{+}, (1−4)_{+}, (3−5)_{+}) = (6, 1, 3, 0, 0, 0).

Par construction, tous les termes de Dσ sont nuls ou supérieurs ou égaux à 2. D’autre part, Dσ(n) est toujours nul. Par conséquent, Dσ et ΔDσ ont le même nombre de termes (strictement) positifs. Il est clair que Δ^{r}Dσ et Δ^{r−1}Mσ décrivent les différences supérieures ou égales à r (r ≥ 1) entre termes consécutifs de σw, la connexion entre D et M étant explicitée dans le lemme 1.7 ci-dessous. Il est encore utile de noter que les termes positifs de Δ^{′r}Dσ (ou de Δ^{′r}ΔDσ) correspondent aux paires (j − 1, j) (0 ≤ j − 1) telles que σ(j − 1) > σ(j) > r.

Lemme 1.7. — Soit σ ↦ σ̃ la bijection de 𝔖_{n} sur lui-même définie par l’identité σ̃(k) = σ(n + 1 − k) (k ∈ [ n]). On a Mσ̃(1) = σ(n) et Mσ̃(k + 1) = ΔDσ(k) pour chaque k ∈ [n − 1].

Démonstration. — Par définition Mσ̃(1) = (σ̃(1) − 0)_{+} = σ̃(1) et σ̃(1) = σ(n + 1 − 1) = σ(n). Soit k = σ̃(j) avec k ∈ [n − 1] ; on a alors σ̃^{−1}(k) = j et σ(n + 1 − j) = k. D’où il vient

Mσ̃(k + 1)=(σ̃(1 + j) − k)_{+} =(σ(n − j) − k)_{+} =(σ(−1 + (n + 1 − j)) − k)_{+}
=(σ(−1 + σ^{−1}(k)) − (k − 1) − 1)_{+} =ΔDσ(k).

Prenant σ comme dans l’exemple ci-dessus, on trouve ΔDσ = (3, 0, 2, 2, 0), σ̃w = (3, 5, 2, 1, 4, 6) et Mσ̃ = (3, 3, 0, 2, 2, 0). La construction d’une bijection reliant E et M est l’objet des sections suivantes.

3. La transformation fondamentale

Étant donnée une permutation σ ∈ 𝔖_{n}, l’ensemble σ^{∗}(k)={σ^{p}(k) : p ∈ ℕ} est l’orbite contenant k (k ∈ [ n]). On note z(σ) le nombre des orbites de σ ou, de façon équivalente, le nombre de cycles de σ. A chaque k ∈ [ n], nous attachons la paire Π_{σ}(k) = (\overline{k}, q_{k}), où \overline{k} est l’élément maximum de l’orbite σ^{∗}(k) et où q_{k} = min\{p ∈ ℕ : σ^{p} = \overline{k}\}.

Définition 1.8. — Pour σ ∈ 𝔖_{n} on désigne par σ̂ la permutation telle que pour chaque k la paire Π_{σ}(σ̂(k)) est le k^{ième} terme de la suite (Π_{σ}(j))_{(j∈[ n])} ordonnée par ordre lexicographique.

Par exemple, en prenant encore σw =(6, 4, 1, 2, 5, 3), on a z(σ)=3, les trois orbites étant {4, 2}, le point fixe {5} et {6, 3, 1}. Comme 4 = σ^{0}(4) = σ^{1}(2), puis 5 = σ^{0}(5) et enfin 6 = σ^{0}(6) = σ^{1}(1) = σ^{2}(3), la suite des Π_{σ}(j), ordonnée suivant l’ordre lexicographique, est

((4, 0), (4, 1), (5, 0), (6, 0), (6, 1), (6, 2)), d’où σ̂w = (4, 2, 5, 6, 1, 3).

Rappelons qu’un élément x_{k} d’une suite (x_{1}, x_{2}, …, x_{n}) ∈ ℕ^{n} est dit saillant si et seulement s’il n’existe aucun élément d’indice inférieur qui soit supérieur ou égal à lui, c’est-à-dire si l’on a x_{k′} < x_{k} pour tout k′ < k. Donc par définition x_{1} est toujours saillant.

Lemme 1.9. — L’élément k de [ n] est maximum dans son orbite σ^{∗}(k) (c’est-à-dire Π_{σ}(k) = (k, 0)) si et seulement si k est saillant dans σ̂w. De plus, k est un point fixe de σ si et seulement si k = σ̂(j) avec soit j = n, soit j < n et σ(j + 1) un autre élément saillant de σ̂w.

Démonstration. — Soit Π_{σ}(k) = (\overline{k}, q). Si et seulement si q est différent de 0, l’entier k n’est pas l’élément maximum \overline{k} de son orbite et k n’est pas saillant dans σ̂w puisque Π_{σ}(\overline{k}) = (\overline{k}, 0) précède Π_{σ}(k) dans l’ordre lexicographique, donc \overline{k} précède k dans la suite σ̂w.

Réciproquement, soient q = 0 et σ̂(j) = k. Ou bien on a j = 1 auquel cas k est saillant, ou bien j ≥ 2, auquel cas pour tout j′ < j, l’élément Π_{σ}(σ̂(j′)) est avant l’élément Π_{σ}(σ̂(j)) (= (k, 0)) pour l’ordre lexicographique ; ce qui implique, en posant σ̂(j′) = k′, que l’on a σ̂(j′) = k′ < \overline{k′} < k = σ̂(j) et prouve l’équivalence entre les éléments maximaux des orbites de σ et les éléments saillants de σ̂w.

Supposons maintenant k = \overline{k} = σ̂(j). Si et seulement si k n’est pas un point fixe de σ, il est immédiatement suivi dans σ̂w d’un élément k′ tel que Π_{σ}(k′) = (k, 1). Par conséquent, on a j < n et σ̂(j + 1) = k′ n’est pas saillant.

Dans ce qui suit 𝔖′_{n} désigne l’ensemble des σ ∈ 𝔖_{n} telles que σ(1) = n et C_{n} est le sous-ensemble des permutations circulaires.

Propriété 1.10. — L’application σ ↦ σ̂ est bijective et satisfait à σ(n) = σ̂(n). Sa restriction à C_{n} est une bijection sur 𝔖′_{n}.

Démonstration. — Étant donné τ ∈ 𝔖_{n}, il existe un et un seul σ ∈ 𝔖_{n} tel que τ = σ̂, car d’une part, les éléments saillants de τw livrent les éléments maximaux des orbites de σ d’après le précédent lemme, d’autre part, les restrictions de σ à chacune de ses orbites sont déterminées par la succession même des éléments de τw. Ceci établit le caractère bijectif de σ ↦ σ̂. Comme τ(1) et n sont toujours des éléments saillants de τw, il est clair que z(σ) = 1 si et seulement si τ(1) = n. Enfin, si l’on a k = σ(n), c’est-à-dire n = σ^{−1}(k), l’entier n est l’élément maximum de σ^{∗}(k) et par conséquent, Π_{σ}(k) = (n, q_{k}) est le dernier terme de la suite (Π_{σ}(j))_{(j∈[ n])} ordonnée par ordre lexicographique, c’est-à-dire k = σ̂(n).

4. Relations entre les excédances et les descentes

Nous allons donner une première application de la transformation fondamentale σ ↦ σ̂. Aux 1-excédances de σ correspondent les 1-descentes de σ̂, mais les 0-descentes de σ̂ ne correspondent pas aux 0-excédances de σ. Ceci amène à introduire un vecteur D′σ̂ tel que Dσ̂ + D′σ̂ (= (D + D′)σ̂) rende compte à la fois des descentes et des éléments saillants dans la suite σ̂w et qu’en outre l’identité Eσ = (D + D′)σ̂ soit vérifiée.

Définition 1.11. — Pour τ ∈ 𝔖_{n}, le facteur D′τ est le n-uple

(D′τ(1), …, D′τ(n)) ∈ ℕ^{n},

où pour j ∈ [ n], on pose D′τ(j) = +1 si d’une part, j est saillant et d’autre part, soit j = n, soit j ≤ n − 1 et τ(1 + τ^{−1}(j)) est aussi saillant ; D′τ(j) = 0 dans tous les autres cas.

Théorème 1.12. — On a identiquement

Eσ = (D + D′)σ̂ et ΔEσ = ΔDσ̂.

Démonstration. — Quelque soit τ ∈ 𝔖_{n}, remarquons d’abord que j ≤ n−1 est saillant dans τw seulement si τ^{−1} ≤ n − 1. Nous vérifions le résultat pour chaque k = σ̂(j) ∈ [ n] en posant Π_{σ}(k) = (\overline{k}, q) et en distinguant les cas suivants :

(i) q ≥ 1 ; on a alors σ̂(j − 1) = k′ où Π_{σ}(k′) = (\overline{k}, q − 1), c’est-à-dire k′ = σ^{−(q−1)}(\overline{k}) = σ^{−(q−1)}(σ^{q}(k)) = σ(k). Donc par définition, on a Dσ̂(k) = (k′ − (k − 1))_{+} = (σ(k) − (k − 1))_{+} = Eσ(k) avec Dσ̂(k) = (D + D′)σ̂(k) puisque k n’est pas saillant.

(ii) q = 0, c’est-à-dire k = \overline{k}. On a toujours Dσ̂(k) = 0 car soit j − 1 = 0, soit j − 1 ≥ 1 avec k′ = σ̂(j − 1) appartenant à une orbite dont l’élément maximum est strictement plus petit que k = \overline{k}. D’autre part, Eσ(k) = 0 ou 1 selon que σ(k) ≠ k ou non, car Eσ(k) = (σ(k)−(k−1))_{+} où σ(k) ≤ k puisque k = \overline{k}. D’après la deuxième partie du lemme 1.9 et la définition de D + D′, on a donc Eσ(k) = 1 si et seulement si 1 = (D + D′)σ̂(k) ≠ Dσ̂(k) = 0.

On remarquera que l’on a (D + D′)τ(j) ≠ Dτ(j) si et seulement si Dτ(j) = 0 et (D + D′)τ(j) = 1.

Exemple. — On a vu dans les exemples précédents que si σw = (6, 4, 1, 2, 5, 3), on avait Eσ = (6, 3, 0, 0, 1, 0) et σ̂w = (4, 2, 5, 6, 1, 3). Comme les éléments successifs σ̂(3) = 5 et σ̂(4) = 6 sont saillants dans σ̂w, on a (D + D′)σ̂(5) = 1. Il vient donc (D + D′)σ̂ = (6, 3, 0, 0, 1, 0) = Eσ et aussi ΔDσ̂ = (5, 2, 0, 0, 0) = ΔEσ.

5. Applications aux permutations alternées

Une permutation σ ∈ 𝔖_{n} est alternée si l’on a σ(2j) < σ(2j −1), σ(2j +1) pour tout entier j tel que 1 ≤ 2j ≤ n − 1 et si l’on a encore σ(n) < σ(n − 1) lorsque n est pair. D’autre part, elle est biexcédée si pour tout j ∈ [ n], on a j < σ(j), σ^{−1}(j) ou j > σ(j), σ^{−1}(j). Les ensembles des permutations alternées et biexcédées sont notés respectivelent T_{n} et B_{n}. Nous allons, dans cette section, utiliser la transformation fondamentale pour construire entre T_{n} et B_{n} une bijection qui servira au chapitre V.

Lemme 1.13. — Soit k = σ̂(j) (j ∈ [ n]) ; on a k < σ(k), σ^{−1}(k) si et seulement si j ≠ 1 et soit j ≤ n − 1 et σ̂(j) < σ̂(j − 1), σ̂(j + 1), soit j = n et σ̂(j) < σ̂(j − 1).

Démonstration. — L’hypothèse k < σ(k) entraîne k ≠ k où \overline{k} est le maximum de l’orbite σ^{∗}(k). Donc j ≠ 1 et σ̂(j − 1) = σ(k) entraînant l’équivalence de k < σ(k) et de σ̂(j) < σ̂(j −1), puisque l’on a σ̂(j) > σ̂(j −1) quand k = \overline{k}. Distinguons deux cas selon que j = n ou non.

Si j = n, on a σ^{−1}(k) = \overline{k} = n, donc k < σ^{−1}(k) et le résultat est prouvé. Si j ≠ n, ou bien σ^{−1}(k) = \overline{k}, auquel cas l’hypothèse k < σ^{−1}(k) équivaut à k = σ̂(j) < σ̂(j + 1), puisque σ̂(j + 1) est le maximum d’une autre orbite ; ou bien σ^{−1}(k) ≠ \overline{k}, auquel cas σ̂(j + 1) = σ^{−1}(k) et k < σ^{−1}(k) équivaut à σ̂(j) < σ̂(j + 1).

Proposition 1.14. — Toute permutation σ ∈ B_{n} a tous ses cycles de longueur paire ; donc B_{n} = ∅ si n est impair. La transformation fondamentale σ ↦ σ̂ établit, lorsque n est pair, une bijection de B_{n} sur T_{n}.

Démonstration. — Dire que σ est biexcédée équivaut à dire que dans toute orbite de σ, d’élément maximum \overline{k}, on a identiquement σ^{2p+1}(\overline{k}) < σ^{2p}(\overline{k}), σ^{2p+2}(\overline{k}) (0 ≤ p). Ces inégalités impliquent d’abord que l’orbite n’est pas réduite à un seul élément ; supposons maintenant qu’elle ait un nombre impair d’éléments, disons 2q+1 (avec q ≥ 1). Ces même inégalités appliquées à p = q entraînent que l’on a \overline{k} = σ^{2q+1}(\overline{k}) < σ^{2q}(\overline{k}), ce qui est impossible puisque \overline{k} est l’élément maximum dans son orbite. La permutation σ n’a donc que des cycles de longueur paire et par conséquent B_{n} = ∅ si n est impair.

La dernière partie de la proposition résulte du lemme 1.13 et des deux équivalences suivantes, qui découlent immédiatement de ce qui précède :

(i) σ est dans B_{2p} si et seulement si les inégalités k < σ(k), σ^{−1}(k) sont satisfaites pour exactement p indices k;

(ii) τ est dans T_{2p} si et seulement si, en posant τ(2p + 1) = 2p + 1, les inégalités τ(j) < τ(j − 1), τ(j + 1) sont vraies pour exactement p indices j ≥ 2.

Exemple. — Nous donnons ci-dessous le tableau des cinq permutations biexcédées de 𝔖_{4} et en face de chacune d’elles, la permutation alternée qui lui correspond par l’application fondamentale.

i = 1 2 3 4 1 2 3 4 = i
σ(i) = 2 1 4 3 2 1 4 3 = σ̂(i)
3 4 1 2 3 1 4 2
B_{4} 4 3 2 1 3 2 4 1 T_{4}
4 3 1 2 4 1 3 2
3 4 2 1 4 2 3 1

4. Relations entre les excédances et les montées

Toujours au moyen de la transformation fondamentale, nous construisons une bijection σ ↦ \overline{σ} telle que Eσ = M\overline{σ}. Soit en effet σ ∈ 𝔖_{n} et notons ζ la permutation circulaire définie dans le lemme 1.4 (ζw = (2, 3, …, n, 1)). On pose successivement

σ_{1} = σ ζ;
puis  σ_{2} = σ̂_{1} (transformation fondamentale);
et enfin  \overline{σ} = σ̃_{2} (où ˜ est défini dans le lemme 1.7).

Théorème 1.15. — L’application σ ↦ \overline{σ} est une bijection de 𝔖_{n} sur lui-même satisfaisant à Eσ = M\overline{σ}.

Démonstration. — Le caractère bijectif est évident d’après ce qui précède. Ensuite, on a Eσ(1) = σ(1) = σ_{1}(n) et on vérifie que Eσ(j + 1) = ΔEσ_{1}(j) pour chaque j ∈ [n − 1]. D’après la propriété 1.10, on a σ_{2}(n) = σ_{1}(n) et d’après le théorème 1.12, il vient ΔEσ_{1} = ΔDσ_{2}. Par conséquent, en utilisant le lemme 1.7, on a bien Eσ = M\overline{σ}.

Par exemple, partant de σw = (6, 4, 1, 2, 5, 3), on a Eσ = (6, 3, 0, 0, 1, 0), puis σ_{1}w = (4, 1, 2, 5, 3, 6) et σ_{2}w = (5, 4, 1, 2, 3, 6) ; enfin \overline{σ}w = (6, 3, 2, 1, 4, 5). Comme on a ΔEσ_{1} = ΔDσ_{2} = (3, 0, 0, 1, 0), on vérifie bien que M\overline{σ} = Eσ.

On a noté que Eσ(k) = 1 si et seulement si σ(k) = k. Par conséquent, la restriction de σ ↦ \overline{σ} au sous ensemble D_{n} des permutations sans points fixes est une bijection sur le sous-ensemble des \overline{σ} ∈ 𝔖_{n} telles que M\overline{σ}(j) ≠ 1, c’est-à-dire des \overline{σ} telles que \overline{σ}(1) ≠ 1 et 1 + \overline{σ}(j) ≠ \overline{σ}(j + 1), pour chaque j ∈ [n − 1]. L’ensemble de ces permutations \overline{σ} n’est autre que la classe, que nous noterons G_{n}, des permutations sans successions. On a ainsi le corollaire suivant.

Corollaire 1.16. — La restriction de σ ↦ \overline{σ} à l’ensemble D_{n} des permutations sans points fixes est une bijection sur l’ensemble G_{n} des permutations sans successions telle que Eσ = M\overline{σ}.

7. Relations avec les permutations circulaires

Pour terminer ce chapitre, il nous reste à étudier la distribution des vecteurs-excédances sur l’ensemble C_{n}. Combinant d’abord les résultats de la propriété 1.10 et du théorème 1.12, nous avons déjà la propriété suivante.

Propriété 1.17. — La restriction de la transformation fondamentale σ ↦ σ̂ à l’ensemble C_{n} est une bijection sur 𝔖′_{n} telle que ΔEσ = ΔDσ̂.

Nous construisons ensuite une bijection σ ↦ σ′ de

𝔖′′_{n} = {σ ∈ 𝔖_{n} : σ(1) = 1}

sur 𝔖′_{n} telle que ΔEσ = ΔDσ′. Si σ est dans 𝔖′′_{n}, on pose i = σ̂^{−1}(n) et σ′ est défini comme l’unique permutation telle que

σ′w = (σ̂(i), σ̂(i + 1), …, σ̂(n), σ̂(1), …, σ̂(i − 1)).

Lemme 1.18. — L’application σ ↦ σ′ est une bijection de 𝔖′′_{n} sur 𝔖′_{n} satisfaisant à ΔEσ = ΔDσ′.

Démonstration. — D’après la propriété 1.10, on a σ(n) = σ̂(n) et par conséquent σ̂ est dans 𝔖′′_{n}. Il est clair que σ ↦ σ′ est bijectif. En outre, ΔEσ = ΔDσ̂ d’après le théorème 1.12. Il suffit donc de vérifier ΔDσ′(k) = ΔDσ̂(k) pour chaque k ∈ [ n].

Distinguons d’abord deux cas particuliers :

(i) k = σ̂(1). On a k = σ′(n − i + 2) avec σ′(n − i + 1) = σ̂(n) = 1. Donc ΔDσ̂(k) = (0 − k)_{+} et ΔDσ′(k) = (1 − k)_{+} sont nuls.

(ii) k = σ̂(i) = n. On a encore ΔDσ̂(k) = (σ̂(i − 1) − n)_{+} = 0 et aussi, puisque n = σ′(1), l’égalité ΔDσ′(k) = (0 − n)_{+} = 0.

Dans le cas général où k = σ̂(j + 1) ≠ n (j ∈ [n − 1]), on a k = σ′(j′ + 1) avec j′ = j − i + 1 ou n + j − i + 1 selon que j ≥ 1 ou non. Dans les deux cas, on a σ̂(j) = σ′(j′) et par conséquent, (σ̂(j) − k)_{+} est la valeur commune de ΔDσ̂(k) et ΔDσ′(k).

Ce lemme permet la construction suivante : soit σ ∈ 𝔖_{n−1} ; on définit σ_{1} ∈ 𝔖′′_{n} en posant

σ_{1}(n) = 1 et σ_{1}(k) = 1 + σ(k) pour chaque k ∈ [n − 1] ; puis
σ_{2} = σ′_{1}, où τ ↦ τ′ est la bijection définie dans le lemme 1.18 ; enfin
σ′′ est la permutation définie per σ̂′′ = σ_{2}.

Théorème 1.19. — L’application σ ↦ σ′′ est une bijection de 𝔖_{n−1} sur C_{n} telle que Eσ = ΔEσ′′.

Démonstration. — Tout d’abord la bijectivité de σ ↦ σ′′ est évidente. Si σ est dans 𝔖_{n−1}, on a ensuite σ_{1} ∈ 𝔖′′_{n} et Eσ(k) = (σ(k) − (k − 1))_{+} = (σ_{1}(k)−k)_{+} = ΔEσ_{1}(k) pour chaque k ∈ [n−1], d’où il résulte Eσ = ΔEσ_{1}. D’autre part, d’après le lemme 1.18, on a σ_{2} ∈ 𝔖′_{n} et Eσ = ΔEσ_{1} = ΔDσ_{2}. Enfin, en vertu de σ_{2} ∈ 𝔖′_{n}, la propriété 1.17 montre que l’on a σ′′ ∈ C_{n} et ΔEσ′′ = ΔDσ_{2}.

8. Tableau des bijection utilisées

Il paraît intéressant de rappeler les propriétés des bijections construites dans le premier chapitre et d’indiquer leur référence.

La bijection envoie sur  a la propriété  et la référence
σ ↦ σζ^{r} 𝔖_{n} 𝔖_{n}  Δ^{′r}Eσ = Δ^{r}Eσζ^{r} (r ≥ 0)  Lemme 1.4
σ ↦ σ̃  𝔖_{n} 𝔖_{n}  Mσ̃(1) = σ(n) et  Lemme 1.7

Mσ̃(k + 1)=ΔDσ(k) (k ∈[n − 1])

σ ↦ σ̂  𝔖_{n} 𝔖_{n}  Définition 1.8
C_{n} 𝔖′_{n}  Proposition 1.10
𝔖_{n} 𝔖_{n} Eσ = (D + D′)σ̂, ΔEσ = ΔDσ̂ Théorème 1.12
B_{2n} T_{2n}  Proposition 1.14
σ ↦ \overline{σ}  𝔖_{n} 𝔖_{n}  Eσ = M\overline{σ}  Théorème 1.15
D_{n} G_{n}  Corollaire 1.16
σ ↦ σ′  𝔖′′_{n} 𝔖′_{n}  ΔEσ = ΔDσ′  Lemme 1.18
σ ↦ σ′′ 𝔖_{n−1} C_{n}  Eσ = ΔEσ′′  Théorème 1.19

9. Notations générales

Nous réunissons dans cette section toutes les notations utilisées pour les sur- et les sous-ensembles de 𝔖_{n}. Pour n ≥ 1 et 1 ≤ k, r ≤ n, on considère les sous-ensembles suivants de 𝔖_{n} :

C_{n} l’ensemble des permutations circulaires ; (C_{0} = ∅) ; G_{n} l’ensemble des permutations sans successions, c’est-à-dire des σ ∈ 𝔖_{n}

telles que 1 ≠ σ(1) et 1 + σ(j) ≠ σ(j + 1) pour j ∈ [n − 1] ; D_{n} l’ensemble des permutations sans points fixes ; T_{n} l’ensemble des permutations alternées, c’est-à-dire des σ ∈ 𝔖_{n} telles que

σ(2j) < σ(2j − 1), σ(2j + 1) pour tout entier j tel que 2 ≤ 2j ≤ n − 1 et en plus si n est pair, telles que σ(n) < σ(n − 1) ;

B_{n} l’ensemble des permutations biexcédées, c’est-à-dire des σ ∈ 𝔖_{n} telles

que pour chaque j ∈ [ n], on ait j < σ(j), σ^{−1}(j) ou j > σ(j), σ^{−1}(j) ; 𝔖_{n,k} l’ensemble des permutations σ ∈ 𝔖_{n} telles que σ(1) = k; 𝔖′_{n} = 𝔖_{n,n}; 𝔖′′_{n} l’ensemble des permutations σ ∈ 𝔖_{n} telles que σ(n) = 1 ; r𝔖_{n} l’ensemble des permutations σ ∈ 𝔖_{n} telles que

σ^{−1}(n − r + 1) < σ^{−1}(n − r + 2) < ⋯ < σ^{−1}(n).

On posera également : 𝔖 = ⋃_{0≤n} 𝔖_{n}; puis C = ⋃_{1≤n} C_{n}, G = ⋃_{1≤n} G_{n},

T = ⋃_{1≤n} T_{n}, B = ⋃_{1≤n} B_{n} et D = ⋃_{1≤n} D_{n}. Enfin, on utilise les notations

courantes suivantes :

ℕ l’ensemble des entiers naturels ; ℤ l’ensemble des entiers ; ℚ l’ensemble des nombres rationnels.

CHAPITRE II

LES POLYNÔMES EULÉRIENS

1. Interprétation des polynômes eulériens

Les théorèmes 1.12, 1.15, 1.19 et la propriété 1.17 permettent d’établir immédiatement l’égalité des cinq ensembles pondérés E𝔖_{n}, (D + D′)𝔖_{n}, M𝔖_{n}, ΔDC_{n+1}, ΔD𝔖′_{n+1} ; et le théorème 1.12 donne encore : ΔE𝔖_{n} = ΔD𝔖_{n}. La propriété 2.1 suivante résulte alors du théorème 1.5.

Propriété 2.1. — Soit Γ un monôme en Δ et Δ′ de degré r ≥ 0. On a

ΓE𝔖_{n} = Γ(D + D′)𝔖_{n} = ΓM𝔖_{n} = ΓΔEC_{n+1} = ΓΔD𝔖′_{n+1},

où en outre

ΓE𝔖_{n} = ΓD𝔖_{n}

si et seulement si Γ a au moins un Δ comme facteur.

Nous notons |x| le nombre de termes positifs de tout x ∈ ℕ^{p} et introduisant une indéterminée t, nous posons θx = t^{|x|}. Si K est une application dans ℕ^{p} d’une partie P de 𝔖_{n}, l’ensemble pondéré

θKP = ∑{θKσ : σ ∈ P} = ∑_{0≤k} t^{k} · card{σ ∈ P : |Kσ| = k}

sera appelé, par abus de langage, fonction génératrice de K. Pour P fini, θKP sera donc un polynôme en t à coefficients dans ℕ et nous dirons que (P, K) est une interprétation.

Les polynômes eulériens A_{n}(t) et leurs généralisations^{r}A_{n}(t) selon Riordan sont définis par :

rA_{n}(t) = θΔ^{r}E𝔖_{n} pour 0 ≤ r ≤ n − 1.

On conviendra que ^{r}A_{n}(t) = n! pour r ≥ n. On posera A_{0}(t) = 1 et A_{n}(t) = ^{1}A_{n}(t) pour n ≥ 1. Par construction, les^{r}A_{n}(t) sont des polynômes de degré au plus égal à n−r. L’énoncé suivant en donne plusieurs interprétations par simple application de la propriété précédente.

Propriété 2.2. — Soit Γ un monôme en Δ et Δ′ de degré r. On a

rA_{n}(t) = θΓE𝔖_{n} = θΓ(D + D′)𝔖_{n} = θΓM𝔖_{n} = θΓΔEC_{n+1} = θΓΔD𝔖′_{n+1},

où en outre ^{r}A_{n}(t) = θΓD𝔖_{n} si et seulement si Γ au au moins un Δ comme facteur.

De même, d’après le corollaire 1.16, on a l’égalité entre les ensembles pondérés ED_{n} et MG_{n}, d’où encore

θED_{n} = θMG_{n} pour n ≥ 1.

La valeur commune de ces deux derniers polynômes sera désignée par B_{n}(t). L’interprétation (G_{n}, M) de ces polynômes est due à Roselle [25]. L’interprétation (D_{n}, E) servira à établir au chapitre IV l’expression de la fonction génératrice exponentielle des B_{n}(t).

2. Propriétés de symétrie

Les identités (1) et (4) ci-dessous sont bien connues (cf. Riordan [24]). Nous en donnons ici des démonstrations élémentaires. Les polynômes ^{r}A_{n}(t) pour r ≥ 2 n’ont pas de propriété de symétrie évidente. En revanche, si l’on forme les polynômes réciproques t^{n−r} ^{r}A_{n}(t^{−1}), on obtient plusieurs interprétations (cf. les relations (2) et (3) ci-dessous) qui nous serviront effectivement, dans les sections 2.4 et 2.6, pour établir des connexions avec le problème de Simon Newcomb et pour démontrer de nouvelles identités sur les polynômes eulériens.

Propriété 2.3. — Pour n ≥ 1 on a : ^{0}A_{n}(t) = t A_{n}(t). De plus, si Γ est un monôme de la forme Δ′^{′r−1} ou Δ′′^{r−1}Δ′ (r ≥ 1), on a

t^{n−r} ^{r}A_{n}(t^{−1}) = θΓE𝔖_{n} = θΓ(D + D′)𝔖_{n} = θΓM𝔖_{n}.  (2)

On a encore

t^{n−r} ^{r}A_{n}(t^{−1}) = θΔ′′^{r−1}ΔD𝔖_{n},  (3)

d’où en particulier pour r = 1

t^{n−1} A_{n}(t^{−1}) = A_{n}(t).  (4)

Démonstration. — Soit σ ∈ 𝔖_{n}; définissant σ̌ par l’identité σ̌(k) = n + 1 − σ(n + 1 − k), l’on a Eσ̌(k) = 1 si et seulement si Eσ(n + 1 − k) = 1 et Eσ̌(k) ≥ 2 si et seulement si Eσ(n + 1 − k) = 0. Dans ces conditions, il vient |Eσ̌| + |ΔEσ| = n, ce qui établit

0A_{n}(t) = t^{n} A_{n}(t^{−1}).  (5)

D’autre part, la relation entre les vecteurs Eσ̌ et Eσ peut encore s’exprimer par la condition

ΔEσ̌(k) ≥ 1 si et seulement si Δ′Eσ(n − k) = 0 pour 1 ≤ k ≤ n − 1. (6)

Mais la condition (6) est encore équivalente à

|Δ′^{r−1}ΔEσ̌| + |Δ′′^{r−1}Δ′Eσ| = n − r

ou encore à

|Δ′′^{r−1}ΔEσ̌| + |Δ′^{r}Eσ| = n − r.

On en déduit

θΔ′′^{r−1}ΔE𝔖_{n} = t^{n−r} ∑_{0≤k} t^{−k} card{σ ∈ 𝔖_{n} : |Δ′^{r}Eσ| = k}
= t^{n−r} ^{r}A_{n}(t^{−1}),

d’après la propriété 2.2.

Les relations (2) et (3) résultent alors de la propriété 2.1 et faisant r = 1 dans (3), on obtient t^{n−1} A_{n}(t^{−1}) = θΔD𝔖_{n} = A_{n}(t), c’est-à-dire la relation (4). Enfin, l’identité (2) résulte à la fois de (4) et de (5).

Remarque 2.4. — D’après la définition 1.6, pour 1 ≤ r ≤ n et σ ∈ 𝔖_{n}, il y a exactement |Δ′Δ′′^{r−1}Mσ| indices i tels que 1 ≤ i ≤ n − 1, σ(i) < σ(i + 1) et σ(i) < n − r. Comme on a posé d’autre part

rA_{n}(t) = ∑_{0≤k≤n−r} ^{r}A_{n,k} t^{k}

et que d’après la propriété 2.3, on a

θΔ′Δ′′^{r−1}M𝔖_{n} = t^{n−r} ^{r}A_{n}(t^{−1}) = ∑_{0≤s≤n−r} ^{r}A_{n,n−r−s} t^{s},

il vient :

rA_{n,n−r−s} = card{σ ∈ 𝔖_{n} : |Δ′Δ′′^{r−1}Mσ| = s} pour 0 ≤ s ≤ n − r.

Cette remarque nous servira au paragraphe 6 du présent chapitre.

3. Relations de récurrence

Dans cette section, nous établissons une relation de récurrence sur les polynômes eulériens qui généralise l’identité (1) ci-dessus et redémontrons la relation de récurrence trouvée par Riordan [24].

Propriété 2.5. — Pour 0 ≤ r ≤ n, on a l’identité :

t ·^{(r+1)}A_{n}(t) = ^{r}A_{n}(t) + r(t − 1) ·^{r}A_{n−1}(t).

Démonstration. — Pour r = 0, l’identité se réduit à tA_{n}(t) = ^{0}A_{n}(t). Pour r = n, elle est encore vraie avec la convention que nous avons faite que rA_{n}(t) = n! quand r = n. Nous supposons donc 1 ≤ r ≤ n − 1. Pour chaque σ ∈ 𝔖_{n}, on a

Δ^{r}Eσ = ((σ(1) − r)_{+}, (σ(2) − r − 1)_{+}, …, (σ(n − r) − (n − 1))_{+}).

D’une part, on a Δ^{r}E𝔖_{n,s} = Δ^{r}E𝔖_{n,r} pour 1 ≤ s ≤ r; d’autre part, rθΔ^{r}E𝔖_{n,1} = rθΔ^{r}Δ′E𝔖_{n,1} = r^{r}A_{n−1}(t) d’après la propriété 2.2. Il en résulte :^{r}A_{n}(t)−r^{r}A_{n−1}(t) = θΔ^{r}(𝔖_{n}−(𝔖_{n,1}+⋯+𝔖_{n,r})) = θΔ^{r}E(𝔖_{n,r+1}+ ⋯ + 𝔖_{n,n}) = tΔ′Δ^{r}E(𝔖_{n,r+1} + ⋯ + 𝔖_{n,n}) = tΔ′Δ^{r}E(𝔖_{n} − (𝔖_{n,1} + ⋯ + 𝔖_{n,r})) = t(Δ′Δ^{r}E𝔖_{n,1} − rΔ′Δ^{r}E𝔖_{n,1}) = t(^{(r+1)}A_{n}(t) − r^{r}A_{n−1}(t)).

Remarque 2.6. — Riordan ([24], p. 214) a trouvé une autre relation de récurrence, à savoir

rA_{n}(t) = (r + (n − r)t) ·^{r}A_{n−1}(t) + t(1 − t) ·^{r}A′_{n−1}(t) (0 ≤ r ≤ n; 1 ≤ n), (7)

4. RELATIONS AVEC LE ^{⟨⟨} PROBLÈME DE SIMON NEWCOMB^{⟩⟩} 17

où ^{r}A′_{n−1}(t) désigne la dérivée du polynôme ^{r}A_{n−1}(t). Comme on a posé

rA_{n}(t) = ∑_{0≤k≤n−r} ^{r}A_{n,k}t^{k},

cette relation de récurrence est encore équivalente aux (n − r + 1) relations suivantes (cf. [24] p. 215)

rA_{n,k} = (k + r) ·^{r}A_{n−1,k} + (n + 1 − k − r) ·^{r}A_{n−1,k−1} (0 ≤ k ≤ n − r), (8)

où l’on a posé ^{r}A_{n,k} = 0 si k ≤ −1 ou k ≥ n − r + 1.

Comme l’a noté Welschinger [30], on peut redémontrer facilement (8) et par suite (7) en prenant les polynômes eulériens dans l’interprétation

rA_{n}(t) = θΔ′^{r−1}ΔD𝔖_{n}.

En effet, on vérifie tout d’abord que les relations (8) sont vraies pour n = r, en notant que ^{n}A_{n,0} = n! et ^{n}A_{n,k} = 0 pour k ≠ 0. On suppose ensuite 0 ≤ r ≤ n − 1 et l’on pose pour i ∈ [ n] et σ ∈ 𝔖_{n−1}

η_{i}(σ) = (σ(1), …, σ(i − 1), n, σ(i), …, σ(n − 1)).

Il est clair que l’on a

𝔖_{n} = {η_{i}(σ) : i ∈ [ n], σ ∈ 𝔖_{n−1}}.

Soit σ ∈ 𝔖_{n−1} ; alors |Δ′^{r−1}ΔDσ| = k [en abrégé : σ ∈ ^{r}𝔄_{n−1,k}] si et seulement s’il existe k couples (j − 1, j) tels que 1 ≤ j − 1 et σ(j − 1) > σ(j) ≥ r. Prenons σ dans ^{r}𝔄_{n−1,k}; on observe alors que η_{i}(σ) appartient à r𝔄_{n,k} pour les seuls indices i suivants

(i) 1 ≤ i − 1 et σ(i − 1) > σ(i) ≥ r; (ii) i ∈ [n − 1] et σ(k) ≤ r − 1 ; (iii) i = n;

c’est-à-dire pour exactement k + (r − 1) + 1 = k + r indices i ∈ [ n]. Pour les autres n − (k + r) indices i ne satisfaisant à aucune des conditions (i), (ii), (iii), on a η_{i}(σ) ∈ ^{r}𝔄_{n,k+1}. On constate donc que l’ensemble^{r}𝔄_{n,k} est contenu dans la réunion ⋃{η_{i}(^{r}𝔄_{n−1,k} ∪^{r}𝔄_{n−1,k−1}) : i ∈ [ n]}. On voit ensuite que la relation η_{i}(σ) ∈ ^{r}𝔄_{n,k} est vérifiée pour exactement (k + r) indice i si σ est dans ^{r}𝔄_{n−1,k} et pour exactement n − (k − 1 + r) = n + 1 − k − r indices i si σ est dans ^{r}𝔄_{n−1,k−1}. Les relations (8) sont ainsi démontrées.

4. Relations avec le ^{⟨⟨}problème de Simon Newcomb^{⟩⟩}

Nous allons expliciter maintenant le lien entre les polynômes ^{r}A_{n}(t) et les polynômes générateurs que l’on définit pour le^{⟨⟨}problème de Simon Newcomb avec une spécification (1^{r}(n−r))^{⟩⟩} (voir MacMahon [20], vol. 1, chap. 4 et 5). Dans la démonstration de la propriété qui suit, nous considérons σw comme le mot σ(1)σ(2) … σ(n) dont les lettres sont des éléments de [ n].

Propriété 2.7. — Soit r ≥ 2 ; on a : t^{n−r} ^{r}A_{n}(t^{−1}) = r! θΔD_{r}𝔖_{n}, où r𝔖_{n} = {σ ∈ 𝔖_{n} : σ^{−1}(n − r + 1) < σ^{−1}(n − r + 2) < ⋯ < σ^{−1}(n)}.

Démonstration. — D’après la propriété 2.2, il nous suffit d’établir θΔ′′^{r−1}ΔD𝔖_{n} = r! θΔD_{r}𝔖_{n} ou encore de trouver une surjection σ ↦ σ′ de 𝔖_{n} sur _{r}𝔖_{n} telle que

(i) |Δ′′^{r−1}ΔDσ| = |ΔDσ′|;

(ii) l’application σ ↦ σ′ soit homogène de degre r!, c’est-à-dire que l’image inverse de chaque σ′ ∈ _{r}𝔖_{n} ait r! éléments.

Prenons σ ∈ 𝔖_{n} et soit σw =g_{1}i_{n−r+1}g_{2} … g_{r}i_{n}g_{r+1}, où {i_{n−r+1}, …, i_{n}}= {n−r+1, …, n}. On pose σ′w = g_{1}(n−r+1)g_{2} … g_{r}ng_{r+1}. Il est clair que σ′ est dans _{r}𝔖_{n} et que σ ↦ σ′ est homogène de degre r! D’autre part, puisque les éléments n − r + 1, n − r + 2, …, n se présentent dans cet ordre dans le mot σ′w, on a ΔDσ(j) = 0 pour j = n − r + 1, n − r + 2, …, n − 1, ou encore |ΔDσ′| = |Δ′′^{r−1}ΔDσ′|. Enfin, l’identité |Δ′′^{r−1}ΔDσ| = |Δ′′^{r−1}ΔDσ′| résulte du fait que l’on a σ′(j) = σ(j) si σ(j) ≤ n − r et que σ′(j) ≥ n − r + 1 si et seulement si σ(j) ≥ n − r + 1.

Si l’on envoie tout σ′w = g_{1}(n − r + 1)g_{2}(n − r + 2) … g_{r}ng_{r+1} de _{r}𝔖_{n} sur le mot g_{1}(n − r + 1)g_{2}(n − r + 1) … g_{r}(n − r + 1)g_{r+1}, on définit une bijection de _{r}𝔖_{n} sur une classe de mots de spécification (1^{r}(n − r)), c’est-à-dire des mots de longueur n, qui contiennent n − r + 1 lettres distinctes dont l’une d’entre elles est répétée r fois. Si l’on définit maintenant |ΔDf| comme le nombre de descentes, c’est-à-dire le nombre de couples de lettres successives dans f qui vont en décroissant, on voit que l’on a |ΔDf| = |ΔDσ′|. Ainsi t^{n−r} ^{r}A_{n}(t^{−1}) est le polynôme générateur du nombre des descentes pour un ensemble de spécification (1^{r}(n − r)).

5. Relations avec les nombres de Stirling

Rappelons que pour 1 ≤ q ≤ p, le nombre de Stirling de seconde espèce S(p, q) est le nombre de partitions de [ p] en q parties non vides. Le résultat suivant est obtenu par Riordan ([24], p. 213) au moyen de calculs assez complexes.

Propriété 3.8. — L’entier S(p, q) est le nombre de parties W ⊂ [ p] × [ p] de p − q éléments qui satisfont aux conditions suivantes :

(i) W est une quasi-permutation, c’est-à-dire qu’il existe au moins un σ ∈ 𝔖_{p} tel que W ⊂ {(k, σ(k)) ⊂ [ p] × [ p] : k ∈ [ p]};

(ii) W est supra-diagonale, c’est-à-dire que (k, k′) ∈ W implique k < k′.

Démonstration. — Soit {E_{1}, E_{2}, …, E_{p}} une partition de [ p] que nous pouvons considérer comme formée des classes d’une relation d’équivalence E ⊂ [ p] × [ p]. A chaque E_{n} = {i_{1} < i_{2} < ⋯ < i_{n_{j}}} comprenant n_{j} ≥ 1 éléments, nous associons la quasi-permutation supra-diagonale E′_{j} = {(i_{1}, i_{2}), (i_{2}, i_{3}), …, (i_{n_{j}−1}, i_{n_{j}})} contenant n_{j}−1 (éventuellement zéro) éléments de [ p] × [ p]. Posant E′ = ⋃_{1≤j≤q} E′_{j}, on voit que E′ est une quasi-

permutation supra-diagonale ayant ∑(n_{j} − 1) = p − q éléments et que E est la plus fine des équivalences sur [ p] qui contienne E′.

Réciproquement, étant donnée une quasi-application supra-diagonale V ayant p − q éléments, soit E la plus fine de toutes les équivalences sur [ p] qui contienne W. On a W = E′ et la bijection désirée est établie.

La formule de Riordan ([24], p. 214)

rA_{n}(s + 1) = ∑_{0≤k≤n−r} s^{k} (n − k)! S(n + 1 − r, n + 1 − r − k)

étant obtenue par celui-ci au moyen de la méthode algébrique classique d’inversion de Möbius, nous pensons pouvoir nous dispenser d’en reproduire ici la démonstration.

6. Les identités de Worpitzky

Soient m, n, s trois entiers tels que 0 ≤ s < n ≤ m + s et (i_{1}, i_{2}, …, i_{s}) une suite strictement décroissante d’entiers compris entre 1 et n−1 que nous nommerons indices distingués. Nous allons d’abord dénombrer l’ensemble Φ_{m,n,s} de tous les morphismes ϕ : [ n] → [ n] tels que ϕ(i) ≠ ϕ(i+1) si i n’est pas un indice distingué. Le dénombrement de Φ_{m,n,s} permet non seulement d’obtenir l’identité (9) ci-dessous due à Worpitzky, mais une généralisation de celle-ci au cas des polynômes ^{r}A_{n}(t) (r ≥ 2). La proposition 2.9 ci-dessous est bien connue.

Proposition 2.9. — On a : card Φ_{m,n,s} = \binom{m+s}{n}.

Démonstration. — Il suffit de faire correspondre, de façon bijective, à tout ϕ ∈ Φ_{m,n,s} un morphisme injectif ψ : [ n] → [m + s] (c’est-à-dire une application strictement croissante). Dans ce but, désignons pour tout entier k ∈ [ n], par θ(k) le nombre d’indices distingués avant k, à savoir le nombre d’indices j tels que i_{j} < k. On a θ(1) = 0 et θ(n) = s. La bijection ϕ ↦ ψ est alors définie de la façon suivante. Pour tout k ∈ [ n], on pose ψ(k) = ϕ(k) + θ(k). On a 1 ≤ ψ(n) ≤ m + s et ψ est strictement croissante, car si k − 1 est distingué, on a θ(k − 1) < θ(k) et si k − 1 ne l’est pas, on a ϕ(k − 1) < ϕ(k). Dans les deux cas, il vient ψ(k − 1) < ψ(k). Enfin l’application ϕ ↦ ψ est trivialement injective. Elle est aussi surjective, puisque ϕ est uniquement déterminé par les relations ϕ(k) = ψ(k) − θ(k) (1 ≤ k ≤ n).

L’identité de Worpitzky sur les nombres eulériens s’obtient par simple application de cette proposition. L’ensemble de toutes les applications de [ n] dans [ n] étant noté H_{n,m}, soit ϕ ∈ H_{n,m}; on définit δϕ comme l’unique σ ∈ 𝔖_{n} telle que la suite des paires (ϕσ(1), σ(1)), (ϕσ(2), σ(2)), …, (ϕσ(n), σ(n)) soit croissante pour l’ordre lexicographique. Par conséquent, δ^{−1}σ est l’ensemble des applications ϕ : [ n] → [m] telles que ϕσ(i) ≤ ϕσ(i+1) pour i ∈ [n − 1] et telles que l’égalité ϕσ(i) = ϕσ(i + 1) ne soit possible que si σ(i) < σ(i + 1). D’après la remarque 2.4, il y a exactement s = |Δ′Mσ| indices i vérifiant une telle inégalité ; donc, d’après la précédente proposition card δ^{−1}σ = \binom{m+s}{n}. Comme le nombre de permutations σ ∈ 𝔖_{n} satisfaisant à |ΔMσ| = s est donné par le nombre eulérien A_{n,s}, il vient enfin

m^{n} = ∑_{0≤s≤n−1} \binom{m + s}{n}A_{n,s}.  (9)

Cette identité est un cas particulier de l’identité (10) ci-dessous.

Propriété 2.10. — Pour r ∈ [ n] et r ≤ m, on a :

∑_{0≤s≤n−r} ^{r}A_{n,n−r−s}\binom{m + s}{n} = m^{n−r} \frac{m!}{(m − r)!}.  (10)

Démonstration. — Notons d’abord que pour r = 1, on retrouve bien l’identité (9), puisque l’on a A_{n,n−1−s} = A_{n,s} d’après la propriété 2.3. D’autre part, l’identité est vraie pour r = n avec les conventions que nous avons adoptées. On prendra donc r ∈ [n−1]. Soit H_{m,n,r} l’ensemble des applications ϕ : [ n] → [m] dont la restriction à {n − r + 1, n − r + 2, …, n} est injective. Il est immédiat que l’on a card H_{m,n,r} = m^{n−r}m! /(m − r)! Pour ϕ ∈ H_{m,n,r} on définit δϕ comme étant l’unique σ ∈ 𝔖_{n} telle que la suite (ϕσ(1), σ(1)), (ϕσ(2), σ(2)), …, (ϕσ(n), σ(n)) soit croissante pour l’ordre lexicographique. Comme précédemment, on a ϕσ(i) ≤ ϕσ(i+1) pour i ∈ [n−1], mais l’égalité n’est possible que si l’on a σ(i) < σ(i + 1) et σ(i) ≤ n − r, puisque la restriction de ϕ à l’ensemble {n − r + 1, n − r + 2, …, n} est injective. Or, d’après la remarque 2.5, il y a exactement |Δ′Δ^{′′r−1}Mσ| indices i tels que 1 ≤ i ≤ n − 1, σ(i) < σ(i + 1) et σ(i) ≤ n − r. D’après la précédente proposition, on a card δ^{−1}σ = \binom{m+s}{n} avec |Δ′Δ^{′′r−1}Mσ| = s et comme le nombre de σ ∈ 𝔖_{n} satisfaisant à |Δ′Δ^{′′r−1}Mσ| = s est égal à ^{r}A_{n,n−r−s}, on obtient l’identité désirée.

Pour terminer cette section, nous donnons la formule explicite des coefficients ^{r}A_{n,k} obtenue par un simple calcul traduisant de nouveau l’inversion de Möbius (cf. par exemple [26]) à partir des identités (9) et (10).

En effet, pour 1 ≤ n + r, on a \frac{1}{(1 − t)^{n+r}} = ∑_{0≤k} t^{k}\binom{n + r − 1 + k}{n + r − 1}. Donc

\frac{^{r}A_{n−1+r}(t)}{(1 − t)^{n+r}} = ∑_{0≤k} t^{k}\binom{n + r − 1 + k}{n + r − 1} ∑_{0≤s≤n−1}^{r}A_{n+r−1,s} t^{s}

= ∑_{0≤j} t^{j} ∑_{0≤s≤min(j,n−1)}^{r}A_{n+r−1,s}\binom{n + r − 1 + j − s}{n + r − 1}

= ∑_{0≤j} t^{j} ∑_{0≤s≤n−1}^{r}A_{n+r−1,n−1−s}\binom{j + r + s}{n + r − 1}

= ∑_{0≤j} t^{j}(j + r)^{n−1} \frac{(j + r)!}{j!}

en utilisant le fait que \binom{n+r−1+j−s}{n+r−1} = 0 si j ≤ n − 2 et s = j + 1, …, n − 1 et pour la dernière étape en se servant de l’identité (10). Il en résulte

\frac{^{r}A_{n−1+r}(t)}{r! (1 − t)^{n+r}} = ∑_{0≤j} t^{j}(j + r)^{n−1}\binom{j + r}{r}.

On a donc pour 0 ≤ k ≤ n − 1 la formule explicite :

rA_{n−1+r,k} = r! ∑_{0≤i≤k}(−1)^{i}(k − i + r)^{n−1}\binom{n + r}{i}\binom{k − i + r}{r}. (11)

7. Table des polynômes eulériens

Le paragraphe 4 du présent chapitre ou l’identité (11) ci-dessus montre que tous les coefficients des polynômes ^{r}A_{n}(t) sont divisibles par r! (on verra une autre démonstration de ce résultat à la fin du chaitre IV). Comme on a posé

rA_{n}(t) = ∑_{0≤k≤n−r} ^{r}A_{n,k} t^{k} (0 ≤ r ≤ n),

on peut écrire

rA_{n,k} = r!^{r}a_{n,k},

où ^{r}a_{n,k} est un entier (0 ≤ k ≤ n−r). Le présent tableau donne les premières valeurs des coefficients ^{r}a_{n,k} pour r = 1, 2, 3, 4, 5, r ≤ n ≤ 8 et 0 ≤ k ≤ n − r.

r = 1 :

k = 0 1  2  3  4  5  6 7
n = 1 1
2 1 1
3 1 4  1
4 1 11 11  1
5 1 26 66  26  1
6 1 57 302 302  57  1
7 1 120 1191 2416 1191 120 1
8 1 247 4293 15619 15619 4293 247 1

r = 2 :

k = 0  1  2  3  4  5 6
n = 2 1
3 2  1
4 4  7  1
5 8 33  18  1
6 16 131 171 41  1
7 32 473 1208 718 88  1
8 64 1611 7197 8422 2682 183 1

22 CHAPITRE II : LES POLYNÔMES EULÉRIENS

r = 3 :

k = 0 1 2 3 4 5
n = 3 1
4 3  1
5 9  10  1
6 27 67  25  1
7 81 376 326 56  1
8 243 1909 3134 1314 119 1

r = 4 :

k = 0 1 2 3 4
n = 4 1
5 4  1
6 16 13 1
7 64 113 32 1
8 256 821 531 71 1

r = 5 :

k = 0 1 2 3
n = 5 1
6 5  1
7 25 16 1
8 125 171 39 1

CHAPITRE III

LA FORMULE EXPONENTIELLE

Les trois premières sections de ce chapitre contiennent la définition et quelques propriétés d’une construction très générale que nous appelons ⟨⟨composé partitionnel^{⟩⟩}. La motivation de cette notion apparaît dans les sections suivantes, ainsi qu’au chapitre IV, où nous appliquons toutes ces techniques aux polynômes eulériens. Comme nous l’avons déjà mentionné, ces résultats ont été fréquemment étudiés en liaison avec divers problèmes d’énumération et tout particulièrement dans [29], [14] et [15].

Dans ce chapitre, si Z est un ensemble non vide, on note Z^{∗} et Z^{+} les monoïdes libre et abélien libre engendrés par Z. On appelera mots les éléments de Z^{∗}, qu’on présentera comme des suites g = z_{1}z_{2} … z_{r}, où z_{1}, z_{2}, …, z_{r} appartiennent à Z; l’entier r est la longueur du mot g. On appellera monômes les éléments de Z^{+}. Si α est le morphisme canonique de Z^{∗} sur Z^{+}, on prendra dans chaque classe α^{−1}(f), où f ∈ Z^{+}, un mot canonique qu’on identifiera à f. Le monôme f sera dit de degré r si le mot f est de longueur r.

1. La formule de Hurwitz

Dans cette section, Y est un ensemble non vide, muni d’une application λ : Y → ℕ. Le même symbole désignera les morphismes dans ℕ étendant cette application aux monoïdes Y^{∗} et Y^{+}. Le morphisme canonique de Y^{∗} sur Y^{+} sera noté α.

Soit P l’ensemble des parties finies (y compris la partie vide) de ℕ; on considère le sous-ensemble Y_{λ} du produit cartésien Y × P composé de tous les couples (y, I) satisfaisant à la condition card I = λy. On forme ensuite le monoïde libr Y_{λ}^{∗} engendré par Y_{λ}. Soit

h = (y_{1}, I_{1})(y_{2}, I_{2}) … (y_{r}, I_{r})

un mot de Y_{λ}^{∗} de longueur r ≥ 1. On pose

βh = g = y_{1}y_{2} … y_{r} et λh = λg.  (1)

Définition 3.1. — Pour chaque entier r ≥ 1, le composé partitionnel marqué de Y de degré r est le sous-ensemble Y^{((r))} de Y_{λ}^{∗} formé de tous les mots h = (y_{1}, I_{1})(y_{2}, I_{2}) … (y_{r}, I_{r}) de longueur r satisfaisant aux conditions

(i) I_{j} ∩ I_{j′} = ∅ si j ≠ j′; (ii) ⋃{I_{j} : j ∈ [r]} = [λh].

On notera que si λy_{j} est strictement positif pour tout j ∈ [r], la famille {I_{1}, I_{2}, …, I_{r}} est une partition de l’ensemble [λh], aucun de ces sousensembles n’étant vide.

Par convention, on supposera l’existence d’un ensemble Y^{((r))} pour r = 0 contenant un seul élément, à savoir l’élément neutre de Y. Ce dernier est envoyé par β sur l’élément neutre de Y^{∗}. On identifiera, d’autre part, le composé partitionnel marqué Y^{((1))} de degré 1 avec Y.

Théorème 3.3 (Formule de Hurwitz). — Soit E(Y) = ∑{y/λy! : y ∈ Y } la fonction génératrice exponentielle de Y (par rapport à λ). Pour tout r ≥ 0, on a dans la ℚ-algèbre large de Y^{∗} l’identité

(E(Y))^{r} = ∑{βh/λh! : h ∈ Y^{((r))}}.  (2)

Démonstration. — Avec nos conventions sur β, il n’y a rien à prouver pour r = 0. Pour chaque mot g = y_{1}y_{2} … y_{r} de longueur r (r ≥ 1) de Y^{∗}, le nombre de mots h ∈ Y^{((r))} tels que βh = g est égal au nombre de suites (I_{1}, I_{2}, …, I_{r}) de parties de ℕ satisfaisant aux conditions (i) et (ii) de la définition 3.1 ainsi qu’à la condition card I_{j} = λy_{j} pour chaque j ∈ [r]. Or, le nombre de telles suites est évidemment donné par le coefficient multinomial

\binom{λ}{g} = \frac{λg!}{λy_{1}! λy_{2}! … λy_{r}!}.

Donc

∑\{βh/λh! : h ∈ Y^{((r))}, βh = g\} = \frac{1}{λy_{1}! λy_{2}! … λy_{r}!} g,

puisque λh = λg pour βh = g. Or, le facteur 1/(λy_{1}! λy_{2}! … λy_{r}!) est simplement le coefficient de g dans le développement de (E(Y))^{r} et le résultat s’en déduit par sommation sur tous les mots de longueur r de Y^{∗}.

2. Le composé partitionnel

Nous conservons les mêmes notations que dans la section 1, mais nous supposons cette fois que λ > 0 pour tout y ∈ Y. Soit h = (y_{1}, I_{1})(y_{2}, I_{2}) … (y_{r}, I_{r}) un mot de Y^{((r))}. L’hyposhèse ci-dessus entraîne, puisque l’on a card I_{j} = λy_{j} pour chaque j ∈ [r], que les sous-ensembles I_{1}, I_{2}, …, I_{r} sont non vides, donc tous distincts. Il en résulte que h est multilinéaire, c’est-à-dire a toutes ses lettres distinctes. En notant δ le morphisme canonique de Y_{λ}^{∗} sur Y_{λ}^{+}, on voit donc que la classe abélienne δ^{−1}δh contient exactement r! mots. De plus, les conditions (i) et (ii) de la définition 3.1 ne faisant pas intervenir l’ordre des lettres de h, il s’ensuit que Y^{(r))} contient toute une classe abélienne δ^{−1}δh dès qu’il contient h.

Définition 3.3. — On appelle composé partitionnel de Y, de degré r (r ≥ 0), l’ensemble Y^{(r)} = δY^{((r))} et l’union Y^{(+)} = ⋃_{0≤r}Y^{(r)} est le composé partitionnel de Y.

Les éléments de Y^{(r)} sont donc des monômes f = (y_{1}, I_{1})(y_{2}, I_{2}) … (y_{r}, I_{r}) de Y_{λ}^{∗}. On désigne par γf le monôme m = y_{1}y_{2} … y_{s} de Y^{+} et l’on pose encore λf = λm. On a donc l’identité

αβ = γδ

où α est le morphisme α : Y^{∗} → Y^{+} et où β a été défini en (1). On peut rassembler les remarques ainsi faites dans un lemme.

Lemme 3.4. — Pour tout f ∈ Y^{(r)}, on a card{h ∈ Y^{((r))} : δh = f} = r! et si δh = f, on a : γf = αβh.

Venons-en à la formule fondamentale de ce chapitre.

Théorème 3.5 (Formule exponentielle). — Dans la ℚ-algèbre large de Y^{+}, on a l’identité

∑{γf/λf! : f ∈ Y^{(+)}} = exp E(Y).

Démonstration. — On a ∑{γf/λf! : f ∈ Y^{(0)}} = 1. D’autre part, pour f ∈ Y^{(r)} (r ≥ 1), on a

∑{αβh/λh! : δh = f} = r! (γf/λf!)

d’après le lemme précédent. D’où, il résulte

∑\{γf/λf! : f ∈ Y^{(r)}\} = \frac{1}{r!} ∑\{αβh/λh! : h ∈ Y^{((r))}\}

pour chaque r ≥ 1. Utilisant le théorème 3.2, on obtient donc par sommation sur tous les r ∈ ℕ

∑\{γf/λf! : f ∈ Y^{(+)}\} = ∑_{0≤r} \frac{1}{r!}(E(Y))^{r} = exp E(Y).

Remarque 3.6. — Dans la ℚ-algèbre large de Y^{+}, on a pris la topologie des séries formelles induite par l’ordre o suivant : si a = ∑{m a_{m} : m ∈ Y^{+}} est une série formelle, son ordre o(a) est défini par

o(a) = inf{n ≥ 1 : λm = n, a_{m} ≠ 0}.

Utilisons les notations abrégées

γ{Y^{(+)} ∩ λ^{−1}n} = ∑{λf : f ∈ Y^{(+)}, λf = n} (n ≥ 0);
{Y_{n}} = ∑{y : y ∈ Y, λy = n} (n ≥ 1).

Les séries formelles γ{Y^{(+)} ∩ λ^{−1}n} et {Y_{n}} sont d’ordre égal à n, ce qui permet d’écrire la formule exponentielle sous la forme :

∑_{0≤n} \frac{1}{n!} γ\{Y^{(+)} ∩ λ^{−1}n\} = exp(∑_{1≤n} \frac{1}{n!} \{Y_{n}\}).  (3)

3. Une formule d’inversion pour les séries exponentielles

Pour f ∈ Y^{(+)} désignons par z(f) l’unique r ∈ ℕ tel que f ∈ Y^{(r)} ; l’entier z(f) n’est autre que le degré de f. Posons

\overline{γ}\{Y^{(+)} ∩ λ^{−1}n\} = ∑\{λf · (−1)^{z(f)+n} : f ∈ Y^{(+)}, λf = n\} (n ≥ 0).

Propriété 3.7. — Dans la ℚ-algèbre large de Y^{+}, on a l’identité

(∑_{0≤n} \frac{1}{n!} γ\{Y^{(+)} ∩ λ^{−1}n\})^{−1} = ∑_{0≤n} \frac{(−1)^{n}}{n!} \overline{γ}\{Y^{(+)} ∩ λ^{−1}n\}.  (4)

Démonstration. — D’après le théorème 3.5, le membre de gauche de l’identité à établir, soit U, est égal à (exp(E(Y))^{−1}, c’est-à-dire à exp(−E(Y)). Notons ϕ le morphisme envoyant sur −y chaque y ∈ Y ; ceci équivaut à U = ϕ exp E(Y), donc de nouveau d’après le théorème 3.5, à

U = ϕ ∑_{0≤n} \frac{1}{n!} γ\{Y^{(+)} ∩ λ^{−1}n\} = ∑_{0≤n} \frac{1}{n!} ∑_{0≤r}(−1)^{r}γ\{Y^{(+)} ∩ λ^{−1}n ∩ z^{−1}r\})^{−1}

= ∑_{0≤n} \frac{(−1)^{n}}{n!} \overline{γ}\{Y^{(+)} ∩ λ^{−1}n\}.

Ceci termine l’établissement des formules que nous utiliserons par la suite. Le théorème 3.2 avc une interprétation adéquate des objets en cause exprime que la transformation de Borel ∑{y : y ∈ Y } ↦ ∑{y/λy! : y ∈ Y } est un morphisme dans l’algèbre large de Y^{+} de l’algèbre large de base Y par rapport au^{⟨⟨}produit d’intercalement^{⟩⟩} (^{⟨⟨}shuffle^{⟩⟩} de Chen, Fox et Lyndon). Le théorème 3.5 est appelé ^{⟨⟨}formule de Cauchy^{⟩⟩} dans les problèmes concernant le groupe symétrique. Sous une forme ou sous une autre, elle a été retrouvée et utilisée souvent dans diverses questions d’énumération. Nous l’appellerons simplement formule exponentielle. En prenant le logarithme, on obtiendrait évidemment la fonction génératrice exponentielle E(Y) de Y en fonction de la fonction génératrice exponentielle du composé partitionnel Y^{(+)} de Y.

Définition 3.8. — Soient Y^{(+)} un composé partitionnel et A un monoïde abélien ; une application μ : Y^{(+)} → A sera dite multiplicative si et seulement s’il existe un morphisme μ′ := Y^{+} → A tel que le diagramme suivant soit commutatif.

[figure: Y^{(+)}; A; μ; γ; μ′; Y^{+}]

4. Le composé partitionnel des applications

Il existe de nombreuses familles de structures qui peuvent être considérées comme le composé partitionnel d’une de leurs sous-familles. Nous examinerons ici, à titre d’exemple, la famille des applications avec le but d’introduire les notions nécessaires pour traiter le cas particulier des permutations.

Définition 3.9. — Soit f : I → I une application d’un ensemble fini I dans lui-même. L’équivalence f^{∗} de f est la relation d’équivalence dans I × I telle que deux éléments i et i′ de I appartiennent à la même classe si et seulement s’il existe des itérées f^{p} et f^{p′}de f satisfaisant à f^{p}(i) = f^{p′}(i′).

Nous appellerons sous-domaines de f les classes de cette équivalence et leur nombre sera désigné par z(f). L’application f sera connexe si z(f) = 1. Ainsi les sous-domaines d’une permutation sont les orbites de celle-ci ; les permutations circulaires sont les permutations connexes.

Dans la suite, on notera F_{n} l’ensemble des applications de [ n] dans lui-même (n ≥ 0) et l’on posera F = ⋃_{0≤n} F_{n}. Désignons par I_{1}, I_{2}, …, I_{r} (r = z(f)) les sous-domaines d’une application f ∈ F_{n} (n ≥ 1). Pour tout j ∈ [r], on note ω_{j} l’unique morphisme (d’ensembles ordonnés) ω_{j} : [card I_{j}] → [ n] qui a pour image I_{j} et f′_{j} la restriction de f à I_{j}. Par définition de l’équivalence f^{∗} on voit que f′_{j}(I_{j}) ⊂ I_{j} et il est licite de poser f_{j} = ω_{j}^{−1}f′_{j} ω_{j} (j ∈ [r]). Les applications f_{j} envoient [card I_{j}] dans lui-même et sont toutes connexes (j ∈ [r]). Enfin, il est clair que toute application f ∈ F_{n} détermine, de façon biunivoque le monôme (appartenant au monoïde (F × P)^{+}, où P désigne toujours l’ensemble des parties finies de ℕ) (f_{1}, I_{1})(f_{2}, I_{2}) … (f_{r}, I_{r}), que l’on appellera sa factorisation canonique, les f_{j} eux-mêmes étant les facteurs de f. Par commodité, on identifiera tout f ∈ F avec sa factorisation canonique et f ∈ F_{0} avec le monôme unité.

Le raccordement avec les trois premières sections se fait de la façon suivante. Soit donnée une famille F d’applications connexes dont les domaines sont des ensembles de la forme [ n] (n ∈ ℕ). Posons Y = F et prenons pour λ l’application qui envoie sur n chaque f ∈ F de domaine [ n] (n ∈ ℕ). Formons ensuite le composé partitionnel F^{(+)}. On constate alors que la factorisation canonique d’une application f ∈ F appartient au composé partitionnel F^{(+)} si et seulement si les facteurs de f appartiennent à F. Avec l’identification faite ci-dessus, on a ainsi la proposition suivante.

Proposition 3.10. — Soit F ⊂ F une famille d’applications connexes. Le composé partitionnel F^{(+)} est l’ensemble des applications f ∈ F dont les facteurs appartiennent à F.

La propriété suivante découle immédiatement de la définition du composé partitionnel d’un ensemble d’applications. Elle exprime le fait que la factorisation canonique d’une application f conserve les excédances et les points fixes de f.

Propriété 3.11. — Soit (f_{1}, I_{1})(f_{2}, I_{2}) … (f_{r}, I_{r}) (r ≥ 1) la factorisation canonique d’une application f. Pour tout j ∈ [r], le morphisme τ_{j} = ω_{j}^{−1} est une bijection de I_{j} sur [card I_{j}] telle que pour tout i ∈ I_{j} on ait les équivalences : i < f(i) ⇔ τ_{j}(i) < f_{j} τ_{j}(i) ; i = f(i) ⇔ τ_{j}(i) = f_{j} τ_{j}(i) ; i > f(i) ⇔ τ_{j}(i) > f_{j} τ_{j}(i).

Démonstration. — En effet, si l’entier i est dans le sous-domaine I_{j}, on a f_{j}(i) = ω_{j}^{−1}f′_{j} ω_{j}(i) = τ_{j}f′_{j} τ_{j}^{−1}(i) où f′_{j} est la restriction de f à I_{j}. Les équivalences ci-dessus résultent alors du fait que τ_{j} : I_{j} → [card I_{j}] est un morphisme strictement croissant.

Récrivons la formule exponentielle (3) et la formule d’inversion (4) dans ce cas particulier du composé partitionnel des applications. On a d’abord F^{(+)} ∩ λ^{−1}n = F_{n} ∩ F^{(+)} pour n ≥ 0 et F ∩ λ^{−1}n = F_{n} ∩ F pour n ≥ 1 et les deux identités (3) et (4) se présentent ainsi

∑_{0≤n} \frac{1}{n!} γ\{F_{n} ∩ F^{(+)}\} = exp(∑_{1≤n} \frac{1}{n!} \{F_{n} ∩ F\});  (5)

(∑_{0≤n} \frac{1}{n!} γ\{F_{n} ∩ F^{(+)}\})^{−1} = ∑_{0≤n} \frac{(−1)^{n}}{n!} \overline{γ}\{F_{n} ∩ F^{(+)}\}.  (6)

En fait, ces deux identités seront appliquées ci-après sous la forme suivante. On suppose donnée une application multiplicative μ : F^{(+)} → Ω (cf. définition 3.8). On forme ensuite l’algèbre sur ℚ du monoïde Ω ; notons \overline{Ω} cette algèbre. On considère enfin l’algèbre \overline{Ω}[[u]] des séries formelles à coefficients dans \overline{Ω} et à une indéterminée u.

Proposition 3.12. — Soit μ : F^{(+)} → Ω une application multiplicative. Dans l’algèbre des séries formelles \overline{Ω}[[u]], on a les identités :

∑_{0≤n} \frac{u^{n}}{n!} μ\{F_{n} ∩ F^{(+)}\} = exp(∑_{1≤n} \frac{u^{n}}{n!} μ\{F_{n} ∩ F\});  (7)

(∑_{0≤n} \frac{u^{n}}{n!} μ\{F_{n} ∩ F^{(+)}\})^{−1} = ∑_{0≤n} \frac{(−u)^{n}}{n!} \overline{μ}\{F_{n} ∩ F^{(+)}\}.  (8)

où \overline{μ}f = (−1)^{z(f)+n}μf pour tout f ∈ F_{n} ∩ F^{(+)} (n ≥ 0).

Démonstration. — Soit μ′ le morphisme de F^{+} dans Ω tel que μ = μ′γ. Désignons par ϕ l’application envoyant tout f ∈ F_{n} ∩ F sur le monôme u^{n}μ′f (n ≥ 0). Comme μ est multiplicative, on a ϕγf = u^{n}μf pour tout f ∈ F_{n} ∩ F^{(+)} (n ≥ 0). Tous les monômes ϕγf où f ∈ F_{n} ∩ F^{(+)} sont donc de degré n (en u). On peut donc prolonger ϕ en un morphisme continu de la ℚ-algèbre large de F^{+} dans \overline{Ω}[[u]]. Appliquant ainsi ϕ aux deux membres des deux identités (5) et (6), on obtient les identités (7) et (8).

5. Applications

Il est évident que si F est l’ensemble C des permutations circulaires, le composé partitionnel C^{(+)} est exactement l’ensemble 𝔖 = ⋃_{0≤n} 𝔖_{n}. On a de plus F_{n} ∩ F^{(+)} = 𝔖_{n} pour n ≥ 0 et F_{n} ∩ F = C_{n} pour n ≥ 1. Enfin, si σ est dans 𝔖_{n}, se rappelant que z(σ) est le nombre des orbites de σ, on voit que le coefficient (−1)^{z(σ)+n} est la signature ϵ(σ) de σ. Dans ces conditions les deux identités (7) et (8) s’écrivent :

∑_{0≤n} \frac{u^{n}}{n!} μ\{𝔖_{n}\} = exp(∑_{1≤n} \frac{u^{n}}{n!} μ\{C_{n}\});  (9)

(∑_{0≤n} \frac{u^{n}}{n!} μ\{𝔖_{n}\})^{−1} = ∑_{0≤n} \frac{(−u)^{n}}{n!} \overline{μ}\{𝔖_{n}\}.  (10)

où \overline{μ}σ = ϵ(σ)μσ pour tout σ ∈ 𝔖. Donnons quelques exemples d’application des formules (9) et (10).

Soit (x_{n})_{n≥1} une suite d’indéterminées commutatives. Si σ est dans 𝔖_{n}, posons μσ = x_{1}^{m_{1}}x_{2}^{m_{2}} … x_{n}^{m_{n}}, où, pour tout k ∈ [ n], l’entier m_{k} est le nombre de cycles de longueur k dans la σ. La fonction μ ainsi définie est multiplicative. Dans ce cas, μ{𝔖_{n}} est le polynôme indicateur de cycles de 𝔖_{n} ou polynôme de Bell (cf. [24] p. 68) et (u^{n}/n!)μ{C_{n}} se réduit à u^{n}x_{n}/n puisque card C_{n} = (n−1)! La formule exponentielle permet donc de retrouver l’expression de la fonction génératrice exponentielle de ces polynômes, à savoir

∑_{0≤n} \frac{u^{n}}{n!} μ\{𝔖_{n}\} = exp(∑_{1≤n} \frac{u^{n}}{n} x_{n}).

Un autre exemple de composé partitionnel est donné par l’ensemble U des applications ultimement idempotentes, c’est-à-dire, pour tout n ≥ 0, des applications f ∈ F_{n} telles que f^{n} = f^{n−1}. Considérons, en effet, pour tout entier n ≥ 1, l’ensemble V_{n} des applications f ∈ F_{n}, dont l’image de la (n − 1)^{ième} itérée f^{n−1} soit réduite à un seul point. Les éléments de V_{n} sont encore appelés arborescences. Posons V = ⋃_{1≤n} V_{n}; il est alors clair que le composé partitionnel de V est l’ensemble U. Posons U_{n} = F_{n} ∩ U pour n ≥ 0 ; on obtient donc pour toute application multiplicative μ : U → Ω, deux identités analogues à (9) et (10) en substituant U_{n} à 𝔖_{n}, V_{n} à C_{n} et en posant \overline{μ}f = (−1)^{z(f)+n} pour tout f ∈ U_{n} (n ≥ 1). On pose naturellement μU_{0} = \overline{μ}U_{0} = 1.

En particulier, prenons pour μ l’application qui envoie sur 1 tout f ∈ U. Comme on a, de façon évidente card V_{n} = n card U_{n−1} pour n ≥ 1, il vient

∑_{0≤n} \frac{u^{n}}{n!} μ\{V_{n}\} = u ∑_{0≤n} \frac{u^{n}}{n!} card U_{n}

et on retrouve, en appliquant la formule (7), ce résultat bien connu : que la série formelle w = ∑_{0≤n}(u^{n}/n!) card U_{n} est solution dans ℚ[[u]] de l’équation w = exp(uw).

Enfin, prenons pour F l’ensemble G de toutes les applications connexes de F. Dans ce cas, le composé partitionnel de G est F tout entier et l’on obtient encore, pour toute application multiplicative μ : F → Ω donnée, deux identités analogues à (9) et à (10).

6. Une identité entre déterminants et permanents

Dans l’énoncé qui suit, Ξ est une matrice infinie Ξ = (ξ_{i,j})_{(i,j=1,2,...)} à coefficients dans un anneau commutatif \overline{Ω} ; on désigne pour tout n ≥ 1 par Ξ_{n} la matrice (ξ_{i,j})_{(1≤i,j≤n)}, par det Ξ_{n} son déterminant et par per Ξ_{n} son permanent.

Théorème 3.13. — Soient a, b et c trois éléments de \overline{Ω} et Ξ une matrice infinie ayant ses coefficients supradiagonaux (resp. diagonaux, resp. infradiagonaux) égaux à a (resp. b, resp. c). On a l’identité

(1 + ∑_{1≤n} \frac{u^{n}}{n!} per Ξ_{n})^{−1} = 1 + ∑_{1≤n} \frac{(−u)^{n}}{n!} det Ξ_{n}.  (11)

Démonstration. — Désignons par ξ_{i,j} les éléments de la matrice Ξ, puis posons μσ = ξ_{1,σ(1)}ξ_{2,σ(2)} … ξ_{n,σ(n)} pour tout σ ∈ 𝔖_{n}. Avec les notations de la propriété 3.11 (en prenant f = σ), on voit que pour un entier i appartenant au sous-domaine (i.e. à l’orbite) I_{j}, on a ξ_{i,σ(i)} = ξ_{τ_{j}(i),f_{j} τ_{j}(i)}. On a ainsi μσ = ∏_{j} ∏_{i} ξ_{i,σ(i)}, où j varie dans [r] et où i, pour j fixé, varie dans I_{j}. Si i est dans I_{j}, l’élément i′ = τ_{j}(i) est dans [card I_{j}] et l’on a, d’après ce qui précède, μσ = ∏_{j} ∏_{i′} ξ_{i′,f_{j}(i′)} = ∏_{j} μf_{j}. L’application μ est donc multiplicative et l’on peut écrire

μ{𝔖_{n}} = ∑_{σ} ξ_{1,σ(1)} ⋯ ξ_{n,σ(n)} = per Ξ_{n};
\overline{μ}\{𝔖_{n}\} = ∑_{σ} ϵ(σ)ξ_{1,σ(1)} ⋯ ξ_{n,σ(n)} = det Ξ_{n}.

Le théorème 3.13 résulte alors de l’identité (10).

Remarque 3.14. — Notons que l’identité (11) n’est pas vraie pour toutes les matrices, mais comme l’a remarque Kittel [18], on peut construire d’autres matrices infinies Ξ que celles considérées dans l’énoncé du théorème 3.13 pour lesquelles l’identité (11) est vérifiée. Par exemple, si la première colonne de la matrice Ξ n’a que des zéros, on a per Ξ_{n} = det Ξ_{n} = 0 pour tout n ≥ 1 et l’identité (11) est trivialement vérifiée.

De même, considérons la matrice Ξ définie par

ξ_{i,j} = \{ \begin{matrix}1, & si 1 ≤ i ≤ j; \\ −(i − 1), & si 1 ≤ i − 1 = j; \\ 0, & si 1 ≤ j ≤ i − 2. \end{matrix}

On obtient facilement per Ξ_{1} = 1 et per Ξ_{n} = 0 pour tout n ≥ 2, ainsi que det Ξ_{n} = n! pour tout n ≥ 1. L’identité (11) est encore vérifiée ; on retrouve en fait l’identité (1 + u)^{−1} = ∑_{0≤n}(−u)^{n}.

6. UNE IDENTITÉ ENTRE DÉTERMINANTS ET PERMANENTS 31

Notons enfin le résultat élémentaire (pour n ≥ 1)

det Ξ_{n} = \{ \begin{matrix}\frac{c(b − a)^{n} − a(b − c)^{n}}{c − a} , & si c ≠ a; \\ = (b − a)^{n−1}(b + (n − 1)a), & si c = a. \end{matrix}

Portant ces valeurs dans la formule (11), on est conduit à l’identité

(1 + ∑_{1≤n} \frac{u^{n}}{n!} per Ξ_{n})^{−1}

= \{ \begin{matrix}\frac{c exp((a − b)u) − a exp((c − b)u)}{c − a}, si c ≠ a; \\ (1 − au) exp((a − b)u), si a ≠ b et c = a. \end{matrix} (12)

CHAPITRE IV

FONCTIONS GÉNÉRATRICES DES POLYNÔMES EULÉRIENS

1. Fonction génératrice exponentielle de ^{0}A_{n}(t), A_{n}(t), B_{n}(t)

Pour σ ∈ 𝔖_{n} (n ≥ 1), nous définissons E′σ ∈ {0, 1}^{n} par la condition E′σ(k) = 1 ou 0 selon que k est ou non un point fixe de σ. De par la définition de E et ΔE on a donc immédiatement : |Eσ| = |E′σ| + |ΔEσ|. Introduisant une nouvelle indéterminée t′, nous posons θ′σ = t′^{|E′σ|}t^{|ΔEσ|} et \overline{A}_{n}(t, t′) = θ′𝔖_{n} (= 1 pour n = 0). Par conséquent, on a

0A_{n}(t) = \overline{A}(t, t); A_{n}(t) = \overline{A}(t, 1);
\overline{A}_{n}(t, 0) = θΔE\{σ ∈ 𝔖_{n} : |E′σ| = 0\} = θΔED_{n} = θED_{n} = B_{n}(t).

(Voir la fin du paragraphe 1 du chapitre II.)

Théorème 4.1. — On a

\overline{A}(t, t′, u) = ∑_{0≤n} \frac{u^{n}}{n!} \overline{A}_{n}(t, t′) = exp(ut′ + C(t, u)),  (1)

où

C(t, u) = ∑_{2≤n} \frac{u^{n}}{n!} t A_{n−1}(t).  (2)

Démonstration. — Que θ′ soit multiplicative découle de la propriété 3.11 et des définitions des vecteurs E′σ et ΔEσ (σ ∈ 𝔖_{n}). Par conséquent, le membre de droite de l’identité (9) du chapitre III devient exp( ∑_{1≤n}(u^{n}/n!) θ′{C_{n}}.

Pour n = 1, on a θ′{C_{n}} = t′ et pour n ≥ 2, d’après les propriétés 2.2 et 2.3, on a : θ′{C_{n}} = θΔE{C_{n}} = t A_{n−1}(t).

Le théorème 4.1 nous a donné une identité sur les polynômes \overline{A}_{n}(t, t′). Nous allons mainteant trouver une formule explicite pour la fonction génératrice \overline{A}(t, t′, u) en utilisant les résultats de la section 6 du chapitre III.

Théorème 4.2. — On a :

\overline{A}(t, t′, u) = ∑_{0≤n} \frac{u}{n!}\overline{A}_{n}(t, t′) = \frac{1 − t}{exp((t − t′)u) − t exp((1 − t′)u)}. (3)

En particulier,

\overline{A}(t, t, u) = ∑_{0≤n} \frac{u^{n}}{n!}^{0}A_{n}(t) = \frac{1 − t}{1 − t exp((1 − t)u)};  (4)

\overline{A}(t, 1, u) = ∑_{0≤n} \frac{u^{n}}{n!} A_{n}(t) = \frac{1 − t}{−t + exp((t − 1)u)};  (5)

\overline{A}(t, 0, u) = ∑_{0≤n} \frac{u^{n}}{n!} B_{n}(t) = \frac{1 − t}{exp(ut) − t exp(u)}.  (6)

Démonstration. — Avec les notations du théorème 3.13, si l’on pose a = t, b = t′ et c = 1, on a pour σ ∈ 𝔖_{n} (n ≥ 1) l’égalité ξ_{1,σ(1)} … ξ_{n,σ(n)} = θ′σ; soit \overline{A}_{n}(t, t′) = per Ξ_{n}. La première identité résulte donc de la formule (11) du chapitre III. En posant successivement t′ = t, puis t′ = 1, enfin t′ = 0, on obtient les trois suivantes.

Remarque 4.3. — Ces formules peuvent aussi s’obtenir par le procédé suivant. D’après la propriété 2.2, on a ^{0}A_{n}(t) = t A_{n}(t) pour tout n ≥ 1 ; on en tire

\overline{A}(t, t, u) = ∑_{0≤n} \frac{u^{n}}{n!}^{0}A_{n}(t) = 1 + t ∑_{1≤n} \frac{u^{n}}{n!} A_{n}(t),

soit

\overline{A}(t, t, u) = 1 + t(\overline{A}(t, 1, u) − 1). (7)

D’autre part, d’après le théorème 4.1 on a

exp(C(t, u)) = \overline{A}(t, 1, u) exp(−u) (8)

ou encore

\overline{A}(t, t, u) = exp(ut − u)\overline{A}(t, 1, u). (9)

Du système formé par les deux équations (7) et (9), on déduit immédiatement les identités (4) et (5). On calcule ensuite C(t, u) en utilisant la formule (8) et l’on en tire l’identité (3) en se servant du théorème 4.1.

Remarque 4.4. — Les formules (4) et (5) sont connues (cf. Riordan [24], p. 215 et 39). La formule (6) a été obtenue par Roselle [25], par les méthodes traditionnelles du calcul différentiel et intégral, dans le cas particulier où B_{n}(t) = θMG_{n} (n ≥ 1).

Notons encore que du théorème 4.1 résulte immédiatement, par simple dérivation, que la fonction génératrice A = \overline{A}(t, 1, u) est solution de l’équation différentielle de Bernoulli :

\frac{∂}{∂u}A = A(1 + t(A − 1)).

On peut aussi prouver ce résultat directement et pour ce faire, nous ferons la convention suivante que nous utiliserons encore dans la section 2 : si σ est dans 𝔖_{n} (n ≥ 1), on considère σw comme le mot σ(1)σ(2) … σ(n) dont les lettres sont les éléments de [ n] ; lorsque σ est l’élément unique σ_{0} ∈ 𝔖_{0}, alors σw est le mot vide σ_{0}w. Si f = y_{1}y_{2} … y_{m} est un mot dont les lettres y_{1}, y_{2}, …, y_{m} sont des entiers tous distincts, on désigne par ω l’unique morphisme surjectif ω : {y_{1}, y_{2}, …, y_{m}} → [ m] et l’on note ωf le mot ωy_{1} ωy_{2} … ω y_{m}. On pose encore ωσ_{0}w = σ_{0}w.

Prenons alors un mot σw ∈ 𝔖_{n+1} (n ≥ 0) ; il s’écrit univoquement σw = f(n + 1)f′. Considérons l’application σw ↦ (ωf, ωf′) ; on a ωf ∈ 𝔖_{m} et ωf′ ∈ 𝔖_{n−m} pour un certain m tel que 0 ≤ m ≤ n et puisque ω est un morphisme strictement croissant, on a encore

|ΔDσ| + δ_{n,m} = |ΔDωf| + |ΔDωf′| + 1

où, comme d’usage, δ_{n,m} = 1 ou 0 selon que m = n ou m ≠ n. D’autre part, l’image réciproque par l’application ci-dessus du couple (τw, τ′w) où τ ∈ 𝔖_{m} et τ′ ∈ 𝔖_{n−m}, contient \binom{n}{m} éléments. On en déduit :

A_{n+1}(t) = A_{n}(t) + t ∑_{0≤m≤n−1} \binom{n}{m}A_{m}(t)A_{n−m}(t) (n ≥ 0).

Il en résulte que la fonction génératrice A = \overline{A}(t, 1, u) est bien solution de l’équation différentielle précédente. Ce résultat a été établi pour la première fois par Riordan [23].

2. Fonction génératrice exponentielle des polynômes ^{r}A_{n}(t)

Pour r ≥ 1 posons

rA_{n}(t, u) = ∑_{r−1≤n} \frac{u^{n−r+1}}{(n − r + 1)!} ^{r}A_{n}(t).

On a en particulier ^{1}A(t, u) = \overline{A}(t, 1, u), dont on connaît déjà la formule explicite (cf. (5)). Le but de la présente section est d’établir l’identité remarquable suivante, due à Riordan ([24] p. 235)

rA(t, u) = (r − 1)! (^{1}A(t, u))^{r}.

Construction d’une bijection de ⋃_{0≤n}𝔖_{n+r−1} sur 𝔖_{r−1} × 𝔖^{((r))}. — Il s’agit

d’une bijection sur le produit cartésien de 𝔖_{r−1} par le composé partitionnel marqué 𝔖^{((r))} (r ≥ 1). Pour définir ce dernier, il faut munir l’ensemble 𝔖 d’une application λ; nous prenons naturellement l’application définie par

λσ = n ⇔ σ ∈ 𝔖_{n} (n ∈ ℕ).

Notons que l’élément unique σ_{0} ∈ 𝔖_{0} appartient à 𝔖, satisfait à λσ_{0} = 0 et est distinct de l’élément neutre e du monoïde 𝔖^{∗} pour lequel on a aussi λe = 0.

2. FONCTION GÉNÉRATRICE EXPONENTIELLE DES POLYNÔMES 35

Soit maintenant σ ∈ 𝔖_{n+r−1} (0 ≤ n) ; le mot σw s’écrit univoquement σw = g_{1}i_{1}g_{2}i_{2} … g_{r−1}i_{r−1}g_{r} où {i_{1}, i_{2}, …, i_{r}} = [r − 1] et où g_{1}, g_{2}, …, g_{r} sont des mots (éventuellement vides) dont les lettres sont des entiers. Soient I_{1}, I_{2}, …, I_{r} les sous-ensembles de ℕ dont les éléments sont respectivement les lettres des mots g_{1}, g_{2}, …, g_{r}. Posant σ_{j}w = ωg_{j} pour chaque j ∈ [r] (où ω est le morphisme défini à la fin de la section précédente et où l’on a σ_{r} = σ_{0} si le mot g_{j} est vide), on voit immédiatement que le mot

h = (σ_{1}, I_{1})(σ_{2}, I_{2}) … (σ_{r}, I_{r})

est un élément du composé partitionnel 𝔖^{((r))}.

On note β′σ (= βh dans les notations du chapitre III) le mot σ_{1}σ_{2} … σ_{r} ∈ 𝔖^{∗} de longueur r. Soit ensuite \overline{σ} la permutation définie par \overline{σ} = i_{1}i_{2} … i_{r−1}. On a \overline{σ} ∈ 𝔖_{r−1} et comme λh = λβ′σ = λσ_{1} +⋯+λσ_{r} = λσ −(r−1) = n, on voit que l’application σ ↦ (\overline{σ}, h) envoie 𝔖_{n+r−1} dans 𝔖_{r−1} × 𝔖^{((r))} ∩ λ^{−1}n. Il est d’autre part immédiat de vérifier que cette application est bijective. Ceci achève la construction de la bijection cherchée.

Maintenant, puisque card 𝔖_{r−1} est égal à (r − 1)!, on peut écrire

∑\{\frac{β′σ}{(λσ − r + 1)!} : σ ∈ ⋃_{0≤n} 𝔖_{n+r−1}\} = (r − 1)! ∑\{\frac{βh}{λh!} : h ∈ 𝔖^{((r))}\}

= (r − 1)! (∑\{\frac{σ}{λσ!} : σ ∈ 𝔖\})^{r},

d’après le théorème 3.2. Notant ϖ_{r}σ l’image abélienne de β′σ, on obtient l’identité suivante valable dans l’algèbre large sur ℚ du monoïde abélien 𝔖^{+}

∑\{\frac{ϖ_{r}(σ)}{(λσ − r + 1)!} : σ ∈ ⋃_{0≤n} 𝔖_{n+r−1}\} = (r − 1)! (∑\{\frac{σ}{λσ!} : σ ∈𝔖\})^{r}. (10)

Soient enfin μ : 𝔖^{+} → Ω un morphisme dans un monoïde abélien Ω et u une indéterminée. Comme déjà vu au chapitre III, on vérifie que l’application σ ↦ u^{λσ}μσ (σ ∈ 𝔖) peut être prolongée en un morphisme continu ϕ de la ℚ-algèbre large de 𝔖^{+} dans \overline{Ω}[[u]]. Appliquant ϕ aux deux membres de l’identité (10), on trouve

∑_{0≤n} \frac{u^{n}}{n!} μϖ_{r}\{𝔖_{n+r−1}\} = (r − 1)! (∑_{0≤n} \frac{u^{n}}{n!} μ\{𝔖_{n}\})^{r}.  (11)

Théorème 4.5. — Pour r ≥ 1 on a : ^{r}A(t, u) = (r − 1)! (^{1}A(t, u))^{r}. Démonstration. — Pour r = 1, il n’y a rien à prouver. Supposons r ≥ 2 et

prenons pour μ le morphisme prolongeant l’application σ ↦ θΔDσ = t^{|ΔDσ|} au monoïde 𝔖^{+}. Si l’on a σ ∈ 𝔖_{n+r−1} et σw = g_{1}i_{1}g_{2}i_{2} … g_{r−1}i_{r−1}g_{r} avec {i_{1}, i_{2}, …, i_{r−1}} = [r − 1], il vient |ΔDg_{j}| = |ΔDωg_{j}| (j ∈ [r]), puisque ω est un morphisme injectif. D’autre part, puisque le mot g_{1}g_{2}, … g_{r} contient toutes les lettres du mot σw supérieures ou égales à r, on a |Δ′^{r−1}ΔDσ| = ∑_{j} |ΔDωg_{j}|, d’où μϖ_{r}σ = θΔ′^{r−1}ΔDσ. On obtient alors, d’après la propriété 2.2, μϖ_{r}{𝔖_{n+r−1}} = ^{r}A_{n+r−1}(t). Comme on a d’autre part μ{𝔖_{n}} = A_{n}(t), le théorème 4.5 résulte de l’identité (11).

3. Autres interprétations des polynômes eulériens

Les techniques du chapitre précédent pourraient être appliquées à d’autres problèmes d’énumération. Par exemple, au lieu d’introduire la fonction multiplicative θ′ du paragraphe 1, on peut, pour chaque σ ∈ 𝔖_{n} (n ≥ 1), poser μσ = θ′σ · r^{z(σ)}, où r est une indéterminée et où z(σ) est le nombre de cycles de σ. La fonction μ est évidemment multiplicative et l’on peut appliquer la proposition 3.12. De plus, on a, comme dans la démonstration du théorème 4.1

μ{C_{n}} = t′ r,  pour n = 1 ;
= r θΔEC_{n} = r t A_{n−1}(t),  pour n ≥ 2.

La proposition 3.12 conduit donc à l’identité, dans laquelle μ{𝔖_{0}} = 1,

∑_{0≤n} \frac{u^{n}}{n!} μ\{𝔖_{n}\} = exp(r(ut′ + ∑_{2≤n} \frac{u^{n}}{n!} t A_{n−1}(t))).  (12)

Le membre de gauche de cette dernière identité est la fonction génératrice exponentielle des permutations classées à la fois par nombre de cycles et par nombre d’excédances. Maintenant les identités (3) et (12), ainsi que le théorème 4.1 permettent d’écrire, lorsque r est un entier positif,

∑_{0≤n} \frac{u^{n}}{n!} μ\{𝔖_{n}\} = ( \overline{A}(t, t′, u))^{r}.  (13)

On obtient donc d’après (3) la formule explicite de cette fonction génératrice exponentielle.

Si nous posons identiquement t′ = 1, nous obtenons

μ{𝔖_{n}} = ∑{t^{|ΔEσ|}r^{z(σ)} : σ ∈ 𝔖_{n}}

que nous désignons par Q_{n}(t, r) (n ≥ 1). On posera également Q_{0}(t, r) = 1. Il résulte de (13) que l’on a, lorsque r est un entier positif,

(r − 1)! ∑_{0≤n} \frac{u^{n}}{n!} Q_{n}(t, r) = (r − 1)! (^{1}A(t, u))^{r}
= ^{r}A(t, u)  [d’après le théorème 4.5]

= ∑_{0≤n} \frac{u^{n}}{n!} ^{r}A_{n+r−1}(t).

On en déduit une nouvelle inteerprétation des polynômes ^{r}A_{n}(t), à savoir

rA_{n+r−1}(t) = (r − 1)! Q_{n}(t, r) (r ≥ 1).  (14)

Enfin, désignons par s(σ) le nombre des éléments saillants de la suite σw où σ ∈ 𝔖_{n} (n ≥ 1). Comme l’on a |Mσ̂| + |ΔEσ| = n et s(σ̂) = z(σ), on obtient

∑{t^{|Mσ|}r^{s(σ)} : σ ∈ 𝔖_{n}} = t^{n} ∑{t^{−|ΔEσ|}r^{z(σ)} : σ ∈ 𝔖_{n}}
= t^{n} Q_{n}(t^{−1}, r).  (15)

Le premier membre de l’identité (15) est le polynôme générateur des permutations σ ∈ 𝔖_{n} classées à la fois suivant leur nombre d’éléments saillants et leur nombre de montées. Ce polynôme générateur a été considéré pour la première fois par Dillon et Roselle [10] qui ont à son sujet prouvé un certain nombre d’identités, qu’on pourrait retrouver à partir des formules (14) et (15) et des résultats de ce chapitre.

Enfin, notons que la propriété 2.6 fait apparaître que les coefficents des polynômes ^{r}A_{n}(t) snt tous divisibles par r! (ce que ne fait pas apparaître le théorème 4.5). Si on donc on pose

rA_{n}(t) = r!^{r}P_{n}(t),

il semble intéressant d’obtenir une interprétation pour les polynômes ^{r}P_{n}(t) (0 ≤ r ≤ n).

D’abord, si r = n, on a ^{r}P_{n}(t) = 1 et pour r = 0 et 1, on a ^{r}P_{n}(t) = ^{r}A_{n}(t). On fait donc l’hypothèse 2 ≤ r ≤ n−1. La restriction de tout σ ∈ 𝔖_{n} à [n−r] est une injection de [n − r] dans [ n] que nous noterons ϕσ. L’application ϕ est évidemment une surjection de 𝔖_{n} sur l’ensemble I_{n−r,n} des injections de [n − r] dans [ n] telle que l’image inverse de tout τ ∈ I_{n−r,n} a r! éléments. Introduisons l’application Λ de ℕ^{p} (p ≥ 1) dans lui-même envoyant chaque vecteur (x_{1}x_{2}, …, x_{p}) sur ((x_{1} − 1)_{+}, (x_{2} − 1)_{+}, …, (x_{p} − 1)_{+}). On a ainsi Δ = Δ′′Λ = ΛΔ′′ et Δ^{r} = Δ′′^{r}Λ^{r} pour r ≥ 1. Définissant le vecteurexcédance d’une injection de façon évidente, on a ainsi

Δ^{r}Eσ = ((σ(1) − r)_{+}, …, (σ(n − r))_{+}) = Λ^{r}Eϕσ.

D’où l’on déduit Δ^{r}E𝔖_{n} = r! Λ^{r}E I_{n−r,n} et par suite

rA_{n}(t) \frac{1}{r!} = ^{r}P_{n}(t) = θΛ^{r}E I_{n−r,n}.

Cette dernière interprétation des polynômes ^{r}A_{n}(t)/r! est due à Strosser [28].

CHAPITRE V

LES SOMMES ALTERNÉES A_{n}(−1) ET B_{n}(−1)

1. Distribution du nombre des descentes sur 𝔖′_{n}

Nous attachons à chaque σ ∈ 𝔖′_{n} (= {σ ∈ 𝔖_{n} : σ(1) = n}) un mot noté V (σ) = v_{1}v_{2} … v_{n} dans les lettres de l’alphabet X = \{m, \overline{m}, d, \overline{d}\} par les règles suivantes, où, par définition, σ(n + 1) = σ(1) ( = n).

(1) Pour chaque j ∈ [ n], on a v_{j} ∈ \{d, \overline{d}\} ou v_{j} ∈ \{m, \overline{m}\} selon que σ(j) > σ(j + 1) ou σ(j) < σ(j + 1) ;

(2) si v_{j} ∈ \{d, \overline{d}\}, j ∈ [n − 1], on a v_{j} = d ou \overline{d} selon que v_{j+1} est dans \{d, \overline{d}\} ou dans \{m, \overline{m}\};

(3) si v_{j} ∈ \{m, \overline{m}\}, (2 ≤ j ≤ n), on a v_{j} = m ou \overline{m} selon que v_{j−1} est dans \{m, \overline{m}\} ou dans \{d, \overline{d}\}.

En raison de σ(1) = σ(n + 1) = n, on a toujours v_{1} ∈ \{d, \overline{d}\}, v_{n} ∈ \{m, \overline{m}\} et les seules occurrences des lettres \overline{d} et \overline{m} se rencontrent dans les facteurs v_{j}v_{j+1} = \overline{d} \overline{m} correspondant aux indices j ∈ [n − 1] tels que σ(j) > σ(j + 1) < σ(j + 2). Par exemple, pour σ(w) = (7, 1, 4, 6, 3, 2, 5), on aurait V (σ) = \overline{d} \overline{m} m d \overline{d} \overline{m} m.

Introduisons maintenant pour tout lettre x et tout mot g la dérivation g (∂/∂x) envoyant chaque mot f = x_{1}x_{2} … x_{p} sur l’ensemble pondéré formé de tous les mots obtenus en remplaçant dans f chaque occurrence de la lettre x par le mot g. Formellement, g (∂/∂x) est l’opérateur linéaire défini par sa restriction à X, à savoir

(g \frac{∂}{∂x})x′ = \{ \begin{matrix}g, & si x′ = x; \\ x′, & si x′ ∈ X \ \{x\}; \end{matrix}

et par l’identité

(g \frac{∂}{∂x})ff′ = (g \frac{∂}{∂x})f · f′ + f · (g \frac{∂}{∂x})f′.

Donc si f = f_{1}xf_{2}x … f_{r−1}xf_{r}, où les f_{i} ne contiennent pas la lettre x, l’on aura :

(g \frac{∂}{∂x})f = f_{1}gf_{2}x … f_{r−1}xf_{r} +f_{1}xf_{2}g … f_{r−1}xf_{r} +⋯+f_{1}xf_{2}x … f_{r−1}gf_{r}.

Par exemple, on a :

(\overline{d} \overline{m}\frac{∂}{∂m})(\overline{d} \overline{m} m d \overline{d} \overline{m} m) = \overline{d} \overline{m} \overline{d} \overline{m} d \overline{d} \overline{m} m + \overline{d} \overline{m} m d \overline{d} \overline{m} \overline{d} \overline{m}.

Lemme 5.1. — Soit

∇ = (d \overline{d} \frac{∂}{∂\overline{d}}) + (\overline{m} m \frac{∂}{∂ \overline{m}}) + (\overline{d} \overline{m}\frac{∂}{∂d}) + (\overline{d} \overline{m} \frac{∂}{∂m}).

On a identiquement : V 𝔖′_{n} = ∇ V 𝔖′_{n−1} (n ≥ 2).

Démonstration. — Il existe une bijection de 𝔖′_{n−1}×[ n] sur 𝔖′_{n−1} envoyant chaque (σ′, k) ∈ 𝔖′_{n−1} × [ n] sur la permutation σ ∈ 𝔖′_{n} telle que σw soit obtenue en ajoutant 1 à tous les chiffres de σ′w et en insérant 1 entre le k^{ième} et le (k + 1)^{ième} terme de σ′w. Soit V (σ′) = v′_{1}v′_{2} … v′_{n−1} et supposons v′_{k} ∈ \{d, \overline{d}\} c’est-à-dire 1 ≤ k ≤ n − 1 et σ′(k) > σ′(k + 1). On a σ(k) = 1 + σ′(k) > σ(k + 1) = 1 < σ(k + 2) = 1 + σ′(k + 1), donnant dans V (σ) le facteur v_{k}v_{k+1} = \overline{d} \overline{m}. Maintenant :

(i) si v′_{k} = \overline{d}, c’est-à-dire si v′_{k+1} = \overline{m} et σ′(k + 1) < σ′(k + 2), on a v_{k+2} = m puisque σ(k +2) = 1+σ′(k +1) < σ(k +3) = 1+σ′(k +2) et toute l’opération équivaut au remplacement de v′_{k+1} = \overline{m} par v_{k+1}v_{k+2} = \overline{m} m. Remarquons qu’avec nos conventions, si k = n − 2, on a σ′(k + 2) = σ′(n) = σ′(1) = n − 1.

(ii) si v′_{k} = d, c’est-à-dire si σ′(k+1) < σ′(k+2), on a encore v_{k+2} ∈ \{d, \overline{d}\} et V (σ) est déduit de V (σ′) en remplaçant v′_{k} = d par v_{k}v_{k=1} = \overline{d} \overline{m}. Un raisonnement analogue s’applique si v′_{k} = m ou \overline{m}.

Notons maintenant α le morphisme canonique envoyant le monoïde libre engendré par \{m, \overline{m}, d, \overline{d}\} sur le monoïde commutatif libre de même base.

Théorème 5.2. — Il existe des entiers positifs c_{n,k} tels que

αV 𝔖′_{n} = ∑_{2≤2k≤n} c_{n,k} (\overline{d} \overline{m})^{k} (d + m)^{n−2k} (n ≥ 2).

Démonstration. — Pour n = 2, on a V 𝔖′_{n} = \overline{d} \overline{m} et le résultat s’en déduit par induction sur n puisque ∇ commute avec α.

Remarque 5.3. — Les coefficients c_{n,k} des polynômes αV 𝔖′_{n} obéissent à des relations de récurrence qu’il est facile d’établir. Posons, par convention, c_{n,k} = 0 si k ≤ 0 ou si 2k ≥ n + 1 ; on alors les deux relations :

c_{2,1} = 1 et pour n ≥ 3, k ≥ 1,
c_{n,k} = kc_{n−1,k} + 2(n + 1 − 2k)c_{n−1,k−1}.

Remarque 5.4. — La fonction génératrice des nombres c_{n,k} est donnée par Barton & David ([3] p. 180, voir aussi [17]). La théorie de ces auteurs se rattache aux considérations présentes en utilisant l’observation suivante dont la démonstration est laissée au lecteur.

Pour σ ∈ 𝔖_{n−1}, soit σ′ ∈ 𝔖′_{n} définie par σ′(1) = n, σ′(1 + j) = n + 1 − σ(n − j). Le nombre des facteurs d ou \overline{d} de V (σ′) surpasse de 1 le nombre des j ∈ [n−1] tels que σ(j) > σ(j−1) et le nombre de facteurs \overline{d} \overline{m} de V (σ′) est égal au nombre des j ∈ [n − 2] tels que σ(j) > σ(j + 1) < σ(j + 2), augmenté d’une unité.

2. Applications aux polynômes eulériens

Le théorème 5.2 va nous permettre de donner une interprétation combinatoire aux nombres A_{n}(−1). Il est commode, tout d’abord, de noter la relation suivante sur les cardinaux des ensembles T_{n} des permutations alternées (cf. chap. I, § 9).

Propriété 2.5. — Pour p ≥ 1, on a : card T_{2p−1} = card T_{2p} ∩ 𝔖′_{2p}. Démonstration. — En effet, l’application qui envoie chaque σ′ ∈ 𝔖′_{n}

telle que V (σ′) = (\overline{d} \overline{m})^{p} (n = 2p ≥ 2) sur l’élément σ ∈ 𝔖_{n−1} défini par σ(j) = σ′(j + 1) (j ∈ [n − 1]), est une bijection sur T_{n−1}. D’autre part, il est clair que l’on a : T_{2p} ∩ 𝔖′_{2p} = \{σ′ ∈ 𝔖′_{2p} : V (σ′) = (\overline{d} \overline{m})^{p}\}.

Théorème 5.6. — Pour n ≥ 2 on a l’identité :

t A_{n−1}(t) = ∑_{2≤2k≤n} c_{n,k} t^{k}(1 + t)^{n−2k}. (1)

De plus, pour n ≥ 1, on a :

A_{2p}(−1) = 0 et (−1)^{p−1} A_{2p−1}(−1) = card T_{2p−1}.

Démonstration. — Pour σ′ ∈ 𝔖′_{n}, le nombre des occurrences des lettres d ou \overline{d} dans V (σ′) est égal à |ΔDσ′|, puisque l’on a v_{n} ∈ \{m, \overline{m}\}. Or d’après les propriétés 2.2 et 2.3, on a θΔD𝔖′_{n} = ^{0}A_{n−1}(t) = t A_{n−1}(t). On en déduit que t A_{n−1}(t) est obtenu en faisant d = \overline{d} = t et m = \overline{m} = 1 dans θV 𝔖′_{n}. La formule (1) résulte alros du théorème 5.2.

D’autre part, le second membre de la formule (1) admet le facteur (1 + t) si n est impair. On en conclut que A_{2p}(−1) est nul pour p ≥ 1. Au contraire, pour n = 2p ≥ 2, on voit que c_{2p,p} = (−1)^{p−1}A_{2p−1}(−1). Or

c_{2p,p} = card\{σ′ ∈ 𝔖′_{2p} : V (σ′) = (\overline{m} \overline{d})^{p}\} = card T_{2p} ∩ 𝔖′_{2p} = card T_{2p−1},

d’après la propriété 5.5. Le théorème 5.6 en résulte.

3. Applications aux polynômes B_{n}(t)

Nous donnons enfin des identités analogues à celles du théorème 4.6, concernant les polynômes B_{n}(t) = θED_{n} = θMG_{n}, où comme précédemment

D_{n} = {σ ∈ 𝔖_{n} : σ(j) ≠ j}; G_{n} = {σ ∈ 𝔖_{n} : 1 ≠ σ(1), 1 + σ(j) ≠ σ(j + 1)}.

Pour démontrer le théorème 5.9 ci-dessous, nous allons de nouveau appliquer la formule exponentielle et utiliser les propriétés élémentaires des permutations et de la transformation fondamentale du chapitre I. Pour n = 2p ≥ 2 et σ ∈ 𝔖_{n}, nous posons μσ = 1 si et seulement si σ est biexcédée, c’est-à-dire si σ ∈ B (cf. chap. 1, § 9) et μσ = 0 dans les autres cas.

Lemme 5.7. — L’application μ est multiplicative. En d’autres termes, σ est une permutation biexcédée, si tous les termes de sa factorisation canonique sont aussi des permutations biexcédes.

Démonstration. — Ce lemme résulte encore de la propriété 3.11. Soit σ_{1}σ_{2} … σ_{r} la décomposition en produit de cycles disjoints d’une permutation σ ∈ B et (f_{1}, I_{1})(f_{2}I_{2}) ⋯ (f_{r}, I_{r}) sa factorisation canonique. Avec les mêmes notations que dans la propriété 3.11, on a f_{j} = τ_{j}σ_{j}τ_{j}^{−1} (j ∈ [r]). Par suite, i < σ(i) ⇔ τ_{j}(i) < f_{j}τ_{j}(i) et i < σ^{−1}(i) ⇔ σσ^{−1}(i) < σ^{−1}(i) ⇔ f_{j}τ_{j}σ^{−1}(i) < τ_{j}σ^{−1}(i) ⇔ τ_{j}(i) < f_{j}^{−1}τ_{j}(i), puisque les entiers i et σ^{−1}(i) appartiennent à la même orbite. On a les mêmes équivalences en remplaçant le symbole “<” par “>”.

Lemme 5.8. — Pour p ≥ 1 on a :

μ{𝔖_{2p}} = card B_{2p} et μ{𝔖_{2p−1}} = μ{C_{2p−1}} = 0; (2) μ{C_{2p}} = card B_{2p} ∩ C_{2p} = card T_{2p} ∩ 𝔖′_{2p}. (3)

Démonstration. — Les relations (2) résultent de la définition de μ et de la proposition 1.14. D’après la propriété 1.10 et la proposition 1.14, la transformation fondamentale σ ↦ σ̂ est une bijection de B_{2p} ∩ C_{2p} sur T_{2p} ∩ 𝔖′_{2p}. La relation (3) est ainsi vérifiée.

Pour la démonstration du théorème ci-dessous, l’utilisation des nombres complexes est une simple commodité d’écriture évitant de recourir au produit d’Hadamard.

Théorème 5.9. — Pour p ≥ 1 on a :

B_{2p−1}(−1) = 0 et (−1)^{p}B_{2p}(−1) = card T_{2p}.

Démonstration. — On applique la formule (9) du chapitre III avec l’application multiplicative μ du lemme 5.7. D’après (2), le premier membre de cette formule s’écrit : 1+ ∑_{1≤n}(u^{n}/n!) card B_{n}. Maintenant pour p ≥ 1 on a

μ{C_{2p}} = card T_{2p} ∩ 𝔖′_{2p}  [d’après (3)]
= card T_{2p−1}  [d’après la propriété 5.5]
= (−1)^{p−1}A_{2p−1}(−1). [d’après le théorème 5.6]

Compte-tenu de la relation (2) le second membre de la formule (9) du chapitre III s’écrit donc

exp(∑_{1≤p} \frac{u^{2p}}{(2p)!} (−1)^{p−1}A_{2p−1}(−1)).

En utilisant le fait que A_{n}(−1) = 0 si n est pair, on en déduit :

∑_{0≤n} \frac{u^{n}}{n!} card B_{n} = exp(∑_{2≤n} \frac{(iu)^{n}}{n!} (−1)A_{n−1}(−1)),

où i est le nombre complexe de module 1 et d’argument π/2. Or le membre de droite de cette dernière équation est la valeur pour t = −1 de l’expression

exp(∑_{2≤n} \frac{(iu)^{n}}{n!} t A_{n−1}(t)),

qui d’après le théorème 4.1 est égale à

∑_{0≤n} \frac{(iu)^{n}}{n!} B_{n}(t).

En identifiant terme à terme, il en résulte que l’on a B_{n}(−1) = 0 si n est impair et que pour n = 2p, on a (−1)^{p} B_{2p}(−1) = card B_{2p} = card T_{2p} d’après la proposition 1.14.

4. Les développements de tg u et de 1/ cos u

De l’identité (5) du théorème 4.2, on tire

∑_{0≤n} \frac{(iu)^{n}}{n!} A_{n}(−1) = \frac{2}{1 + e^{−2iu}} ,

qu’on peut récrire

∑_{1≤n} \frac{u(iu)^{n−1}}{n!} A_{n}(−1) = \frac{1 − e^{−2iu}}{i(1 + e^{−2iu})} = tg u,

soit, en utilisant le théorème 5.6,

tg u = ∑_{1≤p} \frac{u^{2p−1}}{(2p − 1)!} card T_{2p−1}. (4)

De même, d’après l’identité (6) du théorème 4.2, on a

∑_{0≤n} \frac{(iu)^{n}}{n!} B_{n}(−1) = \frac{2}{e^{−iu} + e^{iu}} = \frac{1}{cos u}.

D’après le théorème 5.9, on déduit donc :

\frac{1}{cos u} = 1 + ∑_{1≤p} \frac{u^{2p}}{(2p)!} card T_{2p}. (5)

Les identités (4) et (5) sont dues à Désiré André [1]. Nous avons pu les établir ici sans recourir aux méthodes traditionnelles du calcul différentiel et intégral, en n’utilisant que l’identité de Cauchy et des constructions sur la catégorie des ensembles totalement ordonnés finis.

Nous laissons au lecteur l’amusement de vérifier par les mêmes techniques la formule élémentaire

\frac{1}{cos u} = exp(∫ tg u du)

en utilisant une définition appropriée de l’intégrale.

5. Table des nombres d’Euler

On a souvent appelé nombres d’Euler les coefficients du développement de tg u et de 1/ cos u. Les valeurs numériques de ces premiers coefficients ont déjà été obtenues par Euler lui-même (voir [16], p. 299–301). Nous reproduisons ci-dessous ces premières valeurs. Rappelons que pour n ≥ 1 on note T_{n} le sous-ensemble de 𝔖_{n} formé par les permutations alternées, qu’on a ensuite les identités

(−1)^{p−1} A_{2p−1}(−1) = card T_{2p−1}; (−1)^{p−1} B_{2p}(−1) = card T_{2p} (p ≥ 1).

Le tableau des quantités t_{n} = card T_{n} pour n = 1, 2, …, 14 est alors le suivant.

\begin{matrix}n & t_{n} \\ 1 & 1 \\ 2 & 1 \\ 3 & 2 \\ 4 & 5 \\ 5 & 16 \\ 6 & 61 \\ 7 & 272 \\ 8 & 1385 \\ 9 & 7936 \\ 10 & 50521 \\ 11 & 353792 \\ 12 & 2702765 \\ 13 & 22368256 \\ 14 & 199360981 \end{matrix}

BIBLIOGRAPHIE

[1] Désiré André. — Dévelopements de sec x et de tang x, C. R. Acad. Sc. Paris, t. 88, 1879, p. 965–967.

[2] Désiré André. — Mémoire sur le nombre des permutations alternées, Journal de Math., t. 7, 1881, p. 167.

[3] D. E. Barton, F. N. David. — Combinatorial Chance. — Griffin, London, 1962.

[4] L. Carlitz. — Eulerian numbers and polynomials, Math. Magazine, t. 32, 1959, p. 247–260.

[5] L. Carlitz. — Eulerian numbers and polynomials of higher order, Duke Math. J., t. 27, 1960, p. 401–423.

[6] L. Carlitz. — A note on Eulerian numbers, Arch . Math., t. 14, 1963, p. 383–390.

[7] L. Carlitz, J. Riordan. — Congruences for Eulerian Numbers, Duke Math. J., t. 20, 1953, p. 339–343.

[8] L. Carlitz, D. P. Roselle and R. A. Scoville. — Permutations and Sequences with Repetitions by Number of Increases, J. Combin. Theory, t. 1, 1966, p. 350–374.

[9] P. Cartier, D. Foata. — Problèmes combinatoires de commutation et réarrangements. Lecture Notes in Math., no. 85, Springer-Verlag, Berlin, 1969.

[10] J. F. Dillon, D. P. Roselle. — Eulerian numbers of higher order, Duke Math. J., t. 35, 1968, p. 247–256.

[11] R. C. Entringer. — A combinatorial interpretation of the Euler and Bernoulli numbers, Nieuw Arch. V. Wiskunde, t. 14, 1966, p. 241–246.

[12] Dominique Foata. — É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.

[13] G. Frobenius. — Über die Bernoullischen Zahlen und die Eulerschen Polynome, Sitz. Berichte Preuss. Akad. Wiss., 1910, p. 808–847.

[14] R. Frucht. — A combinatorial approach to the Bell polynomials and their generalizations. Recent Progress in Combinatorics (W. T. Tutte, ed.), Academic Press, London and New York, 1964, p. 69–74.

[15] R. Frucht, G.-C. Rota. — Polynomios de Bell y partitiones de conjuntos finitos, Scientia, t. 126, 1965, p. 5–10.

[16] Ch. Jordan. — Calclulus of finite differences. — Röttig & Romwalter, Budapest, 1939.

[17] W.O. Kermack, A.G. McKendrick. — Some distributions associated with a randomly arranged set of numbers, Proc. Roy. Soc. Edinburgh Sec. A., t. 57, 1937, p. 332–376.

[18] B. Kittel. — Communication privée.

[19] P. A. MacMahon. — Second memoir on the composition of numbers, Phil. Trans. Royal Soc. London, A, t. 207, 1908, p. 65–134.

[20] P. A. MacMahon. — Combinatory Analysis, vol. 1 and 2. — Cambridge, Cambridge Univ. Press, 1915, (Reprinted by Chelsea, New York, 1955).

[21] E. Netto. — Lehrbuch der Combinatorik. — B. G. Teubner, Leipzig, 1900.

[22] F. Poussin. — Sur une propriété arithmétique de certains polynômes associés aux nombres d’Euler, C. R. Acad. Sc. Paris, t. 266, 1968, p. 392–393.

[23] J. Riordan. — Triangular permutation numbers, Proc. Amer. Math. Soc., t. 2, 1951, p. 404–407.

[24] J. Riordan. — An Introduction to Combinatorial Analysis. — New York, J. Wiley, 1958.

[25] D. P. Roselle. — Permutations by number of rises and successions, Proc. Amer. Math. Soc., t. 19, 1968, p. 8–16.

[26] G.-C. Rota. — On the foundations of Combinatorial Theory,, J. Wahrscheinlichkeitstheorie, t. 2, 1966, p. 340–368.

[27] E. B. Shanks. — Iterated sums of powers of binomial coefficients, Amer. Math. Monthly, t. 58, 1951, p. 404–407.

[28] R. Strosser. — Séminaire de théorie combinatoire, I.R.M.A., Université de Strasbourg, 1969–1970.

[29] G. E. Uhlenbeck, G. W. Ford. — The theory of graphs with applications to the virial development of the properties of gases, Studies in Statistical Mechanics, vol. 1 (J. de Boer and G. E. Uhlenbeck, eds.), North-Holland, Amsterdam, 1962, p. 112–211.

[38] Ph. Welschinger. — Séminaire de théorie combinatoire, I.R.M.A., Université de Strasbourg, 1969–1970.

[39] J. Worpitzky. — Studien über die Bernoullischen und Eulerschen Zahlen, J. für die reine und angewandte Math., t. 94, 1883, p. 203–232.

46 BIBLIOGRAPHIE