144
4 Approche combinatoire
Fig. 4.4 L’arbre de taille 24 représentant l’expression obtenue par dérivation de exp(x ∗ x) + (x ∗
(x + x)), expression qui est représentée dans la figure 4.3
et satisfait les équations de récurrence suivantes, analogues à l’équation (4.21) :
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
δ(x) = 1;
δ(exp(f )) = 2 + |f | + δ(f );
δ(f + g) = 1 + δ(f ) + δ(g);
δ(f ∗ g) = 3 + |f | + |g| + δ(f ) + δ(g).
Ces relations résultent simplement des formules classiques
⎧
⎪ ⎪ ⎨
⎪ ⎪ ⎩
d x = 1;
d exp(f ) = (df ) ∗ exp(f );
d(f + g) = (df ) + (dg);
d(f ∗ g) = (df ) ∗ g + f ∗ (dg).
Soit D(z) :=
f ∈F δ(f )z |f | ; nous pouvons aussi l’écrire, en détaillant les divers
types d’expressions, comme
δ(x) z
|x|
+
f
δ (exp(f )) z
| exp(f )|
+
f,g
δ(f + g) z
|f +g|
+
f,g
δ(f ∗ g) z
|f ∗g| .
Les équations de récurrence sur le paramètre δ(f ) se traduisent alors sur D(z) en
D(z) = z +
f
(2 + |f | + δ(f )) z
1+|f |
+
f,g
(1 + δ(f ) + δ(g)) z
1+|f |+|g|
+
f,g
(3 + |f | + |g| + δ(f ) + δ(g)) z
1+|f |+[g| .