454
B Rappels mathématiques : combinatoire
Laurent de f en a ;
(ii) Res(f, a) est l’unique nombre complexe c tel que la fonction f (z) −
c
z − a
admette une primitive holomorphe au voisinage épointé de a ;
(iii) Res(f, a) =
1
2iπ
∂D
f (ζ )dζ où ∂D est le bord simple et direct de D.
Théorème B.5 (Théorème des résidus) Soient U un ouvert simplement connexe
du plan et F une partie finie de U . Soient f une fonction holomorphe sur U \ F et
γ un lacet à valeurs dans U \ F . Alors
1
2iπ
γ
f (ζ )dζ =
s∈F
Res(f, s)Ind γ (s).
B.3.2 Séries bivariées
Les séries qui ont été présentées dans la section B.3.1 sont univariées et leur étude
permet seulement d’énumérer les classes d’objets. L’analyse d’algorithmes vise plus
souvent à analyser un paramètre h en fonction de la taille de l’objet. Les séries
génératrices bivariées ont un pouvoir d’expression plus grand puisqu’elles prennent
en compte deux paramètres conjointement (l’un d’eux étant la taille). En notant
C n,k = {γ ∈ C n ; h(γ ) = k} et c n,k = Card C n,k , on obtient alors des séries
bivariées :
C(z, u) =
γ ∈C
z
|γ | u
h(γ )
=
n,k≥0
c n,k z
n u
k (série génératrice ordinaire)
C(z, u) =
γ ∈C
z |γ |
|γ |!
u
h(γ )
=
n,k≥0
c n,k
n!
z
n u
k (série génératrice exponentielle).
Supposons que le modèle probabiliste considéré soit la distribution uniforme
sur les c n éléments de C n , l’ensemble des objets de taille n. Appelons cette loi
de probabilité P n et notons E n l’espérance selon cette loi. Alors l’espérance du
paramètre h sur les objets de taille n est obtenue en dérivant la série bivariée C(z, u)
par rapport à la variable u :
E n [h] =
γ ∈C n
1
c n
h(γ ) =
1
c n
k≥0
kc n,k =
[z n ]
∂
∂u C(z, u)
u=1
[z n ]C(z, 1)
.
En dérivant encore, on a accès à la variance puis aux moments d’ordre supérieur de
la variable aléatoire. Mentionnons enfin que nous ne sommes pas limités à seulement
deux variables. D’autres variables peuvent être introduites si besoin pour étudier des
paramètres supplémentaires, et ceci dans une même série génératrice multivariée.
B Rappels mathématiques : combinatoire
Laurent de f en a ;
(ii) Res(f, a) est l’unique nombre complexe c tel que la fonction f (z) −
c
z − a
admette une primitive holomorphe au voisinage épointé de a ;
(iii) Res(f, a) =
1
2iπ
∂D
f (ζ )dζ où ∂D est le bord simple et direct de D.
Théorème B.5 (Théorème des résidus) Soient U un ouvert simplement connexe
du plan et F une partie finie de U . Soient f une fonction holomorphe sur U \ F et
γ un lacet à valeurs dans U \ F . Alors
1
2iπ
γ
f (ζ )dζ =
s∈F
Res(f, s)Ind γ (s).
B.3.2 Séries bivariées
Les séries qui ont été présentées dans la section B.3.1 sont univariées et leur étude
permet seulement d’énumérer les classes d’objets. L’analyse d’algorithmes vise plus
souvent à analyser un paramètre h en fonction de la taille de l’objet. Les séries
génératrices bivariées ont un pouvoir d’expression plus grand puisqu’elles prennent
en compte deux paramètres conjointement (l’un d’eux étant la taille). En notant
C n,k = {γ ∈ C n ; h(γ ) = k} et c n,k = Card C n,k , on obtient alors des séries
bivariées :
C(z, u) =
γ ∈C
z
|γ | u
h(γ )
=
n,k≥0
c n,k z
n u
k (série génératrice ordinaire)
C(z, u) =
γ ∈C
z |γ |
|γ |!
u
h(γ )
=
n,k≥0
c n,k
n!
z
n u
k (série génératrice exponentielle).
Supposons que le modèle probabiliste considéré soit la distribution uniforme
sur les c n éléments de C n , l’ensemble des objets de taille n. Appelons cette loi
de probabilité P n et notons E n l’espérance selon cette loi. Alors l’espérance du
paramètre h sur les objets de taille n est obtenue en dérivant la série bivariée C(z, u)
par rapport à la variable u :
E n [h] =
γ ∈C n
1
c n
h(γ ) =
1
c n
k≥0
kc n,k =
[z n ]
∂
∂u C(z, u)
u=1
[z n ]C(z, 1)
.
En dérivant encore, on a accès à la variance puis aux moments d’ordre supérieur de
la variable aléatoire. Mentionnons enfin que nous ne sommes pas limités à seulement
deux variables. D’autres variables peuvent être introduites si besoin pour étudier des
paramètres supplémentaires, et ceci dans une même série génératrice multivariée.