# Analyse d'algorithmes de manipulation de fichiers

Philippe Flajolet

► To cite this version:

Philippe Flajolet. Analyse d'algorithmes de manipulation de fichiers. [Rapport de recherche] IRIA-RR-321, IRIA. 1978, pp.30. hal-04716536

HAL Id: hal-04716536

https://inria.hal.science/hal-04716536v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Dw-04266 RR321

RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_2.png" /></figure>

ANALYSE D'ALGORITHMES
DE MANIPULATION DE FICHIERS

Philippe FLAJOLET

Rapport de Recherche N° 321

Août 1978

30p
ANALYSE D'ALGORITHMES DE MANIPULATION
DE FICHIERS

Philippe Flajolet

RESUME

Nous présentons une méthode générale d'analyse d'algorithmes opérant des suites d'adjonctions, interrogations et suppressions sur un fichier. Les algorithmes y sont comparés non sur des opérations uniques mais sur l'ensemble de toutes les évolutions possibles de la structure. Cette note décrit des résultats de dénombrements en montrant que les fonctions génératrices associées s'expriment naturellement en termes de fractions continues.

SUMMARY

We describe a general method for analyzing algorithms operating on a file. The operations allowed are insertions, deletions and queries. Algorithms are compared on the set of all possible evolutions of the structure. This work describes enumeration results obtained by expressing generating functions as continued fractions.
# 1 - HISTOIRES DE FICHIERS

Le terme d'_histoires de fichiers_ et la problématique qu'il recouvre ont été introduits par [Françon, 1978]. L'idée essentielle consiste, pour des opérations traitant une structure dynamique, à comparer le comportement d'algorithmes non pas sur une opération unique mais sur une suite d'opérations représentant toutes les évolutions possibles de la structure.

Nous nous intéressons dans cette note à l'évaluation de performances d'algorithmes de manipulation de fichiers dont les opérations sont de l'un des trois types suivants : adjonctions, interrogations, suppressions. Notons A, I et S chacun de ces types d'opérations ; un _schéma_ est un mot sur {A,I,S} qui vérifie la condition suivante :

Condition des schémas : Un mot w sur {A,I,S} est un schéma ssi

- (i) $|w|_A = |w|_S$

- (ii) pour tout préfixe gauche u de w: $|u|_A \ge |u|_S$.

On note S l'ensemble des schémas.

Un schéma représente une suite d'opérations permises qui part d'un fichier vide et revient à un fichier vide, et telle qu'aucune suppression ne soit effectuée sur un fichier vide. Nous verrons par la suite comment s'affranchir de la contrainte (i) de départ et retour au fichier vide.

Un schéma est représentable par une ligne brisée plane de la manière suivante :

Soit w un mot sur $A,I,S$ : w = w₁w₂...wⁿ ; on part de l'origine et on associe à la lettre wᵢ une montée de vecteur $|wᵢ|_1$ si wᵢ = A, un palier de vecteur $|wᵢ|_0$ si wᵢ = I et une descente de vecteur $|-wᵢ|_1$ si wᵢ = S. On appelle _hauteur_ d'un mot (en particulier d'un schéma) l'ordonnée maximale du chemin associé au mot.

La condition des schémas se traduit par le fait que le chemin associé à un schéma part de l'origine, termine sur l'axe des abscisses et est tout entier situé au-dessus de cet axe. Chaque lettre représentant une opération de type
adjonction, interrogation ou suppression d'un élément dans un fichier, la hauteur
du chemin en chaque point représente la taille de ce fichier après la suite d'o-
pérations correspondantes.

<u>Exemple</u> : Au schéma W = AASISAIIA correspond le diagramme suivant :

<figure><img src="image_3.png" /></figure>

ainsi que la suite (dans le temps) de taille de fichier 0,1,2,1,1,0,1,1,0,0.

Nous introduisons maintenant une notion de nombre de possibilités : à
chaque opération A,I,S est associé un certain nombre de possibilité. Par
exemple, pour une file de priorité où les opérations sont extraction du mini-
mum et adjonction, le nombre de possibilité d'adjonction d'un élément vaut
k+1 (autant de possibilités que d'intervalles entre les k éléments du fichier) ;
le nombre de possibilité de suppression vaut 1 (on extrait le minimum) et le
nombre de possibilité d'interrogation vaut 0.

De manière générale, un type de **structure de donnée** est défini par une
fonction de possibilités pos : {A,I,S} × N → N où pos(w;k) représente le nombre
de possibilités de l'opération w appliquée à un fichier de taille k. Etant
donné un schéma w = w₁ w₂ ... wₖ tel que la suite des hauteurs de ses sommets
soit e₀, e₁, ..., eₙ avec e₀ = eₙ = 0, on appelle **histoire** (de la structure) régie
par le schéma w toute suite d'entiers h = h₁ h₂ ... hₙ, telle que
0 ≤ hⱼ ≤ pos(wⱼ, eⱼ - 1). Le nombre d'histoires régie par le schéma w noté
pos(w) est ainsi donné par :

$$
\operatorname{pos}(w) = \operatorname{pos}(w_0, e_1) \cdot \operatorname{pos}(w_1, e_2) \cdots \operatorname{pos}(w_{n-1}, e_n)
$$
Ainsi une histoire avec son schéma associé correspond-elle à l'une des évolutions possibles de la structure. On se propose ici d'évaluer les coûts d'algorithmes intégrés sur des ensembles d'histoires de même longueur (durée), dans le but d'évaluer et de comparer les comportements d'algorithmes sur des suites d'opérations. Une telle étude a déjà été effectuée par [Françon, 1978] pour certains types de structures de données les plus importants : dictionnaires, files de priorité, listes linéaires, ... . Les résultats obtenus utilisent des méthodes de combinatoire géométrique des permutation, de [Foata, Schützenberger 1970] et [Françon, Viennot, 1978]. La présente note entre dans le cadre d'un travail plus large entrepris en collaboration avec J. Françon, G. Viennot et J. Vuillemin.

## 2 - DENOMBREMENTS D'HISTOIRES ET FRACTIONS CONTINUES

Nous nous proposons de traiter les histoires de fichiers correspondant à un type de structure tout à fait général. Nous supposons donc donnée une fonction pos de possibilités définie par

$$ \operatorname{pos}(A,k) = \alpha_k \qquad \operatorname{pos}(I,k) = \iota_k \qquad \operatorname{pos}(S,k) = \sigma_k. $$

Notre but est d'obtenir divers résultats de dénombrements, notamment : l'énumération des histoires de longueur n, l'énumération des histoires de longueur n et hauteur h... .

Pour chacun de ces problèmes, et pour d'autres problèmes reliés, nous établissons diverses expressions très simples sous forme de fractions continues des fonctions génératrices associées.

**Théorème 1** : Soit $H_n$ le nombre d'histoires de longueur n de la structure S et soit $H(z) = \sum H_n z^n$ la fonction génératrice correspondante. Alors $H(z)$ possède le développement en fraction continue :

$$ H(z) = \frac{1}{1 - \iota_0 z - \frac{\alpha_0 \sigma_1 z^2}{1 - \iota_1 z - \frac{\alpha_1 \sigma_2 z^2}{1 - \iota_2 z - \frac{\alpha_2 \sigma_3 z^3}{\dots}}}} $$
Preuve : La preuve des résultats de cette section est une application d'une
méthode très générale de dénombrement et d'estimation de probabilités due à
[Schützenberger, 1961].

On définit un codage des schémas qui associe à chaque lettre A, I ou S
d'un schéma sa hauteur dans le schéma. Ainsi au schéma AASISAIIS correspond
le codage a₀a₁s₂i₁s₁a₀i₁i₁s₁ ; c'est-à-dire que la suite des indices dans le
code se lit comme la suite des hauteurs des sommets dans la représentation
plane du schéma. De manière plus précise, soit l'alphabet infini X = ¯A u ¯I u ¯S
où ¯A = {a₀,a₁,a₂,...} , ¯I = {i₀,i₁,i₂,...} et ¯S = {s₀,s₁,s₂,...}; le codage
c de A,I,S* dans X* est défini par :

$$
c(w_1 \ w_2 \ \dots \ w_n) = u_1 \ u_2 \ \dots \ u_n
$$

ssi sont satisfaites les conditions

(i) les $w_i$ sont de même nature que les $u_i$ correspondants :

$$
w_j = A \Rightarrow u_j \in \bar{A} ; w_j = I \Rightarrow u_j \in \bar{I} ; w_j = S \Rightarrow u_j \in \bar{S}
$$

(ii) pour chaque lettre w_j, si w_j = A (resp I, S) et si k est la différence
entre le nombre de A et le nombre de S dans le préfixe w_1, w_2, ..., w_j,
alors u_j = a_k (resp i_k, s_k).

Nous étudions maintenant les codages des schémas de hauteur bornée. Soit
pour chaque h entier, l'alphabet fini

$$
X_h = \{a_0, a_1, a_2, \dots, a_{h-1} ; i_0, i_1, \dots, i_h ; s_1, s_2, \dots, s_h\}
$$

L'ensemble K[h] des codes de schémas de hauteur bornée par h est caractérisé
par l'égalité

$$
K^{[h]} = c(S) \cap X_h^* \quad (S \text{ note l'ensemble des schémas}).
$$
Par ailleurs $K^{[h]}$ possède une structure très simple : c'est un langage rationnel (ou régulier) car définissable par expression régulière :

$$K^{[0]} = (i_0)^*$$

$$K^{[1]} = (i_0 + a_0 i_1^* s_1)^*$$

$$K^{[2]} = (i_0 + a_0(i_1 + a_1 i_2^* s_2)^* s_1)^*,$$

et en général $K^{[h]}$ est décrit par une expression de hauteur d'étoile $h+1$ :

$$K^{[h]} = (i_0 + a_0(i_1 + a_1(\dots(i_{h-1} + a_{h-1} s_h^*)^*\dots)^* s_2)^* s_1)^*.$$

La preuve formelle d'une telle propriété s'effectue par récurrence sur $h$ en montrant que $K^{[h+1]}$ est obtenu à partir de $K^{[h]}$ par substitution à $i_h$ de $(i_h + a_h i_{h+1}^* s_{h+1})$.

Considérons maintenant pour chaque $K^{[h]}$ la série formelle $\overline{K}^{[h]}$ en les indéterminées non commutatives $X_h$ qui est la série caractéristique de $K^{[h]}$. Chacune des opérations étoiles apparaissant dans l'expression de $K^{[h]}$ est non ambiguë car "parenthésée" par un couple $(a_j, s_{j+1})$. Par conséquent $\overline{K}^{[h]}$ s'obtient simplement à partir de l'expression de $K^{[h]}$ en remplaçant les étoiles par des quasi-inverses. Ainsi en introduisant la notation commode

$$\frac{x|y}{1-z} \quad \text{pour dénoter } x(1-y)^{-1}z,$$

dérive-t-on pour $\overline{K}_h$ l'expression :

$$\begin{aligned} \overline{K}^{[h]} &= \frac{1}{1 - i_0 - \frac{a_0 |s_1|}{1 - i_1 - \frac{a_1 |s_2|}{1 - i_2 - \frac{a_2 |s_3|}{1 - i_3 - \dots}}}} \\ &\qquad \frac{a_{h-1} |s_h|}{1 - i_h} \end{aligned}$$

Soit de même $\overline{K}$ la série caractéristique de $K$. Comme $K = \bigcup_{h} K^{[h]}$ et comme $K^{[1]} \subseteq K^{[2]} \subseteq K^{[3]} \dots$, on a $\overline{K} = \lim_{h \to \infty} \overline{K}^{[h]}$. Il est ainsi justifié de considérer
la série caractéristique des schémas comme égale à la fraction continue (non commutative)†

$$ \frac{1}{1 - i_0 - \frac{a_0 |s_1|}{1 - i_1 - \frac{a_1 |s_2|}{1 - i_2 - \frac{a_2 |s_3|}{\dots}}} \dots} $$

Le théorème 1 se déduit de là en utilisant les méthodes générales de dénombrement par morphisme et passage à l'image commutative. Soit $H_n^{[h]}$ le nombre d'histoires de longueur $n$ et de hauteur bornée par $h$ ; la série génératrice $H_n^{[h]}(z) = \sum H_n^{[h]} z^n$ s'obtient à partir de $\overline{K}^{[h]}$, en faisant commuter les variables, par le morphisme $\chi$ :

$$ \left\{ \begin{array}{lcl} a_j & \to & \alpha_j z \\ i_j & \to & \dot{1}_j z \\ s_j & \to & \sigma_j z \end{array} \right. $$

Naturellement $H(z) = \lim_{h \to \infty} H_n^{[h]}(z)$, ce qui achève la prouve du théorème.□

L'analyse des algorithmes pose concernant les histoires de fichiers les problèmes d'évaluation suivants :

- déterminer le nombre total $N_{k,n}$ d'opérations effectuées sur un fichier de taille $k$ dans l'ensemble des histoires de longueur $n$ ; c'est le problème dit des "passages à niveaux". On a l'égalité $N_{k,n} = NA_{k,n} + NI_{k,n} + NS_{k,n}$ où les nombres $NA_{k,n}$ (resp $NS_{k,n}$, $NI_{k,n}$) comptent des adjonctions (resp suppressions, interrogations) effectuées sur un fichier de taille $k$ sur l'ensemble des histoires de longueur $n$.

- déterminer le nombre $M_{k,n}$ d'histoires de longueur $n+k$ dont les $k$ premières étapes sont spécifiées. $M_{k,n}$ compte les histoires généralisées qui commencent au niveau $k$ au lieu de commencer à zéro.

<footnote>† L'équivalence entre cette fraction continue non commutative et la série caractéristique des chemins permet de donner une présentation géométrique de diverses opérations algébriques sur les fractions continues. (par ex. tassements</footnote>
- évaluer le coût moyen d'un algorithme intégré sur n opérations, ce
qui revient à calculer la quantité :

$$
C_n = \sum_{\substack{\omega \in \{A, I, S\} \\ k \in N}} N_{\omega_k, n} C_{\omega(k)}
$$

où Cω(k) représente le coût de l'opération ω sur un fichier de
taille k (cf [Françon, 1978]).

Avec des notations évidentes, on considère les quantités homologues
N<sub>k,n</sub><sup>[h]</sup>, NA<sub>k,n</sub><sup>[h]</sup> ... relatives aux histoires de hauteur bornée et l'on désigne
par N<sub>k</sub>, NA<sub>k</sub><sup>...</sup>, N<sub>k</sub><sup>[h]</sup>, NA<sub>k</sub><sup>[h]</sup>,... les séries génératrices associées. Par
commodité, on notera de manière unique les quantités liées à des histoires de
hauteur bornées et les quantités correspondantes pour les histoires de hauteur
non bornées en écrivant J<sup>[∞]</sup> = lim<sub>h→∞</sub> J<sup>[h]</sup>.

**Corollaire 2** : Pour $k \le h \le \infty$ la série génératrice des interrogations à niveau $k$ dans les histoires de hauteur au plus $h$ est donnée par

$$
NI_k^{[h]} = \alpha_0 \sigma_1 \alpha_1 \sigma_2 \cdots \alpha_{k-1} \sigma_k \cdot l_k z^{2k+1} [\mu_0 H^{[h]} \ \mu_1 H^{[h]} \ \dots \ \mu_k H^{[h]}]^2
$$

où

$$
\mu_0 H^{[h]} = \frac{1}{1 - \mu_0^2 - \frac{\alpha_0 \sigma_1^2 z^2}{1 - \mu_1^2 z - \frac{\alpha_1 \sigma_2^2 z^2}{\dots}}}
$$

$$
\mu_1 H^{[h]} = \frac{1}{1 - \mu_1^2 z - \frac{\alpha_1 \sigma_2^2 z^2}{1 - \mu_2^2 z - \frac{\alpha_2 \sigma_3^2 z^2}{\dots}}},
$$

$$
\mu_1 H^{[h]} = \frac{1}{1 - \mu_2^2 z - \frac{\alpha_2 \sigma_3^2 z^2}{1 - \mu_3^2 z - \frac{\alpha_3 \sigma_4^2 z^2}{\dots}}}, \text{ etc...,}
$$

les fractions étant tronquées au niveau h.

**Preuve** : La série $\bar{K}^{[h]}$ est par définition la série caractéristique des histoires de hauteur $\le h$ :

$$
\bar{K}^{[h]} = \sum_{u \in K_h} u ;
$$

la série NI<sub>k</sub><sup>[h]</sup> est obtenue à partir de la série O de comptage des occurrences de
i<sub>h</sub>,

$$
0 = \sum |u|_{i_h} \cdot u,
$$
en passant à l'image commutative et en appliquant le morphisme du théorème 1 défini par :

$$ \chi(a_j) = \alpha_j z ; \quad \chi(i_j) = \iota_j ; \quad \chi(s_j) = \sigma_j z. $$

Or la série non commutative $O$ s'obtient à partir de $\overline{K}^{[h]}$ par la dérivation à telle que :

$$ \partial a_j = 1 ; \quad \partial s_j = 1 ; \quad \partial i_j = 1 \quad \text{si } j \neq k ; \quad \partial i_k = i_k. $$

Le résultat de l'énoncé se déduit directement en combinant le calcul de cette dérivée, et l'application du morphisme $\chi$. $\square$

**Note** : On obtient de manière analogue les séries $NA_k^{[h]}$ et $NS_k^{[h]}$.

**Corollaire 3** : Pour $k \le h \le \infty$ la série génératrice des histoires débutant à hauteur $k$ est donnée, avec les notations du corollaire 1, par :

$$ M_k^{[h]} = \sigma_1 \sigma_2 \dots \sigma_k z^k \cdot [\mu_0^H^{[h]} \dots \mu_k^H^{[h]}]. $$

**Preuve** : La preuve utilise une décomposition selon le dernier passage aux niveaux 0, 1, 2, ... comme suggéré par le diagramme ci-dessous :

<figure><img src="image_4.png" /><figcaption>Diagramme des histoires (généralisées) commençant au niveau k. $\square$</figcaption></figure>

**Note** : On énumère de même les histoires commençant en zéro et finissant au niveau $k$, les histoires commençant à niveau $k$ et finissant en $l$ etc.... Les séries génératrices d'histoires commençant à hauteur $k$ ont des relations étroites avec les polynômes qui apparaissent dans les réduites (résultats obtenus en collaboration avec J. Françon).

Enfin, on énoncera sans preuve le résultat suivant concernant le coût des adjonctions.
**Corollaire 4** : Soient $c_0, c_1, c_2, \dots$ les coûts d'une adjonction à un fichier de taille 0, 1, 2, ... ; soit $C_n^{[h]} = \sum_{k,n} NA_k^{[h]} c_k$ le coût total des adjonctions dans les histoires de taille n ; la série génératrice $C^{[h]}$ a pour expression :

$$ C^{[h]}(z) = \left\{ \frac{d}{du} G(z,u) \right\}_{u=1} \quad \text{où} \quad G(z,u) = \frac{1}{1 - l_0 z - \frac{\alpha_0 \sigma_1 \text{zu}_0}{1 - l_1 z - \frac{\alpha_1 \sigma_2 \text{zu}_1}{\dots}}} \quad \square $$

Des résultats analogues valent pour les autres opérations.

**Structures sans interrogation**

Dans le cas particulier où les possibilités d'interrogations sont nulles on peut donner au théorème 1 une forme particulière :

**Proposition 5**<sup>+</sup> Pour des structures sans interrogation, c-a-d telles que $l_j = 0$, le nombre d'histoires de longueur n et de profondeur $\le h$ vaut :

$$ H_n^{[h]} = \sum_{\substack{n_0+n_1+\dots+n_h \\ = n-1}} \binom{n_0+n_1-1}{n_1} \binom{n_1+n_2-1}{n_2} \dots \binom{n_{h-1}+n_h-1}{n_h} \lambda_1^{n_1} \lambda_2^{n_2} \dots \lambda_h^{n_h} $$

où $\lambda_j = \alpha_{j-1} \sigma_j$.

**Preuve** : On peut par exemple démontrer le résultat général d'après lequel le coefficient de $z_0^{n_0} z_1^{n_1} \dots z_r^{n_r}$ dans le développement en série entière de la fraction

$$ F(z_1, z_2, \dots) = \frac{1}{1 - \frac{z_0}{1 - \frac{z_1}{1 - \frac{z_2}{1 - \dots}}}} $$

est égal au produit

$$ \alpha_{n_0} n_1 \dots n_r = \binom{n_0+n_1-1}{n_1} \binom{n_1+n_2-1}{n_2} \dots \binom{n_{r-1}+n_{r-2}-1}{n_{r-1}} $$

<footnote>† On pourra comparer cette proposition à la question de [Rogers, 1907] p. 73.</footnote>
Il suffit de remarquer que $\alpha_{n_1 n_2 \dots n_r}$ compte les arbres généraux ayant
$n_1$ sommets à profondeur 1, $n_2$ sommets à profondeur 2 etc..., les profondeurs
étant comptées à partir de -1 pour la racine. On détermine élémentairement le
nombre de façons d'associer, pour chaque j, $n_{j-1}$ sommets de niveau j-1 à $n_j$
sommets de niveau j de sorte à respecter la structure d'arbre :

<figure><img src="image_5.png" /></figure>

3 - PROLONGEMENTS COMBINATOIRES

Nous avons montré précédemment comment les dénombrements d'histoires s'ex-
priment simplement en terme de fractions continues. La particularisation aux
fonctions de possibilités étudiées par [Françon-Viennot, 78] et [Françon, 78]
permet de donner une preuve combinatoire de divers développements en fraction
continue de séries classiques. A l'inverse le théorème 1 permet de construire
des interprétations, en termes d'histoires de fichiers, de tels développements ;
nous en montrons une application aux fonctions elliptiques qui rejoint certains
résultats de [Viennot, 1978].

3.1 - Nombres factoriels, nombres tangents et nombres Eulériens

Pour une fonction de possibilité définie en considérant deux types d'in-
terrogation $I^+$ et $I^-$ avec la fonction de possibilité

$$
\operatorname{pos}(A,k) = \operatorname{pos}(I^+,k) = \operatorname{pos}(I^-,k) = \operatorname{pos}(S,k) = k+1,
$$
Françon et Viennot ont établi une correspondance entre histoires et per-
mutations dont nous donnons maintenant une description succinte :

La correspondance que nous appellerons C associe à toute histoire de
longueur n une permutation de [n+1] en construisant l'arbre tournoi binaire
dont la permutation se déduit par projection. Cet arbre tournoi est obtenu
en partant de l'arbre vide par création successive de sommets avec dans l'ordre
l'étiquetage 1, 2, 3, ... n, n+1. Une lettre A dans le schéma correspond à
la création d'un point double de l'arbre, une lettre I⁺ à la création d'un
point simple à gauche, une lettre I⁻ à la création d'un point simple à droite
et une lettre S à la création d'une feuille ; la valeur correspondante dans
l'histoire indique l'emplacement du nouveau sommet créé dans l'arbre partiel
(dans l'ordre de gauche à droite par exemple). On termine par le sommet (n+1).

**Exemple** : Soit le schéma I⁻AI⁺ASAI⁻SS et l'histoire (suite de possibilités).
001021011. L'algorithme décrit construit par étapes les arbres suivants

<figure><img src="image_6.png" /></figure>

Soit en projection (1,7,10,4,8,6,9,2,5,3).

☐

<footnote>† Un arbre tournoi est un arbre étiqueté de façon croissante.</footnote>
Le théorème 1 permet de traduire directement cette correspondance en le
développement en fraction continue de F(z) = $\sum_{n \ge 0} (n+1)! z^n$ :

$$
F(z) = \frac{1}{1 - 2z - \frac{1.2z^2}{1 - 4z - \frac{2.3z^2}{1 - 6z - \frac{3.4z^2}{\dots}}}}
$$

De plus la correspondance C est construite pour associer aux lettres A et
l' des schémas d'histoires les doubles montées et les creux des permutations.
Soit A$_{n,k}$ le nombre de permutations de n à k montées ; les A$_{n,k}$ sont les nombres
Eulériens, cf. [Foata, Schützenberger, 1970], [Comtet, 1970] t. II p. 82. La
série génératrice exponentielle des A$_{n,k}$ vaut

$$
\sum A_{n,k} \frac{u^n}{n!} t^{k-1} = \frac{1-t}{e^{u(t-1)} - 1} .
$$

Les méthodes du théorème 1 conduisent pour la fonction génératrice ordinaire des
nombres Eulériens à la forme :

$$
\sum A_{n,k} u^n t^k = \frac{1}{1 - 1.u(t+1) - \frac{1.2u_t^2}{1 - 2.u(t+1) - \frac{2.3u_t^2}{1 - 3.u(t+1) - \frac{3.4u_t^2}{\dots}}}}
$$

Enfin Françon et Viennot ont montré que la correspondance C fournit
pour la fonction de possibilité :

$$
\operatorname{pos}(A,k) = \operatorname{pos}(S,k) = k+1 \qquad \operatorname{pos}(I^+,k) = \operatorname{pos}(I^-,k) = 0,
$$

une bijection entre les histoires de longueur 2n et les permutations alternantes
de [2n+1] lesquelles sont comptées par les nombres tangents (ou nombre d'Euler)
E_{2n+1} tels que

$$
\operatorname{tg} x = \sum_{n \ge 0} E_{2n+1} \frac{x^{2n+1}}{(2n+1)!} .
$$
On retrouve ainsi le développement en fraction continue de la série généra-
trice ordinaire des nombres tangents :

$$
\sum_{E_{2n+1}} z^{2n} = \frac{1}{1 - \frac{1.2z^2}{1 - \frac{2.3z^2}{1 - \frac{3.4z^2}{\vdots}}}}
$$

Utilisant l'écriture des séries génératrices ordinaires sous forme de
transformées de Laplace des séries exponentielles correspondantes, on peut
énoncer sous leur forme classique les résultats suivants dont on a ainsi une
preuve combinatoire :

Corollaire 6 : Les séries génératrices des factorielles, des nombres tangents et des nombres Eulériens sont données par :

$$
\int_0^\infty \frac{e^{-u} du}{z+u} = \frac{1}{z + \frac{1}{1 + \frac{1}{z + \frac{2}{1 + \frac{2}{z + \frac{3}{1 + \ldots}}}}}}
$$

$$
\int_0^\infty \text{thu} \ e^{-zu} \ du = \frac{1}{z^2 + \frac{1.2}{1 + \frac{2.3}{z^2 + \frac{3.4}{1 + \dots}}}}
$$

$$
\int_0^\infty \frac{1-t}{e^{(1-t)u}} e^{-zu} du = \frac{1}{z + \frac{1}{1 + \frac{t}{z + \frac{2}{1 + \frac{2t}{z + \frac{3}{1 + \dots}}}}}}
$$

Ces résultats déjà anciens sont donnés dans la formulation de [Wall, 1948]. De
la même manière, par des méthodes combinatoires, il est possible d'établir les déve-
loppements en fractions continues des transformées de Laplace de $\frac{1}{\cos x}$ + tg x et de
x tg $\frac{x}{2}$ qui ne semblent pas classiques (résultats obtenus en collaboration avec
J. Françon).
## 3.2 - Fonctions elliptiques

Le développement en fraction continue du théorème 1 est en fait une des formes les plus générale de développement en fractions continues de séries entières ; on montre en effet classiquement le résultat suivant ([Perron, 1957], t.II, p. 129) :

**Théorème** : Soit la série $f(x) = 1 + c_1 x + c_2 x^2 + \dots$ ; sous condition que les déterminants de Hankel

$$H_k(f) = \begin{vmatrix} c_1 & c_2 & \cdots & c_k \\ c_2 & c_3 & \cdots & c_{k+1} \\ \vdots & \vdots & & \vdots \\ c_k & c_{k+1} & \cdots & c_{2k-1} \end{vmatrix}$$

soient tous différents de zéro, il existe pour f un développement en fraction continue de la forme

$$f(x) = 1 + \frac{k_1 x}{1 + l_1 x - \frac{k_2 x^2}{1 + l_2 x - \frac{k_3 x^2}{1 + \dots}}}$$

Ainsi pour toute série vérifiant les conditions de Hankel, il existe un développement en fraction continue analogue à un développement de fonctions génératrices d'histoires. On dispose donc pour tous les développements de ce type tels que les coefficients soient entiers :

$$k_1, k_2, \dots \in \mathbb{N} ; \quad -l_1, -l_2, \dots \in \mathbb{N}$$

d'un procédé systématique d'interprétation combinatoire. C'est notamment le cas pour les fonctions elliptiques - cf [Whittaker, Watson, 1902], [Wall, 1948],
puisqu'on sait que

$$
\int_0^\infty cn(u,k) e^{-zu} du = \frac{1}{z + \frac{1^2}{z + \frac{2^2 k^2}{z + \frac{3^2}{z + \frac{4^2 k^2}{z + \ldots}}}}} =
$$

$$
\int_0^\infty dn(u,k) e^{-zu} du = \frac{1}{z + \frac{1^2 k^2}{z + \frac{2^2}{z + \frac{3^2 k^2}{z + \frac{4^2}{z + \ldots}}}}} =
$$

**Corollaire 7** : Le coefficient de $\frac{z^n}{n!} k^r$ dans le développement en série de $cn(u,k) - resp. dn(u,k)$ compte les histoires de longueur $n$ présentant $r$ passages à niveau pair -resp impair- pour la fonction de possibilité

$$
\operatorname{pos}(A,k) = k+1, \quad \operatorname{pos}(S,k) = k, \quad \operatorname{pos}(I,k) = 0.
$$

[]

Cette interprétation complète celle de [Viennot, 1978]. De manière plus générale, les développements en fractions continues des transformées des fonctions éliptiques sont interprétables comme séries génératrices de permutations alternantes (cn,dn) ou <<bégayantes>> (sn,cn,dn,sn²) (travail en collaboration avec J. Françon).

# 4 - APPLICATIONS ALGORITHMIQUES

La présentation sous forme de fractions continues des dénombrements d'histoires met en évidence les propriétés valables pour toute classe d'histoires (cf les Corollaires 2,3,4). Elle montre que les fonctions génératrices d'histoires de hauteur bornée sont des fractions rationnelles dont les numérateurs vérifient des récurrences linéaires. Ces récurrences sont le reflet direct du type de structure de donnée. Il reste à identifier dans chaque cas particulier les familles de polynômes qui apparaissent. Nous décrivons brièvement les premiers dénombrements ; ceux-ci, pour les types de données usuels, mettent en jeu plusieurs familles de polynômes classiques : les polynômes de Fibonacci (Tchebycheff), Hermite, Mittag-Leffler et Laguerre. Les résultats sont résumés par le tableau suivant
<table><thead><tr><th rowspan="2">Type de donnée</th><th colspan="3">Possibilités</th><th rowspan="2">Polynômes</th></tr><tr><th>pos(A,k)</th><th>pos(S,k)</th><th>pos(I,k)</th></tr></thead><tbody><tr><td>Pile</td><td>1</td><td>1</td><td>0</td><td>Fibonacci<br>(Tchebycheff)</td></tr><tr><td>File de priorité</td><td>k+1</td><td>1</td><td>0</td><td>Hermite</td></tr><tr><td>Liste linéaire simple</td><td>1</td><td>k</td><td>0</td><td>Hermite</td></tr><tr><td>Liste linéaire</td><td>k+1</td><td>k</td><td>0</td><td>Mittag-Leffler</td></tr><tr><td>Dictionnaire</td><td>k+1</td><td>k</td><td>2k+1</td><td>Laguerre</td></tr></tbody></table>

## Piles, files et polynômes de Fibonacci

Une pile est une structure sans interrogation telle que les possibilités d'adjonction et de suppression soient égales à 1 (indépendamment de la taille du fichier). Les histoires sont alors nécessairement de longueur paire et le nombre d'histoires de longueur $2n$ vaut le $n^{\text{ième}}$ nombre de Catalan $B_n = \frac{1}{n+1} \binom{2n}{n}$. Ce nombre compte aussi les arbres binaires de taille $n$ et les arbres généraux de taille $n+1$ (cf [Knuth, 1968]). L'application des méthodes de la section 2 permet de montrer :

**Proposition 8** : Soit la suite $\{F_j\}$ des polynômes appelés polynômes de Fibonacci et définis par la récurrence :

$$F_0(u) = 0 \quad F_1(u) = 1 \quad \text{et pour } j \ge 0 \quad F_{j+2}(u) = F_{j+1}(u) - u F_j(u);$$

les fonctions génératrices des histoires de genre pile valent (avec les notations du §2)

$$(i) \quad H^{[h]}(z) = \frac{F_{h+1}(z^2)}{F_{h+2}(z^2)}$$

$$(ii) \quad N_k^{[h]}(z) = z^{2k} \frac{F_{h-k+1}(z^2) F_{h-k+2}(z^2)}{F_{h+2}^2(z^2)}$$

$$(iii) \quad M_k^{[h]}(z) = z^k \frac{F_{h-k+2}(z^2)}{F_{h+2}(z^2)}$$

□
Ces résultats généralisent aux histoires de taille bornée les dénombrements relatifs aux histoires de taille non bornée obtenus par [Françon, 1977] et semble-t-il par [Read, 1978]. Le résultat (i) est connu depuis Kreweras et a été retrouvé par de Bruijn et al. ; le résultat (iii) généralise les distributions $(\gamma)$ et $(\delta)$ de Kreweras.

Les polynômes de Fibonacci sont des variantes des polynômes de Tchebycheff ; leurs coefficients sont les diagonales montantes prises avec des signes alternés du triangle de Pascal ; leurs zéros s'expriment simplement en fonction des racines de l'unité ; ceci conduit pour les dénombrements $H_n^{[h]}$, $N_{k,n}^{[h]}$ et $M_{k,n}^{[h]}$ à des expressions comme sommes trigonométriques et à des expressions équivalentes comme somme de coefficient binomiaux. Ces polynômes apparaissent fréquemment dans les dénombrements d'arbres et de chemins [Kreweras, 1970], [de Bruijn-Knuth-Rice, 1972], [Flajolet-Raoult-Vuillemin, 1978].

## Files de priorité, listes linéaires simples et polynômes d'Hermite

Les files de priorité correspondent aux possibilités :

$$ \operatorname{pos}(A,k) = k+1; \operatorname{pos}(S,k) = 1; \operatorname{pos}(I,k) = 0. $$

La fonction génératrice des histoires comptées par longueur admet donc le développement en fraction continue :

$$ \Gamma = \frac{1}{1 - \frac{1 \cdot z}{1 - \frac{2 \cdot z^2}{1 - \frac{3 \cdot z^4}{\dots}}}} $$

Le calcul des premières réduites montre les valeurs :

$$ \Gamma^{[0]} = 1, \quad \Gamma^{[1]} = \frac{1}{1-z^2}, \quad \Gamma^{[2]} = \frac{1-2z^2}{1-3z^2}, \quad \Gamma^{[3]} = \frac{1-5z^2}{1-6z^2+3z^4} $$

$$ \Gamma^{[4]} = \frac{1-9z^2+8z^4}{1-10z^2+15z^4}, \dots $$
et en général :

$\Gamma[h] = \frac{P_h(z)}{Q_h(z)}$, où les polynômes $P_n$ et $Q_n$ vérifient les récurrences :

$P_n = P_{n-1} - nz^2 P_{n-2}$ ; $Q_n = Q_{n-1} - nz^2 A_{n-2}$.

On peut comparer ces polynômes avec les polynômes d'Hermite $H_r$, sous la forme donnée par exemple par [Rainville; 1960] :

par définition $\sum_n H_n(x) \frac{t^n}{n!} = \exp(2tx - t^2)$, et les $H_n$ ont pour expression :

$$H_n(x) = \sum_{0 \le k \le \frac{n}{2}} (-1)^k \frac{n!(2x)^{n-2k}}{k!(n-2k)!}.$$

La comparaison des premières valeurs suggère que les polynômes $\{Q_n\}$ sont des variantes élémentaires des polynômes $\{H_n\}$. On vérifie facilement (par exemple par recurrence) la relation suivante :

$$Q_{n-1}(x) = x^n 2^{n/2} H_n\left(\frac{x}{\sqrt{2}}\right).$$

on obtient ainsi :

**Proposition 9** : Les histoires de type *file de priorité* de hauteur bornée ont pour fonction génératrice

$$\Gamma[h](z) = \frac{P_h(z)}{Q_h(z)}$$

où les polynômes $Q$ sont des variantes élémentaires des polynômes d'Hermite données par :

$$Q_{n-1}(z) = z^n 2^{n/2} H_n\left(\frac{x}{\sqrt{2}}\right). \quad \square$$

Les polynômes numérateurs $P$ vérifient une propriété analogue. Des rapports entre histoires de type *file de priorité* de hauteur non bornée et polynômes d'Hermite ont été mis en évidence par [Françon, 1978]. On notera également le développement en fractions continues (cf. [Wall, 1948] p 358) :
$$e^{x^2/2} \int_x^\infty e^{-u^2/2} du = \frac{1}{x + \frac{1}{x + \frac{2}{x + \frac{3}{x + \ldots}}}}$$

Des résultats similaires sont valables pour la structure **liste linéaire simple** pour laquelle :

$$\text{pos}(A;k) = 1 \quad \text{pos}(S;k) = k$$

**Listes linéaires et polynômes de Mittag-Leffler :**

Les **listes linéaires** correspondent aux possibilités :

$$\text{pos}(A;k) = k+1 \quad \text{pos}(S;k) = k \quad \text{pos}(I;k) = 0.$$

La fonction génératrice des histoires comptées par longueur vaut :

$$\Gamma(z) = \frac{1}{1 - \frac{z^2}{1 - \frac{z^2}{1 - \frac{z^2}{1 - \frac{z^2}{\dots}}}}}$$

et elle correspond à la série génératrice ordinaire des nombres secants. Le calcul des réduites montre :

$$\Gamma^{[0]} = 1 \quad \Gamma^{[1]} = \frac{1}{1-z^2} \quad \Gamma^{[2]} = \frac{1-4z^2}{1-5z^2} \quad \Gamma^{[3]} = \frac{1-13z^2}{1-14z^2+9z^4},$$

et en général $\Gamma^{[h]} = \frac{P_h}{Q_h}$ où les polynômes P et Q satisfont les recurrences :

$$P_n(z) = P_{n-1}(z) - n^2 z^2 P_{n-2}(z); \quad Q_n(z) = Q_{n-1}(z) - n^2 z^2 Q_{n-2}(z).$$

Nous déterminons maintenant la fonction génératrice des polynômes Q. Il est commode de poser $v^2 = -z^2$ c-a-d de définir les polynômes $\overline{Q}$ pairs et à coefficients positifs tels que $\overline{Q}_n(v) = Q_n(iv)$ ; il est également commode de faire 1'extension $\overline{Q}_{-1} = Q_{-1} = 1$ et de considérer la série génératrice :

$$K(v,t) = \sum_{j \ge -1} \overline{Q}_j(v) \frac{t^{j+1}}{j+1}.$$
La recurrence sur les polynômes Q se traduit, en multipliant par $\frac{t^n}{n!}$ et en sommant, par :

$$ \sum_{n \ge 1} \bar{Q}_n(v) \frac{t^n}{n!} = \sum_{n \ge 1} \bar{Q}_{n-1}(v) \frac{t^n}{n!} + v^2 \sum_{n \ge 1} n^2 \frac{t^n}{n!}, $$

soit après quelques manipulations par la relation :

$$ \frac{dK}{dt} = K + v^2 t^2 \frac{dK}{dt} - v^2 t K $$

et finalement :

$$ \frac{dK}{dt}(1-v^2 t^2) = K(1+v^2 t) . $$

Cette équation différentielle est à variables séparables ; notant $K' = \frac{dK}{dt}$, il vient :

$$ \frac{K'}{K} = \frac{1+v^2 t}{1-v^2 t^2} = \frac{\frac{1}{2}(1+v)}{1-vt} + \frac{\frac{1}{2}(1-v)}{1-vt} $$

soit en intégrant par rapport à t :

$$ \ln K = c(v) - \frac{1}{2v} (1+v) \ln (1-vt) + \frac{1}{2v} (1-v) \ln (1+vt) ; $$

les conditions initiales montrent que $c(v) = 0$, d'où finalement :

$$ K(v,t) = (1-v^2 t^2)^{-1/2} \left[ \frac{1+vt}{1-vt} \right]^{\frac{1}{2v}} . $$

Le développement du premier facteur est simple ; il fait intervenir comme coefficients les binomiaux $\binom{2n}{n}$. Quant au second facteur, c'est à une transformation linéaire près la série génératrice double des polynômes reciproques des polynômes de Mittag-Leffler $g_n$. Ceux-ci sont classiquement définis par leur fonction génératrice (cf [Rainville, 1960]).

$$ 1 + \sum_{n \ge 1} g_n(z) \frac{x^n}{n!} = \left[ \frac{1+t}{1-t} \right]^z $$

et s'expriment sous forme hypergéométrique par :

$$ g_n(z) = 2z {}_2F_1(1-n, 1-z, 2, 2). $$
**Proposition 10** : Les histoires de type **liste linéaire** de hauteur bornée ont pour fonction génératrice

$$ \Gamma^{[h]}(z) = \frac{P_h(z)}{Q_h(z)} $$

où les polynômes dénominateurs Q ont pour coefficients des convolutions de coefficients binomiaux $\binom{2k}{k}$ par des nombres de Mittag-Leffler :

$$ \sum_{n \ge -1} Q_n(z) \frac{t^{n+1}}{n+1!} = (1+z^2 t^2)^{-1/2} \left[ \frac{1+izt}{1-izt} \right]^{\frac{1}{2iz}} . \quad \square $$

**Dictionnaires et polynômes de Laguerre.**

Les histoires de type **dictionnaire** correspondent à la fonction de possibilité :

$$ \operatorname{pos}(A,k) = k+1 \ ; \ \operatorname{pos}(S,k) = k \ ; \ \operatorname{pos}(I,k) = 2k+1, $$

soit pour la fonction génératrice des histoires comptées par longueur l'expression :

$$ \Gamma = \frac{1}{1 - z - \frac{1^2 z^2}{1 - 3z - \frac{2^2 z^2}{1 - 5z - \frac{3^2 z^2}{\dots}}}} $$

Le calcul des réduites donne les valeurs :

$$ \Gamma^{[0]} = \frac{1}{1-z} \ ; \ \Gamma^{[1]} = \frac{1-3z}{1-4z+2z^2} \ ; \ \Gamma^{[2]} = \frac{1-8z+11z^2}{1-9z+18z^2-6z^3} \ ; $$

et en général $\Gamma^{[h]}(z) = \frac{P_h(z)}{Q_h(z)}$, où les polynômes P et Q vérifient les récurrences :

$$ P_n(z) = (1 - (2n+1)z) P_{n-1}(z) - n^2 z^2 P_{n-2}(z), $$

$$ Q_n(z) = (1 - (2n+1)z) Q_{n-1}(z) - n^2 z^2 Q_{n-2}(z). $$

Le calcul des séries génératrices de ces polynômes se conduit comme dans le cas des listes linéaires (polynômes de Mittag-Leffler). On part des conditions initiales $Q_{-1} = 1$, $Q_0 = 1-z$, et l'on pose
$$
K(z,t) = \sum_{j \ge -1} Q_j(z) \frac{t^{j+1}}{j+1!}
$$

La recurrence sur les polynômes Q conduit à l'équation différentielle

$$
\frac{dK}{dt} (1 + tz)^2 = K(1 - z - z^2 t),
$$

soit en séparant les variables et en intégrant :

$$
\ln K = c(z) - \frac{1}{z} (1+tz)^{-1} - \ln (1+tz).
$$

Les conditions initiales K(z,0) = 1 montrent que c(z) = 1/z, d'où :

$$
\ln K = \frac{t}{1+tz} - \ln (1+tz),
$$

et finalement

$$
K(z,t) = \frac{1}{1+tz} \exp \frac{1}{1+tz} .
$$

Sous cette forme on reconnaît que les polynômes Q sont à une constante multiplicative près les polynômes réciproques des polynômes de Laguerre. En effet, les polynômes de Laguerre $L_n$ sont définis classiquement par

$$
L_n(x) = \sum (-1)^k \binom{n}{k} \frac{x^k}{k!},
$$

et ont pour série génératrice ordinaire :

$$
\sum L_n(x) t^h = \frac{1}{1-t} \exp \frac{-xt}{1-t} .
$$

La comparaison de cette série avec la forme de K montre :

**Proposition 11** : Les histoires de type _dictionnaire_ de hauteur bornée ont pour série génératrice

$$
\Gamma^{[h]}(z) = \frac{P_h(z)}{Q_h(z)}
$$

où les polynômes Q sont, à un facteur multiplicatif près, les polynômes réciproques des polynômes de Laguerre :

$$
Q_n(z) = (-1)^{n+1} (n+1)! z^{n+1} L_{n+1}\left(\frac{1}{z}\right).
$$

□
## Histoires relatives à une population bornée.

Comme on l'a vu dans les sections précédentes, les fractions continues permettent d'exprimer les histoires de hauteur bornée. Elles constituent aussi le cadre dans lequel traiter des opérations effectuées sur un fichier de référence de taille N fixée. De telles histoires sont dites relatives à une population (ensemble de clefs) bornée. Nous montrons ici le cas des files de priorité et le cas des listes linéaires.

## Files de priorité sur un ensemble de clef bornée

Ce cas correspond à la fonction possibilité :

$$ \operatorname{pos}(A,k) = N-k \quad ; \operatorname{pos}(S,k) = 1 \quad ; \operatorname{pos}(I,k) = 0 $$

avec la contrainte que les opérations sur un fichier de taille supérieure à N sont impossibles.

La fonction génératrice des histoires comptées par longueur est rationnelle et a pour expression :

$$ \Gamma_N = \frac{1}{1 - \frac{N \cdot z}{1 - \frac{(N-1)z^2}{\dots}} \dots 1 - \frac{2z^2}{1 - z^2}} $$

Le calcul des premières valeurs montre :

$$ \Gamma_0 = 1 \quad \Gamma_1 = \frac{1}{1-z^2} \quad \Gamma_2 = \frac{1-z^2}{1-3z^2} \quad \Gamma_3 = \frac{1-3z^2}{1-6z^2+3z^4} $$

On vérifie par recurrence que les $\Gamma_N$ s'expriment au moyen d'une famille unique de polynômes $Q_N$ par :

$$ \Gamma_N = \frac{Q_{N-1}}{Q_N} $$

<footnote>† Ces histoires ont été considérées pour la première fois par Françon.</footnote>
où les polynômes Q satisfont la récurrence :

$$Q_N(z) = Q_{N-1}(z) - Nz^2 Q_{N-2}(z).$$

Ainsi les polynômes $Q_N$ sont égaux aux variantes élémentaires des polynômes d'Hermite déjà rencontrés.

**Proposition 12** : Les histoires de type *file de priorité* sur un *ensemble de clefs* bornées ont pour fonction générale

$$\Gamma_N(z) = \frac{Q_{N-1}(z)}{Q_N(z)},$$

où les polynômes Q sont reliés aux polynômes d'Hermite par la relation

$$Q_{n-1}(z) = z^n \frac{2^{n/2}}{H_n\left(\frac{z}{\sqrt{2}}\right)}.$$

□

Listes linéaires sur ensemble de clefs borné

Soit encore N la taille de la population de référence ; les *listes linéaires* sur ensemble de clefs borné (de taille N) correspondent aux possibilités

$$\text{pos}(A,k) = N-k \quad ; \quad \text{pos}(S,k) = k \quad ; \quad \text{pos}(I,k) = 0,$$

avec la condition que les opérations sur fichiers de taille supérieure à N sont impossibles.

La série générale des histoires comptées par longueur est rationnelle et a pour expression :

$$K(z) = \frac{1}{1 - \frac{N \cdot 1z^2}{1 - \frac{(N-1) \cdot 2z^2}{1 - \frac{(N-2) \cdot 3z^2}{\dots}}}} \cdot \\ 1 - \frac{2 \cdot (N-1)z^2}{1 - 1 \cdot N z^2}$$
Pour calculer cette expression, on peut par exemple utiliser le développement classique de la transformée de Laplace de sech<sup>k</sup> u (cf [Wall, 1948] p 306) :

$$ \int_0^\infty \sech^k u e^{-tu} du = \frac{1}{t + \frac{1 \cdot k}{t + \frac{2 \cdot (k+1)}{t + \frac{3 \cdot (k+2)}{\vdots}}}} $$

On obtient K à partir de cette expression en posant $k = -N$, puis en transformant la fraction :

$$ \int_0^\infty \mathrm{ch}^N u e^{-zu} \, du = \frac{1}{1 - \frac{N \cdot 1 \cdot (1/z)^2}{1 - \frac{(N-1) \cdot 2 \cdot (1/z)^2}{\vdots}}} $$

Ainsi, $K(\frac{1}{z}) = z \int_0^\infty \mathrm{ch}^N u e^{-zu} \, du$, ce qui signifie que la série génératrice exponentielle des histoires comptées par longueur vaut :

$$ \sum K_n \frac{u^n}{n!} = \mathrm{ch}^N u $$

Pour revenir à la série génératrice ordinaire, on développe $\mathrm{ch}^N u$ :

$$ K\left(\frac{1}{z}\right) = \frac{z}{2^N} \int_0^\infty \left( \sum_j \binom{N}{j} e^{u(N-2j)} \right) e^{-zu} \, du $$

Or, $z \int_0^\infty e^{u\alpha} e^{-zu} \, du = \frac{z}{z-u}$, ce qui donne l'expression de K :

$$ K\left(\frac{1}{z}\right) = \frac{z}{2^N} \sum_j \frac{\binom{N}{j}}{z - N + 2j} $$

et la valeur des coefficients :

$$ K_n = \frac{1}{2^N} \sum_j \binom{N}{j} (N-2j)^n $$
**Proposition 13** : Les histoires de **liste linéaire relatives** à **un ensemble borné de clefs** ont pour série génératrice

$$K(x) = \frac{1}{2^N} \sum_j \frac{\binom{N}{j}}{1-(N-2j)x},$$

et sont dénombrées par

$$K_n = \frac{1}{2^N} \sum_j \binom{N}{j} (N-2j)^n.$$

□

## 5 - CONCLUSION

Nous avons présenté dans cette note les premiers calculs de fonctions génératrices. Il reste à effectuer les calculs des nombres d'opérations effectuées à chaque niveau, et à les combiner avec les fonctions de coûts relatives aux algorithmes analysés. Un tel travail est en cours de réalisation (cf [Flajolet, Françon, Viennot, Vuillemin, 1978]).

**Remerciements** : Ce travail a bénéficié des suggestions et des encouragements de J. Françon, J-M Steyaert et J. Vuillemin.
BIBLIOGRAPHIE

[Comtet, 1970] L'Analyse Combinatoire, Paris.

[de Bruijn, Knuth, Rice, 1972] The Average Height of Planted Plane Trees, in Graph Theory and Computing, pp 15-22.

[Flajolet, Françon, Viennot, Vuillemin, 1978] Algorithmique et combinatoire des arbres et des permutations (à paraître).

[Flajolet, Raoult, Vuillemin, 1978] The Number of Registers Required to Evaluate Arithmetic Expressions, in Theoretical Computer Science (à paraître).

[Foata, Schützenberger, 1970] Théorie Géométrique des Polynômes Eulériens, Springer Verlag Berlin.

[Françon, 1977] On the Analysis of Algorithms for Trees, in Theoretical Computer Science, 4 pp 155-169.

[Françon, 1978] Histoires de Fichiers, in R.A.I.R.O. Inf. Th. vol 12 pp 49-62.

[Françon, Viennot, 1978] Permutations selon leurs Pics, Creux, Doubles Montées et Doubles Descentes, Nombres d'Euler et de Genocchi (soumis à publication).

[Knuth, 1968] The Art of Computer Programming, vol 1 Reading (USA).

[Kreweras, 1970] Sur les Eventails de Segments, in Cahiers du B.U.R.O., 15, pp 3-41.

[Perron, 1957] Die Lehre von den Kettenbrüchen, Stuttgart.
[Rainville, 1960] Special Function, Chelsea Pub C. New-York.

[Read, 1978] The Chord Intersection Problem, in Abstracts of 2nd Internat. Conf. on Comb. Math., New-York.

[Rogers, 1907] On the representation of certain asymptotic series as convergent continued fractions, in Proc. Lond. Math. Soc. Series 2, vol 4 pp. 72-89.

[Schützenberger, 1961] On a Special Class of Recurrent Events, in Ann. Math. Stat., 32 pp 1201-1213.

[Viennot, 1978] Une interpretation combinatoire des coefficients des développements en série entière des fonctions elliptiques de Jacobi (à paraître).

[Wall, 1948] Analytic Theory of Continued Fractions, New-York.

[Whittaker, Watson, 1902] A Course in Modern Analysis, Cambridge.