0% ont trouvé ce document utile (0 vote)

38 vues49 pages

Lecture Notes in Mathematics: 138 Dominique Foata Marcel-P. SCH Utzenberger

Ce document est une version révisée de 2005 d'un texte initialement publié en 1970 sur la théorie géométrique des polynômes eulériens. Il présente une introduction historique sur les nombres d'Euler et explore diverses propriétés et applications des polynômes eulériens en relation avec les permutations et les nombres de Stirling. Le contenu est structuré en chapitres détaillant des concepts mathématiques avancés et des résultats théoriques.

Transféré par

aminetomora

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

0% ont trouvé ce document utile (0 vote)

38 vues49 pages

Lecture Notes in Mathematics: 138 Dominique Foata Marcel-P. SCH Utzenberger

Transféré par

aminetomora

Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.

Formats disponibles

Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Lecture Notes in

Mathematics
arXiv:math/0508232v1 [math.CO] 15 Aug 2005

A collection of informal reports and seminars

Edited by A. Dold, Heidelberg and B. Eckmann, Zürich
Series : Institut de Mathématique, Université de Strasbourg
Advisers : P. A. Meyer and M. Karoubi

138
Dominique Foata
Université de Strasbourg

Marcel-P. Schützenberger
Université de Paris

Théorie Géométrique
des Polynômes Eulériens

Springer-Verlag
Berlin · Heidelberg · New York 1970
The present volume is a 2005 revised version of the text that was originally published
in the Springer-Verlag Lecture Notes in Mathematics Series, back in 1970. We thank Anne
Berstel for her careful proof-reading.
TABLE DES MATIÈRES

CHAPITRE 0. Introduction et historique des nombres d’Euler . . 1

1. Bref historique sur les nombres d’Euler . . . . . . . . . . . . . . . . . . . . . . . . 1
2. Résumé du mémoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2

CHAPITRE PREMIER. Propriétés générales des systèmes d’excé-

dances et de montées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1. Excédances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2. Descentes et montées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3. La transformation fondamentale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
4. Relations entre les excédances et les descentes . . . . . . . . . . . . . . . . . 8
5. Applications aux permutations alternées . . . . . . . . . . . . . . . . . . . . . . . 9
6. Relations entre les excédances et les montées . . . . . . . . . . . . . . . . . . 10
7. Relations avec les permutations circulaires . . . . . . . . . . . . . . . . . . . . . 11
8. Tableau des bijections utilisées . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
9. Notations générales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

CHAPITRE 2. Les polynômes eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1. Interprétation des polynômes eulériens . . . . . . . . . . . . . . . . . . . . . . . . . 14
2. Propriétés de symétrie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3. Relations de récurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
4. Relations avec le hh problème de Simon Newcomb ii . . . . . . . . . . . . . 17
5. Relations avec les nombres de Stirling . . . . . . . . . . . . . . . . . . . . . . . . . . 18
6. Les identités de Worpitzky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
7. Table des polynômes eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

CHAPITRE 3. La formule exponentielle .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1. La formule de Hurwitz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2. Le composé partitionnel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3. Une formule d’inversion pour les séries exponentielles . . . . . . . . . 26
4. Le composé partitionnel des applications . . . . . . . . . . . . . . . . . . . . . . 27
5. Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
6. Une identité entre déterminants et permanents . . . . . . . . . . . . . . . . 30

CHAPITRE 4. Fonctions génératrices des polynômes eulériens . . 32

1. Fonction génératrice exponentielle de 0An (t), An (t) et Bn (t) . 32
2. Fonction génératrice exponentielle des polynômes rAn (t) . . . . . . 34
3. Autres interprétations des polynômes eulériens . . . . . . . . . . . . . . . . 36
iv

CHAPITRE 5. Les sommes alternées An (−1) et Bn (−1) . . . . . . . . . . . . 38

1. Distribution du nombre des descentes sur S′n
................. 38
2. Applications aux polynômes eulériens . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3. Applications aux polynômes Bn (t) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4. Les développements de tg u et de 1/ cos u . . . . . . . . . . . . . . . . . . . . . . 42
5. Table des nombres d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

Bibliographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
CHAPITRE 0

INTRODUCTION ET HISTORIQUE
DES NOMBRES D’EULER

1. Bref historique sur les nombres d’Euler

On sait depuis Euler que la relation
X un 1−t
An (t) = (1)
n! −t + exp(u(t − 1))
n≥0

définit des polynômes symétriques

X
A0 (t) = 1 et An (t) = tn−1 An (t−1 ) = An,k tk (n ≥ 1),
0≤k≤n−1

de degré (n − 1), dont les coefficents An,k sont des entiers positifs de somme
An (1) = n!
Worpitzky [31] a donné la formule

n
X x+k
x = An,k (2)
n
0≤k≤n−1

et Frobenius [13], qui a appelé les An (t) polynômes eulériens, a indiqué

l’identité X
An (t) = (n − k)! (t − 1)k S(n, n − k), (3)
0≤k≤n−1

dans laquelle S(n, j) désigne le nombre de Stirling de seconde espèce, c’est-

à-dire le nombre de partitions en j classes d’un ensemble de n éléments. Une
bibliographie de cette question a été rassemblée par Carlitz [4].
De par ailleurs, les polynômes eulériens apparaissent dans divers problèmes
d’énumération concernant le groupe symétrique Sn sur l’ensemble totalement
ordonné [ n ] = {1, 2, . . . , n} (= ∅ pour n = 0). Ainsi, d’après (1) la somme
alternée (−1)p−1 A2p−1 (−1) est le coefficient de u2p−1 /(2p − 1)! dans le
développement de tg u (voir chapitre V § 4 du présent article) et Désiré André
[1], [2] (voir aussi [21], chap. 4) a découvert que ce dernier nombre est celui
des permutations σ ∈ S2p−1 qui sont alternées, c’est-à-dire telles que pour
chaque j ∈ [p − 1], on ait à la fois σ(2j) < σ(2j − 1) et σ(2j) < σ(2j + 1).
2 CHAPITRE 0 : INTRODUCTION ET HISTORIQUE DES NOMBRES D’EULER

MacMahon (19] a étudié le nombre A′n,k des permutations σ ∈ Sn telles

que j < σ(j) pour exactement k éléments j ∈ [ n ] et en application de son
′
n,k est aussi le nombre des σ ∈ Sn
hh Master Theorem ii, il a montré que A

qui possèdent k montées, c’est-à-dire qui satisfont à σ(j) < σ(j + 1) pour
exactement k valeurs j ∈ [ n − 1 ]. Carlitz et Riordan [7] ont reconnu que les
A′n,k sont précisément les coefficients des polynômes eulériens et Riordan a
généralisé ceux-ci au moyen de sa théorie des hh rook polynomials ii. Appelons
r-excédance de σ ∈ Sn tout j ∈ [ n ] tel que j + r ≤ σ(j) (0 ≤ r) et soit
r
An,k le nombre des σ ∈ Sn ayant k r-excédances (1An,k = An,k ) ; Riordan,
dans le dernier chapitre de son livre [24], considère avec des notations un peu
différentes les polynômes
X
r r
An (t) = An,k tk (4)
0≤k

et à leur sujet établit des extensions des formules (1) et (3). D’autres généra-
lisations sont dues à Carlitz et son école ([5], [8], [10]).
Soit |∆′ M σ| le nombre des montées de σ ∈ Sn . Roselle [25] a calculé
′
le polynôme Bn (t) défini comme la somme de t|∆ M σ| étendue au sous-
ensemble Gn des σ ∈ Sn tels que 1 6= σ(1) et 1 + σ(j) 6= σ(j + 1) pour chaque
j ∈ [ n − 1 ]. Il note que Bn (1) est le nombre de permutations sans points
fixes de Sn et il constate que la somme alternée (−1)p B2p (−1) est égale
au coefficient de u2p /(2p)! dans le développement de 1/ cos u, c’est-à-dire au
2pième nombre d’Euler. Or, on sait depuis longtemps que ce coefficient est le
nombre des σ ∈ S2p tels que σ(2p − 1) < 2p et σ(2j − 1) < σ(2j) > σ(2j + 1)
(j ∈ [p − 1]) ([1], [14]), ceci étant d’ailleurs un cas particulier d’une formule
plus générale due à Entringer [11] et dans une direction assez différente de la
théorie des hh runs up and down ii développée par David et Barton à des fins
statistiques [3].
Enfin, dans la théorie dite du hh problème de Newcomb ii, on considère au
lieu de l’ensemble ordonné [ n ] un ensemble préordonné quelconque X. Les
énoncés y dépendent donc de façon cruciale de la structure de X, ce qui
conduit à une problématique sensiblement différente, sauf si l’on réintroduit
des hypothèses particulières sur X comme par exemple dans le cas des
polynômes de Shanks [27], des polynômes de Poussin [22] ou dans celui de la
r r
hh spécification (1 (n − r)) ii qui fait apparaı̂tre directement les entiers A
n,k .
Hormis ce dernier cas, nous avons entièrement laissé de côté le problème
de Newcomb qui nous eût entraı̂né fort loin des polynômes eulériens. Au
demeurant, les mêmes techniques de base ont été employées récemment par
l’un de nous [9] pour traiter le cas général et certaines de ses applications.

2. Résumé du mémoire
Les théorèmes qui viennent d’être rappelés ont été, en règle générale,
établis en utilisant conjointement quelques propriétés géométriques (hh combi-
natoires ii) des permutations et les méthodes plus expéditives du calcul
2. RÉSUMÉ DU MÉMOIRE 3

différentiel et intégral. En particulier, aucune connexion sauf la coı̈ncidence

de l’aboutissement de deux séries de calculs ne semble avoir été vue entre les
sommes alternées An (−1) et Bn (−1) et la signification des polynômes An (t)
et Bn (t) en termes d’excédances ou de montées.
Le but du présent mémoire est au contraire de développer la théorie
géométrique sous-jacente et c’est de façon subsidiaire que nous en déduisons
des identités entre séries ou polynômes. Nous nous sommes cependant
attachés à toujours retrouver les résultats classiques. Dans de nombreux
cas, cette approche évacue pratiquement tous les calculs : c’est ce qui se
produit par exemple en ce qui concerne les formules reliant les polynômes
eulériens et les nombres de Stirling. Dans d’autres cas, nous obtenons
des séries d’identités nouvelles (par exemple les hh formules sommatoires ii
généralisant celle de Worpitzky données dans la section 6 du chapitre II ou
le théorème 5.6). Les méthodes du chapitre III contiennent implicitement
l’énumération du nombre des excédances pour les permutations dont les
longueurs des cycles satisfont à des conditions de divisibilité données.
Plus important nous semble la démonstration du fait que toutes les
identités classiques concernant les polynômes eulériens sont seulement la
traduction de propriétés très simples des morphismes d’ensembles totalement
ordonnés finis. Pour l’essentiel, elles dérivent soit de méthodes élémentaires
courantes comme l’inversion de Möbius ou la formule exponentielle, soit d’une
opération unique nouvelle σ 7→ σ̂ appelée ici transformation fondamentale,
déjà introduite par l’un de nous [12] dans le cadre général du problème de
Newcomb. Simultanément, les énoncés que nous proposons, expriment, en
règle, des bijections entre ensembles. Ils sont donc plus riches que les identités
énumératives classiques auxquelles ils se réduisent quand, en fin de calcul, on
substitue à ces ensembles le nombre de leurs éléments.
Le chapitre I est consacré à l’étude détaillée des propriétés de la transfor-
mation fondamentale. Celle-ci est une bijection de Sn sur lui-même ayant la
propriété que l’ensemble des hh excédances ii de σ est envoyé, de façon biuni-
voque, sur celui des hh descentes ii de σ̂. Elle permet ici d’établir que la distri-
bution du nombre des excédances sur les permutations de Sn est la même que
sur le sous-ensemble Cn+1 des permutations circulaires de Sn+1 . Ce résultat
est étendu dans le paragraphe 4, où nous employons les bi-excédances (c’est-
à-dire les j ∈ [ n ] tels que j soit à la fois strictement plus petit que σ(j)
et que σ −1 (j)) et les creux (c’est-à-dire les j ∈ [ n ] tels que j soit à la fois
strictement plus petit que σ(j − 1) et que σ(j + 1)) pour étudier les sommes
alternées. Cette dualité pourrait être étendue à des constructions plus com-
plexes sur lesquelles nous reviendrons peut-être dans un autre travail.
Dans le chapitre II, nous retrouvons et généralisons diverses formules de
récurrence de Riordan et l’identité de Worpitzky, en application des résultats
précédents et de la considérations des morphismes [ n ] → [m], c’est-à-dire,
puisque [ n ] et [m] sont des ensembles totalement ordonnés des applications
φ : [ n ] → [m] telles que i ≤ j implique φ(i) ≤ φ(j).
4 CHAPITRE 0 : INTRODUCTION ET HISTORIQUE DES NOMBRES D’EULER

Dans le chapitre III, nous croyons utile de donner d’abord une théorie
systématique de la formule exponentielle classique de Cauchy exprimant le
groupe symétrique en fonction des permutations circulaires. Cette formule est
un cas particulier d’une constructuon très générale permettant de ramener
divers problèmes d’énumération à un problème analogue sur une sous-famille
hh génératrice ii constituée par des objets hh connexes ii. Afin de clarifier ces

notions, nous donnons quelques énoncés sous une forme qui permettrait
de traiter les énumérations d’arborescences. Retournant aux permutations,
une application de cette formule et des résultats du chapitre I nous permet
d’obtenir dans le chapitre IV la fonction génératrice exponentielle du nombre
des r-excédances pour les permutations ayant une composition en cycles
donnée.
Dans le chapitre V, nous établissons un théorème sur la distribution du
nombre des montées pour les permutations ayant un nombre de creux fixé. De
façon plus explicite, soit S′n,k l’ensemble des permutations σ ∈ Sn ayant k
creux et telles que σ(1) = n (2 ≤ 2k ≤ n) ; alors le nombre de σ ∈ S′n,k
ayant j montées est donné par le coefficient binomial n−2k

j (0 ≤ j ≤ n−2k).
Nous déduisons de ce résultat les expressions des sommes alternées An (−1)
et Bn (−1) en fonction du nombre des permutations alternées. En particulier,
les développements de tg u et 1/ cos u sont obtenus sans calcul à partir de
l’expression des fonctions génératrices exponentielles des polynômes An (t) et
Bn (t) données dans le chapitre IV.
Dans tout ce travail, étant donnés deux ensembles A et B finis et une
application φ : A → B, nous appellerons ensemble pondéré l’application
φ# : B → N définie pour chaque b ∈ B par φ# (b) = card φ−1 (b). Par abus
de notation, on désignera par φA l’ensemble pondéré φ# et il sera commode
#
P #
d’identifier φA et φ à l’élément {φ (b) : b ∈ B} du Q-module libre de
base B.
Nous sommes reconnaissants au professeur J. Riordan de nous avoir fait
bénéficier de ses conseils et de son érudition. La dactylographie de ce mémoire
est due à Mlle Cler, du département de mathématique de Strasbourg, que
nous tenons à remercier.
CHAPITRE PREMIER

PROPRIÉTÉS GÉNÉRALES DES SYSTÈMES

D’EXCÉDANCES ET DE MONTÉES

1. Excédances
Dans tout ce chapitre, nous utilisons la notation x+ pour désigner la partie
positive x+ = max{0, x} de tout x ∈ Z et pour σ ∈ Sn , nous désignons
par σw le n-uple (ou vecteur) (σ(1), σ(2), . . . , σ(n)) ∈ Nn . Par conséquent,
σw = ∅ pour n = 0.
Définition 1.1. — Pour σ ∈ Sn , le système des 0-excédances de σ est le
n-uple Eσ = (Eσ(1), Eσ(2), . . . , Eσ(n)) ∈ Nn , où 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).
Définition 1.2. — Quelque soit l’entier p ≥ 1, on note ∆, ∆′ et ∆′′
les applications de Np dans Np−1 envoyant respectivement chaque vecteur
x = (x1 , x2 , . . . , xp ) ∈ Np sur

∆x = (x1 − 1)+ , (x2 − 1)+ , . . . , (xp−1 − 1)+ ;
∆′ x = (x2 , x3 , . . . , xp );
∆′′ x = (x1 , x2 , . . . , xp−1 ).
Il est immédiat que les trois opérateurs ∆, ∆′ , ∆′′ ainsi définis commutent
deux à deux. Prenant le mê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 généralement le vecteur ∆r E décrit les r-excédances de σ
mentionnées dans l’introduction. L’une des raisons motivant l’introduction
de ∆′ est contenue dans le lemme 1.4 ci-dessous. L’opérateur ∆′′ permettra
dans le deuxième chapitre de formuler une intéressante propriété de symétrie
des polynômes eulériens (propriété 2.3).
6 CHAPITRE PREMIER : SYSTÈMES D’EXCÉDANCES ET DE MONTÉES

Remarque 1.3. — Pour σ ∈ Sn et k ∈ [ n ], on a Eσ(k) = 1 si et seulement

si (σ(k) − k + 1)+ = 1, c’est-à-dire si k = σ(k) est un point fixe de σ.
Lemme 1.4. — Soit ζ ∈ Sn la permutation circulaire envoyant n
sur 1 et chaque k ≤ n − 1 sur k + 1 ou encore la permutation définie par
ζw = (2, 3, . . . , n, 1). Pour chaque r ≥ 0 et chaque σ ∈ Sn on a
∆′r Eσ = ∆r Eσζ r .
Dé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 résultat a la conséquence immédiate suivante qui nous servira
fréquemment par la suite.
Théorème 1.5. — Quelque soit le monôme Γ de degré r ≥ 0 en les
applications ∆ et ∆′ , les ensembles pondérés ∆r ESn , ∆′r ESn et ΓESn
sont égaux.
Démonstration. — Puisque σ 7→ σζ r est une bijection de Sn sur lui-même,
l’égalité ∆r ESn = ∆′r ESn résulte immédiatement du lemme 1.4. Comme
∆ et ∆′ commutent, on peut écire Γ = ∆s ∆′r−s , d’où ΓESn = ∆r ESn .

2. Descentes et montées
En parallèle avec les excédances, nous introduisons le système des 0-
descentes, Dσ, et des 0-montées, M σ, de σ ∈ Sn par la définition suivante,
dans laquelle on convient que σ(0) = σ −1 (0) = σ(n + 1) = 0.
Définition 1.6. — Pour σ ∈ Sn , on pose
Dσ = Dσ(1), Dσ(2), . . . , Dσ(n) ∈ Nn ;

M σ = M σ(1), M σ(2), . . . , M σ(n) ∈ Nn ;

où 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 supérieurs ou égaux
à 2. D’autre part, Dσ(n) est toujours nul. Par conséquent, Dσ et ∆Dσ ont
le même nombre de termes (strictement) positifs. Il est clair que ∆r Dσ et
∆r−1 M σ décrivent les différences supérieures ou égales à r (r ≥ 1) entre
termes consécutifs de σw, la connexion entre D et M étant explicité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.
3. LA TRANSFORMATION FONDAMENTALE 7

Lemme 1.7. — Soit σ 7→ σ̃ la bijection de Sn sur lui-même définie

par l’identité σ̃(k) = σ(n + 1 − k) (k ∈ [ n ]). On a M σ̃(1) = σ(n) et
M σ̃(k + 1) = ∆Dσ(k) pour chaque k ∈ [n − 1].
Démonstration. — Par dé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’où 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
Étant donnée une permutation σ ∈ Sn , l’ensemble σ ∗ (k) = {σ p (k) : p ∈ N}
est l’orbite contenant k (k ∈ [ n ]). On note z(σ) le nombre des orbites de σ
ou, de façon équivalente, le nombre des cycles de σ. A chaque k ∈ [ n ], nous
attachons la paire Πσ (k) = (k, qk ), où k est l’élément maximum de l’orbite
σ ∗ (k) et où qk = min{p ∈ N : σ p (k) = k}.
Définition 1.8. — Pour σ ∈ Sn on désigne par σ̂ la permutation telle que
ième
pour chaque k la paire Πσ (σ̂(k)) est le k terme de la suite Πσ (j) (j∈[ n ])
ordonnée par ordre lexicographique.
Par exemple, en prenant encore σw = (6, 4, 1, 2, 5, 3), on a z(σ) = 3, les trois
orbites é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),
ordonnée suivant l’ordre lexicographique, est
(4, 0), (4, 1), (5, 0), (6, 0), (6, 1), (6, 2) , d’où σ̂w = (4, 2, 5, 6, 1, 3).
Rappelons qu’un élément xk d’une suite (x1 , x2 , . . . , xn ) ∈ Nn est dit
saillant si et seulement s’il n’existe aucun élément d’indice inférieur qui soit
supérieur ou égal à lui, c’est-à-dire si l’on a xk′ < xk pour tout k ′ < k. Donc
par définition x1 est toujours saillant.
Lemme 1.9. — L’élément k de [ n ] est maximum dans son orbite σ ∗ (k)
(c’est-à-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 élément saillant de σ̂w.
Démonstration. — Soit Πσ (k) = (k, q). Si et seulement si q est différent
de 0, l’entier k n’est pas l’élément maximum k de son orbite et k n’est
pas saillant dans σ̂w puisque Πσ (k) = (k, 0) précède Πσ (k) dans l’ordre
lexicographique, donc k précède k dans la suite σ̂w.
Ré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’élément Πσ (σ̂(j ′ ))
8 CHAPITRE PREMIER : SYSTÈMES D’EXCÉDANCES ET DE MONTÉES

est avant l’élément Πσ (σ̂(j)) (= (k, 0)) pour l’ordre lexicographique ; ce qui
implique, en posant σ̂(j ′ ) = k ′ , que l’on a σ̂(j ′ ) = k ′ < k ′ < k = σ̂(j)
et prouve l’équivalence entre les éléments maximaux des orbites de σ et les
éléments saillants de σ̂w.
Supposons maintenant k = k = σ̂(j). Si et seulement si k n’est pas un
point fixe de σ, il est immédiatement suivi dans σ̂w d’un élément k ′ tel que
Πσ (k ′ ) = (k, 1). Par conséquent, on a j < n et σ̂(j + 1) = k ′ n’est pas
saillant.
Dans ce qui suit S′n désigne l’ensemble des σ ∈ Sn telles que σ(1) = n
et Cn est le sous-ensemble des permutations circulaires.
Propriété 1.10. — L’application σ 7→ σ̂ est bijective et satisfait à
σ(n) = σ̂(n). Sa restriction à Cn est une bijection sur S′n .
Démonstration. — Étant donné τ ∈ Sn , il existe un et un seul σ ∈ Sn tel
que τ = σ̂, car d’une part, les éléments saillants de τ w livrent les éléments
maximaux des orbites de σ d’après le précédent lemme, d’autre part, les
restrictions de σ à chacune de ses orbites sont déterminées par la succession
même des éléments de τ w. Ceci établit le caractère bijectif de σ 7→ σ̂.
Comme τ (1) et n sont toujours des élé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-à-dire
n = σ −1 (k), l’entier n est l’élément maximum de σ ∗ (k) et par conséquent,
Πσ (k) = (n, qk ) est le dernier terme de la suite (Πσ (j))(j∈[ n ]) ordonnée par
ordre lexicographique, c’est-à-dire k = σ̂(n).

4. Relations entre les excédances et les descentes

Nous allons donner une première application de la transformation fonda-
mentale σ 7→ σ̂. Aux 1-excédances de σ correspondent les 1-descentes de σ̂,
mais les 0-descentes de σ̂ ne correspondent pas aux 0-excédances de σ. Ceci
amène à introduire un vecteur D′ σ̂ tel que Dσ̂ + D′ σ̂ (= (D + D′ )σ̂) rende
compte à la fois des descentes et des éléments saillants dans la suite σ̂w et
qu’en outre l’identité Eσ = (D + D′ )σ̂ soit vérifiée.
Définition 1.11. — Pour τ ∈ Sn , le vecteur D′ τ est le n-uple
D′ τ (1), . . . , D′ τ (n) ∈ Nn ,

où 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.
Théorème 1.12. — On a identiquement
Eσ = (D + D′ )σ̂ et ∆Eσ = ∆Dσ̂.
Démonstration. — Quelque soit τ ∈ Sn , remarquons d’abord que j ≤ n−1
est saillant dans τ w seulement si τ −1 (j) ≤ n − 1. Nous vérifions le résultat
pour chaque k = σ̂(j) ∈ [ n ] en posant Πσ (k) = (k, q) et en distinguant les
cas suivants :
5. APPLICATIONS AUX PERMUTATIONS ALTERNÉES 9

(i) q ≥ 1 ; on a alors σ̂(j − 1) = k ′ où Πσ (k ′ ) = (k, q − 1), c’est-à-dire

k = σ −(q−1) (k) = σ −(q−1) (σ q (k)) = σ(k). Donc par dé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-à-dire k = k. On a toujours Dσ̂(k) = 0 car soit j − 1 = 0,
soit j − 1 ≥ 1 avec k ′ = σ̂(j − 1) appartenant à une orbite dont l’élément
maximum est strictement plus petit que k = k. D’autre part, Eσ(k) = 0 ou 1
selon que σ(k) 6= k ou non, car Eσ(k) = (σ(k)−(k−1))+ où σ(k) ≤ k puisque
k = k. D’après la deuxième partie du lemme 1.9 et la définition de D + D′ ,
on a donc Eσ(k) = 1 si et seulement si 1 = (D + D′ )σ̂(k) 6= Dσ̂(k) = 0.

On remarquera que l’on a (D + D′ )τ (j) 6= Dτ (j) si et seulement si

Dτ (j) = 0 et (D + D′ )τ (j) = 1.
Exemple. — On a vu dans les exemples précé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 élé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 alternées

Une permutation σ ∈ Sn est alternée si l’on a σ(2j) < σ(2j − 1), σ(2j + 1)
pour tout entier j tel que 2 ≤ 2j ≤ n − 1 et si l’on a encore σ(n) < σ(n − 1)
lorsque n est pair. D’autre part, elle est biexcédée si pour tout j ∈ [ n ], on
a j < σ(j), σ −1 (j) ou j > σ(j), σ −1 (j). Les ensembles des permutations
alternées et biexcédées sont notés respectivement Tn et Bn . Nous allons, dans
cette section, utiliser la transformation fondamentale pour construire entre
Tn et Bn 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 6= 1 et soit j ≤ n − 1 et σ̂(j) < σ̂(j − 1), σ̂(j + 1), soit j = n
et σ̂(j) < σ̂(j − 1).
Démonstration. — L’hypothèse k < σ(k) entraı̂ne k 6= k où k est le
maximum de l’orbite σ ∗ (k). Donc j 6= 1 et σ̂(j − 1) = σ(k) entraı̂nant
l’équivalence de k < σ(k) et de σ̂(j) < σ̂(j −1), puisque l’on a σ̂(j) > σ̂(j −1)
quand k = k. Distinguons deux cas selon que j = n ou non.
Si j = n, on a σ −1 (k) = k = n, donc k < σ −1 (k) et le résultat est prouvé.
Si j 6= n, ou bien σ −1 (k) = k, auquel cas l’hypothèse k < σ −1 (k) équivaut à
k = σ̂(j) < σ̂(j + 1), puisque σ̂(j + 1) est le maximum d’une autre orbite ;
ou bien σ −1 (k) 6= k, auquel cas σ̂(j + 1) = σ −1 (k) et k < σ −1 (k) équivaut à
σ̂(j) < σ̂(j + 1).

Proposition 1.14. — Toute permutation σ ∈ Bn a tous ses cycles de

longueur paire ; donc Bn = ∅ si n est impair. La transformation fondamentale
σ 7→ σ̂ établit, lorsque n est pair, une bijection de Bn sur Tn .
10 CHAPITRE PREMIER : SYSTÈMES D’EXCÉDANCES ET DE MONTÉES

Démonstration. — Dire que σ est biexcédée équivaut à dire que dans toute
orbite de σ, d’élément maximum k, on a identiquement σ 2p+1 (k) < σ 2p (k),
σ 2p+2 (k) (0 ≤ p). Ces inégalités impliquent d’abord que l’orbite n’est pas
réduite à un seul élément ; supposons maintenant qu’elle ait un nombre impair
d’éléments, disons 2q + 1 (avec q ≥ 1). Ces mêmes inégalités appliquées à
p = q entraı̂nent que l’on a k = σ 2q+1 (k) < σ 2q (k), ce qui est impossible
puisque k est l’élément maximum dans son orbite. La permutation σ n’a
donc que des cycles de longueur paire et par conséquent Bn = ∅ si n est
impair.
La dernière partie de la proposition résulte du lemme 1.13 et des deux
équivalences suivantes, qui découlent immédiatement de ce qui précède :
(i) σ est dans B2p si et seulement si les inégalités k < σ(k), σ −1 (k) sont
satisfaites pour exactement p indices k ;
(ii) τ est dans T2p si et seulement si, en posant τ (2p + 1) = 2p + 1, les
inégalités τ (j) < τ (j − 1), τ (j + 1) sont vraies pour exactement p indices
j ≥ 2.

Exemple. — Nous donnons ci-dessous le tableau des cinq permutations

biexcédées de S4 et en face de chacune d’elles, la permutation alterné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
B4 4 3 2 1 3 2 4 1 T4
4 3 1 2 4 1 3 2
3 4 2 1 4 2 3 1

4. Relations entre les excédances et les montées

Toujours au moyen de la transformation fondamentale, nous construisons
une bijection σ 7→ σ telle que Eσ = M σ. Soit en effet σ ∈ Sn et notons ζ la
permutation circulaire définie dans le lemme 1.4 (ζw = (2, 3, . . . , n, 1)). On
pose successivement
σ1 = σ ζ;
puis σ2 = σ̂1 (transformation fondamentale);
et enfin σ = σ̃2 (où ˜ est défini dans le lemme 1.7).

Théorème 1.15. — L’application σ 7→ σ est une bijection de Sn sur

lui-même satisfaisant à Eσ = M σ.
Démonstration. — Le caractère bijectif est évident d’après ce qui précède.
Ensuite, on a Eσ(1) = σ(1) = σ1 (n) et on vérifie que Eσ(j + 1) = ∆Eσ1 (j)
pour chaque j ∈ [n − 1]. D’après la propriété 1.10, on a σ2 (n) = σ1 (n) et
7. RELATIONS AVEC LES PERMUTATIONS CIRCULAIRES 11

d’après le théorème 1.12, il vient ∆Eσ1 = ∆Dσ2 . Par conséquent, en utilisant

le lemme 1.7, on a bien Eσ = M σ.

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 σw = (6, 3, 2, 1, 4, 5).
Comme on a ∆Eσ1 = ∆Dσ2 = (3, 0, 0, 1, 0), on vérifie bien que M σ = Eσ.
On a noté que Eσ(k) = 1 si et seulement si σ(k) = k. Par conséquent,
la restriction de σ 7→ σ au sous-ensemble Dn des permutations sans points
fixes est une bijection sur le sous-ensemble des σ ∈ Sn telles que M σ(j) 6= 1,
c’est-à-dire des σ telles que σ(1) 6= 1 et 1 + σ(j) 6= σ(j + 1), pour chaque
j ∈ [n − 1]. L’ensemble de ces permutations σ n’est autre que la classe, que
nous noterons Gn , des permutations sans successions. On a ainsi le corollaire
suivant.
Corollaire 1.16. — La restriction de σ → 7 σ à l’ensemble Dn des
permutations sans points fixes est une bijection sur l’ensemble Gn des per-
mutations sans successions telle que Eσ = M σ.

7. Relations avec les permutations circulaires

Pour terminer ce chapitre, il nous reste à étudier la distribution des
vecteurs-excédances sur l’ensemble Cn . Combinant d’abord les résultats de la
propriété 1.10 et du théorème 1.12, nous avons déjà la propriété suivante.
Propriété 1.17. — La restriction de la transformation fondamentale
σ 7→ σ̂ à l’ensemble Cn est une bijection sur S′n telle que ∆Eσ = ∆Dσ̂.
Nous construisons ensuite une bijection σ 7→ σ ′ de

S′′n = {σ ∈ Sn : σ(n) = 1}

sur S′n telle que ∆Eσ = ∆Dσ ′ . Si σ est dans S′′n , on pose i = σ̂ −1 (n) et σ ′
est défini comme l’unique permutation telle que

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

Lemme 1.18. — L’application σ 7→ σ ′ est une bijection de S′′n sur S′n

satisfaisant à ∆Eσ = ∆Dσ ′ .
Démonstration. — D’après la propriété 1.10, on a σ(n) = σ̂(n) et
par conséquent σ̂ est dans S′′n . Il est clair que σ 7→ σ ′ est bijectif. En
outre, ∆Eσ = ∆Dσ̂ d’après le théorème 1.12. Il suffit donc de vé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’égalité ∆Dσ ′ (k) = (0 − n)+ = 0.
12 CHAPITRE PREMIER : SYSTÈMES D’EXCÉDANCES ET DE MONTÉES

Dans le cas général où k = σ̂(j + 1) 6= 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 conséquent, (σ̂(j) − k)+ est la valeur commune
de ∆Dσ̂(k) et ∆Dσ ′ (k).

Ce lemme permet la construction suivante : soit σ ∈ Sn−1 ; on définit

σ1 ∈ S′′n en posant

σ1 (n) = 1 et σ1 (k) = 1 + σ(k) pour chaque k ∈ [n − 1] ; puis

σ2 = σ1′ , où τ 7→ τ ′ est la bijection définie dans le lemme 1.18 ; enfin
σ ′′ est la permutation définie per σ̂ ′′ = σ2 .

Théorème 1.19. — L’application σ 7→ σ ′′ est une bijection de Sn−1

sur Cn telle que Eσ = ∆Eσ ′′ .
Démonstration. — Tout d’abord la bijectivité de σ 7→ σ ′′ est évidente.
Si σ est dans Sn−1 , on a ensuite σ1 ∈ S′′n et Eσ(k) = (σ(k) − (k − 1))+ =
(σ1 (k)−k)+ = ∆Eσ1 (k) pour chaque k ∈ [n−1], d’où il résulte Eσ = ∆Eσ1 .
D’autre part, d’après le lemme 1.18, on a σ2 ∈ S′n et Eσ = ∆Eσ1 = ∆Dσ2 .
Enfin, en vertu de σ2 ∈ S′n , la propriété 1.17 montre que l’on a σ ′′ ∈ Cn et
∆Eσ ′′ = ∆Dσ2 .

8. Tableau des bijection utilisées

Il paraı̂t intéressant de rappeler les propriétés des bijections construites
dans le premier chapitre et d’indiquer leur référence.

La bijection envoie sur a la propriété et la référence

σ 7→ σζ r Sn Sn ∆′r Eσ = ∆r Eσζ r (r ≥ 0) Lemme 1.4
σ 7→ σ̃ Sn Sn M σ̃(1) = σ(n) et Lemme 1.7
M σ̃(k + 1) = ∆Dσ(k) (k ∈ [n − 1])
σ 7→ σ̂ Sn Sn Définition 1.8
Cn S′n Proposition 1.10
Sn Sn Eσ = (D + D′ )σ̂, ∆Eσ = ∆Dσ̂ Théorème 1.12
B2n T2n Proposition 1.14
σ 7→ σ Sn Sn Eσ = M σ Théorème 1.15
Dn Gn Corollaire 1.16
′
σ 7→ σ S′′n S′n ∆Eσ = ∆Dσ ′
Lemme 1.18
σ 7→ σ ′′ Sn−1 Cn Eσ = ∆Eσ ′′ Théorème 1.19
9. NOTATIONS GÉNÉRALES 13

9. Notations générales
Nous réunissons dans cette section toutes les notations utilisées pour les
sur- et les sous-ensembles de Sn . Pour n ≥ 1 et 1 ≤ k, r ≤ n, on considère
les sous-ensembles suivants de Sn :
Cn l’ensemble des permutations circulaires ; (C0 = ∅) ;
Gn l’ensemble des permutations sans successions, c’est-à-dire des σ ∈ Sn
telles que 1 6= σ(1) et 1 + σ(j) 6= σ(j + 1) pour j ∈ [n − 1] ;
Dn l’ensemble des permutations sans points fixes ;
Tn l’ensemble des permutations alternées, c’est-à-dire des σ ∈ Sn 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) ;
Bn l’ensemble des permutations biexcédées, c’est-à-dire des σ ∈ Sn telles
que pour chaque j ∈ [ n ], on ait j < σ(j), σ −1 (j) ou j > σ(j), σ −1 (j) ;
Sn,k l’ensemble des permutations σ ∈ Sn telles que σ(1) = k ; S′n = Sn,n ;
S′′n l’ensemble des permutations σ ∈ Sn telles que σ(n) = 1 ;
r Sn l’ensemble des permutations σ ∈ Sn telles que
σ −1 (n − r + 1) < σ −1 (n − r + 2) < · · · < σ −1 (n).
S S S
On posera également : S = Sn ; puis C = Cn , G = Gn ,
S S 0≤nS 1≤n 1≤n
T = Tn , B = Bn et D = Dn . Enfin, on utilise les notations
1≤n 1≤n 1≤n
courantes suivantes :
N l’ensemble des entiers naturels ;
Z l’ensemble des entiers ;
Q l’ensemble des nombres rationnels.
CHAPITRE II

LES POLYNÔMES EULÉRIENS

1. Interprétation des polynômes eulériens

Les théorèmes 1.12, 1.15, 1.19 et la propriété 1.17 permettent d’établir
immédiatement l’égalité des cinq ensembles pondérés ESn , (D + D′ )Sn ,
M Sn , ∆ECn+1 , ∆DS′n+1 ; et le théorème 1.12 donne encore : ∆ESn =
∆DSn . La propriété 2.1 suivante résulte alors du théorème 1.5.
Propriété 2.1. — Soit Γ un monôme en ∆ et ∆′ de degré r ≥ 0. On a
ΓESn = Γ(D + D′ )Sn = ΓM Sn = Γ∆ECn+1 = Γ∆DS′n+1 ,
où en outre
ΓESn = ΓDSn
si et seulement si Γ a au moins un ∆ comme facteur.
Nous notons |x| le nombre de termes positifs de tout x ∈ Np et introduisant
une indéterminée t, nous posons θx = t|x| . Si K est une application dans Np
d’une partie P de Sn , l’ensemble pondéré
X X
θKP = {θKσ : σ ∈ P} = tk · card{σ ∈ P : |Kσ| = k}
0≤k

sera appelé, par abus de langage, fonction génératrice de K. Pour P fini,

θKP sera donc un polynôme en t à coefficients dans N et nous dirons que
(P, K) est une interprétation.
Les polynômes eulériens An (t) et leurs généralisations rAn (t) selon Riordan
sont définis par :
r
An (t) = θ∆r ESn pour 0 ≤ r ≤ n − 1.
On conviendra que rAn (t) = n! pour r ≥ n. On posera A0 (t) = 1 et
An (t) = 1An (t) pour n ≥ 1. Par construction, les rAn (t) sont des polynômes de
degré au plus égal à n−r. L’énoncé suivant en donne plusieurs interprétations
par simple application de la propriété précédente.
Propriété 2.2. — Soit Γ un monôme en ∆ et ∆′ de degré r. On a
An (t) = θΓESn = θΓ(D + D′ )Sn = θΓM Sn = θΓ∆ECn+1 = θΓ∆DS′n+1 ,
r

où en outre rAn (t) = θΓDSn si et seulement si Γ a au moins un ∆ comme

facteur.
2. PROPRIÉTÉS DE SYMÉTRIE 15

De même, d’après le corollaire 1.16, on a l’égalité entre les ensembles

pondérés EDn et M Gn , d’où encore
θEDn = θM Gn pour n ≥ 1.
La valeur commune de ces deux derniers polynômes sera désignée par Bn (t).
L’interprétation (Gn , M ) de ces polynômes est due à Roselle [25]. L’interpré-
tation (Dn , E) servira à établir au chapitre IV l’expression de la fonction
génératrice exponentielle des Bn (t).

2. Propriétés de symétrie
Les identités (1) et (4) ci-dessous sont bien connues (cf. Riordan [24]). Nous
en donnons ici des démonstrations élémentaires. Les polynômes rAn (t) pour
r ≥ 2 n’ont pas de propriété de symétrie évidente. En revanche, si l’on forme
les polynômes réciproques tn−r rAn (t−1 ), on obtient plusieurs interprétations
(cf. les relations (2) et (3) ci-dessous) qui nous serviront effectivement, dans
les sections 2.4 et 2.6, pour établir des connexions avec le problème de
Simon Newcomb et pour démontrer de nouvelles identités sur les polynômes
eulériens.
Propriété 2.3. — Pour n ≥ 1 on a :
0
An (t) = t An (t). (1)
De plus, si Γ est un monôme de la forme ∆′′r−1 ∆ ou ∆′′r−1 ∆′ (r ≥ 1), on a
tn−r rAn (t−1 ) = θΓESn = θΓ(D + D′ )Sn = θΓM Sn . (2)
On a encore
tn−r rAn (t−1 ) = θ∆′′r−1 ∆DSn , (3)
d’où en particulier pour r = 1
tn−1 An (t−1 ) = An (t). (4)
Démonstration. — Soit σ ∈ Sn ; définissant σ̌ par l’identité σ̌(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 établit
0
An (t) = tn An (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 équivalente à
|∆′r−1 ∆E σ̌| + |∆′′r−1 ∆′ Eσ| = n − r
ou encore à
|∆′′r−1 ∆E σ̌| + |∆′r Eσ| = n − r.
16 CHAPITRE II : LES POLYNÔMES EULÉRIENS

On en déduit
X
θ∆′′r−1 ∆ESn = tn−r t−k card{σ ∈ Sn : |∆′r Eσ| = k}
0≤k

=t An (t−1 ),
n−r r

d’après la propriété 2.2.

Les relations (2) et (3) résultent alors de la propriété 2.1 et faisant
r = 1 dans (3), on obtient tn−1 An (t−1 ) = θ∆DSn = An (t), c’est-à-dire
la relation (4). Enfin, l’identité (2) résulte à la fois de (4) et de (5).
Remarque 2.4. — D’après la définition 1.6, pour 1 ≤ r ≤ n et σ ∈ Sn , 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 posé d’autre part
X
r r
An (t) = An,k tk
0≤k≤n−r
et que d’après la propriété 2.3, on a
X
θ∆′ ∆′′r−1 M Sn = tn−r rAn (t−1 ) = r
An,n−r−s ts ,
0≤s≤n−r
il vient :
r
An,n−r−s = card{σ ∈ Sn : |∆′ ∆′′r−1 M σ| = s} pour 0 ≤ s ≤ n − r.
Cette remarque nous servira au paragraphe 6 du présent chapitre.

3. Relations de récurrence
Dans cette section, nous établissons une relation de récurrence sur les
polynômes eulériens qui généralise l’identité (1) ci-dessus et redémontrons la
relation de récurrence trouvée par Riordan [24].
Propriété 2.5. — Pour 0 ≤ r ≤ n, on a l’identité :
t · (r+1)An (t) = rAn (t) + r(t − 1) · rAn−1 (t).
Démonstration. — Pour r = 0, l’identité se réduit à tAn (t) = 0An (t).
Pour r = n, elle est encore vraie avec la convention que nous avons faite que
r
An (t) = n! quand r ≥ n. Nous supposons donc 1 ≤ r ≤ n − 1. Pour chaque
σ ∈ Sn , on a
∆r Eσ = (σ(1) − r)+ , (σ(2) − r − 1)+ , . . . , (σ(n − r) − (n − 1))+ .

D’une part, on a ∆r ESn,s = ∆r ESn,r pour 1 ≤ s ≤ r ; d’autre part,

rθ∆r ESn,1 = rθ∆r ∆′ ESn,1 = r rAn−1 (t) d’après la propriété 2.2. Il en
résulte : rAn (t)−r rAn−1 (t) = θ∆r (Sn −(Sn,1 +· · ·+Sn,r )) = θ∆r E(Sn,r+1 +
· · · + Sn,n ) = t∆′ ∆r E(Sn,r+1 + · · · + Sn,n ) = t∆′ ∆r E(Sn − (Sn,1 + · · · +
Sn,r )) = t(∆′ ∆r ESn,1 − r∆′ ∆r ESn,1 ) = t((r+1)An (t) − r rAn−1 (t)).
Remarque 2.6. — Riordan ([24], p. 214) a trouvé une autre relation de
récurrence, à savoir
An (t) = (r + (n − r)t) · rAn−1 (t) + t(1 − t) · rA′n−1 (t) (0 ≤ r ≤ n; 1 ≤ n), (7)
r
4. RELATIONS AVEC LE hh PROBLÈME DE SIMON NEWCOMB ii 17

où rA′n−1 (t) désigne la dérivée du polynôme rAn−1 (t). Comme on a posé
X
r r
An (t) = An,k tk ,
0≤k≤n−r

cette relation de récurrence est encore équivalente aux (n − r + 1) relations

suivantes (cf. [24] p. 215)
r
An,k = (k + r) · rAn−1,k + (n + 1 − k − r) · rAn−1,k−1 (0 ≤ k ≤ n − r), (8)
où l’on a posé rAn,k = 0 si k ≤ −1 ou k ≥ n − r + 1.
Comme l’a noté Welschinger [30], on peut redémontrer facilement (8) et
par suite (7) en prenant les polynômes eulériens dans l’interprétation
r
An (t) = θ∆′r−1 ∆DSn .
En effet, on vérifie tout d’abord que les relations (8) sont vraies pour n = r,
en notant que nAn,0 = n! et nAn,k = 0 pour k 6= 0. On suppose ensuite
0 ≤ r ≤ n − 1 et l’on pose pour i ∈ [ n ] et σ ∈ Sn−1

ηi (σ) = σ(1), . . . , σ(i − 1), n, σ(i), . . . , σ(n − 1) .
Il est clair que l’on a
Sn = {ηi (σ) : i ∈ [ n ], σ ∈ Sn−1 }.
Soit σ ∈ Sn−1 ; alors |∆′r−1 ∆Dσ| = k [en abrégé : σ ∈ r An−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 An−1,k ; on observe alors que ηi (σ) appartient à
r
An,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-à-dire pour exactement k + (r − 1) + 1 = k + r indices i ∈ [ n ]. Pour les
autres n − (k + r) indices i ne satisfaisant à aucune des conditions (i), (ii),
(iii), on a ηi (σ) ∈Sr An,k+1 . On constate donc que l’ensemble r An,k est contenu
dans la réunion {ηi (r An−1,k ∪ r An−1,k−1 ) : i ∈ [ n ]}. On voit ensuite que
la relation ηi (σ) ∈ r An,k est vérifiée pour exactement (k + r) indice i si σ est
dans r An−1,k et pour exactement n − (k − 1 + r) = n + 1 − k − r indices i
si σ est dans r An−1,k−1 . Les relations (8) sont ainsi démontrées.

4. Relations avec le hh problème de Simon Newcomb ii

Nous allons expliciter maintenant le lien entre les polynômes rAn (t) et les
polynômes générateurs que l’on définit pour le hh problème de Simon Newcomb
avec une spécification (1r (n − r)) ii (voir MacMahon [20], vol. 1, chap. 4 et 5).
Dans la démonstration de la propriété qui suit, nous considérons σw comme
le mot σ(1)σ(2) . . . σ(n) dont les lettres sont des éléments de [ n ].
Propriété 2.7. — Soit r ≥ 2 ; on a : tn−r rAn (t−1 ) = r! θ∆D r Sn , où
−1
r Sn = {σ ∈ Sn : σ (n − r + 1) < σ −1 (n − r + 2) < · · · < σ −1 (n)}.
18 CHAPITRE II : LES POLYNÔMES EULÉRIENS

Démonstration. — D’après la propriété 2.3, il nous suffit d’établir

θ∆′′r−1 ∆DSn = r! θ∆D r Sn ou encore de trouver une surjection σ 7→ σ ′
de Sn sur r Sn telle que
(i) |∆′′r−1 ∆Dσ| = |∆Dσ ′ | ;
(ii) l’application σ 7→ σ ′ soit homogène de degré r!, c’est-à-dire que
l’image inverse de chaque σ ′ ∈ r Sn ait r! éléments.
Prenons σ ∈ Sn et soit σw = g1 in−r+1 g2 . . . gr in gr+1 , où {in−r+1 , . . . , in }=
{n−r+1, . . . , n}. On pose σ ′ w = g1 (n−r+1)g2 . . . gr ngr+1 . Il est clair que σ ′
est dans r Sn et que σ 7→ σ ′ est homogène de degré r! D’autre part, puisque
les éléments n − r + 1, n − r + 2, . . . , n se pré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’identité |∆′′r−1 ∆Dσ| = |∆′′r−1 ∆Dσ ′ |
ré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 = g1 (n−r+1)g2 (n−r+2) . . . gr ngr+1 de r Sn sur le

mot f = g1 (n−r +1)g2 (n−r +1) . . . gr (n−r +1)gr+1 , on définit une bijection
de r Sn sur une classe de mots de spécification (1r (n − r)), c’est-à-dire des
mots de longueur n, qui contiennent n − r + 1 lettres distinctes dont l’une
d’entre elles est répétée r fois. Si l’on définit maintenant |∆Df | comme le
nombre de descentes, c’est-à-dire le nombre de couples de lettres successives
dans f qui vont en décroissant, on voit que l’on a |∆Df | = |∆Dσ ′ |. Ainsi
tn−r rAn (t−1 ) est le polynôme générateur du nombre des descentes pour un
ensemble de spécification (1r (n − r)).

5. Relations avec les nombres de Stirling

Rappelons que pour 1 ≤ q ≤ p, le nombre de Stirling de seconde espèce
S(p, q) est le nombre de partitions de [ p ] en q parties non vides. Le résultat
suivant est obtenu par Riordan ([24], p. 213) au moyen de calculs assez
complexes.
Propriété 2.8. — L’entier S(p, q) est le nombre de parties W ⊂
[ p ] × [ p ] de p − q éléments qui satisfont aux conditions suivantes :
(i) W est une quasi-permutation, c’est-à-dire qu’il existe au moins un
σ ∈ Sp tel que W ⊂ {(k, σ(k)) ∈ [ p ] × [ p ] : k ∈ [ p ]} ;
(ii) W est supra-diagonale, c’est-à-dire que (k, k ′ ) ∈ W implique k < k ′ .
Démonstration. — Soit {E1 , E2 , . . . , Eq } une partition de [ p ] que nous
pouvons considérer comme formée des classes d’une relation d’équivalence
E ⊂ [ p ] × [ p ]. A chaque Ej = {i1 < i2 < · · · < inj } comprenant
nj ≥ 1 éléments, nous associons la quasi-permutation supra-diagonale
Ej′ = {(i1 , i2 ), (i2 , i3 ), . . . , (inj −1 , inj )} S
contenant nj −1 (éventuellement zéro)
′
éléments de [ p ] × [ p ]. Posant E = Ej′ , on voit que E ′ est une quasi-
P 1≤j≤q
permutation supra-diagonale ayant (nj − 1) = p − q éléments et que E est
la plus fine des équivalences sur [ p ] qui contienne E ′ .
6. LES IDENTITÉS DE WORPITZKY 19

Réciproquement, étant donnée une quasi-application supra-diagonale W

ayant p − q éléments, soit E la plus fine de toutes les équivalences sur [ p ]
qui contienne W . On a W = E ′ et la bijection désirée est établie.

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

X
r
An (s + 1) = sk (n − k)! S(n + 1 − r, n + 1 − r − k)
0≤k≤n−r

étant obtenue par celui-ci au moyen de la méthode algébrique classique

d’inversion de Möbius, nous pensons pouvoir nous dispenser d’en reproduire
ici la démonstration.

6. Les identités de Worpitzky

Soient m, n, s trois entiers tels que 0 ≤ s < n ≤ m + s et (i1 , i2 , . . . , is )
une suite strictement décroissante d’entiers compris entre 1 et n − 1 que nous
nommerons indices distingués. Nous allons d’abord dénombrer l’ensemble
Φm,n,s de tous les morphismes φ : [ n ] → [ m ] tels que φ(i) 6= φ(i+1) si i n’est
pas un indice distingué. Le dénombrement de Φm,n,s permet non seulement
d’obtenir l’identité (9) ci-dessous due à Worpitzky, mais une généralisation
de celle-ci au cas des polynômes rAn (t) (r ≥ 2). La proposition 2.9 ci-dessous
est bien connue.
Proposition 2.9. — On a : card Φm,n,s = m+s

n .
Démonstration. — Il suffit de faire correspondre, de façon bijective, à
tout φ ∈ Φm,n,s un morphisme injectif ψ : [ n ] → [m + s] (c’est-à-dire
une application strictement croissante). Dans ce but, désignons pour tout
entier k ∈ [ n ], par θ(k) le nombre d’indices distingués avant k, à savoir
le nombre d’indices j tels que ij < k. On a θ(1) = 0 et θ(n) = s. La
bijection φ 7→ ψ est alors définie de la faç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 distingué, 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 φ 7→ ψ est trivialement injective. Elle est aussi surjective,
puisque φ est uniquement déterminé par les relations φ(k) = ψ(k) − θ(k)
(1 ≤ k ≤ n).

L’identité de Worpitzky sur les nombres eulériens s’obtient par simple

application de cette proposition. L’ensemble de toutes les applications de [ n ]
dans [ m ] étant noté Hn,m , soit φ ∈ Hn,m ; on définit δφ comme l’unique
σ ∈ Sn telle que la suite des paires (φσ(1), σ(1)), (φσ(2), σ(2)), . . . ,
(φσ(n), σ(n)) soit croissante pour l’ordre lexicographique. Par conséquent,
δ −1 σ est l’ensemble des applications φ : [ n ] → [m] telles que φσ(i) ≤ φσ(i+1)
pour i ∈ [n − 1] et telles que l’égalité φσ(i) = φσ(i + 1) ne soit possible que
si σ(i) < σ(i + 1). D’après la remarque 2.4, il y a exactement s = |∆′ M σ|
indices i vérifiant une telle inégalité ; donc, d’après la précédente proposition
20 CHAPITRE II : LES POLYNÔMES EULÉRIENS

card δ −1 σ = m+s

n
. Comme le nombre de permutations σ ∈ Sn satisfaisant
à |∆M σ| = s est donné par le nombre eulérien An,s , il vient enfin
X m + s
n
m = An,s . (9)
n
0≤s≤n−1

Cette identité est un cas particulier de l’identité (10) ci-dessous.

Propriété 2.10. — Pour r ∈ [ n ] et r ≤ m, on a :

X
r m+s m!
An,n−r−s = mn−r . (10)
n (m − r)!
0≤s≤n−r

Démonstration. — Notons d’abord que pour r = 1, on retrouve bien

l’identité (9), puisque l’on a An,n−1−s = An,s d’après la propriété 2.3. D’autre
part, l’identité est vraie pour r = n avec les conventions que nous avons
adoptées. On prendra donc r ∈ [n−1]. Soit Hm,n,r l’ensemble des applications
φ : [ n ] → [m] dont la restriction à {n − r + 1, n − r + 2, . . . , n} est injective.
Il est immédiat que l’on a card Hm,n,r = mn−r m! /(m − r)! Pour φ ∈ Hm,n,r
on définit δφ comme étant l’unique σ ∈ Sn telle que la suite (φσ(1), σ(1)),
(φσ(2), σ(2)), . . . , (φσ(n), σ(n)) soit croissante pour l’ordre lexicographique.
Comme précédemment, on a φσ(i) ≤ φσ(i + 1) pour i ∈ [n − 1], mais l’égalité
n’est possible que si l’on a σ(i) < σ(i + 1) et σ(i) ≤ n − r, puisque la
restriction de φ à l’ensemble {n − r + 1, n − r + 2, . . . , n} est injective. Or,
d’après la remarque 2.4, il y a exactement |∆′ ∆′′r−1 M σ| indices i tels que
1 ≤ i ≤ n − 1, σ(i) < σ(i + 1) et σ(i) ≤ n − r. D’après la précédente
proposition, on a card δ −1 σ = m+s n
avec |∆′ ∆′′r−1 M σ| = s et comme le
nombre de σ ∈ Sn satisfaisant à |∆′ ∆′′r−1 M σ| = s est égal à rAn,n−r−s , on
obtient l’identité désirée.
Pour terminer cette section, nous donnons la formule explicite des coeffi-
cients rAn,k obtenue par un simple calcul traduisant de nouveau l’inversion
de Möbius (cf. par exemple [26]) à partir des identités (9) et (10).
1 X n + r − 1 + k
En effet, pour 1 ≤ n + r, on a = tk . Donc
(1 − t)n+r n+r−1
0≤k

r
An−1+r (t) X k n + r − 1 + k
X
r
= t An+r−1,s ts
(1 − t)n+r n+r−1
0≤k 0≤s≤n−1

n+r−1+j−s
X X
j r
= t An+r−1,s
n+r−1
0≤j 0≤s≤min(j,n−1)

X
j
X
r j+r+s
= t An+r−1,n−1−s
n+r−1
0≤j 0≤s≤n−1
X (j + r)!
= tj (j + r)n−1
j!
0≤j
7. TABLE DES POLYNÔMES EULÉRIENS 21

en utilisant le fait que n+r−1+j−s

n+r−1
= 0 si j ≤ n − 2 et s = j + 1, . . . , n − 1
et pour la dernière étape en se servant de l’identité (10). Il en résulte
r

An−1+r (t) X
j n−1 j + r
= t (j + r) .
r! (1 − t)n+r r
0≤j
On a donc pour 0 ≤ k ≤ n − 1 la formule explicite :

k−i+r

n−1 n + r
X
r i
An−1+r,k = r! (−1) (k − i + r) . (11)
i r
0≤i≤k

7. Table des polynômes eulériens

Le paragraphe 4 du présent chapitre ou l’identité (11) ci-dessus montre
que tous les coefficients des polynômes rAn (t) sont divisibles par r! (on verra
une autre démonstration de ce résultat à la fin du chaitre IV). Comme on a
posé
X
r r
An (t) = An,k tk (0 ≤ r ≤ n),
0≤k≤n−r
on peut écrire
r
An,k = r! ran,k ,
où ran,k est un entier (0 ≤ k ≤ n − r). Le présent tableau donne les premières
valeurs des coefficients ran,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 POLYNÔMES EULÉ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 premières sections de ce chapitre contiennent la définition et

quelques propriétés d’une construction très générale que nous appelons
hh composé partitionnel ii. La motivation de cette notion apparaı̂t dans les

sections suivantes, ainsi qu’au chapitre IV, où nous appliquons toutes ces
techniques aux polynômes eulériens. Comme nous l’avons déjà mentionné,
ces résultats ont été fréquemment étudiés en liaison avec divers problèmes
d’énumération et tout particuliè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 abélien libre engendrés par Z. On appellera mots les
éléments de Z ∗ , qu’on présentera comme des suites g = z1 z2 . . . zr , où z1 , z2 ,
. . . , zr appartiennent à Z ; l’entier r est la longueur du mot g. On appellera
monômes les éléments de Z + . Si α est le morphisme canonique de Z ∗ sur Z + ,
on prendra dans chaque classe α−1 (f ), où f ∈ Z + , un mot canonique qu’on
identifiera à f . Le monôme f sera dit de degré 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 → N. Le même symbole désignera les morphismes dans N étendant
cette application aux monoı̈des Y ∗ et Y + . Le morphisme canonique de Y ∗
sur Y + sera noté α.
Soit P l’ensemble des parties finies (y compris la partie vide) de N ; on
considère le sous-ensemble Yλ du produit cartésien Y × P composé de tous
les couples (y, I) satisfaisant à la condition card I = λy. On forme ensuite le
monoı̈de libre Yλ∗ engendré par Yλ . Soit

h = (y1 , I1 )(y2 , I2 ) . . . (yr , Ir )

un mot de Yλ∗ de longueur r ≥ 1. On pose
βh = g = y1 y2 . . . yr ∈ Y ∗ et λh = λg. (1)

Définition 3.1. — Pour chaque entier r ≥ 1, le composé partitionnel

marqué de Y de degré r est le sous-ensemble Y ((r)) de Yλ∗ formé de tous les
mots h = (y1 , I1 )(y2 , I2 ) . . . (yr , Ir ) de longueur r satisfaisant aux conditions
(i) SIj ∩ Ij ′ = ∅ si j 6= j ′ ;
(ii) {Ij : j ∈ [r]} = [λh].
24 CHAPITRE III : LA FORMULE EXPONENTIELLE

On notera que si λyj est strictement positif pour tout j ∈ [r], la famille
{I1 , I2 , . . . , Ir } est une partition de l’ensemble [λh], aucun de ces sous-
ensembles n’étant vide.
Par convention, on supposera l’existence d’un ensemble Y ((r)) pour r = 0
contenant un seul élément, à savoir l’élément neutre de Y . Ce dernier est
envoyé par β sur l’élément neutre de Y ∗ . On identifiera, d’autre part, le
composé partitionnel marqué Y ((1)) de degré 1 avec Y .
P
Théorème 3.3 (Formule de Hurwitz). — Soit E(Y ) = {y/λy! : y ∈ Y }
la fonction génératrice exponentielle de Y (par rapport à λ). Pour tout r ≥ 0,
on a dans la Q-algèbre large de Y ∗ l’identité
r X
E(Y ) = {βh/λh! : h ∈ Y ((r)) }. (2)

Démonstration. — Avec nos conventions sur β, il n’y a rien à prouver

pour r = 0. Pour chaque mot g = y1 y2 . . . yr de longueur r (r ≥ 1) de Y ∗ ,
le nombre de mots h ∈ Y ((r)) tels que βh = g est égal au nombre de suites
(I1 , I2 , . . . , Ir ) de parties de N satisfaisant aux conditions (i) et (ii) de la
définition 3.1 ainsi qu’à la condition card Ij = λyj pour chaque j ∈ [r]. Or, le
nombre de telles suites est évidemment donné par le coefficient multinomial

λ λg!
= .
g λy1 ! λy2 ! . . . λyr !
Donc
X 1
{βh/λh! : h ∈ Y ((r)) , βh = g} = g,
λy1 ! λy2 ! . . . λyr !
puisque λh = λg pour βh = g. Or, le facteur 1/(λy1 ! λy2 ! . . . λyr !) est
r
simplement le coefficient de g dans le développement de E(Y ) et le résultat
s’en déduit par sommation sur tous les mots de longueur r de Y ∗ .

2. Le composé partitionnel
Nous conservons les mêmes notations que dans la section 1, mais
nous supposons cette fois que λy > 0 pour tout y ∈ Y . Soit h =
(y1 , I1 )(y2 , I2 ) . . . (yr , Ir ) un mot de Y ((r)) . L’hypothèse ci-dessus entraı̂ne,
puisque l’on a card Ij = λyj pour chaque j ∈ [r], que les sous-ensembles I1 ,
I2 , . . . , Ir sont non vides, donc tous distincts. Il en résulte que h est multi-
linéaire, c’est-à-dire a toutes ses lettres distinctes. En notant δ le morphisme
canonique de Yλ∗ sur Yλ+ , on voit donc que la classe abélienne δ −1 δh contient
exactement r! mots. De plus, les conditions (i) et (ii) de la définition 3.1 ne
faisant pas intervenir l’ordre des lettres de h, il s’ensuit que Y (r)) contient
toute une classe abélienne δ −1 δh dès qu’il contient h.
Définition 3.3. — On appelle composé partitionnel S de Y , de degré r
(r) ((r)) (+) (r)
(r ≥ 0), l’ensemble Y = δY et l’union Y = Y est le composé
partitionnel de Y . 0≤r
2. LE COMPOSÉ PARTITIONNEL 25

Les éléments de Y (r) sont donc des monômes f = (y1 , I1 )(y2 , I2 ) . . . (yr , Ir )
de Yλ+ . On désigne par γf le monôme m = y1 y2 . . . ys de Y + et l’on pose
encore λf = λm. On a donc l’identité
αβ = γδ
où α est le morphisme α : Y ∗ → Y + et où β a été dé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 à la formule fondamentale de ce chapitre.
Théorème 3.5 (Formule exponentielle). — Dans la Q-algèbre large
de Y + , on a l’identité
X
{γf /λf ! : f ∈ Y (+) } = exp E(Y ).

Démonstration. — On a {γf /λf ! : f ∈ Y (0) } = 1. D’autre part, pour

P
f ∈ Y (r) (r ≥ 1), onX
a
{αβh/λh! : δh = f } = r! (γf /λf !)
d’après le lemme précédent. D’où, il résulte
X 1 X
{γf /λf ! : f ∈ Y (r) } = {αβh/λh! : h ∈ Y ((r)) }
r!
pour chaque r ≥ 1. Utilisant le théorème 3.2, on obtient donc par sommation
sur tous les r ∈ N
X X 1 r
{γf /λf ! : f ∈ Y (+) } = E(Y ) = exp E(Y ).
r!
0≤r

Remarque 3.6. — Dans la Q-algèbre large de Y + , onPa pris la topologie

des séries formelles induite par l’ordre o suivant : si a = {m am : m ∈ Y + }
est une série formelle, son ordre o(a) est défini par
o(a) = inf{n ≥ 1 : λm = n, am 6= 0}.
Utilisons les notations abrégées
X
γ{Y (+) ∩ λ−1 n} = {λf : f ∈ Y (+) , λf = n} (n ≥ 0);
X
{Yn } = {y : y ∈ Y, λy = n} (n ≥ 1).

Les séries formelles γ{Y (+) ∩ λ−1 n} et {Yn } sont d’ordre égal à n, ce qui
permet d’écrire la formule exponentielle sous la forme :
X 1 X 1
γ{Y (+) ∩ λ−1 n} = exp {Yn } . (3)
n! n!
0≤n 1≤n
26 CHAPITRE III : LA FORMULE EXPONENTIELLE

3. Une formule d’inversion pour les séries exponentielles

Pour f ∈ Y (+) désignons par z(f ) l’unique r ∈ N tel que f ∈ Y (r) ;
l’entier z(f ) n’est autre que le degré de f . Posons
X
γ{Y (+) ∩ λ−1 n} = {λf · (−1)z(f )+n : f ∈ Y (+) , λf = n} (n ≥ 0).

Propriété 3.7. — Dans la Q-algèbre large de Y + , on a l’identité

X 1 −1 X (−1)n
(+) −1
γ{Y ∩ λ n} = γ{Y (+) ∩ λ−1 n}. (4)
n! n!
0≤n 0≤n

Démonstration. — D’après le théorème 3.5, le membre de gauche

de l’identité à établir, soit U , est égal à (exp(E(Y ))−1 , c’est-à-dire à
exp(−E(Y )). Notons φ le morphisme envoyant sur −y chaque y ∈ Y ; ceci
équivaut à U = φ exp E(Y ), donc de nouveau d’après le théorème 3.5, à
X 1 X 1 X
U =φ γ{Y (+) ∩ λ−1 n} = (−1)r γ{Y (+) ∩ λ−1 n ∩ z −1 r}
n! n!
0≤n 0≤n 0≤r
X (−1)n
= γ{Y (+) ∩ λ−1 n}.
n!
0≤n

Ceci termine l’établissement des formules que nous utiliserons par la suite.
Le théorème 3.2 avc une interprétation
P adéquate des objets
P en cause exprime
que la transformation de Borel {y : y ∈ Y } 7→ {y/λy! : y ∈ Y } est
+
un morphisme dans l’algèbre large de Y de l’algèbre large de base Y par
rapport au hh produit d’intercalement ii (hh shuffle ii de Chen, Fox et Lyndon). Le
théorème 3.5 est appelé hh formule de Cauchy ii dans les problèmes concernant
le groupe symétrique. Sous une forme ou sous une autre, elle a été retrouvée
et utilisée souvent dans diverses questions d’énumération. Nous l’appellerons
simplement formule exponentielle. En prenant le logarithme, on obtiendrait
évidemment la fonction génératrice exponentielle E(Y ) de Y en fonction de
la fonction génératrice exponentielle du composé partitionnel Y (+) de Y .
Définition 3.8. — Soient Y (+) un composé partitionnel et A un monoı̈de
abé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.
µ
Y (+) ✲ A
✯
✟
✟
γ ✟
❄ ✟✟ ′
✟ µ
Y+
4. LE COMPOSÉ PARTITIONNEL DES APPLICATIONS 27

4. Le composé partitionnel des applications

Il existe de nombreuses familles de structures qui peuvent être consi-
dérées comme le composé partitionnel d’une de leurs sous-familles. Nous
examinerons ici, à titre d’exemple, la famille des applications avec le but
d’introduire les notions nécessaires pour traiter le cas particulier des permu-
tations.

Définition 3.9. — Soit f : I → I une application d’un ensemble fini I dans

lui-même. L’équivalence f ∗ de f est la relation d’équivalence dans I × I telle
que deux éléments i et i′ de I appartiennent à la même classe si et seulement
′ ′
s’il existe des itérées f p et f p de f satisfaisant à f p (i) = f p (i′ ).

Nous appellerons sous-domaines de f les classes de cette équivalence et

leur nombre sera désigné 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 Fn l’ensemble S des applications de [ n ] dans
lui-même (n ≥ 0) et l’on posera F = 0≤n Fn . Désignons par I1 , I2 ,
. . . , Ir (r = z(f )) les sous-domaines d’une application f ∈ Fn (n ≥ 1).
Pour tout j ∈ [r], on note ωj l’unique morphisme (d’ensembles ordonnés)
ωj : [card Ij ] → [ n ] qui a pour image Ij et fj′ la restriction de f à Ij .
Par définition de l’équivalence f ∗ on voit que fj′ (Ij ) ⊂ Ij et il est licite de
poser fj = ωj−1 fj′ ωj (j ∈ [r]). Les applications fj envoient [card Ij ] dans
lui-même et sont toutes connexes (j ∈ [r]). Enfin, il est clair que toute
application f ∈ Fn détermine, de façon biunivoque le monôme (appartenant
au monoı̈de (F × P)+ , où P désigne toujours l’ensemble des parties finies
de N) (f1 , I1 )(f2 , I2 ) . . . (fr , Ir ), que l’on appellera sa factorisation canonique,
les fj eux-mêmes étant les facteurs de f . Par commodité, on identifiera tout
f ∈ F avec sa factorisation canonique et f ∈ F0 avec le monôme unité.
Le raccordement avec les trois premières sections se fait de la façon sui-
vante. Soit donnée une famille F d’applications connexes dont les domaines
sont des ensembles de la forme [ n ] (n ∈ N). Posons Y = F et prenons pour λ
l’application qui envoie sur n chaque f ∈ F de domaine [ n ] (n ∈ N). Formons
ensuite le composé partitionnel F (+) . On constate alors que la factorisation
canonique d’une application f ∈ F appartient au composé partitionnel F (+)
si et seulement si les facteurs de f appartiennent à 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 composé partitionnel F (+) est l’ensemble des applications f ∈ F dont les
facteurs appartiennent à F .
La propriété suivante découle immédiatement de la définition du composé
partitionnel d’un ensemble d’applications. Elle exprime le fait que la factori-
sation canonique d’une application f conserve les excédances et les points
fixes de f .
28 CHAPITRE III : LA FORMULE EXPONENTIELLE

Propriété 3.11. — Soit (f1 , I1 )(f2 , I2 ) . . . (fr , Ir ) (r ≥ 1) la factorisa-

tion canonique d’une application f . Pour tout j ∈ [r], le morphisme τj = ωj−1
est une bijection de Ij sur [card Ij ] telle que pour tout i ∈ Ij on ait les
équivalences : i < f (i) ⇔ τj (i) < fj τj (i) ; i = f (i) ⇔ τj (i) = fj τj (i) ;
i > f (i) ⇔ τj (i) > fj τj (i).
Démonstration. — En effet, si l’entier i est dans le sous-domaine Ij , on a
fj (i) = ωj−1 fj′ ωj (i) = τj fj′ τj−1 (i) où fj′ est la restriction de f à Ij . Les
équivalences ci-dessus résultent alors du fait que τj : Ij → [card Ij ] est un
morphisme strictement croissant.

Récrivons la formule exponentielle (3) et la formule d’inversion (4) dans

ce cas particulier du composé partitionnel des applications. On a d’abord
F (+) ∩ λ−1 n = Fn ∩ F (+) pour n ≥ 0 et F ∩ λ−1 n = Fn ∩ F pour n ≥ 1 et
les deux identités (3) et (4) se présentent ainsi
X 1 X 1
(+)
γ{Fn ∩ F } = exp {Fn ∩ F } ; (5)
n! n!
0≤n 1≤n
X 1 −1 X (−1)n
γ{Fn ∩ F (+) } = γ{Fn ∩ F (+) }. (6)
n! n!
0≤n 0≤n

En fait, ces deux identités seront appliquées ci-après sous la forme sui-
vante. On suppose donnée une application multiplicative µ : F (+) → Ω (cf.
définition 3.8). On forme ensuite l’algèbre sur Q du monoı̈de Ω ; notons Ω
cette algèbre. On considère enfin l’algèbre Ω[[u]] des séries formelles à coef-
ficients dans Ω et à une indéterminée u.
Proposition 3.12. — Soit µ : F (+) → Ω une application multiplicative.
Dans l’algèbre des séries formelles Ω[[u]], on a les identités :
X un X un
µ{Fn ∩ F (+) } = exp µ{Fn ∩ F } ; (7)
n! n!
0≤n 1≤n
X un −1 X (−u)n
µ{Fn ∩ F (+) } = µ{Fn ∩ F (+) }. (8)
n! n!
0≤n 0≤n

où µf = (−1)z(f )+n µf pour tout f ∈ Fn ∩ F (+) (n ≥ 0).

Démonstration. — Soit µ′ le morphisme de F + dans Ω tel que µ = µ′ γ.
Désignons par φ l’application envoyant tout f ∈ Fn ∩ F sur le monôme
un µ′ f (n ≥ 0). Comme µ est multiplicative, on a φγf = un µf pour tout
f ∈ Fn ∩ F (+) (n ≥ 0). Tous les monômes φγf où f ∈ Fn ∩ F (+) sont donc
de degré n (en u). On peut donc prolonger φ en un morphisme continu de
la Q-algèbre large de F + dans Ω[[u]]. Appliquant ainsi φ aux deux membres
des deux identités (5) et (6), on obtient les identités (7) et (8).
5. APPLICATIONS 29

5. Applications
Il est évident que si F est l’ensemble C des permutations
S circulaires, le
composé partitionnel C (+) est exactement l’ensemble S = 0≤n Sn . On a de
plus Fn ∩ F (+) = Sn pour n ≥ 0 et Fn ∩ F = Cn pour n ≥ 1. Enfin, si σ est
dans Sn , 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 identités (7) et (8) s’écrivent :
X un X un
µ{Sn } = exp µ{Cn } ; (9)
n! n!
0≤n 1≤n
X un −1 X (−u)n
µ{Sn } = µ{Sn }. (10)
n! n!
0≤n 0≤n

où µσ = ǫ(σ)µσ pour tout σ ∈ S. Donnons quelques exemples d’application

des formules (9) et (10).
Soit (xn )n≥1 une suite d’indéterminées commutatives. Si σ est dans Sn ,
posons µσ = xm 1 m2 mn
1 x2 . . . xn , où, pour tout k ∈ [ n ], l’entier mk est le
nombre de cycles de longueur k dans la σ. La fonction µ ainsi définie est
multiplicative. Dans ce cas, µ{Sn } est le polynôme indicateur de cycles de Sn
ou polynôme de Bell (cf. [24] p. 68) et (un /n!)µ{Cn } se réduit à un xn /n
puisque card Cn = (n−1)! La formule exponentielle permet donc de retrouver
l’expression de la fonction génératrice exponentielle de ces polynômes, à
savoir X un X un
µ{Sn } = exp xn .
n! n
0≤n 1≤n
Un autre exemple de composé partitionnel est donné par l’ensemble U
des applications ultimement idempotentes, c’est-à-dire, pour tout n ≥ 0, des
applications f ∈ Fn telles que f n = f n−1 . Considérons, en effet, pour tout
entier n ≥ 1, l’ensemble Vn des applications f ∈ Fn , dont l’image de la
(n − 1)ième itérée f n−1 soit réduite à un seulS
point. Les éléments de Vn sont
encore appelés arborescences. Posons V = 1≤n Vn ; il est alors clair que
le composé partitionnel de V est l’ensemble U . Posons Un = Fn ∩ U pour
n ≥ 0 ; on obtient donc pour toute application multiplicative µ : U → Ω,
deux identités analogues à (9) et (10) en substituant Un à Sn , Vn à Cn et en
posant µf = (−1)z(f )+n pour tout f ∈ Un (n ≥ 1). On pose naturellement
µU0 = µU0 = 1.
En particulier, prenons pour µ l’application qui envoie sur 1 tout f ∈ U .
Comme on a, de façon évidente card Vn = n card Un−1 pour n ≥ 1, il vient
X un X un
µ{Vn } = u card Un
n! n!
0≤n 0≤n

et on retrouve, en appliquant
P n la formule (7), ce résultat bien connu : que la
série formelle w = (u /n!) card Un est solution dans Q[[u]] de l’équation
w = exp(uw). 0≤n
30 CHAPITRE III : LA FORMULE EXPONENTIELLE

Enfin, prenons pour F l’ensemble G de toutes les applications connexes

de F . Dans ce cas, le composé partitionnel de G est F tout entier et l’on
obtient encore, pour toute application multiplicative µ : F → Ω donnée,
deux identités analogues à (9) et à (10).

6. Une identité entre déterminants et permanents

Dans l’énoncé qui suit, Ξ est une matrice infinie Ξ = (ξi,j )(i,j=1,2,... ) à
coefficients dans un anneau commutatif Ω ; on désigne pour tout n ≥ 1
par Ξn la matrice (ξi,j )(1≤i,j≤n) , par det Ξn son déterminant et par per Ξn
son permanent.
Théorème 3.13. — Soient a, b et c trois éléments de Ω et Ξ une
matrice infinie ayant ses coefficients supradiagonaux (resp. diagonaux, resp.
infradiagonaux) égaux à a (resp. b, resp. c). On a l’identité
X un −1 X (−u)n
1+ per Ξn =1+ det Ξn . (11)
n! n!
1≤n 1≤n

Démonstration. — Désignons par ξi,j les éléments de la matrice Ξ, puis

posons µσ = ξ1,σ(1) ξ2,σ(2) . . . ξn,σ(n) pour tout σ ∈ Sn . Avec les notations de
la propriété 3.11 (en prenant f = σ), on voit que pour un entier i appartenant
au sous-domaine
Q Q (i.e. à l’orbite) Ij , on a ξi,σ(i) = ξτj (i),fj τj (i) . On a ainsi
µσ = j i ξi,σ(i) , où j varie dans [r] et où i, pour j fixé, varie dans Ij .
′
Si i est dans Ij , l’élément
Q Qi = τj (i) estQdans [card Ij ] et l’on a, d’après
ce qui précède, µσ = j i′ ξi′ ,fj (i′ ) = j µfj . L’application µ est donc
multiplicative et l’on peut écrire
X
µ{Sn } = ξ1,σ(1) · · · ξn,σ(n) = per Ξn ;
σ
X
µ{Sn } = ǫ(σ)ξ1,σ(1) · · · ξn,σ(n) = det Ξn .
σ
Le théorème 3.13 résulte alors de l’identité (10).

Remarque 3.14. — Notons que l’identité (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 considérées dans l’énoncé du théorème 3.13 pour
lesquelles l’identité (11) est vérifiée. Par exemple, si la première colonne de
la matrice Ξ n’a que des zéros, on a per Ξn = det Ξn = 0 pour tout n ≥ 1 et
l’identité (11) est trivialement vérifiée.
De même, considérons la matrice Ξ définie par
1, si 1 ≤ i ≤ j ;
(
ξi,j = −(i − 1), si 1 ≤ i − 1 = j ;
0, si 1 ≤ j ≤ i − 2.
On obtient facilement per Ξ1 = 1 et per Ξn = 0 pour tout n ≥ 2, ainsi que
det Ξn = n! pour tout n ≥ 1. P L’identité (11) est encore vérifiée ; on retrouve
en fait l’identité (1 + u)−1 = 0≤n (−u)n .
6. UNE IDENTITÉ ENTRE DÉTERMINANTS ET PERMANENTS 31

Notons enfin le résultat élémentaire (pour n ≥ 1)

n n
 c(b − a) − a(b − c)

, si c 6= a ;
det Ξn = c−a
= (b − a)n−1 (b + (n − 1)a), si c = a.


Portant ces valeurs dans la formule (11), on est conduit à l’identité

X un −1
1+ per Ξn
n!
1≤n
 c exp((a − b)u) − a exp((c − b)u) , si c 6= a;


= c−a (12)

(1 − au) exp((a − b)u), si a 6= b et c = a.
CHAPITRE IV

FONCTIONS GÉNÉRATRICES
DES POLYNÔMES EULÉRIENS

1. Fonction génératrice exponentielle de 0An (t), An (t), Bn (t)

Pour σ ∈ Sn (n ≥ 1), nous dé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
définition de E et ∆E on a donc immédiatement : |Eσ| = |E ′ σ| + |∆Eσ|.
′
Introduisant une nouvelle indéterminée t′ , nous posons θ ′ σ = t′|E σ| t|∆Eσ| et
An (t, t′ ) = θ ′ Sn (= 1 pour n = 0). Par conséquent, on a
0
An (t) = An (t, t); An (t) = An (t, 1);
An (t, 0) = θ∆E{σ ∈ Sn : |E ′ σ| = 0} = θ∆EDn = θEDn = Bn (t).

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

Théorème 4.1. — On a
X un
A(t, t′ , u) = An (t, t′ ) = exp(ut′ + C(t, u)), (1)
n!
0≤n
où X un
C(t, u) = t An−1 (t). (2)
n!
2≤n

Démonstration. — Que θ ′ soit multiplicative découle de la propriété 3.11

et des définitions des vecteurs E ′ σ et ∆Eσ (σ ∈ Sn ). Par conséquent, le mem-
(u /n!) θ ′ {Cn }).
P n
bre de droite de l’identité (9) du chapitre III devient exp(
1≤n
′ ′
Pour n = 1, on a θ {Cn } = t et pour n ≥ 2, d’après les propriétés 2.2 et 2.3,
on a : θ ′ {Cn } = θ∆E{Cn } = t An−1 (t).

Le théorème 4.1 nous a donné une identité sur les polynômes An (t, t′ ).
Nous allons maintenant trouver une formule explicite pour la fonction
génératrice A(t, t′ , u) en utilisant les résultats de la section 6 du chapitre III.
Théorème 4.2. — On a :
X un 1−t
A(t, t′ , u) = An (t, t′ ) = . (3)
n! exp((t − t )u) − t exp((1 − t′ )u)
′
0≤n
1. FONCTION GÉNÉRATRICE EXPONENTIELLE 33

En particulier,
X un 1−t
0
A(t, t, u) = An (t) = ; (4)
n! 1 − t exp((1 − t)u)
0≤n
X un 1−t
A(t, 1, u) = An (t) = ; (5)
n! −t + exp((t − 1)u)
0≤n
X un 1−t
A(t, 0, u) = Bn (t) = . (6)
n! exp(ut) − t exp(u)
0≤n

Démonstration. — Avec les notations du théorème 3.13, si l’on pose a = t,

b = t′ et c = 1, on a pour σ ∈ Sn (n ≥ 1) l’égalité ξ1,σ(1) . . . ξn,σ(n) = θ ′ σ ;
soit An (t, t′ ) = per Ξn . La première identité ré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 procédé

suivant. D’après la propriété 2.2, on a 0An (t) = t An (t) pour tout n ≥ 1 ; on
en tire
X un X un
0
A(t, t, u) = An (t) = 1 + t An (t),
n! n!
0≤n 1≤n
soit
A(t, t, u) = 1 + t(A(t, 1, u) − 1). (7)
D’autre part, d’après le théorème 3.9 on a
exp(C(t, u)) = A(t, 1, u) exp(−u) (8)
ou encore
A(t, t, u) = exp(ut − u)A(t, 1, u). (9)

Du système formé par les deux équations (7) et (9), on déduit immédiatement
les identités (4) et (5). On calcule ensuite C(t, u) en utilisant la formule (8)
et l’on en tire l’identité (3) en se servant du théorème 4.1.
Remarque 4.4. — Les formules (4) et (5) sont connues (cf. Riordan [24],
p. 215 et 39). La formule (6) a été obtenue par Roselle [25], par les méthodes
traditionnelles du calcul différentiel et intégral, dans le cas particulier où
Bn (t) = θM Gn (n ≥ 1).
Notons encore que du théorème 4.1 résulte immédiatement, par sim-
ple dérivation, que la fonction génératrice A = A(t, 1, u) est solution de
l’équation différentielle de Bernoulli :

∂
A = A(1 + t(A − 1)).
∂u
On peut aussi prouver ce résultat directement et pour ce faire, nous ferons
la convention suivante que nous utiliserons encore dans la section 2 : si σ est
34 CHAPITRE IV : FONCTIONS GÉNÉRATRICES

dans Sn (n ≥ 1), on considère σw comme le mot σ(1)σ(2) . . . σ(n) dont les

lettres sont les éléments de [ n ] ; lorsque σ est l’élément unique σ0 ∈ S0 , alors
σw est le mot vide σ0 w. Si f = y1 y2 . . . ym est un mot dont les lettres y1 , y2 ,
. . . , ym sont des entiers tous distincts, on désigne par ω l’unique morphisme
surjectif ω : {y1 , y2 , . . . , ym } → [ m ] et l’on note ωf le mot ωy1 ωy2 . . . ω ym .
On pose encore ωσ0 w = σ0 w.
Prenons alors un mot σw ∈ Sn+1 (n ≥ 0) ; il s’écrit univoquement
σw = f (n + 1)f ′ . Considérons l’application σw 7→ (ωf, ωf ′ ) ; on a ωf ∈ Sm
et ωf ′ ∈ Sn−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
où, comme d’usage, δn,m = 1 ou 0 selon que m = n ou m 6= n. D’autre part,
l’image réciproque par l’application ci-dessus du couple (τ w, τ ′ w) où τ ∈ Sm
n
et τ ′ ∈ Sn−m , contient m

éléments. On en déduit :
X n
An+1 (t) = An (t) + t Am (t)An−m (t) (n ≥ 0).
m
0≤m≤n−1

Il en résulte que la fonction génératrice A = A(t, 1, u) est bien solution de

l’équation différentielle précédente. Ce résultat a été établi pour la première
fois par Riordan [23].

2. Fonction génératrice exponentielle des polynômes rAn (t)

Pour r ≥ 1 posons

r
X un−r+1 r
An (t, u) = An (t).
(n − r + 1)!
r−1≤n

On a en particulier 1A(t, u) = A(t, 1, u), dont on connaı̂t déjà la formule

explicite (cf. (5)). Le but de la présente section est d’établir l’identité
remarquable suivante, due à Riordan ([24] p. 235)
r
A(t, u) = (r − 1)! 1A(t, u) .
r

Sn+r−1 sur Sr−1 × S((r)) . — Il s’agit

S
Construction d’une bijection de
0≤n
d’une bijection sur le produit cartésien de Sr−1 par le composé partitionnel
marqué S((r)) (r ≥ 1). Pour définir ce dernier, il faut munir l’ensemble S
d’une application λ ; nous prenons naturellement l’application définie par
λσ = n ⇔ σ ∈ Sn (n ∈ N).
Notons que l’élément unique σ0 ∈ S0 appartient à S, satisfait à λσ0 = 0
et est distinct de l’élément neutre e du monoı̈de S∗ pour lequel on a aussi
λe = 0.
2. FONCTION GÉNÉRATRICE EXPONENTIELLE DES POLYNÔMES 35

Soit maintenant σ ∈ Sn+r−1 (0 ≤ n) ; le mot σw s’écrit univoquement

σw = g1 i1 g2 i2 . . . gr−1 ir−1 gr où {i1 , i2 , . . . , ir−1 } = [r−1] et où g1 , g2 , . . . , gr
sont des mots (éventuellement vides) dont les lettres sont des entiers. Soient
I1 , I2 , . . . , Ir les sous-ensembles de N dont les éléments sont respectivement
les lettres des mots g1 , g2 , . . . , gr . Posant σj w = ωgj pour chaque j ∈ [r]
(où ω est le morphisme défini à la fin de la section précédente et où l’on a
σj = σ0 si le mot gj est vide), on voit immédiatement que le mot

h = (σ1 , I1 )(σ2 , I2 ) . . . (σr , Ir )

est un élément du composé partitionnel marqué S((r)) .

On note β ′ σ (= βh dans les notations du chapitre III) le mot σ1 σ2 . . . σr ∈
∗
S de longueur r. Soit ensuite σw la permutation définie par σw =
i1 i2 . . . ir−1 . On a σ ∈ Sr−1 et comme λh = λβ ′ σ = λσ1 + · · · + λσr =
λσ − (r − 1) = n, on voit que l’application σ 7→ (σ, h) envoie Sn+r−1 dans
Sr−1 × S((r)) ∩ λ−1 n. Il est d’autre part immédiat de vérifier que cette ap-
plication est bijective. Ceci achève la construction de la bijection cherchée.
Maintenant, puisque card Sr−1 est égal à (r − 1)!, on peut écrire
Xn β′σ [ o Xn βh o
:σ∈ Sn+r−1 = (r − 1)! : h ∈ S((r))
(λσ − r + 1)! λh!
0≤n
Xn σ or
= (r − 1)! :σ∈S ,
λσ!

d’après le théorème 3.2. Notant ̟r σ l’image abélienne de β ′ σ, on obtient

l’identité suivante valable dans l’algèbre large sur Q du monoı̈de abélien S+
Xn ̟r (σ) [ o Xn σ or
: σ∈ Sn+r−1 = (r − 1)! : σ ∈S . (10)
(λσ − r + 1)! λσ!
0≤n

Soient enfin µ : S+ → Ω un morphisme dans un monoı̈de abélien Ω et u une

indéterminée. Comme déjà vu au chapitre III, on vérifie que l’application
σ 7→ uλσ µσ (σ ∈ S) peut être prolongée en un morphisme continu φ de
la Q-algèbre large de S+ dans Ω[[u]]. Appliquant φ aux deux membres de
l’identité (10), on trouve
X un X un r
µ̟r {Sn+r−1 } = (r − 1)! µ{Sn } . (11)
n! n!
0≤n 0≤n

r
Théorème 4.5. — Pour r ≥ 1 on a : rA(t, u) = (r − 1)! 1A(t, u) .
Démonstration. — Pour r = 1, il n’y a rien à prouver. Supposons r ≥ 2 et
prenons pour µ le morphisme prolongeant l’application σ 7→ θ∆Dσ = t|∆Dσ|
au monoı̈de S+ . Si l’on a σ ∈ Sn+r−1 et σw = g1 i1 g2 i2 . . . gr−1 ir−1 gr
36 CHAPITRE IV : FONCTIONS GÉNÉRATRICES

avec {i1 , i2 , . . . , ir−1 } = [r − 1], il vient |∆Dgj | = |∆Dωgj | (j ∈ [r]),

puisque ω est un morphisme injectif. D’autre part, puisque le mot g1 g2 , . . . gr
contient toutes P les lettres du mot σw supérieures ou égales à r, on a
′r−1
|∆ ∆Dσ| = j |∆Dωgj |, d’où µ̟r σ = θ∆′r−1 ∆Dσ. On obtient alors,
d’après la propriété 2.2, µ̟r {Sn+r−1 } = rAn+r−1 (t). Comme on a d’autre
part µ{Sn } = An (t), le théorème 4.5 résulte de l’identité (11).

3. Autres interprétations des polynômes eulériens

Les techniques du chapitre précédent pourraient être appliquées à d’autres
problèmes d’énumération. Par exemple, au lieu d’introduire la fonction
multiplicative θ ′ du paragraphe 1, on peut, pour chaque σ ∈ Sn (n ≥ 1),
poser µσ = θ ′ σ · r z(σ) , où r est une indéterminée et où z(σ) est le nombre
de cycles de σ. La fonction µ est évidemment multiplicative et l’on peut
appliquer la proposition 3.12. De plus, on a, comme dans la démonstration
du théorème 4.1
µ{Cn } = t′ r, pour n = 1 ;
= r θ∆ECn = r t An−1 (t), pour n ≥ 2.
La proposition 3.12 conduit donc à l’identité, dans laquelle µ{S0 } = 1,
X un X un
µ{Sn } = exp r(ut′ + t An−1 (t)) . (12)
n! n!
0≤n 2≤n

Le membre de gauche de cette dernière identité est la fonction génératrice

exponentielle des permutations classées à la fois par nombre de cycles et
par nombre d’excédances. Maintenant les identités (3) et (12), ainsi que le
théorème 4.1 permettent d’écrire, lorsque r est un entier positif,
X un r
µ{Sn } = A(t, t′ , u) . (13)
n!
0≤n

On obtient donc d’après (3) la formule explicite de cette fonction génératrice

exponentielle.
Si nous posons identiquement t′ = 1, nous obtenons
X
µ{Sn } = {t|∆Eσ| r z(σ) : σ ∈ Sn }
que nous désignons par Qn (t, r) (n ≥ 1). On posera également Q0 (t, r) = 1.
Il résulte de (13) que l’on a, lorsque r est un entier positif,
X un r
(r − 1)! Qn (t, r) = (r − 1)! 1A(t, u)
n!
0≤n
= rA(t, u) [d’après le théorème 4.5]
X un
r
= An+r−1 (t).
n!
0≤n

On en déduit une nouvelle interprétation des polynômes rAn (t), à savoir

r
An+r−1 (t) = (r − 1)! Qn (t, r) (r ≥ 1). (14)
2. FONCTION GÉNÉRATRICE EXPONENTIELLE DES POLYNÔMES 37

Enfin, désignons par s(σ) le nombre des éléments saillants de la suite σw

où σ ∈ Sn (n ≥ 1). Comme l’on a |M σ̂| + |∆Eσ| = n et s(σ̂) = z(σ), on
obtient
X X
{t|M σ| r s(σ) : σ ∈ Sn } = tn {t−|∆Eσ| r z(σ) : σ ∈ Sn }
= tn Qn (t−1 , r). (15)

Le premier membre de l’identité (15) est le polynôme générateur des per-

mutations σ ∈ Sn classées à la fois suivant leur nombre d’éléments saillants
et leur nombre de montées. Ce polynôme générateur a été considéré pour la
première fois par Dillon et Roselle [10] qui ont à son sujet prouvé un cer-
tain nombre d’identités, qu’on pourrait retrouver à partir des formules (14)
et (15) et des résultats de ce chapitre.
Enfin, notons que la propriété 2.6 fait apparaı̂tre que les coefficents des
polynômes rAn (t) sont tous divisibles par r! (ce que ne fait pas apparaı̂tre le
théorème 4.5). Si donc on pose
r
An (t) = r! rPn (t),

il semble intéressant d’obtenir une interprétation pour les polynômes rPn (t)
(0 ≤ r ≤ n).
D’abord, si r = n, on a rPn (t) = 1 et pour r = 0 et 1, on a rPn (t) = rAn (t).
On fait donc l’hypothèse 2 ≤ r ≤ n−1. La restriction de tout σ ∈ Sn à [n−r]
est une injection de [n − r] dans [ n ] que nous noterons φσ. L’application φ
est évidemment une surjection de Sn sur l’ensemble In−r,n des injections de
[n − r] dans [ n ] telle que l’image inverse de tout τ ∈ In−r,n a r! éléments.
Introduisons l’application Λ de Np (p ≥ 1) dans lui-même envoyant chaque
vecteur (x1 x2 , . . . , xp ) sur ((x1 − 1)+ , (x2 − 1)+ , . . . , (xp − 1)+ ). On a ainsi
∆ = ∆′′ Λ = Λ∆′′ et ∆r = ∆′′r Λr pour r ≥ 1. Définissant le vecteur-
excédance d’une injection de façon évidente, on a ainsi
∆r Eσ = (σ(1) − r)+ , . . . , (σ(n − r) − r)+ = Λr Eφσ.

D’où l’on déduit ∆r ESn = r! Λr E In−r,n et par suite

r 1
An (t) = rPn (t) = θΛr E In−r,n .
r!

Cette dernière interprétation des polynômes rAn (t)/r! est due à Strosser [28].
CHAPITRE V

LES SOMMES ALTERNÉES An (−1) ET Bn (−1)

1. Distribution du nombre des descentes sur S′n

Nous attachons à chaque σ ∈ S′n (= {σ ∈ Sn : σ(1) = n}) un mot noté
V (σ) = v1 v2 . . . vn dans les lettres de l’alphabet X = {m, m, d, d} par les
règles suivantes, où, par définition, σ(n + 1) = σ(1) ( = n).
(1) Pour chaque j ∈ [ n ], on a vj ∈ {d, d} ou vj ∈ {m, m} selon que
σ(j) > σ(j + 1) ou σ(j) < σ(j + 1) ;
(2) si vj ∈ {d, d}, j ∈ [n − 1], on a vj = d ou d selon que vj+1 est dans
{d, d} ou dans {m, m} ;
(3) si vj ∈ {m, m}, (2 ≤ j ≤ n), on a vj = m ou m selon que vj−1 est
dans {m, m} ou dans {d, d}.
En raison de σ(1) = σ(n + 1) = n, on a toujours v1 ∈ {d, d}, vn ∈
{m, m} et les seules occurrences des lettres d et m se rencontrent dans
les facteurs vj vj+1 = d 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 (σ) = d m m d d m m.
Introduisons maintenant pour tout lettre x et tout mot g la dérivation
g (∂/∂x) envoyant chaque mot f = x1 x2 . . . xp sur l’ensemble pondéré formé
de tous les mots obtenus en remplaçant dans f chaque occurrence de la
lettre x par le mot g. Formellement, g (∂/∂x) est l’opérateur linéaire défini
par sa restriction à X, à savoir
g, si x′ = x ;
∂
′
g x =
∂x x′ , si x′ ∈ X \ {x} ;
et par l’identité
∂ ∂ ∂
g ff′ = g f · f′ + f · g f ′.
∂x ∂x ∂x
Donc si f = f1 xf2 x . . . fr−1 xfr , où les fi ne contiennent pas la lettre x, l’on
aura :
∂
g f = f1 gf2 x . . . fr−1 xfr +f1 xf2 g . . . fr−1 xfr +· · · +f1 xf2 x . . . fr−1 gfr .
∂x
Par exemple, on a :
∂
dm (d m m d d m m) = d m d m d d m m + d m m d d m d m.
∂m
1. DISTRIBUTION DU NOMBRE DES DESCENTES 39

Lemme 5.1. — Soit

∂ ∂ ∂ ∂
∇ = dd + mm + dm + dm .
∂d ∂m ∂d ∂m
On a identiquement : V S′n = ∇ V S′n−1 (n ≥ 2).
Démonstration. — Il existe une bijection de S′n−1 × [ n ] sur S′n envoyant
chaque (σ ′ , k) ∈ S′n−1 × [ n ] sur la permutation σ ∈ S′n telle que σw soit
obtenue en ajoutant 1 à tous les chiffres de σ ′ w et en insérant 1 entre le
k ième et le (k + 1)ième terme de σ ′ w. Soit V (σ ′ ) = v1′ v2′ . . . vn−1
′
et supposons
′ ′ ′
vk ∈ {d, d} c’est-à-dire 1 ≤ k ≤ n − 2 et σ (k) > σ (k + 1). On a
σ(k) = 1 + σ ′ (k) > σ(k + 1) = 1 < σ(k + 2) = 1 + σ ′ (k + 1), donnant
dans V (σ) le facteur vk vk+1 = d m. Maintenant :
(i) si vk′ = d, c’est-à-dire si vk+1 ′
= m et σ ′ (k + 1) < σ ′ (k + 2), on a
vk+2 = m puisque σ(k + 2) = 1 + σ (k + 1) < σ(k + 3) = 1 + σ ′ (k + 2) et toute
′
′
l’opération équivaut au remplacement de vk+1 = m par vk+1 vk+2 = m m.
Remarquons qu’avec nos conventions, si k = n − 2, on a σ ′ (k + 2) = σ ′ (n) =
σ ′ (1) = n − 1.
(ii) si vk′ = d, c’est-à-dire si σ ′ (k+1) < σ ′ (k+2), on a encore vk+2 ∈ {d, d}
et V (σ) est déduit de V (σ ′ ) en remplaçant vk′ = d par vk vk+1 = d m. Un
raisonnement analogue s’applique si vk′ = m ou m.
Notons maintenant α le morphisme canonique envoyant le monoı̈de libre
engendré par {m, m, d, d} sur le monoı̈de commutatif libre de même base.
Théorème 5.2. — Il existe des entiers positifs cn,k tels que
X
αV S′n = cn,k (d m)k (d + m)n−2k (n ≥ 2).
2≤2k≤n

Démonstration. — Pour n = 2, on a V S′n = d m et le résultat s’en déduit

par induction sur n puisque ∇ commute avec α.
Remarque 5.3. — Les coefficients cn,k des polynômes αV S′n obéissent à
des relations de récurrence qu’il est facile d’établir. Posons, par convention,
cn,k = 0 si k ≤ 0 ou si 2k ≥ n + 1 ; on alors les deux relations :
c2,1 = 1 et pour n ≥ 3, k ≥ 1,
cn,k = kcn−1,k + 2(n + 1 − 2k)cn−1,k−1 .

Remarque 5.4. — La fonction génératrice des nombres cn,k est donnée

par Barton & David ([3] p. 180, voir aussi [17]). La théorie de ces auteurs se
rattache aux considérations présentes en utilisant l’observation suivante dont
la démonstration est laissée au lecteur.
Pour σ ∈ Sn−1 , soit σ ′ ∈ S′n définie par σ ′ (1) = n, σ ′ (1 + j) =
n + 1 − σ(n − j). Le nombre des facteurs d ou d de V (σ ′ ) surpasse de 1 le
nombre des j ∈ [n−1] tels que σ(j) > σ(j −1) et le nombre de facteurs d m de
V (σ ′ ) est égal au nombre des j ∈ [n − 2] tels que σ(j) > σ(j + 1) < σ(j + 2),
augmenté d’une unité.
40 CHAPITRE V : LES SOMMES ALTERNÉES

2. Applications aux polynômes eulériens

Le théorème 5.2 va nous permettre de donner une interprétation combina-
toire aux nombres An (−1). Il est commode, tout d’abord, de noter la relation
suivante sur les cardinaux des ensembles Tn des permutations alternées (cf.
chap. I, § 9).
Propriété 5.5. — Pour p ≥ 1, on a : card T2p−1 = card T2p ∩ S′2p .
Démonstration. — En effet, l’application qui envoie chaque σ ′ ∈ S′n
telle que V (σ ′ ) = (d m)p (n = 2p ≥ 2) sur l’élément σ ∈ Sn−1 défini par
σ(j) = σ ′ (j + 1) (j ∈ [n − 1]), est une bijection sur Tn−1 . D’autre part, il est
clair que l’on a : T2p ∩ S′2p = {σ ′ ∈ S′2p : V (σ ′ ) = (d m)p }.

Théorème 5.6. — Pour n ≥ 2 on a l’identité :

X
t An−1 (t) = cn,k tk (1 + t)n−2k . (1)
2≤2k≤n
De plus, pour p ≥ 1, on a :
A2p (−1) = 0 et (−1)p−1 A2p−1 (−1) = card T2p−1 .

Démonstration. — Pour σ ′ ∈ S′n , le nombre des occurrences des lettres d

ou d dans V (σ ′ ) est égal à |∆Dσ ′ |, puisque l’on a vn ∈ {m, m}. Or d’après
les propriétés 2.2 et 2.3, on a θ∆DS′n = 0An−1 (t) = t An−1 (t). On en déduit
que t An−1 (t) est obtenu en faisant d = d = t et m = m = 1 dans θV S′n . La
formule (1) résulte alros du théorè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 A2p (−1) est nul pour p ≥ 1. Au contraire,
pour n = 2p ≥ 2, on voit que c2p,p = (−1)p−1 A2p−1 (−1). Or

c2p,p = card{σ ′ ∈ S′2p : V (σ ′ ) = (m d)p } = card T2p ∩ S′2p = card T2p−1 ,

d’après la propriété 5.5. Le théorème 5.6 en résulte.

3. Applications aux polynômes Bn (t)

Nous donnons enfin des identités analogues à celles du théorème 4.6,
concernant les polynômes Bn (t) = θEDn = θM Gn , où comme précédemment

Dn = {σ ∈ Sn : σ(j) 6= j}; Gn = {σ ∈ Sn : 1 6= σ(1), 1 + σ(j) 6= σ(j + 1)}.

Pour démontrer le théorème 5.9 ci-dessous, nous allons de nouveau appliquer

la formule exponentielle et utiliser les propriétés élémentaires des permuta-
tions et de la transformation fondamentale du chapitre I. Pour n = 2p ≥ 2 et
σ ∈ Sn , nous posons µσ = 1 si et seulement si σ est biexcédée, c’est-à-dire
si σ ∈ B (cf. chap. 1, § 9) et µσ = 0 dans les autres cas.
3. APPLICATIONS AUX POLYNÔMES 41

Lemme 5.7. — L’application µ est multiplicative. En d’autres termes, σ

est une permutation biexcédée, si tous les termes de sa factorisation cano-
nique sont aussi des permutations biexcédes.
Démonstration. — Ce lemme résulte encore de la propriété 3.11. Soit
σ1 σ2 . . . σr la décomposition en produit de cycles disjoints d’une permutation
σ ∈ B et (f1 , I1 )(f2 I2 ) · · · (fr , Ir ) sa factorisation canonique. Avec les mêmes
notations que dans la propriété 3.11, on a fj = τj σj τj−1 (j ∈ [r]). Par
suite, i < σ(i) ⇔ τj (i) < fj τj (i) et i < σ −1 (i) ⇔ σσ −1 (i) < σ −1 (i) ⇔
fj τj σ −1 (i) < τj σ −1 (i) ⇔ τj (i) < fj−1 τj (i), puisque les entiers i et σ −1 (i)
appartiennent à la même orbite. On a les mêmes équivalences en remplaçant
le symbole “<” par “>”.
Lemme 5.8. — Pour p ≥ 1 on a :
µ{S2p } = card B2p et µ{S2p−1 } = µ{C2p−1 } = 0; (2)
µ{C2p } = card B2p ∩ C2p = card T2p ∩ S′2p . (3)
Démonstration. — Les relations (2) résultent de la définition de µ et
de la proposition 1.14. D’après la propriété 1.10 et la proposition 1.14, la
transformation fondamentale σ 7→ σ̂ est une bijection de B2p ∩ C2p sur
T2p ∩ S′2p . La relation (3) est ainsi vérifiée.
Pour la démonstration du théorème ci-dessous, l’utilisation des nombres
complexes est une simple commodité d’écriture évitant de recourir au produit
d’Hadamard.
Théorème 5.9. — Pour p ≥ 1 on a :
B2p−1 (−1) = 0 et (−1)p B2p (−1) = card T2p .
Démonstration. — On applique la formule (9) du chapitre III avec
l’application multiplicative µP du lemme 5.7. D’après (2), le premier membre
de cette formule s’écrit : 1 + (un /n!) card Bn . Maintenant pour p ≥ 1 on a
1≤n

µ{C2p } = card T2p ∩ S′2p [d’après (3)]

= card T2p−1 [d’après la propriété 5.5]
= (−1)p−1 A2p−1 (−1). [d’après le théorème 5.6]
Compte-tenu de la relation (2) le second membre de la formule (9) du
chapitre III s’écrit donc
X u2p
p−1
exp (−1) A2p−1 (−1) .
(2p)!
1≤p
En utilisant le fait que An (−1) = 0 si n est pair, on en déduit :
X un X (iu)n
card Bn = exp (−1)An−1 (−1) ,
n! n!
0≤n 2≤n
42 CHAPITRE V : LES SOMMES ALTERNÉES

où i est le nombre complexe de module 1 et d’argument π/2. Or le membre

de droite de cette dernière équation est la valeur pour t = −1 de l’expression
X (iu)n
exp t An−1 (t) ,
n!
2≤n
qui d’après le théorème 4.1 est égale à
X (iu)n
Bn (t).
n!
0≤n

En identifiant terme à terme, il en résulte que l’on a Bn (−1) = 0 si n est

impair et que pour n = 2p, on a (−1)p B2p (−1) = card B2p = card T2p d’après
la proposition 1.14.

4. Les développements de tg u et de 1/ cos u

De l’identité (5) du théorème 4.2, on tire
X (iu)n 2
An (−1) = ,
n! 1 + e−2iu
0≤n
qu’on peut récrire
X u(iu)n−1 1 − e−2iu
An (−1) = = tg u,
n! i(1 + e−2iu )
1≤n
soit, en utilisant le théorème 5.6,
X u2p−1
tg u = card T2p−1 . (4)
(2p − 1)!
1≤p
De même, d’après l’identité (6) du théorème 4.2, on a
X (iu)n 2 1
Bn (−1) = −iu iu
= .
n! e +e cos u
0≤n
D’après le théorème 5.9, on déduit donc :
1 X u2p
=1+ card T2p . (5)
cos u (2p)!
1≤p

Les identités (4) et (5) sont dues à Désiré André [1]. Nous avons pu les établir
ici sans recourir aux méthodes traditionnelles du calcul différentiel et intégral,
en n’utilisant que l’identité de Cauchy et des constructions sur la catégorie
des ensembles totalement ordonnés finis.
Nous laissons au lecteur l’amusement de vérifier par les mêmes techniques
la formule élémentaire
1 Z
= exp tg u du
cos u
en utilisant une définition appropriée de l’intégrale.
5. TABLE DES NOMBRES D’EULER 43

5. Table des nombres d’Euler

On a souvent appelé nombres d’Euler les coefficients du développement de
tg u et de 1/ cos u. Les valeurs numériques de ces premiers coefficients ont déjà
été obtenues par Euler lui-même (voir [16], p. 299–301). Nous reproduisons
ci-dessous ces premières valeurs. Rappelons que pour n ≥ 1 on note Tn le
sous-ensemble de Sn formé par les permutations alternées, qu’on a ensuite
les identités

(−1)p−1 A2p−1 (−1) = card T2p−1 ; (−1)p−1 B2p (−1) = card T2p (p ≥ 1).

Le tableau des quantités tn = card Tn pour n = 1, 2, . . . , 14 est alors le

suivant.

n tn
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
BIBLIOGRAPHIE

[1] Désiré André. — Dévelopements de sec x et de tang x, C. R. Acad. Sc. Paris, t. 88,
, p. 965–967.
[2] Désiré André. — Mémoire sur le nombre des permutations alternées, Journal de
Math., t. 7, , p. 167.
[3] D. E. Barton, F. N. David. — Combinatorial Chance. — Griffin, London, .
[4] L. Carlitz. — Eulerian numbers and polynomials, Math. Magazine, t. 32, ,
p. 247–260.
[5] L. Carlitz. — Eulerian numbers and polynomials of higher order, Duke Math. J.,
t. 27, , p. 401–423.
[6] L. Carlitz. — A note on Eulerian numbers, Arch . Math., t. 14, , p. 383–390.
[7] L. Carlitz, J. Riordan. — Congruences for Eulerian Numbers, Duke Math. J., t. 20,
, 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, , p. 350–374.
[9] P. Cartier, D. Foata. — Problèmes combinatoires de commutation et réarrangements.
Lecture Notes in Math., no. 85, Springer-Verlag, Berlin, .
[10] J. F. Dillon, D. P. Roselle. — Eulerian numbers of higher order, Duke Math. J.,
t. 35, , p. 247–256.
[11] R. C. Entringer. — A combinatorial interpretation of the Euler and Bernoulli
numbers, Nieuw Arch. V. Wiskunde, t. 14, , p. 241–246.
[12] Dominique Foata. — Étude algébrique de certains problèmes d’analyse combinatoire
et du calcul des probabilités, Publ. Inst. Statist. Univ. Paris, t. 14, , p. 81–241.
[13] G. Frobenius. — Über die Bernoullischen Zahlen und die Eulerschen Polynome, Sitz.
Berichte Preuss. Akad. Wiss., , p. 808–847.
[14] R. Frucht. — A combinatorial approach to the Bell polynomials and their gener-
alizations. Recent Progress in Combinatorics (W. T. Tutte, ed.), Academic Press,
London and New York, , p. 69–74.
[15] R. Frucht, G.-C. Rota. — Polynomios de Bell y partitiones de conjuntos finitos,
Scientia, t. 126, , p. 5–10.
[16] Ch. Jordan. — Calculus of finite differences. — Röttig & Romwalter, Budapest,
.
[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, , p. 332–376.
[18] B. Kittel. — Communication privée.
[19] P. A. MacMahon. — Second memoir on the composition of numbers, Phil. Trans.
Royal Soc. London, A, t. 207, , p. 65–134.
[20] P. A. MacMahon. — Combinatory Analysis, vol. 1 and 2. — Cambridge, Cambridge
Univ. Press, , (Reprinted by Chelsea, New York, ).
[21] E. Netto. — Lehrbuch der Combinatorik. — B. G. Teubner, Leipzig, .
[22] F. Poussin. — Sur une propriété arithmétique de certains polynômes associés aux
nombres d’Euler, C. R. Acad. Sc. Paris, t. 266, , p. 392–393.
[23] J. Riordan. — Triangular permutation numbers, Proc. Amer. Math. Soc., t. 2, ,
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, , p. 8–16.
[26] G.-C. Rota. — On the foundations of Combinatorial Theory, J. Wahrscheinlichkeits-
theorie, t. 2, , p. 340–368.
[27] E. B. Shanks. — Iterated sums of powers of binomial coefficients, Amer. Math.
Monthly, t. 58, , p. 404–407.
BIBLIOGRAPHIE 45

[28] R. Strosser. — Séminaire de théorie combinatoire, I.R.M.A., Université de Stras-

bourg, –.
[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, , p. 119–211.
[30] Ph. Welschinger. — Séminaire de théorie combinatoire, I.R.M.A., Université de
Strasbourg, –.
[31] J. Worpitzky. — Studien über die Bernoullischen und Eulerschen Zahlen, J. für die
reine und angewandte Math., t. 94, , p. 203–232.

Vous aimerez peut-être aussi

Découverte des Nombres de Bernoulli
Pas encore d'évaluation
Découverte des Nombres de Bernoulli
55 pages
(Expository Notes) Denis Monasse-Sommation Et Intégration Formelles (2002)
Pas encore d'évaluation
(Expository Notes) Denis Monasse-Sommation Et Intégration Formelles (2002)
7 pages
Thèse sur le théorème de Piatetski-Shapiro
Pas encore d'évaluation
Thèse sur le théorème de Piatetski-Shapiro
111 pages
Zéros des polynômes orthogonaux classiques
Pas encore d'évaluation
Zéros des polynômes orthogonaux classiques
98 pages
AGREG Gabriel
Pas encore d'évaluation
AGREG Gabriel
206 pages
Corrigé d'exercices sur l'intégration et les polynômes
Pas encore d'évaluation
Corrigé d'exercices sur l'intégration et les polynômes
7 pages
Coefficients Binomiaux Generalises Et Polyno Mes de Macdonald
Pas encore d'évaluation
Coefficients Binomiaux Generalises Et Polyno Mes de Macdonald
36 pages
Révision Sup 1 - Polynômes - Résumé, Applications, Exercices Et Problèmes
Pas encore d'évaluation
Révision Sup 1 - Polynômes - Résumé, Applications, Exercices Et Problèmes
27 pages
Centrale Supelec PC 2016 Maths 2 Corrige
Pas encore d'évaluation
Centrale Supelec PC 2016 Maths 2 Corrige
10 pages
Problèmes sur polynômes et endomorphismes
Pas encore d'évaluation
Problèmes sur polynômes et endomorphismes
5 pages
Exercices de mathématiques Polytechnique 2019
Pas encore d'évaluation
Exercices de mathématiques Polytechnique 2019
86 pages
Propriétés des racines de polynômes aléatoires
Pas encore d'évaluation
Propriétés des racines de polynômes aléatoires
7 pages
1 2007 CT WB 01 22 Corrige - Sujet1 Maths - Generales
Pas encore d'évaluation
1 2007 CT WB 01 22 Corrige - Sujet1 Maths - Generales
12 pages
Correction d'exercices sur les polynômes
Pas encore d'évaluation
Correction d'exercices sur les polynômes
11 pages
ds02 Relations Sommes
Pas encore d'évaluation
ds02 Relations Sommes
4 pages
DV 6 - Énoncé - Algèbre Linéaire, Dérivation Discrète de Polynômes
Pas encore d'évaluation
DV 6 - Énoncé - Algèbre Linéaire, Dérivation Discrète de Polynômes
3 pages
DL Maths
Pas encore d'évaluation
DL Maths
8 pages
Corrige1 Maths 1 Centrale MP 1991
Pas encore d'évaluation
Corrige1 Maths 1 Centrale MP 1991
4 pages
Correction Devoir Mathématiques MPSI 4
Pas encore d'évaluation
Correction Devoir Mathématiques MPSI 4
8 pages
DM 1 de Révisions
Pas encore d'évaluation
DM 1 de Révisions
3 pages
Une Identit Pour Des Polyn Mes D Appell 2017 Comptes Rendus Mathematique
Pas encore d'évaluation
Une Identit Pour Des Polyn Mes D Appell 2017 Comptes Rendus Mathematique
4 pages
Mathématiques: Nombres et Géométrie
Pas encore d'évaluation
Mathématiques: Nombres et Géométrie
4 pages
Mathématiques PSI 2023 : Fonctions et Probabilités
Pas encore d'évaluation
Mathématiques PSI 2023 : Fonctions et Probabilités
8 pages
Corr Sujet 16
Pas encore d'évaluation
Corr Sujet 16
10 pages
DM - Séries Entières
Pas encore d'évaluation
DM - Séries Entières
4 pages
Polynômes et fractions rationnelles expliqués
Pas encore d'évaluation
Polynômes et fractions rationnelles expliqués
36 pages
Maths Ulm 1992
Pas encore d'évaluation
Maths Ulm 1992
7 pages
Polynômes de Tchebychev et Fractions Rationnelles
Pas encore d'évaluation
Polynômes de Tchebychev et Fractions Rationnelles
7 pages
Primitives et Fractions Rationnelles
Pas encore d'évaluation
Primitives et Fractions Rationnelles
5 pages
Polynômes et Nombres de Bernoulli : Formule d'Euler-Mac Laurin
Pas encore d'évaluation
Polynômes et Nombres de Bernoulli : Formule d'Euler-Mac Laurin
5 pages
dm13 Polynomes
Pas encore d'évaluation
dm13 Polynomes
6 pages
Polynômes Orthogonaux en Physique
Pas encore d'évaluation
Polynômes Orthogonaux en Physique
9 pages
Intégrales de Wallis et Formule de Stirling
Pas encore d'évaluation
Intégrales de Wallis et Formule de Stirling
9 pages
Zeta 2
Pas encore d'évaluation
Zeta 2
2 pages
cenMP2 C
Pas encore d'évaluation
cenMP2 C
14 pages
Screenshot 2025-01-03 at 17.27.32
Pas encore d'évaluation
Screenshot 2025-01-03 at 17.27.32
5 pages
Polynômes Orthogonaux et Propriétés d'Intégrabilité
Pas encore d'évaluation
Polynômes Orthogonaux et Propriétés d'Intégrabilité
4 pages
SB 1948-1951 1 321 0
Pas encore d'évaluation
SB 1948-1951 1 321 0
10 pages
Fractions Rationnelles : Concepts et Décomposition
Pas encore d'évaluation
Fractions Rationnelles : Concepts et Décomposition
5 pages
Nombres algébriques et constructions géométriques
Pas encore d'évaluation
Nombres algébriques et constructions géométriques
6 pages
Opérateur de différence et polynômes
Pas encore d'évaluation
Opérateur de différence et polynômes
6 pages
Banque E3A E4A 1999 MP Mathématiques 3 CB
Pas encore d'évaluation
Banque E3A E4A 1999 MP Mathématiques 3 CB
5 pages
Maths Mines-Ponts PSI 2004 M2 (Enoncé 2)
Pas encore d'évaluation
Maths Mines-Ponts PSI 2004 M2 (Enoncé 2)
5 pages
Relations entre racines et coefficients
Pas encore d'évaluation
Relations entre racines et coefficients
9 pages
Problèmes et solutions Olympiade mathématique
Pas encore d'évaluation
Problèmes et solutions Olympiade mathématique
10 pages
Analyse 2 Polynomes Et Fractions Rationnelles
Pas encore d'évaluation
Analyse 2 Polynomes Et Fractions Rationnelles
9 pages
Polynômes et Orthogonalité dans R[X]
Pas encore d'évaluation
Polynômes et Orthogonalité dans R[X]
3 pages
Lascoux
Pas encore d'évaluation
Lascoux
31 pages
Algèbre II : Polynômes et Fractions Rationnelles
Pas encore d'évaluation
Algèbre II : Polynômes et Fractions Rationnelles
45 pages
Corrigé de Mathématiques 2 - CCP PSI 2010
Pas encore d'évaluation
Corrigé de Mathématiques 2 - CCP PSI 2010
5 pages
Concours Maths MP-MPI 2023
Pas encore d'évaluation
Concours Maths MP-MPI 2023
7 pages
Algèbre II : Polynômes et Espaces Vectoriels
Pas encore d'évaluation
Algèbre II : Polynômes et Espaces Vectoriels
68 pages
Mathematique I (Algebre)
Pas encore d'évaluation
Mathematique I (Algebre)
49 pages
Introduction aux polynômes à une variable
100% (1)
Introduction aux polynômes à une variable
32 pages
Correction Devoir MPSI 3 : Polynômes de Legendre
Pas encore d'évaluation
Correction Devoir MPSI 3 : Polynômes de Legendre
8 pages
Suites Poly
Pas encore d'évaluation
Suites Poly
47 pages
S 22 Desar
Pas encore d'évaluation
S 22 Desar
9 pages
Cour 1 Bac SM
Pas encore d'évaluation
Cour 1 Bac SM
10 pages
La Classification Des Plantes Corrige Serie D Exercices 1
100% (1)
La Classification Des Plantes Corrige Serie D Exercices 1
2 pages
Stage Junior 2014
Pas encore d'évaluation
Stage Junior 2014
89 pages
Soins de base dans les pays en développement
Pas encore d'évaluation
Soins de base dans les pays en développement
9 pages
Théorème de D'Alembert-Gauss
Pas encore d'évaluation
Théorème de D'Alembert-Gauss
2 pages
Algorithmique Avancée : Graphes et Ascenseurs
Pas encore d'évaluation
Algorithmique Avancée : Graphes et Ascenseurs
5 pages
Cours Denombrement 1 SM
Pas encore d'évaluation
Cours Denombrement 1 SM
10 pages
Optimisation Combinatoire IX
Pas encore d'évaluation
Optimisation Combinatoire IX
18 pages
Carrés Magiques
Pas encore d'évaluation
Carrés Magiques
27 pages
Théorie Des Graphes
Pas encore d'évaluation
Théorie Des Graphes
69 pages
Partie Log Base
Pas encore d'évaluation
Partie Log Base
2 pages
Exercices de Théorie des Graphes
100% (1)
Exercices de Théorie des Graphes
2 pages
Exercice Sur Logarithme Neperien
100% (1)
Exercice Sur Logarithme Neperien
3 pages
TD3: Plus Court Chemin PCC
Pas encore d'évaluation
TD3: Plus Court Chemin PCC
2 pages
Problèmes d'Affectation et Flot Maximal
Pas encore d'évaluation
Problèmes d'Affectation et Flot Maximal
29 pages
M211: Mathématiques Discrètes
Pas encore d'évaluation
M211: Mathématiques Discrètes
42 pages
Graphe 1
Pas encore d'évaluation
Graphe 1
5 pages
Corrige Analyse Combinatoire Complet
Pas encore d'évaluation
Corrige Analyse Combinatoire Complet
2 pages
Analyse Combinatoire 022355
Pas encore d'évaluation
Analyse Combinatoire 022355
28 pages
Cours RO Graphes S7 1412-Unlocked Unlocked
Pas encore d'évaluation
Cours RO Graphes S7 1412-Unlocked Unlocked
16 pages
Chapitre4 - Arbre Couvrant À Poids Minimal
Pas encore d'évaluation
Chapitre4 - Arbre Couvrant À Poids Minimal
29 pages
Exercices et corrections sur les fonctions logarithmiques
Pas encore d'évaluation
Exercices et corrections sur les fonctions logarithmiques
16 pages
Théorie des Graphes pour Étudiants
Pas encore d'évaluation
Théorie des Graphes pour Étudiants
28 pages
Indice Maths Terminale Spécialité 2020
91% (11)
Indice Maths Terminale Spécialité 2020
475 pages
Graphe Arbres Algo
Pas encore d'évaluation
Graphe Arbres Algo
12 pages
Concepts d'Arbres en Théorie des Graphes
Pas encore d'évaluation
Concepts d'Arbres en Théorie des Graphes
37 pages
Test structurel : analyse statique et dynamique
Pas encore d'évaluation
Test structurel : analyse statique et dynamique
36 pages
Graphes Acycliques, Eulériens et Hamiltoniens
Pas encore d'évaluation
Graphes Acycliques, Eulériens et Hamiltoniens
9 pages
Optimisation du Tri Rapide
Pas encore d'évaluation
Optimisation du Tri Rapide
8 pages
Optimisation des graphes : Dijkstra et chemins
Pas encore d'évaluation
Optimisation des graphes : Dijkstra et chemins
3 pages
Chapitre3 2022 ENSIASEtud
100% (1)
Chapitre3 2022 ENSIASEtud
57 pages
Code source pour la gestion de graphes
Pas encore d'évaluation
Code source pour la gestion de graphes
10 pages
Cours sur les Algorithmes de Graphes
Pas encore d'évaluation
Cours sur les Algorithmes de Graphes
29 pages
Contrôle Continu Th. GRA - Semestre 3
Pas encore d'évaluation
Contrôle Continu Th. GRA - Semestre 3
3 pages