318
7 Arbres digitaux
La relation suivante permet dans les cas simples de calculer ϕ(k) à partir de la série
de Poisson γ (z) associée au péage γ : pour k ≥ 0,
ϕ(k) = n![z
k
] γ (−z).
(7.33)
Rappelons que la transformée binomiale étant une involution, nous avons aussi
γ (n) =
n
k=0
n
k
(−1)
k ϕ(k).
Ainsi nous pouvons écrire l’espérance dans le modèle de Bernoulli à partir de
l’espérance dans le modèle de Poisson en faisant intervenir la séquence (ϕ(k)) ainsi
définie.
Proposition 7.36 (Dépoissonisation et formule de Rice – coût additif) Soit v un
paramètre additif de péage γ . Dans le modèle de Bernoulli pour un trie à n clés,
l’espérance du coût v s’écrit
E n [v] =
n
k=2
(−1)
k
n
k
ϕ(k)
w∈A
∗
p
k
w ,
où la fonction ϕ(k) est définie pour k ≥ 0 grâce à l’équation (7.32) (ou de manière
équivalente grâce à l’équation (7.33)).
Remarque 7.37 Notons que γ (0) = γ (1) = 0 implique ϕ(0) = ϕ(1) = 0. Ceci
justifie le fait que la sommation commence à k = 2.
Cette formulation de l’espérance en fonction de la série ϕ(k) peut paraître
assez artificielle au premier abord, mais elle s’avère finalement très adaptée aux
paramètres additifs de cette section. En effet, pourvu que les coefficients ϕ(k) aient
une forme particulière (en fait admettent un relèvement analytique), nous allons
pouvoir appliquer la formule de Nörlund-Rice (souvent abrégée en formule de Rice)
présentée ci-après.
Proposition-Définition 7.38 La formule de Nörlund-Rice [196, 197] transforme
une somme binomiale en une intégrale dans le plan complexe de la façon suivante.
Pour un entier positif σ 0 , soit
T (n) =
n
k=1+σ 0
(−1)
k
n
k
ϕ(k).
S’il existe une fonction (s) et un réel σ 1 ∈]σ 0 , σ 0 + 1[ tel que (s) est un
relèvement analytique de la séquence ϕ(k) (i.e., (k) = ϕ(k) pour tout entier
k ≥ 1 + σ 0 ) avec (s) analytique et de croissance au plus polynomiale sur le
7 Arbres digitaux
La relation suivante permet dans les cas simples de calculer ϕ(k) à partir de la série
de Poisson γ (z) associée au péage γ : pour k ≥ 0,
ϕ(k) = n![z
k
] γ (−z).
(7.33)
Rappelons que la transformée binomiale étant une involution, nous avons aussi
γ (n) =
n
k=0
n
k
(−1)
k ϕ(k).
Ainsi nous pouvons écrire l’espérance dans le modèle de Bernoulli à partir de
l’espérance dans le modèle de Poisson en faisant intervenir la séquence (ϕ(k)) ainsi
définie.
Proposition 7.36 (Dépoissonisation et formule de Rice – coût additif) Soit v un
paramètre additif de péage γ . Dans le modèle de Bernoulli pour un trie à n clés,
l’espérance du coût v s’écrit
E n [v] =
n
k=2
(−1)
k
n
k
ϕ(k)
w∈A
∗
p
k
w ,
où la fonction ϕ(k) est définie pour k ≥ 0 grâce à l’équation (7.32) (ou de manière
équivalente grâce à l’équation (7.33)).
Remarque 7.37 Notons que γ (0) = γ (1) = 0 implique ϕ(0) = ϕ(1) = 0. Ceci
justifie le fait que la sommation commence à k = 2.
Cette formulation de l’espérance en fonction de la série ϕ(k) peut paraître
assez artificielle au premier abord, mais elle s’avère finalement très adaptée aux
paramètres additifs de cette section. En effet, pourvu que les coefficients ϕ(k) aient
une forme particulière (en fait admettent un relèvement analytique), nous allons
pouvoir appliquer la formule de Nörlund-Rice (souvent abrégée en formule de Rice)
présentée ci-après.
Proposition-Définition 7.38 La formule de Nörlund-Rice [196, 197] transforme
une somme binomiale en une intégrale dans le plan complexe de la façon suivante.
Pour un entier positif σ 0 , soit
T (n) =
n
k=1+σ 0
(−1)
k
n
k
ϕ(k).
S’il existe une fonction (s) et un réel σ 1 ∈]σ 0 , σ 0 + 1[ tel que (s) est un
relèvement analytique de la séquence ϕ(k) (i.e., (k) = ϕ(k) pour tout entier
k ≥ 1 + σ 0 ) avec (s) analytique et de croissance au plus polynomiale sur le