9.2 Etude combinatoire analytique
377
Par exemple, pour n’importe quelle urne, H
1, 1, z
u 0
v 0
=
1
1 − Sz
u 0 +v 0
S
.
Dans l’exercice 9.2, nous calculons H pour l’urne originale de Pólya-Eggenberger
R = SI 2 .
Le résultat suivant est qualifié de « basic isomorphism » dans Flajolet et
al. [103]. Il relie H , la fonction génératrice des histoires, aux solutions d’un système
différentiel canoniquement attaché à l’urne.
Théorème 9.2 ([103]) Soient x, y, z des nombres complexes tels que xy = 0.
Soient X(t) et Y (t) les solutions du problème de Cauchy (formel ou analytique)
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
dX
dt
= X
a+1 Y
b
dY
dt
= X
c Y
d+1
X(0) = x, Y (0) = y.
(9.2)
Alors, pour toute configuration initiale (u 0 , v 0 ), pour tout z « assez proche de
l’origine » (dans un cadre analytique),
H
x, y, z
u 0
v 0
= X(z)
u 0 Y (z)
v 0 .
Preuve Un tirage dans l’urne revient à choisir (ou pointer) une lettre d’un mot et à la
remplacer par un mot. Or, en combinatoire analytique, pointer un objet combinatoire
se traduit par une dérivée partielle sur les séries génératrices (voir [94] section I.6.2)
; opérer un remplacement a pour effet de multiplier par un monôme ad hoc. C’est
la raison pour laquelle nous considérons l’opérateur différentiel sur les fonctions de
deux variables
D = x
a+1 y
b ∂
∂x
+ x
c y
d+1 ∂
∂y
.
L’effet de D sur les monômes est lié aux histoires de l’urne par la formule
D (x u 0 y v 0 ) = u 0 x a+u 0 y b+v 0 + v 0 x c+u 0 y d+v 0
= H 1
u 0 u 0 + a
v 0 v 0 + b
x
a+u 0 y
b+v 0 + H 1
u 0 u 0 + c
v 0 v 0 + d
x
c+u 0 y
d+v 0
=
u,v≥0
H 1
u 0 u
v 0 v
x
u y
v
377
Par exemple, pour n’importe quelle urne, H
1, 1, z
u 0
v 0
=
1
1 − Sz
u 0 +v 0
S
.
Dans l’exercice 9.2, nous calculons H pour l’urne originale de Pólya-Eggenberger
R = SI 2 .
Le résultat suivant est qualifié de « basic isomorphism » dans Flajolet et
al. [103]. Il relie H , la fonction génératrice des histoires, aux solutions d’un système
différentiel canoniquement attaché à l’urne.
Théorème 9.2 ([103]) Soient x, y, z des nombres complexes tels que xy = 0.
Soient X(t) et Y (t) les solutions du problème de Cauchy (formel ou analytique)
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
dX
dt
= X
a+1 Y
b
dY
dt
= X
c Y
d+1
X(0) = x, Y (0) = y.
(9.2)
Alors, pour toute configuration initiale (u 0 , v 0 ), pour tout z « assez proche de
l’origine » (dans un cadre analytique),
H
x, y, z
u 0
v 0
= X(z)
u 0 Y (z)
v 0 .
Preuve Un tirage dans l’urne revient à choisir (ou pointer) une lettre d’un mot et à la
remplacer par un mot. Or, en combinatoire analytique, pointer un objet combinatoire
se traduit par une dérivée partielle sur les séries génératrices (voir [94] section I.6.2)
; opérer un remplacement a pour effet de multiplier par un monôme ad hoc. C’est
la raison pour laquelle nous considérons l’opérateur différentiel sur les fonctions de
deux variables
D = x
a+1 y
b ∂
∂x
+ x
c y
d+1 ∂
∂y
.
L’effet de D sur les monômes est lié aux histoires de l’urne par la formule
D (x u 0 y v 0 ) = u 0 x a+u 0 y b+v 0 + v 0 x c+u 0 y d+v 0
= H 1
u 0 u 0 + a
v 0 v 0 + b
x
a+u 0 y
b+v 0 + H 1
u 0 u 0 + c
v 0 v 0 + d
x
c+u 0 y
d+v 0
=
u,v≥0
H 1
u 0 u
v 0 v
x
u y
v