Séries formelles et combinatoire : l’exemple des
parenthésages
Préparation à l’agrégation de mathématiques
Université de Nice - Sophia Antipolis
Antoine Ducros
3 octobre 2006
Soient E un ensemble et n un entier. Considérons une suite de symboles
a1 ∗1 a2 ∗2 . . . ∗n−2 an−1 ∗n−1 an , où chaque ai est un élément de E et où
chaque ∗i désigne une loi interne sur E, c’est-à-dire une application de E × E
vers E. Par exemple, prenons E = R∗+ , n = 3, a1 = 3, a2 = 2, a3 = 5, ∗1 = / et
∗2 = + ; la suite de symboles obtenue est alors 3/2+5.
En général, la signification de l’expression a1 ∗1 a2 ∗2 . . . ∗n−2 an−1 ∗n−1 an
est ambiguë : on ne sait pas a priori dans quel ordre effectuer les opérations. Pour
l’indiquer, on a recours à ce qu’on appelle un parenthésage. Ainsi la notation
3/2+5 peut avoir deux sens, mais si l’on écrit (3/2)+5 ou bien 3/(2+5) le doute
est levé.
Techniquement, la façon la plus commode de définir un parenthésage d’une
expression à n termes est de procéder récursivement : lorsque l’expression ne
comporte qu’un terme, il n’y a qu’un parenthésage. Si elle en comprend n pour
un certain entier n supérieur ou égal à 2, alors se donner un parenthésage c’est se
donner : un entier k compris entre 1 et n − 1, un parenthésage P de l’expression
formée des k premiers termes, et un parenthésage Q de celle formée des n − k
derniers.
Du point de vue de l’ordre des opérations à effectuer, cela correspond à faire
d’abord le calcul complet pour le premier bloc de k termes (parenthésé via P),
à stocker le résultat r, à faire ensuite le calcul complet pour le second bloc de
n − k termes (parenthésé via Q), à stocker le résultat s, puis à effectuer pour
terminer l’opération r ∗k s.
On se propose de déterminer pour tout entier n supérieur ou égal à 1 le
nombre γn de parenthésages possibles pour une expression comportant n termes.
Donnons quelques valeurs de γn : γ1 et γ2 valent tous deux 1 ; une expression
à trois termes a, b et c peut être parenthésée de deux façons différentes1 : a(bc)
et (ab)c, en conséquence γ3 = 2 ; une expression à 4 termes a, b, c et d peut être
parenthésée de cinq façons différentes : a(b(cd)), a((bc)d), (ab)(cd), (a(bc))d et
((ab)c)d, en conséquence γ4 = 5.
1 Comme vous le constaterez on omet, dans ce qui suit, de noter les symboles d’opérations.
Ceux-ci n’ont en effet aucune importance pour le problème qui nous préocupe ici ; on ne
les a évoqués que pour mettre en évidence l’intérêt mathématique et algorithmique des pa-
renthésages.
1
La définition récursive des parenthésages fournit aussitôt une formule de
n−1
P
récurrence sur les γn , à savoir γn = γk γn−k dès que n ≥ 2. Si l’on pose
k=1
γ0 = 0 on peut même écrire (toujours en supposant n ≥ 2)
n
X
(∗) γn = γk γn−k .
k=0
Cette formule rappelle celle qui définit le produit P de deux séries formelles, aussi
est-il très tentant d’introduire la série S égale à γn X n , qui vit dans Q[[X]].
Notons que comme γ0 est nul, on peut écrire S = XT pour une certaine série
T . En conséquence S 2 = X 2 T 2 ; si δn désigne pour tout n le coefficient de X n
dans S 2 , on a donc δ0 = δ1 = 0.
n
P
Par ailleurs on sait que l’on a δn = γk γn−k , et ce quelque soit n. On peut
k=0
dès lors réécrire (∗) (qui vaut, rappelons-le, pour n ≥ 2) sous la forme γn = δn .
On en déduit que X X
γn X n = δn X n .
n≥2 n≥2
δn X n , qui n’est
P
Comme δ0 et δ1 sont nuls, le terme de droite coı̈ncide avec
n≥0
autre que S 2 . Celui de gauche est quant à lui simplement S − γ0 − γ1 X ; compte-
tenu du fait que γ0 = 0 et γ1 = 1 on obtient finalement l’équation
S − X = S2.
On la réécrit S 2 − S + X = 0, elle est du second degré en l’inconnue S, on la
résout par la formule habituelle dans le corps des fractions Q((X)) de Q[[X]].
On obtient √
1 + ε 1 − 4X
S=
2
avec ε valant a priori 1 ou −1 ; le terme constant de S étant nul on a en fait
ε = −1.
√
Rappelons que l’on a 1 − 4X = ωn (−4X)n avec
P
1 1
2(2 − 1) . . . ( 21 − n + 1)
ωn = ,
n!
ou encore Qn−1
k=0 1 − 2k
ωn = .
2n n!
Lorsque n est au moins égal à 1 (la formule qui suit ne marche pas pour n = 0
en raison du signe, mais ω0 = 1 directement) il vient
Q2n−2
n−1 k=0 k (2n − 2)!
ωn = (−1) Qn−1 = (−1)n−1 2n−1 .
n
2 n! k=1 2k 2 n!(n − 1)!
Il découle de ce qui précède que pour tout n au moins égal à 1 on a
(2n − 2)! (2n − 2)!
γn = −(−4)n (−1)n−1 = .
2.22n−1 n!(n − 1)! n!(n − 1)!
2
Pour ceux qui veulent éviter de parler de séries formelles. Il est possible
de calculer les γn en restant dans le monde (plus classique, et au programme)
des séries entières, mais comme vous allez le voir, c’est au prix de contorsions
aussi pénibles qu’artificielles. La bonne façon de rédiger serait la suivante :
Pn
- remarquer que les conditions γ0 = 0, γ1 = 1 et γn = γk γn−k pour
k=0
n ≥ 2 déterminent complètement la suite des γn ;
- en conséquence, si f est une fonction holomorphe définie au voisinage
P de
l’origine, et donc admettant un développement en série entière f = an z n
de rayon strictement positif, alors on a an = γn pour tout n si et seulement
n
P
si a0 = 0, a1 = 1 et an = ak an−k pour n ≥ 2 ;
k=0
- compte-tenu de la formule relative au produit de deux séries entières, les
conditions ci-dessus équivalent à demander que f (0) soit nul, que f 0 (0)
soit égal à 1, et que f 2 (z) − f (z) − z = 0 pour tout z situé dans le disque
ouvert de convergence de f ;
- or ces propriétés sont vérifiées, comme on le voit à l’aide de la méthode
usuelle de résolution des équations de degré 2, par une et une seule fonction
développable
√ en série entière de rayon strictement positif, celle qui envoie
1 − 1 − 4z √
z sur , où désigne la racine carrée holomorphe usuelle
2
définie sur le disque ouvert de centre 1 et de√rayon 1 ; les γn sont donc les
1 − 1 − 4z
coefficients du développement de z 7→ , et on conclut en les
2
calculant comme à la fin du paragraphe précédent.