(3) $\varepsilon_{p,l}$ est égal au nombre de couples $(p', l')$ satisfaisant aux conditions (1) et (2) de (8.3.6)

$$ (1 \le p \le s; 0 \le l \le \lambda_p - 1). $$

A tout mot $f \in \alpha^{-1}h$ correspond une et une seule permutation standard, à savoir $\Pi f$. Inversement, à la permutation standard $\Pi_o$ correspond un et un seul mot $f$ tel que $\Pi f = \Pi_o$ ; ce mot est $f = x_{i_1} x_{i_2} \dots x_{i_r}$ avec $x_{i_k} = x_{p,l}$ où $(p,l)$ est le couple tel que

$$ (x_{p,l+1}, \varepsilon_{p,l+1}) = (x_{j_k}, \gamma_k \beta^l h). $$

Ainsi $\Pi$ est une bijection de $\alpha^{-1}h$ sur l'ensemble des permutations standards de $N(h)$.

Soit maintenant $f' = x_{v_1} x_{v_2} \dots x_{v_r}$ un mot de $\alpha^{-1}h$. $\Pi$ admet une et une seule factorisation

$$ \begin{gathered} f' = f_1 f_2 \dots f_s \quad \text{où} \quad f_1, f_2, \dots, f_s \in \mathcal{H} \\ f_1 \succeq f_2 \succeq \dots \succeq f_s \end{gathered} $$

Posons

$$ f_s = x_{p,0} x_{p,1} \dots x_{0,\lambda_{p-1}} \quad (\lambda_p = \lambda f_p) $$

$(1 \le p \le s)$ et $\varepsilon_{p,l}$ égal au nombre de couples $(p', l')$ satisfaisant aux conditions (1) et (2) de (8.3.6) $(1 \le p \le s; 0 \le l \le \lambda_{p-1})$.

Formons la permutation $\Pi'f'$ donnée par le produit des cycles disjoints

$$ \Pi' f' = (B_1) (B_2) \dots (B_s) $$

où

$$ (B_p) = ((x_{p,0}, \varepsilon_{p,0}) (x_{p,1}, \varepsilon_{p,1}) \dots (x_{p,\lambda_{p-1}}, \varepsilon_{p,\lambda_{p-1}})) \quad (1 \le p \le s) $$

Alors $\Pi' f'$ satisfait aux conditions (1), (2) et (3) de (8.3.8). Elle est donc standard. Comme la factorisation $f' = f_1 f_2 \dots f_s$ est unique, $\Pi'$ est alors une bijection de $\alpha^{-1}h$ sur l'ensemble des permutations standards de $N(h)$.

L'application $\varphi$ s'écrit alors
$$ \varphi = \Pi^{\prime-1} \Pi $$

et $\varphi$ est ainsi une permutation de l'ensemble $\alpha^{-1}h$.

Nous allons résumer ces résultats dans le théorème suivant et donner la condition nécessaire et suffisante annoncée au début du paragraphe pour les factorisations (S) spéciales.

THEOREME 8.1. - A tout couple $(\mathcal{H}, \leq)$ satisfaisant les conditions (S), c'est-à-dire que $\mathcal{H}$ est un ensemble fixe de mots primitifs totalement ordonné par $\leq$, tel que chaque élément $f \in \mathcal{X}^{*+}$ a une et une seule factorisation $f_1 f_2 \dots f_s$ ($s > 0$) où

$$ (i) \qquad f_1, f_2, \dots, f_s \in \mathcal{H} $$

$$ (ii) \qquad f_1 \geq f_2 \geq \dots \geq f_s, $$

on peut associer une permutation $\varphi$ de $\mathcal{X}^*$ telle que pour tout couple $(x, x') \in \mathcal{X}^2$, on ait

$$ v_{x,x'} \cdot f = \mu_{x,x'} \cdot \varphi f $$

et $\alpha f = \alpha \varphi f$ identiquement.

Soit, de plus, $\mathcal{X}_o$ un sous-ensemble de $\mathcal{X}^2$; on a alors, pour tout couple $(x, x') \in \mathcal{X}_o$, l'identité

$$ v_{x,x'} \cdot f = \xi_{x,x'} \cdot \varphi f $$

si et seulement si $(\mathcal{H}, \leq, \mathcal{X}_o)$ est spécial.

PREUVE.- La première propriété a été démontrée plus haut. Pour la seconde, supposons d'abord que pour un sous-ensemble $\mathcal{X}_o$ de $\mathcal{X}^2$, $(\mathcal{H}, \leq, \mathcal{X}_o)$ soit spécial. Soit $\varphi$ la permutation associée. Nous avons toujours

$$ v_{x,x'} \cdot f = \mu_{x,x'} \cdot \varphi f $$

identiquement pour tout $(x, x') \in \mathcal{X}^2$.

Posons pour $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \alpha^{-1}h$,

$$ f' = \varphi f = x_{v_1} x_{v_2} \dots x_{v_r} = f_1 f_2 \dots f_s $$
où

$$f_p = x_{p,0} x_{p,1} \dots x_{p,\lambda_{p-1}} \in \mathcal{H} \quad (\lambda_p = \lambda f_p) \quad (1 \le p \le s)$$

et

$$f_1 \ge f_2 \ge \dots \ge f_s.$$

Comme $\mathcal{X}_o$ ne peut contenir d'éléments de la diagonale de $\mathcal{X}^2$, on a $v_{x,x'} = \varepsilon_{x,x'}$, $\varphi f = 0$ pour tout $(x, x') \in \mathcal{X}_o$ lorsque $\lambda f = 1$.

Supposons donc $\lambda f > 1$ et soit $(x, x') \in \mathcal{X}_o$. Puisque $(\mathcal{H}, \leq, \mathcal{X}_o)$ est spécial, les seuls couples $(p, l)$ tels que $x_{p,l} = x$ et $x_{p,l+1} = x'$ ne peuvent être

$$(1, \lambda_1 - 1), (2, \lambda_2 - 1), \dots, (s, \lambda_{s-1} - 1)$$

et d'autre part, si $s > 1$, les seuls indices $k$ tels que $x_{v_{k}=x} = 1$ et $x_{v_{k+1}=x'} = 1$ ne peuvent être

$$\lambda_1, \lambda_1 + \lambda_2, \lambda_1 + \dots + \lambda_{s-1}.$$

On a donc identiquement

$$\mu_{x,x'} \varphi f = v_{x,x'} \varphi f \quad \text{pour } (x, x') \in \mathcal{X}_o; \quad (8.3.9)$$

soit

$$v_{x,x'} f = \varepsilon_{x,x'} \varphi f \quad \text{pour } (x, x') \in \mathcal{X}_o.$$

Réciproquement, si cette dernière relation est satisfaite, cela entraîne l'identité (8.3.9), puisqu'on a toujours $v_{x,x'} f = \mu_{x,x'} \varphi f$, ou encore

$$\mu_{x,x'}, f' = \varepsilon_{x,x'}, f' \quad \text{pour } (x, x') \in \mathcal{X}_o. \quad (8.3.10)$$

Si $f' \in \mathcal{H}$, la factorisation de $f'$ ne contient évidemment qu'un seul facteur ($s = 1$) et la relation (8.3.10) entraîne que l'on a forcément

$$(x_{v_r}, x_{v_l}) \notin \mathcal{X}_o$$

ou encore, pour tout $f \in \mathcal{H}$

$$(Lf, Pf) \notin \mathcal{X}_o. \quad (8.3.11)$$
Soit alors $f_m = x_{m,0} x_{m,1} \dots x_{m,\lambda_{m-1}}$ et
$f_{m'} = x_{m',0} x_{m',1} \dots x_{m',\lambda_{m,-1}}$

deux mots distincts de $\mathfrak{h}$.

Si $f_m \succ f_{m'}$ (pour l'ordre dans $\mathfrak{h}$), on a alors

$$ \mu_{x,x'} f_m f_{m'} = \mu_{x,x'} f_m + \mu_{x,x'} f_{m'} = \xi_{x,x'} f_m f_{m'} \quad (8.3.12) $$

pour $(x, x') \in \mathcal{X}_o$.

D'après (8.3.11)

$$(x_{m, \lambda_{m-1}}, x_{m, c}) \text{ et } (x_{m', \lambda_{m'-1}}, x_{m', c}) \notin \mathcal{X}_o. \quad (8.3.13)$$

Si l'on avait $(x_{m, \lambda_{m-1}}, x_{m', c}) \in \mathcal{X}_o$, on aurait pour

$$(x, x') = (x_{m, \lambda_{m-1}}, x_{m', c}), \\ \mu_{x,x'} f_m f_{m'} = \xi_{x,x'} f_m f_{m'} - 1$$

d'après (8.3.13). Ce qui contredirait (8.3.12).

D'où

$$(x_{m, \lambda_{m-1}}, x_{m', c}) \notin \mathcal{X}_o$$

ou encore

$$(L f_m, P f_{m'}) \notin \mathcal{X}_o. \quad (8.3.14)$$

Les relations (8.3.11) et (8.3.14) entraînent donc que $(\mathfrak{h}, \leq, \mathcal{X}_o)$ est spécial.

Ce qui achève la démonstration du théorème 8.1.

Explicitons maintenant ce théorème pour les factorisations spéciales, dont nous avons donné une construction algébrique au chapitre précédent.

L'ensemble à considérer pour ces factorisations est l'ensemble $\mathcal{X}_o = \{(x, x') \in \mathcal{X}^2 : x \le x'\}$ et pour cet ensemble, nous obtenons l'analogue du théorème 6.1', à savoir
THEOREME 6.2. - La permutation $\varphi$ associée à une factorisation spéciale vérifie $\alpha\varphi f = \alpha f$ identiquement et $\nu_{x,x'} f = \xi_{x,x'}\varphi f$ pour tout couple $(x, x') \in \mathcal{X}^2$ tel que $x < x'$.

Ce théorème nous permettra, dans le chapitre suivant, de montrer un résultat combinatoire sur les statistiques d'ordre.

Terminons ce chapitre par un exemple.

### 8.4. Exemple.

Considérons la factorisation (spéciale) en mots lexicographiques standards. Soit $\varphi$ la permutation qu'on lui associe par la méthode du paragraphe 8.3. Nous illustrons la construction de cette permutation sur un exemple.

Prenons pour $\mathcal{X}^*$ le monoïde engendré par $\mathbb{N}$ et considérons le mot $f = x_{i_1} x_{i_2} \dots x_{i_r} = 1 \ 1 \ 1 \ 2 \ 2 \ 2 \ 3 \ 4 \ 4 \ 5 \ 1 \ 1 \ 1 \ 2$ de $\mathcal{X}^*(r=12)$. On lui associe le mot non décroissant

$$f = x_{j_1} x_{j_2} \dots x_{j_r} = 1 \ 1 \ 1 \ 1 \ 2 \ 2 \ 2 \ 2 \ 3 \ 4 \ 4 \ 5 .$$

Formons l'ensemble des couples $N(h)$ où $h = \alpha f$.

$$N(h) = \{ (x_{u_t}, m_t) : 1 \le m \le n_t \ ; \ 1 \le t \le d \}$$

$$\text{où ici } d = 5 \qquad x_{u_t} = t \quad (1 \le t \le 5)$$

$$n_1 = 4 \qquad n_2 = 4 \qquad n_3 = 1 \qquad n_4 = 2 \qquad n_5 = 1 .$$

La permutation $\Pi f : (x_{i_k}, \gamma_k f) \longrightarrow (x_{j_k}, \gamma_k \beta f)$ de l'ensemble $N(h)$ peut s'écrire sous la forme classique

$$\Pi f = \begin{pmatrix} (2,1) & (1,1) & (2,2) & (2,3) & (3,1) & (4,1) & (4,2) & (5,1) & (1,2) & (1,3) & (1,4) \\ (1,1) & (1,2) & (1,3) & (1,4) & (2,1) & (2,2) & (2,3) & (2,4) & (3,1) & (4,1) & (4,2) \end{pmatrix}$$

ou encore comme produit de cycles disjoints

$$\Pi f = ((2,1) \ (1,1) \ (1,2) \ (3,1)) \ ((2,2) \ (1,3) \ (4,1)) \ ((2,3) \ (1,4) \ (4,2)) \\ ((5,1) \ (2,4))$$

Observons le résultat du lemme 8.1. Par exemple, considérons les deux éléments $(x_{p,l}, \epsilon_{p,l}) = (1,2)$ et $(x_{p',l'}, \epsilon_{p',l'}) = (1,4)$ ; ils satisfont $x_{p,l} = x_{p',l'}$ et $\epsilon_{p,l} < \epsilon_{p',l'}$. Nous vérifions alors que $x_{p,l+1} = 3 < 4 = x_{p',l'+1}$.
Formons les mots $x_{p,0} x_{p,1} \dots x_{p,\lambda_{p-1}}$ constitués dans chaque cycle par les premiers éléments de $(x_{p,l}, \varepsilon_{p,l})$. Nous avons 2113, 214, 214, 52 et ils sont tous primitifs. (Cf. lemme 8.2).

D'autre part, les deux mots correspondant à $p=2$ et $p=3$ sont conjugués (214 et 214). On peut observer que l'on a les inégalités $\varepsilon_{2,l} < \varepsilon_{3,l}$ $l=0, 1, 2$.

D'après (8.3.3), nous réécrirons chaque cycle de $\Pi f$ de manière que chaque mot $x_{p,0} x_{p,1} \dots x_{p,\lambda_{p-1}}$ appartienne à $\mathfrak{H}$ (ici l'ensemble des mots minimum dans leurs classes de conjugués). Nous obtenons

$$ \Pi f = ((1,1) (1,2) (3,1) (2,1)) ((1,3) (4,1) (2,2)) ((1,4) (4,2) (2,3)) \\ ((2,4) (5,1)). $$

Nous permutons ensuite les cycles entre eux de façon à satisfactoryer la condition (2) de (8.3.3) pour obtenir l'expression de $\Pi f$ sous forme standard :

$$ \Pi f = ((2,4) (5,1)) ((1,3) (4,1) (2,2)) ((1,4) (4,2) (2,3)) \\ ((1,1) (1,2) (3,1) (2,1)) \quad (8.4.1) $$

et d'après (8.3.4), nous posons

$$ \varphi f = x_{v_1} x_{v_2} \dots x_{v_r} = 2 \ 5 \ 1 \ 4 \ 2 \ 1 \ 4 \ 2 \ 1 \ 1 \ 3 \ 2. $$

Nous observons qu'en réordonnant les mots 25, 142, 143, et 1132 suivant l'ordre décroissant dans $\mathfrak{H}$ et en les juxtaposant, ainsi, on ne fait pas apparaître de nouvelles paires croissantes de lettres successives (l'ordre dans $\mathfrak{H}$ est spécial).

Nous avons

$$ v_{2,5} \ f = \varepsilon_{2,5} \ \varphi f = 1 $$

(il s'agit du couple $(x_{i_{12}}, x_{j_{12}})$ d'une part et du couple $(x_{v_1}, x_{v_2})$ d'autre part).

De même

$$ v_{1,4} \ f = \varepsilon_{1,4} \ \varphi f = 2 $$

$$ v_{1,3} \ f = \varepsilon_{1,3} \ \varphi f = 1. $$
Réciproquement, considérons le mot $f' = 251421421132$. Il admet la factorisation unique $f_1 f_2 f_3 f_4$ avec

$$f_1 = 25 \quad f_2 = 142 \quad f_3 = 142 \quad f_4 = 1132 \quad (1 \le p \le s = 4);$$

posons

$$f_p = x_{p,0} x_{p,1} \dots x_{p,\lambda_{p-1}}.$$

A tout couple $(p, l)$ nous faisons correspondre le mot $c_{p,l} = x_{p,l} x_{p,l+1} \dots x_{p,l+\Lambda_{-1}}$ où $\Lambda = r!$ puis nous déterminons les entiers $\epsilon_{p,l}$ vérifiant les conditions (1) et (2) du lemme 8.3.

Par exemple, il y a 4 couples $(p, l)$ tels que $x_{p,l}=1$. Ce sont $(2,0)$, $(3,0)$, $(4,0)$ et $(4,1)$.

Les mots $c_{p,l}$ associés sont

$$c_{2,0} = 142142 \dots$$

$$c_{3,0} = 142142 \dots$$

$$c_{4,0} = 11321132 \dots$$

$$c_{4,1} = 13211321 \dots$$

Pour l'ordre lexicographique, nous avons

$$c_{4,0} < c_{4,1} < c_{2,0} = c_{3,0}$$

D'où l'on pose, d'après les conditions (1) et (2) du lemme 8.3

$$\epsilon_{4,0} = 1 \quad \epsilon_{4,1} = 2 \quad \epsilon_{2,0} = 3 \quad \epsilon_{3,0} = 4.$$

Si nous formons alors la permutation $\Pi'f'$ donnée par le produit des cycles disjoints

$$\Pi'f' = (B_1) \dots (B_4)$$

où

$$(B_p) = ((x_{p,0}, \epsilon_{p,0}) \dots (x_{p,\lambda_{p-1}}, \epsilon_{p,\lambda_{p-1}})) \quad (1 \le p \le 4)$$

nous retrouvons l'expression (8.4.1).

D'où la correspondance
$f = 2 1 2 2 3 4 4 5 1 1 1 2 \rightarrow \varphi f = 2 5 1 4 2 1 4 2 1 1 3 2$

obtenue par la permutation associée à la factorisation en mots lexico-graphiques standards.

Si nous prenons la factorisation de Spitzer (Cf. 7.5), nous avons une autre permutation $\varphi$ ayant les mêmes propriétés.

La permutation $\Pi f$ sous forme standard s'écrit alors

$\Pi f = ((2,4) (5,1)) ((2,2) (1,3) (4,1)) ((2,3) (1,4) (4,2)) ((1,1) (1,2) (3,1) (2,1))$

correspondant au mot $f' = 2 5 2 1 4 2 1 4 1 1 3 2$.

Par cette permutation, nous associons à $f$ le mot $f'$.
## 9. Statistiques d'ordre. Formule de Spitzer

### 9.1. Introduction.

Les résultats combinatoires présentés jusqu'ici ont une interprétation naturelle en calcul des probabilités. Lorsque $\mathcal{X} = \mathbb{R}$, nous allons associer à tout mot $f = x_{i_1} x_{i_2} \dots x_{i_n}$ ($n > 0$) de $\mathcal{X}^*$ le vecteur $(x_{i_1}, x_{i_2}, \dots, x_{i_n})$ de $\mathbb{R}^n$ qui sera considéré comme une réalisation d'un certain vecteur aléatoire $X = (X_1, X_2, \dots, X_n)$. Au mot non décroissant $\beta f$ va correspondre une réalisation de la statistique d'ordre $(X_1^*, X_2^*, \dots, X_n^*)$ (voir § 9.2 ci-dessous). Les théorèmes 6.1 et 8.1 vont nous fournir ainsi un nouveau théorème sur les statistiques d'ordre (théorème 9.1) indépendant de la loi de probabilité du vecteur aléatoire.

Soit alors $b: \mathbb{R}^2 \rightarrow \mathbb{R}$ une fonction mesurable telle que $b(x, x') = 0$ si $x \ge x'$ et supposons que $X_1, X_2, \dots, X_n$ sont indépendants et équidistribués. Dans le paragraphe 9.3, nous allons montrer une identité sur une famille de fonctions caractéristiques $\{\Phi_n(\lambda), \psi_k(\lambda)\}_{(n \ge 0, k \ge 1)}$ ayant la même structure formelle que celle de Spitzer. Pour $n \ge 2$, $\Phi_n(\lambda)$ est la fonction caractéristique de la statistique

$$ \sum_{k=2}^{n} b(X_k, X_k^*) $$

$$ \text{et } \Phi_o(\lambda) = \Phi_1(\lambda) = 1; $$

$\psi_k(\lambda)$ est la fonction caractéristique de la statistique

$$ b(X_1, X_2) + \dots + b(X_{k-1}, X_k) + b(X_k, X_1) $$

et l'identité s'écrit

$$ \sum_{n=0}^{\infty} \Phi_n(\lambda) u^n = \exp \left[ \sum_{k=1}^{\infty} \frac{\psi_k(\lambda)}{k} u^k \right] \\ (|u| < 1, \operatorname{Im}(\lambda) \ge 0). $$
La démonstration que nous donnerons sera complètement combina-
toire et il ne sera pas nécessaire de supposer b continu.

Nous définissons (voir début du § 9.3), pour tout $\sigma, \tau \in \sigma_n$
et $f \in \mathcal{X}_n^*$ (n > 1), les deux quantités $Uf$ et $V\tau f$. Il s'agit
essentiellement de faire correspondre à tout $f \in \mathcal{X}_n^*$ (non néces-
sairement multilinéaire) une bijection $\tau_f : \sigma_n \to \sigma_n$ telle que

$$
U \sigma f = V \tau_f(\sigma) f \quad \text{pour tout} \quad \sigma \in \sigma_n.
$$

C'est l'objet du théorème 9.4. Là encore, c'est le cas des
mots non multilinéaires f qui est le plus délicat et qui nous amène
à définir une nouvelle factorisation (lemme 9.1). Le théorème 9.4
nous permet en outre de donner une preuve toute combinatoire du
théorème 2.2 de Spitzer ([38] p. 327).

L'identité de Spitzer a été abondamment étudiée par ailleurs
d'un point de vue analytique (Baxter [4], [5], Wendel [41], Kingman
[21] et Atkinson [2]). Nous n'avons pas cherché ici à appliquer ces
méthodes, mais avons préféré donner une preuve entièrement com-
binatoire de notre résultat. Signalons enfin que Sherman [36] établit
une autre identité du type de Spitzer à partir de la formule de Witt
non commutative. Nous terminons le chapitre par une simple appli-
cation probabiliste des formules de Witt.

9.2. Un théorème sur les statistiques d'ordre.

Les théorèmes 6.1 et 8.1 ont une interprétation naturelle en
calcul des probabilités. Nous la donnons maintenant.

Soit $X_1, X_2, \dots, X_n$ une suite de $n$ ($n > 1$) variables
aléatoires. Elle est dite en dépendance symétrique si la loi de pro-
babilité du vecteur $(X_1, X_2, \dots, X_n)$ est invariante par permuta-
tion des indices $1, 2, \dots, n$.

En particulier, toute suite de variables aléatoires indépen-
dantes et équidistribuées est en dépendance symétrique.

D'autre part, nous désignerons par $X_1^*, X_2^*, \dots, X_n^*$ la suite des $X_k$ ($1 \le k \le n$) rangés en ordre non décroissant. Cette suite est encore appelée la statistique d'ordre de $X_1, X_2, \dots, X_n$.

Nous avons alors
THEOREME 9.1. - Soit $X_1, X_2, \dots, X_n$ ($n > 1$) une suite de variables aléatoires en dépendance symétrique, $X_1^*, X_2^*, \dots, X_n^*$ la statistique d'ordre de cette suite et b une fonction mesurable $b: \mathbb{R}^2 \to \mathbb{R}$ telle que $b(x, x') = 0$ si $x \ge x'$.

Alors les deux variables aléatoires (statistiques)

$$ \sum_{k=2}^{n} b(X_k, X_k^*) \quad \text{et} \quad \sum_{k=2}^{n} b(X_{k-1}, X_k) $$

ont même distribution.

Ce résultat ne dépend pas de la loi de probabilité des $X_k$. Il est en particulier valable pour les distributions singulières du vecteur aléatoire $X = (X_1, X_2, \dots, X_n)$.

Dans la preuve, on utilise une méthode souvent employée dans la théorie des fluctuations des sommes de variables aléatoires. (Cf. par exemple Sparre Andersen [1]).

PREUVE. - Considérons l'espace de probabilité $(\mathbb{R}^n, \mathcal{A}_n, P_x)$ où $\mathcal{A}_n$ est la tribu borélienne de $\mathbb{R}^n$ et $P_x$ la mesure de probabilité du vecteur $X$ et soit

$$ v : (x_1, x_2, \dots, x_n) \to \sum_{k=2}^{n} b(x_k, x_k^*) $$

et

$$ \xi : (x_1, x_2, \dots, x_n) \to \sum_{k=2}^{n} b(x_{k-1}, x_k) $$

les variables aléatoires réelles définies dans $(\mathbb{R}^n, \mathcal{A}_n, P_x)$, où $(x_1^*, x_2^*, \dots, x_n^*)$ désigne le vecteur de $\mathbb{R}^n$ dont les coordonnées sont les $x_k$ rangés en ordre non décroissant.

Désignons par $t$ la bijection qui envoie le vecteur

$$ (x_{i_1}, x_{i_2}, \dots, x_{i_n}) $$

de $\mathbb{R}^n$ sur le mot $f = x_{i_1} x_{i_2} \dots x_{i_n}$ du sous-ensemble $\mathcal{X}_n^*$ (des mots de longueur $n$) du monoïde libre $\mathcal{X}^*$ engendré par $\mathcal{X} = \mathbb{R}$.

D'après le théorème 8.1, pour $\varphi$ (ou le théorème 6.1 pour $\varphi_1$), l'application $t^{-1}\varphi t = \varphi$ est une permutation de $\mathbb{R}^n$ qui à $(x_{i_1}, x_{i_2}, \dots, x_{i_n}) \in \mathbb{R}^n$ fait correspondre un vecteur
$$ (x_{v_1}, x_{v_2}, \dots, x_{v_n}) \in \mathbb{R}^n $$

où

1. $(v_1, v_2, \dots, v_n)$ est une permutation de $(i_1, i_2, \dots, i_n)$;

2. À tout $k \in [2, n]$ tel que $x_k^* > x_{i_k}$ correspond biunivoquement un $k' \in [2, n]$ tel que $x_{v_{k'}} = x_k^* > x_{i_k} = x_{v_{k'}-1}$.

Nous avons ainsi, en tenant compte de $b(x, x') = 0$ si $x \ge x'$

$$ v(x_{i_1}, x_{i_2}, \dots, x_{i_n}) = \sum_{k=2}^{n} b(x_{i_k}, x_k^*) = \sum_{k=2}^{n} b(x_{v_{k-1}}, x_{v_{k'}}) = \xi(x_{v_1}, x_{v_2}, \dots, x_{v_n}) $$

Il en résulte que pour tout ensemble mesurable $B \in \mathcal{A}_1$, on a

$$ v^{-1} B = \psi^{-1} \xi^{-1} B. $$

D'où

$$ P_x v^{-1} B = P_x \psi^{-1} \xi^{-1} B. $$

Le théorème sera ainsi démontré si nous prouvons

$$ P_x \psi^{-1} A = P_x A $$

pour tout $A \in \mathcal{A}_n$.

Ce résultat vient de la dépendance symétrique des $X_k$ et du fait que $\psi^{-1}$ est localement une permutation de $(x_1, x_2, \dots, x_n)$.

De façon précise, définissons une relation d'équivalence (S) sur les vecteurs de $\mathbb{R}^n$ en posant

$$ (x_{i_1}, x_{i_2}, \dots, x_{i_n}) \equiv (x_{i'_1}, x_{i'_2}, \dots, x_{i'_n}) \mod (S) $$

si et seulement si

$$ x_{i_k} < x_{i_l} \text{ (resp. } x_{i_k} = x_{i_l}) \iff x_{i'_k} < x_{i'_l} \text{ (resp. } x_{i'_k} = x_{i'_l}) $$

pour tout couple $(k, l)$ ($1 \le k, l \le n$).

La définition de la permutation $\varphi$ (Cf. 8.3) (ou celle de $\Phi_1$, Cf. 6.2) entraîne alors que si

$$ (x_{i_1}, x_{i_2}, \dots, x_{i_n}) \equiv (x_{i'_1}, x_{i'_2}, \dots, x_{i'_n}) \mod (S) $$
alors

$$ \psi^{-1}(x_{i_1}, x_{i_2}, \dots, x_{i_n}) \equiv \psi^{-1}(x_{i'_1}, x_{i'_2}, \dots, x_{i'_n}) \mod(S). $$

De là, l'extension de $\psi^{-1}$ à l'ensemble quotient $\mathbb{R}^n/S$ est une permutation de $\mathbb{R}^n/S$ et d'autre part, à toute classe d'équivalence $F \in \mathbb{R}^n/S$, correspond une permutation $(\sigma_1, \sigma_2, \dots, \sigma_n)$ de $[1, n]$ telle que si $(x_{i_1}, x_{i_2}, \dots, x_{i_n}) \in F$, alors

$$ \psi^{-1}(x_{i_1}, x_{i_2}, \dots, x_{i_n}) = (x_{i_1 \sigma_1}, x_{i_2 \sigma_2}, \dots, x_{i_n \sigma_n}) $$

que nous poserons égal à $\sigma(x_{i_1}, x_{i_2}, \dots, x_{i_n})$.

Les classes d'équivalence $F$ de $\mathbb{R}^n/S$ forment ainsi une partition finie de $\mathbb{R}^n$ en sous-ensembles mesurables. Nous écrirons

$$ \mathbb{R}^n = \bigcup_{k \in \text{ensemble fini}} F_k $$

où les $F_k$ sont disjoints deux à deux

et nous désignerons par $\sigma^{(k)}$ la permutation de $\mathbb{R}^n$ coincidant sur $F_k$ avec la restriction de $\psi^{-1}$ à $F_k$.

Soit alors $A \in \alpha_n$.

Nous avons

$$ A = \bigcup_k A \cap F_k $$

où les ensembles $A \cap F_k$ sont disjoints deux à deux.

$$ \psi^{-1} A = \bigcup_k \psi^{-1}(A \cap F_k) = \bigcup_k \sigma^{(k)}(A \cap F_k). $$

Les $\sigma^{(k)}(A \cap F_k)$ étant d'une part mesurables et d'autre part disjoints deux à deux,

$$ P_x \psi^{-1} A = \sum_k P_x \sigma^{(k)}(A \cap F_k) $$

mais comme la suite $X_1, X_2, \dots, X_n$ est en dépendance symétrique, $P_x \sigma^{(k)}(A \cap F_k) = P_x(A \cap F_k)$.

D'où
$$ P_X \Psi^{-1} A = \sum_k P_X (A \cap F_k) = P_X (\cup_k A \cap F_k) \\ = P_X A. $$

Ce qui achève la démonstration du théorème.

Si dans la démonstration du théorème 9.1, nous remplaçons la bijection $\Phi_1$ par la bijection $\Phi_2$, nous avons alors le résultat

THEOREME 9.1'. - Sous les mêmes hypothèses que le théorème 9.1, les variables aléatoires

$$ \sum_{k=1}^{n-1} b(X_k^*, X_k) \quad \text{et} \quad \sum_{k=1}^{n-1} b(X_{k+1}, X_k) $$

ont même distribution

Nous donnons dans le prochain paragraphe une identité sur les fonctions caractéristiques des variables aléatoires analogue à celle donnée par Spitzer dans la théorie des fluctuations de sommes de variables aléatoires.

### 9.3. Une identité sur les fonctions caractéristiques des statistiques d'ordre.

Nous introduisons d'abord quelques notations.

Soit $\mathcal{X}$ un ensemble totalement ordonné. Pour tout mot $f = x_1 x_2 \dots x_n$ de $\mathcal{X}^*(n > 0)$ et toute permutation

$$ \sigma : k \to i_k \quad (1 \le k \le n) \text{ de } [1, n], $$

nous posons

$$ \sigma f = x_{i_1} x_{i_2} \dots x_{i_n}. $$

Soit encore $b$ une application $b: \mathcal{X}^2 \to \Omega$ telle que $b(x, x') = 0$ si $x \succeq x'$ (pour l'ordre total dans $\mathcal{X}$), $\Omega$ étant un anneau commutatif (unitaire). Nous posons alors pour tout $f \in \mathcal{X}^*_n$

$$ U \sigma f = b(x_{i_1}, x_{i_2}) + b(x_{i_2}, x_{i_3}) + \dots + b(x_{i_{n-1}}, x_{i_n}) $$

$$ \text{si } n > 1 $$

$$ \text{et } U \sigma f = 0 \quad \text{si } n = 1 $$
Lorsque $\mathcal{X} = \mathbf{R}$, nous introduisons en outre pour tout $f \in \mathcal{X}_n^*(n > 0)$,

$$S\sigma f = \max_{1 \le k \le n} \left( \sum_{k'=1}^{k} x_{i_k} \right)^+.$$

Soit maintenant $\tau$ une permutation de $[1, n]$ donnée comme produit des cycles disjoints

$$\tau = (B_1) (B_2) \dots (B_s) \qquad (9.3.1)$$

avec

$$(B_p) = (i_{\Lambda_{p-1}+1} \ i_{\Lambda_{p-1}+2} \ \dots \ i_{\Lambda_p}) \qquad (9.3.2)$$

$$(\Lambda_o = 0; 1 \le p \le s).$$

Nous posons alors

$$B_p f = x_{i_{\Lambda_{p-1}}+1} \ x_{i_{\Lambda_{p-1}}+2} \ \dots \ x_{i_{\Lambda}} \in \mathcal{X}^*,$$

$$\begin{align*} \text{D } B_p f &= b(x_{i_{\Lambda_p}}, x_{i_{\Lambda_p}}) \quad \text{si } \Lambda_p = \Lambda_{p-1} + 1 \\ &= b(x_{i_{\Lambda_{p-1}}+1}, x_{i_{\Lambda_{p-1}}+2}) + \dots + b(x_{i_{\Lambda_{p-1}}}, x_{i_{\Lambda_p}}) + b(x_{i_{\Lambda_p}}, x_{i_{\Lambda_{p-1}}+1}) \end{align*}$$

$$\text{si } \Lambda_p > \Lambda_{p-1} + 1$$

$$(1 \le p \le s)$$

et enfin

$$V \tau f = D B_1 f + D B_2 f + \dots + D B_s f.$$

Dans le cas où $\mathcal{X} = \mathbf{R}$, nous posons enfin

$$T \tau f = \sum_{p=1}^{s} (x_{i_{\Lambda_{p-1}}+1} + x_{i_{\Lambda_{p-1}}+2} + \dots + x_{i_{\Lambda_p}})^+$$

Nous montrons alors le résultat suivant

**THEOREME 9.2.** - Pour tout mot $f = x_1 x_2 \dots x_n$ de $\mathcal{X}_n^*(n > 1)$ les ensembles $\{U\sigma f : \sigma \in \mathcal{S}_n\}$ et $\{V\tau f : \tau \in \mathcal{S}_n\}$ sont identiques.

Ce théorème est à rapprocher de celui de Spitzer ([37] théorème 2.2), à savoir
THEOREME 9.3 (Spitzer).- Pour tout mot $f = x_1 x_2 \dots x_n$ de $\mathcal{X}^*$
$(n \ge 1)$ où $\mathcal{X}$ est la droite réelle $\mathbf{R}$, les ensembles $\{S \sigma f : \sigma \in \sigma_n\}$
et $\{T \tau f : \tau \in \sigma_n\}$ sont identiques.

Soit $\mathcal{X}'$ l'ensemble des mots $f = x_1 x_2 \dots x_n$ de $\mathcal{X}_n^*$ tels
que pour des $r_k$ rationnels $(1 \le k \le n)$ on ait

$$
r_1 x_1 + r_2 x_2 + \dots + r_n x_n = 0
$$

si et seulement si $r_k = 0$ pour tout $k \in [1, n]$.

Spitzer construit alors pour tout $f \in \mathcal{X}'$ une bijection
$\tau_f: \sigma_n \to \sigma'_n$ telle que pour tout $\sigma \in \sigma'_n$ on ait

$$
S \sigma f = T \tau_f(\sigma) f.
$$

Il étend alors ce résultat à tous les mots $f \in \mathcal{X}_n^*$ par suite
de la continuité des fonctions

$$
x = (x_1, x_2, \dots, x_n) \longrightarrow S \sigma f \quad \text{et} \quad x \longrightarrow T \tau f
$$

$(f \text{ étant le mot } f = x_1 x_2 \dots x_n \text{ de } \mathcal{X}_n^*).$

Dans le théorème 9.2, nous ne faisons aucune hypothèse topo-
logique sur l'anneau $\Omega$ ou sur l'application $b$ (en dehors de
$b(x, x') = 0$ si $x \ge x'$) et l'argument employé est de nature com-
plètement combinatoire. Nous utilisons les factorisations spéciales
introduites dans les chapitres précédents, et en particulier pour la
factorisation (spéciale) de Spitzer (Cf. 7.5) nous donnons une nou-
velle preuve du théorème 9.3, ne faisant pas intervenir la conti-
nuité des fonctions $x \to S\sigma f$ et $x \to T\tau f$.

En fait, nous montrons

THEOREME 9.4.- A toute factorisation spéciale $(\mathcal{H}, \leq)$ de $\mathcal{X}^*$ est
associée une famille d'applications $(\tau_f)_{f \in \mathcal{X}^*}$ telle que

$$
(i) \quad \text{pour tout } f \in \mathcal{X}_n^* \text{ (n > 0)}
$$

$$
\tau_f : \sigma_n \to \sigma_n
$$

est une bijection

$$
(ii) \quad \text{pour tout } f \in \mathcal{X}_n^* \text{ (n > 0) et } \sigma \in \sigma_n
$$

$$
U \sigma f = V \tau_f(\sigma) f.
$$
Lorsque $\mathcal{X} = \mathbb{R}$ et que $(\mathcal{H}, \leq)$ est la factorisation (spéciale) de Spitzer, la famille $\tau_f$ satisfait en plus la relation

$$S \sigma f = T \tau_f(\sigma) f$$

$(f \in \mathcal{X}_n^* ; n > 0).$

Pour la preuve, nous aurons besoin d'un lemme préliminaire (lemme 9.1 ci-dessous) que nous allons démontrer après avoir rapi-
pelé quelques notations.

Soit $\mathcal{Y}^*$ le monoïde libre engendré par le produit cartésien
$\mathcal{Y} = \mathcal{X} \times \mathbb{N}$. Si $g = y_1 y_2 \dots y_n$ est un mot de $\mathcal{Y}^*$ tel que

$$y_k = (x_k, m_k) \quad (x_k \in \mathcal{X}, m_k \in \mathbb{N} ; 1 \le k \le n)$$

nous posons

$$\rho g = x_1 x_2 \dots x_n \in \mathcal{X}^* \quad \text{et} \quad m_k = m(k) g$$

(ou simplement $m(k)$ s'il n'y a pas risque de confusion $1 \le k \le n$).

Supposons en outre donnée la factorisation spéciale $(\mathcal{H}, \leq)$ de $\mathcal{X}^*$. Nous désignerons alors par $\mathcal{H}'$ le sous-ensemble des mots $g \in \mathcal{Y}^*$ tels que

$$1/ \rho g = f^q \text{ où } f \in \mathcal{H} \text{ et } q > 0 \text{ et tels que}$$

$$2/ \text{ le mot } m(1)g \text{ m}(1+\lambda f)g \dots \text{ m}(1+(q-1)\lambda f)g \text{ est un mot lexicographique standard dans le monoïde libre engendré par } \mathbb{N} \text{ .} \\ \text{ Nous avons alors}$$

LEMME 9.1.- Tout mot multilinéaire $g$ de $\mathcal{Y}^*$ a une factorisation unique $g_1 g_2 \dots g_s$ telle que

$$1/ g_1, g_2, \dots, g_s \in \mathcal{H}'$$

$$2/ \text{ en posant } \rho g_p = f_p^{q_p} \text{ avec } f_p \in \mathcal{H}, \text{ on a pour } 1 \le p < s$$

$$- \text{ou } f_p > f_{p+1}$$

$$- \text{ou } f_p = f_{p+1} \text{ et } m(1)g_p > m(1)g_{p+1}.$$

D'autre part, toute classe multilinéaire de mots conjugués de $\mathcal{Y}^*$ contient un et un seul mot de $\mathcal{H}'$.
PREUVE. - En effet, soit $g = y_1 y_2 \dots y_n$ un mot multilinéaire de $y^*$.

Posons

$\rho g = x_1 x_2 \dots x_n \text{ et } y_k = (x_k, m_k) \quad m_k \in \mathbb{N} \quad (1 \le k \le n).$

Soit $f_1^{q'_1} f_2^{q'_2} \dots f_v^{q'_v}$ la factorisation (unique) de $\rho g$ telle que
$f_1, f_2, \dots, f_v \in \mathfrak{H} ; f_1 > f_2 > \dots > f_v$ et $q'_1, q'_2, \dots, q'_v \ge 1$.

Posons

$$
K_u = q'_1 \cdot \lambda f_1 + q'_2 \cdot \lambda f_2 + \dots + q'_u \cdot \lambda f_u
$$

et

$$
g'_{u} = y_{K_{u-1}+1} y_{K_{u-1}+2} \cdots y_{K_{u}} \quad (1 \le u \le v; K_{o} = 0).
$$

Si tous les $q'_u$ sont égaux à 1, on pose $g_u = g'_u$ ($1 \le u \le v$) et $v = s$ et $g_1 g_2 \dots g_s$ est la factorisation unique de g satis- faisant aux conditions 1/ et 2/ de l'énoncé.

Si on a $q'_{u} > 1$ pour un certain $u \in [1, v]$, nous considé-
rons alors la suite des entiers (distincts car $g$ est multilinéaire).

$$
m(K_{u-1}+1), m(K_{u-1}+1+\lambda f_u), \dots, m(K_{u-1}+1+(q'_u-1)\lambda f_u).
$$

Dans le monoïde libre engendré par $\mathbb{N}$, le mot

$$
m(K_{u-1}+1) \quad m(K_{u-1}+1+\lambda f_u) \quad \dots \quad m(K_{u-1}+1+(q'_u-1)\lambda f_u)
$$

admet une factorisation unique en mots lexicographiques standards ;
nous pouvons ainsi écrire

$$
g'_{u} = g''_{u,1} g''_{u,2} \dots g''_{u,a_u}
$$

$$
où \quad \rho g''_{u,c} = f''_{u,c}
$$

$f_u \in \mathcal{H}$

et où

$$
m(1)g''_{u,c} \quad m(1+\lambda f_u)g''_{u,c} \quad \dots \quad m(1+(q''_{u,c}-1)\lambda f_u)g''_{u,c}
$$

est un mot lexicographique standard dans le monoïde libre engendré par $\mathbb{N}$ ($1 \le c \le a_u$).
Si $a_u > 1$, on a en outre

$$m(1)g''_{u,1} > m(1)g''_{u,2} > \dots > m(1)g''_{u,a_u}.$$

D'autre part, si $v > 1$, alors on a pour tout $u$ ($1 \le u \le v$)

$$\rho g''_{u,a_u} = f_u > f_{u+1} = \rho g''_{u+1,1}.$$

Ce qui démontre la première partie du lemme.

Pour la seconde partie du lemme, soit $g'$ un mot multi-linéaire de $\mathcal{Y}^*$. Alors $\rho g' = f'^q$ où $f'$ est primitif et $q$ maximal $> 0$. Dans la classe de $f'$ il existe un et un seul mot $f \in \mathcal{F}$.

D'autre part, parmi tous les mots $g$ de la classe de $g'$ tels que $\rho g = f^q$, il y en a un et un seul qui soit tel que le mot (qui a toutes ses lettres distinctes puisque $g'$ est multilinéaire)

$$m(1) g \quad m(1+\lambda f) g \quad \dots \quad m(1+(q-1)\lambda f) g$$

soit un mot lexicographique standard.

Ce qui achève la démonstration du lemme.

La démonstration du théorème 9.4 consiste alors à associer à tout $f = x_1 x_2 \dots x_n$ de $\mathcal{X}_n^*$ ($n > 0$) un mot $\rho'f = y_1 y_2 \dots y_n$ de $\mathcal{Y}^*$ en posant

$$y_k = (x_k, \gamma_k f) \quad (1 \le k \le n),$$

puis à définir une certaine bijection entre les $n!$ permutations de $\sigma_n$ et les $n!$ mots de la classe abélienne de $\rho'f$ (puisque ce mot est multilinéaire dans $\mathcal{Y}^*$).

De façon précise, supposons que $\tau \in \sigma_n$ est donné comme produit des cycles disjoints

$$\tau = (B_1) (B_2) \dots (B_s) \\ (B_p) = (i_{\Lambda_{p-1}+1} \ i_{\Lambda_{p-1}+2} \ \dots \ i_{\Lambda_p}) \\ (1 \le p \le s \ ; \ \Lambda_0 = 0).$$

Considérons les mots
$$B_p \rho' f = y_{i_{\Lambda_{p-1}+1}} y_{i_{\Lambda_{p-1}+2}} \cdots y_{i_{\Lambda_p}}$$

D'après le lemme 9.1, il n'y a qu'un et qu'un seul mot de $\mathfrak{C}'$ conjugué à $B_p \rho'$ f. Comme chacun des cycles $(B_p)$ n'est défini qu'à une permutation circulaire près de ses éléments, on peut le réécrire d'une seule façon

$$(B_p) = (i_{\kappa_{p,1}} \ i_{\kappa_{p,2}} \ \cdots \ i_{\kappa_{p,\lambda_p}})$$

où $(K_{p,1}, K_{p,2}, \dots, K_{p,\lambda_p})$ est une permutation circulaire de

$$(\Lambda_{p-1} + 1, \ \Lambda_{p-1} + 2, \ \dots, \ \Lambda_p)$$

et où le mot

$$g_p = y_{i_{\kappa_{p,1}}} \ y_{i_{\kappa_{p,2}}} \ \cdots \ y_{i_{\kappa_{p,\lambda_p}}} \ \in \mathfrak{C}'$$

Posons

$$\rho g_p = f_p^{q_p} \quad \text{avec} \quad f_p \in \mathfrak{C}.$$

La permutation $\tau$ n'étant définie qu'à une permutation près de ses cycles, il existe une et une seule permutation $(p_1, p_2, \dots, p_i)$ de $[1, s]$ telle que l'on ait pour tout couple $(l, l')$ $(1 \le l < l' \le s)$

$$f_{p_l} \supseteq f_{p_l'}$$

et si $f_{p_l} = f_{p_l'}$, alors $m(1)g_{p_l} > m(1)g_{p_l'}$.

Posons

$$g = g_{p_1} \ g_{p_2} \ \cdots \ g_{p_s} = y_{i_1'} \ y_{i_2'} \ \cdots \ y_{i_s'}$$

Nous faisons alors correspondre à $\tau$ la permutation

$$\sigma_f(\tau) : k \longrightarrow i_k' \quad (1 \le k \le n).$$

Réciproquement, étant donné $\sigma \in \sigma_n$, soit

$$\sigma f = x_{i_1} \ x_{i_2} \ \cdots \ x_{i_n} \quad \text{et} \quad \sigma \rho' f = y_{i_1} \ y_{i_2} \ \cdots \ y_{i_n}.$$

Le mot $\sigma \rho' f$, multilinéaire dans $\mathcal{Y}^*$ a d'après le lemme 9.1 une factorisation unique $g_1 g_2 \cdots g_s$ satisfaisant les conditions 1/ et 2/ du lemme 9.1.

Nous posons alors
$$ \tau_f(\sigma) = (i_1 i_2 \dots i_{\Lambda_1}) (i_{\Lambda_1+1} i_{\Lambda_1+2} \dots i_{\Lambda_2}) \dots (i_{\Lambda_{s-1}+1} i_{\Lambda_{s-1}+2} \dots i_{\Lambda_s}) $$

$$ \text{où } \Lambda_p = \lambda g_1 + \lambda g_2 + \dots + \lambda g_p \quad (1 \le p \le s \; ; \; \Lambda_o = 0). $$

Par construction, nous avons évidemment

$$ \sigma_f[\tau_f(\sigma)] = \sigma $$

Ce qui établit la première partie du théorème 9.4.

De plus, puisque $(\mathcal{H}, \leq) \text{ est spécial,}$

$$ x_{i_{\Lambda_p}} = \mathbf{L} \rho g_p \geq \mathbf{P} \rho g_p = x_{i_{\Lambda_{p-1}+1}} \quad (1 \le p \le s) \quad (9.3.3) $$

et pour $1 \le p < s$, puisqu'en posant $\rho g_p = f_p^{q_p}$ avec $f_p \in \mathcal{H}$, on a
$f_p \ge f_{p+1}$, alors

$$ x_{i_{\Lambda_p}} = \mathbf{L} \rho g_p \geq \mathbf{P} \rho g_{p+1} = x_{i_{\Lambda_{p+1}}} $$

D'où l'on a

$$ b(x_{i_{\Lambda_p}}, x_{i_{\Lambda_{p-1}+1}}) = 0 $$

et

$$ b(x_{i_{\Lambda_p}}, x_{i_{\Lambda_{p+1}}}) = 0. $$

Par suite, les deux quantités

$$ U \sigma f = b(x_{i_1}, x_{i_2}) + b(x_{i_2}, x_{i_3}) + \dots + b(x_{i_{n-1}}, x_{i_n}) $$

et

$$ V_{\tau_f}(\sigma) f = \sum_{p=1}^{s} \left( b(x_{i_{\Lambda_{p-1}+1}}, x_{i_{\Lambda_{p-1}+2}}) + \dots + b(x_{i_{\Lambda_{p-1}}}, x_{i_{\Lambda_p}}) + b(x_{i_{\Lambda_p}}, x_{i_{\Lambda_{p-1}+1}}) \right) $$

sont égales.

Lorsque $\mathcal{H} = \mathbb{R}$ et que $(\mathcal{H}, \leq) \text{ est la factorisation spéciale de Spitzer, on a en outre}$

$$ S \sigma f = \max_{1 \le k \le n} \left( \sum_{k'=1}^{k} x_{i_{k'}} \right)^{+} = \sum_{p=1}^{s} \left( x_{i_{\Lambda_{p-1}+1}} + x_{i_{\Lambda_{p-1}+2}} + \dots + x_{i_{\Lambda_p}} \right)^{+} = T \tau_f(\sigma) f, $$

puisque si $h = x_{v_1} x_{v_2} \dots x_{v_r}$ est un mot de $\mathcal{H}$, on a

fini
et le

orres
$\mathcal{H}$
$\leq$
$s$

mme
ions
$$ \frac{\sum_{k=1}^{r} x_{v_k}}{r} \ge \frac{\sum_{k=1}^{t} x_{v_k}}{t} \quad \text{pour } 1 \le t \le r $$

donc a fortiori $\sum_{k=1}^{r} x_{v_k} \ge \sum_{k=1}^{t} x_{v_k}$ pour $1 \le t \le r$.

Ceci achève la démonstration du théorème 9.4. Les deux théorèmes 9.2 et 9.3 s'en déduisent alors immédiatement.

Soit maintenant $X_1, X_2, \dots, X_n$ une suite de n variables aléatoires en dépendance symétrique. Soit $\tau$ une permutation de $\sigma_n$ donnée par le produit des cycles disjoints.

$$ \tau = (B_1) (B_2) \dots (B_s). $$

où

$$ (B_p) = (i_{\Lambda_{p-1}+1}, i_{\Lambda_{p-1}+2}, \dots, i_{\Lambda_p}). $$

Posons

$$ V\tau X = \sum_{\rho=1}^{s} (b(X_{i_{\Lambda_{p-1}+1}}, X_{i_{\Lambda_{p-1}+2}}) + \dots + b(X_{i_{\Lambda_{p-1}}}, X_{i_{\Lambda_p}}) + b(X_{i_{\Lambda_p}}, X_{i_{\Lambda_{p-1}+1}})). $$

Enfin, pour $\sigma: k \to \sigma_k \quad (1 \le k \le n)$, nous posons

$$ U\sigma X = \sum_{k=1}^{n-1} b(X_{\sigma_k}, X_{\sigma_{k+1}}). $$

Suivant la même méthode que Spitzer ([38] p. 329) il résulte de la dépendance symétrique des $X_k$ et du théorème 9.2, que pour toute fonction mesurable à variables complexes $h(x)$, on a

$$ Eh[U X] = \frac{1}{n!} \sum_{\sigma} Eh[U\sigma X] = \frac{1}{n!} \sum_{\tau} Eh[V\tau X]. \quad (9.3.5) $$

Supposons maintenant que les variables aléatoires $X_1, X_2, \dots, X_n$ sont indépendantes et équidistribuées, et posons pour $h(x) = \exp(i\lambda x)$ où $\mathbf{I}_m(\lambda) \ge 0$,

$$ \Phi_n(\lambda) = \begin{cases} 1 & \text{si } n=1 \\ E \exp\{i\lambda(b(X_1, X_2) + \dots + b(X_{n-1}, X_n))\} & \text{si } n>1 \end{cases} $$

et
$$ \psi_k(\lambda) = \begin{cases} 1 & \text{si } k=1 \\ E \exp \{i\lambda(b(X_1, X_2) + \dots + b(X_{k-1}, X_k) + b(X_k, X_1))\}. & \text{si } k \neq 1 \end{cases} $$

Si la permutation $\tau$ est le produit de $k_l$ cycles de longueur $l$ ($1 \le l \le n$; $k_1 + 2k_2 + \dots + nk_n = n$), alors

$$ \text{Eh } [V_{\tau} X] = \psi_1(\lambda)^{k_1} \psi_2(\lambda)^{k_2} \dots \psi_n(\lambda)^{k_n}. $$

Par suite, il résulte de (9.3.5)

$$ n! \Phi_n(\lambda) = \sum C(k_1, k_2, \dots, k_n) \psi_1(\lambda)^{k_1} \psi_2(\lambda)^{k_2} \dots \psi_n(\lambda)^{k_n} \quad (9.3.6) $$

où $C(k_1, k_2, \dots, k_n)$ est le nombre de permutations de $\sigma_n$ qui sont produits de $k_l$ cycles de longueur $l$ ($1 \le l \le n$).

Mais d'après Riordan ([33] p. 68), toute fonction génératrice de la forme

$$ C_n(t_1, t_2, \dots, t_n) = \sum C(k_1, k_2, \dots, k_n) t_1^{k_1} t_2^{k_2} \dots t_n^{k_n} $$

satisfait à la relation

$$ \sum_{n=0}^{\infty} C_n(t_1, t_2, \dots, t_n) \frac{u^n}{n!} = \exp \left[ \sum_{k=1}^{\infty} u^k \frac{t_k}{k} \right]. $$

Si maintenant $u$ est une variable réelle et les

$$ C_n(t_1, t_2, \dots, t_n) / n! $$

des quantités complexes bornées en module par une même valeur, alors la série $\sum_{n=0}^{\infty} C_n(t_1, t_2, \dots, t_n) \frac{u^n}{n!}$ converge pour tout $|u| < 1$.

En particulier, en posant

$$ C_n(t_1, t_2, \dots, t_n) = n! \Phi_n(\lambda) \quad n \ge 0 $$

et

$$ t_k = \psi_k(\lambda) \quad k \ge 1, $$

nous avons

$$ \left| \frac{n! \Phi_n(\lambda)}{n!} \right| < 1. $$
D'où l'identité

$$ \sum_{n=0}^{\infty} \Phi_n(\lambda) u^n = \exp \left[ \sum_{k=1}^{\infty} \frac{\psi_k(\lambda)}{k} u^k \right] $$

valable pour Im(λ) ≥ 0 et |u| < 1. C'est l'identité de Spitzer, pour un nouveau couple de fonctions caractéristiques. Résumons ces résultats dans un théorème,

THEOREME 9.5. - Soit $X_1, X_2, \dots, X_n, \dots$ une suite de variables aléatoires indépendantes et équidistribuées ; $X_1^*, X_2^*, \dots, X_n^*$ la statistique d'ordre de $X_1, X_2, \dots, X_n$ pour tout $n > 1$ et $b : \mathbb{R}^2 \to \mathbb{R}$ une fonction mesurable telle que $b(x, x') = 0$ pour $x \ge x'$, alors pour $n > 1$

$$ E \exp \left[ i \lambda \sum_{k=2}^{n} b(X_k, X_k^*) \right] = E \exp \left[ i \lambda \sum_{k=2}^{n} b(X_{k-1}, X_k) \right]. $$

Si $\Phi_n(\lambda)$ est la valeur commune de ces deux quantités

$$ (\Phi_0(\lambda) = \Phi_1(\lambda) = 1) $$

et $\psi_k(\lambda)$ la fonction caractéristique de la statistique

$$ b(X_1, X_2) + \dots + b(X_{k-1}, X_k) + b(X_k, X_1), $$

l'identité de Spitzer est satisfaite pour la famille

$$ \{\Phi_n(\lambda), \psi_k(\lambda)\} (n \ge 0, k > 1) $$

c'est-à-dire

$$ \sum_{n=0}^{\infty} \Phi_n(\lambda) u^n = \exp \left[ \sum_{k=1}^{\infty} \frac{\psi_k(\lambda)}{k} u^k \right] $$

$$ (|u| < 1 \quad \text{Im}(\lambda) \ge 0). $$

## 9.4. Quelques applications probabilistes des factorisations spéciales.

Donnons, pour finir, une interprétation probabiliste simple des formules de Witt (Cf. proposition 5.1).

Soit $x_1, x_2, \dots, x_q$ q nombres réels (q > 0) rationnelle-ment indépendants (c'est-à-dire que pour tous $r_1, r_2, \dots, r_q$ ra-tionnels $\sum_{i=1}^q r_i x_i = 0 \implies r_i = 0 (1 \le i \le q)$) et considérons une
variable aléatoire discrète X prenant les valeurs $x_1, x_2, \dots, x_q$ avec la probabilité $1/q$.

Soit alors $X_1, X_2, \dots, X_n$ une suite de n variables aléatoires indépendantes et ayant la même loi que X.

Posons

$$S_k = X_1 + \dots + X_k \quad (1 \le k \le n).$$

Nous avons

**PROPOSITION 9.1.- La probabilité que la ligne polygonale**

$$(0,0)(1,S_1)(1,S_2)\dots(n,S_n)$$

soit entièrement située au-dessous de la corde (0,0) (n, S_n) est donnée par

$$(1/n) \sum_{d|n} \mu(n/d)/q^{n-d}$$

ou encore

$$P_r \left[ \left\lfloor \frac{n-1}{k=1} S_k/k < S_n/n \right\rfloor \right] = \frac{1}{n} \sum_{d|n} \mu(n/d)/q^{n-d}$$

ou $\mu$ désigne la fonction de Möbius.

**PREUVE.-** Soit Q l'ensemble $\{x_1, x_2, \dots, x_q\}$ et Q_n l'ensemble des mots du monoïde libre $Q^*$ engendré par Q de longueur n. Dans la proposition 5.1, nous avons montré que pour toute factorisation de Schützenberger de type b, soit $(\mathcal{H}, \leq)$, le nombre des mots de longueur n et ne contenant que des lettres d'un sous-ensemble de cardinalité q était donné par la première formule de Witt de paramètres n et q.

Pour la factorisation spéciale de Spitzer (cf. § 7.5), les mots $t = x_{i_1} x_{i_2} \dots x_{i_n}$ de $\mathcal{H}$ ne contenant que des lettres de Q vérifient alors

$$\frac{x_{i_1}}{1}, \frac{x_{i_1} + x_{i_2}}{2}, \dots, \frac{x_{i_1} + x_{i_2} + \dots + x_{i_{n-1}}}{n-1} < \frac{x_{i_1} + x_{i_2} + \dots + x_{i_n}}{n}$$
(puisque les $x_k$ sont rationnellement indépendants) et sont les seuls
qui aient cette propriété.

D'où le résultat, d'après la formule de Witt et le fait que
l'ensemble des mots de Q de longueur n a pour cardinalité $q^n$.

Une interprétation analogue pourrait être donnée de la seconde
formule de Witt en termes de cheminement aléatoire dans le plan.
# 10. Applications combinatoires. Formule de Dixon

## 10.1. Introduction.

Nous utilisons maintenant les résultats du chapitre 4 pour démontrer ou redémontrer certaines identités combinatoires contenant des coefficients binomiaux. En fait, dans tous les cas étudiés, nous allons considérer deux sous-ensembles de mots d'un monoïde libre et établir entre eux une bijection qui conserve une certaine propriété. Pour obtenir les identités combinatoires, tout revient alors à compter les éléments de chacun des ensembles (finis !). Ces méthodes permettent ainsi de donner une interprétation aux coefficients binomiaux apparaissant dans ces formules : nous montrons explicitement quels sont les objets qui sont comptés.

Une première identité que nous étudierons est celle de Dixon [9]

$$ \sum_{k=0}^{2p} (-1)^k \left( \binom{2p}{k} \right)^3 = (-1)^p \frac{(3p)!}{(p!)^3} \quad (10.1.1.) $$

Il en existe de nombreuses démonstrations depuis celle de Richmond [32] jusqu'aux plus récentes : celles de Ljunggren [23], Staver [39] et Nanjundiah [29].

Mac Mahon ([27] p. 121) en donne une démonstration élégante en appliquant son "Master Theorem" (Voir aussi Hall [18] p.50).

Toutes ces démonstrations utilisent des techniques d'algèbre commutative (changement de variables dans les fonctions généra-trices, opérations élémentaires sur les coefficients binomiaux,...) et naturellement ne nous fournissent aucune indication sur l'exis-tence de bijections d'ensembles, nous permettant d'expliciter ce résultat.

Dans la prochaine section, nous établissons une correspondance biunivoque : ♡ → ♡' entre deux sous-ensembles ♡ et ♡' d'un
monoïde libre engendré par un ensemble $\mathcal{X}$ réduit à trois éléments ($\mathcal{X} = \{x_1, x_2, x_3\}$) (proposition 10.1). Prenant alors des mots abéliens h d'un certain type et considérant la bijection induite : $\alpha^{-1} h \cap \mathcal{V} \to \alpha^{-1} h \cap \mathcal{W}$, nous déduisons la formule de Dixon avec h défini par $hx_1 = hx_2 \neq hx_3 = 2p$ ($p > 0$) (section 10.3) ; puis avec h défini par $hx_1 = b+c$, $hx_2 = c+a$ et $hx_3 = a+b$ où $a, b$ et $c$ sont des entiers non négatifs, nous établissons la formule de Fjeldstad (section 10.4).

$$ \Sigma (-1)^k \binom{b+c}{c+k} \binom{c+a}{a+k} \binom{a+b}{b+k} = \frac{(a+b+c)!}{a! b! c!} \quad (10.4.2) $$

La façon d'établir ces identités est originale et la bijection $\mathcal{V} \to \mathcal{W}$, définie ci-dessous, leur donne une interprétation en terme de sous-ensembles de mots d'un monoïde libre.

## 10.2. Un résultat combinatoire.

Considérons un ensemble ordonné $\mathcal{X}$, réduit à trois éléments $x_1, x_2, x_3$ ($x_1 < x_2 < x_3$). Nous rappelons que pour tout couple $(x_t, x_u)$ ($t, u = 1, 2, 3$) et tout mot $f = x_{i_1}x_{i_2}\dots x_{i_r}$ de $\mathcal{X}^*$, $v_{x_t, x_u} f$ désigne le nombre d'indices $k$ tels que

$$ x_{i_k} = x_t \quad \text{et} \quad x_{j_k} = x_u \quad (x_{j_1} x_{j_2} \dots x_{j_r} = \beta f) $$

étant toujours le mot non décroissant de la classe abélienne de $f$.

Notons par $\mathcal{V}$ le sous-ensemble des mots $f \in \mathcal{X}^*$ tels que

$$ v_{x_u x_u} f = 0 \quad \text{pour tout} \quad u = 1, 2, 3 \quad (10.2.1) $$

et par $\mathcal{W}$ le sous-monoïde libre de $\mathcal{X}^*$ engendré par l'ensemble $\mathfrak{S}_1$ des mots

$$ x_1 x_2, x_1 x_3, x_2 x_3, x_1 x_2 x_3, x_1 x_3 x_2. \quad (10.2.2) $$

c'est-à-dire les cinq mots multilinéaires de $\mathcal{X}^*$ minimum dans leurs classes de conjugués (par rapport à l'ordre lexicographique) et non réduits à une seule lettre.

Soit $\theta : \mathcal{Y} \to \mathcal{X}^*$ une bijection.

Nous rappelons que nous avons défini dans le chapitre 4 une surjection $\rho : \mathcal{Y}^* \to \mathcal{X}^*$ (ses propriétés sont décrites dans la proposition 4.2) et que dans chaque classe $\rho^{-1}f$ ($f \in \mathcal{X}^*$), nous avons distingué un élément Cf dit élément canonique. Sa définition
(voir définition 4.1) dépend d'un sous-ensemble $\mathfrak{S}$ de $\mathcal{Y}^*$ et nous prendrons ici $\mathfrak{S} = \Theta^{-1} \mathfrak{S}_0$ où $\mathfrak{S}_0$ est le sous-ensemble de $\mathcal{X}^*$ des mots multilinéaires minimum dans leurs classes de conjugués, c'est-à-dire

$$ \mathfrak{S}_0 = \mathfrak{S}_1 \cup \{x_1, x_2, x_3\}. $$

Par commodité, nous poserons pour $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{X}^*$, $\Theta^{-1} f = [x_{i_1} x_{i_2} \dots x_{i_r}]$. Nous montrons d'abord

PROPOSITION 10.1. - $\Theta C : \mathfrak{V} \longrightarrow \mathfrak{VV}$ établit une application bijective telle que

$$ (i) \quad \alpha \Theta C_f = \alpha f \quad \text{et} $$

$$ (ii) \quad \text{pour tout couple } \{(x_t, x_u) : 1 \le t < u \le 3\} $$

$$ v_{x_t, x_u} = \xi_{x_t, x_u} \Theta C_f. \quad (10.2.3) $$

PREUVE. - (i) est satisfait d'après les propriétés de la fonction $C$ (proposition 4.4). Soit ensuite $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathfrak{V}$ et

$$ \beta f = x_{j_1} x_{j_2} \dots x_{j_r}. $$

D'après la proposition 4.2, si $g = y_{l_1} y_{l_2} \dots y_{l_s} \in \mathcal{Y}^*$ est un mot de $\rho^{-1} f$, aucun des mots $\Theta y_{l_p}$ ($1 \le p \le s$) n'est réduit à une seule lettre, car autrement il existerait un indice $k \in [1, r]$ pour lequel $x_{i_k} = x_{j_k}$ ; ce qui contredirait $f \in \mathfrak{V}$.

Réciproquement, si le mot $g = y_{l_1} y_{l_2} \dots y_{l_s} \in \mathcal{Y}^*$ est tel que tous les mots $\Theta y_{l_1}, \Theta y_{l_2}, \dots, \Theta y_{l_s}$ sont multilinéaires et non réduits à une seule lettre, alors il est une représentation en cycles (multilinéaires) d'un mot $f \in \mathfrak{V}$. Ainsi la restriction de $\rho$ à $\mathfrak{S}'$ où $\mathfrak{S}' = \Theta^{-1} \mathfrak{S}_1$ est une surjection de $\mathfrak{S}'$ sur $\mathfrak{V}$.

D'autre part, les mots de $\mathfrak{S}_1$ sont tous non disjoints deux à deux. Il résulte alors, toujours de la proposition 4.2, que la classe $\rho^{-1} f \cap \mathfrak{S}'$ est réduite à un seul élément. Comme l'élément canonique $C_f$ appartient à cette classe, d'après la définition 4.1, c'est donc que l'on a

$$ \rho^{-1} f \cap \mathfrak{S}'^* = \{C_f\} \quad f \in \mathfrak{V} \quad (10.2.4) $$

et puisqu'on a $\rho : \mathfrak{S}'^* \longrightarrow \mathfrak{V}$ est une surjection,
$$ C : \mathcal{V} \to \mathcal{S}'^* \quad \text{est bijectif.} \qquad (10.2.5) $$

Enfin, tout mot $f' \in \mathcal{V}$ a une et une seule factorisation $f_1 f_2 \dots f_s$ où $f_1, f_2, \dots, f_s \in \mathcal{S}_1$ ; ce qui revient encore à dire que $\theta^{-1} : \mathcal{S}'^* \to \mathcal{V}$ est bijectif. Comparant avec (10.2.5),

$$ \theta C : \mathcal{V} \to \mathcal{V} \qquad (10.2.6) $$

est alors une bijection.

Soit $f = x_{i_1} x_{i_2} \dots x_{i_r} \in \mathcal{V}$ et $\beta f = x_{j_1} x_{j_2} \dots x_{j_r}$ ; nous posons

$$ C_f = y_{l_1} y_{l_2} \dots y_{l_s} $$

avec

$$ \theta y_{l_p} = x_{v_{K_p-1}+1} x_{v_{K_p-1}+2} \dots x_{v_{K_p}} \quad (1 \le p \le s; K_o = 0). $$

Alors les indices $k$ pour lesquels le facteur $x_{v_k} x_{v_{k+1}}$ est égal à $x_1 x_2, x_1 x_3$, ou $x_2 x_3$ est nécessairement différent de $x_{K_p}$ pour tout $p \in [1, s]$, puisque les mots de $\mathcal{S}_1$ ont $x_2$ ou $x_3$ pour dernière lettre et $x_1$ ou $x_2$ comme première lettre. On a de même

$$ (x_{v_{K_p}}, x_{v_{K_p-1}+1}) \neq (x_1, x_2), (x_1, x_3) \quad \text{et} \quad (x_2, x_3) $$

$$ \text{pour tout } p \in [1, s]. $$

Il résulte alors de la proposition 4.2 qu'à tout $k \in [1, r]$ tel que $x_{i_k} = x_t < x_u = x_{j_k}$ correspond biunivoquement un indice $k' \in [1, r]$ tel que

$$ x_{v_{k'}-1} = x_t < x_u = x_{v_k}, \quad \text{pour } 1 \le u < t \le 3; $$

d'où la relation (10.2.3).

Illustrons cette proposition 10.1 par un exemple.

**EXEMPLE.** - Soit $f = x_2 x_3 x_3 x_2 x_1 x_3 x_1 x_3 x_2 x_2 x_1 x_1$ un mot de $\mathcal{X}^*$. Le mot non décroissant $\beta f$ s'écrit $\beta f = x_1^4 x_2^4 x_3^4$. Pour déterminer le mot canonique $C_f$, nous cherchons d'abord une représentation en cycles $g$ du mot $f$, selon la méthode du chapitre 4. Soit

$$ g = [x_1 x_2] [x_2 x_3 x_1 x_2 x_3 x_1 x_3 x_2 x_1 x_3]. $$
En appliquant à ce mot l'opérateur $\delta_2^3$ (voir lemme 4.3) nous obtenons une représentation en cycles multilinéaires du mot $f[x_1 x_2][x_2 x_3][x_1 x_2 x_3][x_1 x_3][x_2 x_1 x_3]$.

En prenant à l'intérieur de chaque crochet le mot minimum dans sa classe de conjugués, nous avons le mot canonique

$$ \mathrm{Cf} = [x_1 \ x_2] [x_2 \ x_3] [x_1 \ x_2 \ x_3] [x_1 \ x_3] [x_1 \ x_3 \ x_2] $$

$$ \text{Par suite, } \theta \mathrm{Cf} = x_1 x_2 x_2 x_3 x_1 x_2 x_3 x_1 x_3 x_1 x_3 x_2. $$

Nous pouvons remarquer aussi que

$$ v_{x_1, x_2} f = 2 = \xi_{x_1, x_2} \theta \mathrm{Cf} $$

$$ v_{x_1, x_3} f = 2 = \xi_{x_1, x_3} \theta \mathrm{Cf} $$

$$ v_{x_2, x_3} f = 2 = \xi_{x_2, x_3} \theta \mathrm{Cf}. $$

Posons pour $f \in \mathcal{X}^*$

$$ \nu f = v_{x_1, x_2} f + v_{x_1, x_3} f + v_{x_2, x_3} f \quad \text{et} \quad (10.2.7) $$

$$ \xi f = \xi_{x_1, x_2} f + \xi_{x_1, x_3} f + \xi_{x_2, x_3} f. $$

Si $z$ est une variable réelle ou complexe, nous avons alors pour tout $h \in \mathcal{X}^*$

$$ \sum_{z \in \mathcal{X}^*} \{z^{\alpha} : f \in \alpha^{-1} h \cap \mathcal{V}\} = \sum_{z \in \mathcal{X}^*} \{z^{\alpha} : f \in \alpha^{-1} h \cap \mathcal{V}\} \quad (10.2.8) $$

Les deux membres de cette équation étant pour tout $h \in \bar{\mathcal{X}}^*$ des polynomes en $z$.

C'est cette relation (10.2.8) qui va nous fournir les identités combinatoires. Tout va revenir, pour des h particuliers, à compter combien de mots $f$ de la classe $\alpha^{-1} h \cap \mathcal{V}$ (resp. $\alpha^{-1} h \cap \mathcal{V}\mathcal{V}$) vérifient $\nu f = k$ (resp. $\xi f = k$) où $k$ est un certain entier.

Ecrivons d'abord quelques relations simples satisfaites pour des mots $f \in \mathcal{V}$ et $f \in \mathcal{V}\mathcal{V}$. Soit $h$ un élément de $\mathcal{X}^*$ défini par

$$ h x_1 = p_1, \quad h x_2 = p_2, \quad h x_3 = p_3. $$

Par définition des fonctions $v_{x_t, x_u}$ nous avons pour $f \in \alpha^{-1} h \cap \mathcal{V}$,
$$ 
\begin{aligned}
\nu_{x_1, x_2} f + \nu_{x_1, x_3} f &= p_1 = \nu_{x_2, x_1} f + \nu_{x_3, x_1} f \\
\nu_{x_2, x_3} f + \nu_{x_2, x_1} f &= p_2 = \nu_{x_1, x_2} f + \nu_{x_3, x_2} f \quad (10.2.9) \\
\nu_{x_3, x_1} f + \nu_{x_3, x_2} f &= p_3 = \nu_{x_1, x_3} f + \nu_{x_2, x_3} f
\end{aligned}
$$

D'autre part, comme tout mot $f \in \mathcal{W}$ a une et une seule factorisation $f_1, f_2, \dots, f_s \text{ où } f_1, f_2, \dots, f_s \in \mathfrak{S}_1$, nous pouvons poser, pour tout $x_{u_1}, \dots, x_{u_r} \in \mathfrak{S}_1$

$$ n_{u_1} \dots u_r \text{ f = nombre d'indices q tels que } f_q = x_{u_1} \dots x_{u_r} \\ (1 \le q \le s). $$

Si $f$ est élément de $\mathcal{W} \cap \alpha^{-1} h$, nous avons alors

$$ 
\begin{aligned}
n_{123} f + n_{132} f + n_{12} f + n_{13} f &= p_1 \\
n_{123} f + n_{132} f + n_{12} f + n_{23} f &= p_2 \quad (10.2.10) \\
n_{123} f + n_{132} f + n_{13} f + n_{23} f &= p_2
\end{aligned}
$$

et

$$ \xi f = n_{12} f + n_{13} f + n_{23} f + n_{132} f + 2 \cdot n_{123} f \quad (10.2.11) $$

Nous allons maintenant utiliser ces relations.

### 10.3. L'identite de Dixon.

Posons $p_1 = p_2 = p_3 = 2p$ où $p$ est un entier $> 0$. Nous posons des relations (10.2.9), en posant $\nu_{x_1, x_2} f = k$

$$ 
\begin{aligned}
\nu_{x_3, x_1} f &= \nu_{x_1, x_2} f = \nu_{x_2, x_3} f = k \\
\nu_{x_1, x_3} f &= \nu_{x_2, x_1} f = \nu_{x_3, x_2} f = 2p - k \\
(0 \le k \le 2p) &
\end{aligned}
\quad (10.2.11) $$

et

Par suite, le nombre $\nu f$ est égal à

$$ \nu f = \nu_{x_1, x_2} f + \nu_{x_1, x_3} f + \nu_{x_2, x_3} f = 2p + k $$

Le nombre de mots $f$ de $\mathcal{W} \cap \alpha^{-1} h$ tels que $\nu f = 2p + k$ ($0 \le k \le 2p$) est alors égal à
$$ \binom{2p}{k}^3 $$

puisque ces mots $f$ doivent avoir exactement $k$ fois la lettre $x_2$ dans les $2p$ premières positions, $k$ fois la lettre $x_3$ dans les $2p$ suivantes et $k$ fois la lettre $x_1$ dans les $2p$ dernières, d'après les relations (10.3.1).

Nous pouvons ainsi écrire

$$ \sum_{\{z^{\nu f} : f \in \alpha^{-1} h \cap \mathfrak{W}\}} z^{2p} \sum_{k=0}^{2p} \binom{2p}{k}^3 z^k \quad (10.3.2) $$

D'autre part, si $f$ est un élément de $\alpha^{-1} h \cap \mathfrak{W}$ nous ti-
rons des relations (10.2.10) en posant $n_{12} f = n$,

$$ n_{12} f = n_{13} f = n_{23} f = n \quad (10.3.3) $$

et

$$ n_{123} f + n_{123} f = 2(p-n) $$

$$ (0 \le n \le p). $$

En posant $n_{132} f = k$, la relation (10.2.11) nous donne alors

$$ \xi f = 4p - n - k \quad (0 \le n \le p; 0 \le k \le 2(p-n)). \quad (10.3.4) $$

Un mot $f \in \mathfrak{W} \cap \alpha^{-1} h$ tel que $n_{12} f = n$ a exactement $3n+2(p-n)=2p+n$ mots de $\mathfrak{S}_1$ dans sa factorisation (en mots de $\mathfrak{S}_1$), dont $n$ égaux respectivement à $x_1 x_2$, $x_1 x_3$ et $x_2 x_3$. Le nombre de mots $f \in \mathfrak{W} \cap \alpha^{-1} h$ tels que $n_{12} f = n$ et $n_{132} f = k$ est alors égal à

$$ \frac{(2p+n)!}{(n!)^3 k! (2p-2n-k)!} $$

Par suite, utilisant (10.3.4), nous avons

$$ \sum_{\{z^{\xi f} : f \in \alpha^{-1} h \cap \mathfrak{W}\}} = \sum_{n=0}^{p} \sum_{k=0}^{2(p-n)} \frac{(2p+n)!}{(n!)^3 k! (2p-2n-k)!} z^{4p-n-k} \quad (10.3.5) $$

qui peut encore s'écrire

$$ \sum_{\{z^{\xi f} : f \in \alpha^{-1} h \cap \mathfrak{W}\}} = z^{2p} \sum_{n=0}^{p} \frac{(2p+n)!}{(n!)^3 (2p-2n)!} z^n (z+1)^{2(p-n)} \quad (10.3.6) $$
D'où en comparant avec (10.3.2), la relation

$$ \sum_{k=0}^{2p} \left( \binom{2p}{k} \right)^3 z^k = \sum_{n=0}^{p} \frac{(2p+n)!}{(n!)^3 (2p-2n)!} z^n (z+1)^{2(p-n)} \quad (10.3.7) $$

Pour $z = 1$, nous avons la relation déjà donnée par Mac Mahon ([27] p. 122)

$$ \sum_{k=0}^{2p} \left( \binom{2p}{k} \right)^3 = \sum_{n=0}^{p} \frac{(2p+n)!}{(n!)^3 (2p-2n)!} 2^{2(p-n)} $$

et pour $z = -1$, la formule de Dixon

$$ \sum_{k=0}^{2p} \left( \binom{2p}{k} \right)^3 (-1)^k = (-1)^p \frac{(3p)!}{(p!)^3} $$

## 10.4. L'identité de Fjeldstad.

Good [17] démontre en utilisant le "Master Theorem" de Mac Mahon une identité introduite par Fjeldstad [11] soit

$$ \sum_k (-1)^k \binom{b+c}{c+k} \binom{c+a}{a+k} \binom{a+b}{b+k} = \frac{(a+b+c)!}{a! b! c!} \quad (10.4.1) $$

où $a, b$ et $c$ sont des entiers non négatifs et où la somme est étendue à tous les $k$ pour lesquels le produit des trois coefficients binomiaux est différent de 0.

Soit donc $h \in \overline{\mathcal{X}}^*$ défini par $hx_1 = b+c$, $hx_2 = c+a$ et $hx_3 = a+b$. La bijection $\theta_C$ envoie tous les mots de $\alpha^{-1} h \cap \mathfrak{h}$ sur les mots de $\alpha^{-1} h \cap \mathfrak{h}^*$, La relation (10.2.8) pour un tel $h$ va nous donner de nouveau une démonstration explicite de l'identité (10.4.1).

Soit $f \in \alpha^{-1} h \cap \mathfrak{h}$. Posons

$$ v_{x_1, x_2} f = c + k $$

où $k$ est un entier ; les relations (10.2.9) entraînent alors

$$ k \ge \max \{-a, -b, -c\} $$

et

$$ v_{x_2, x_3} f = a + k \quad \text{et} \quad v_{x_3, x_1} f = b + k. $$
Ainsi le nombre de mots $f$ de $\alpha^{-1}h \cap \mathfrak{V}$ tels que

$$v_{x_1, x_2} f = c + k$$

est donné par

$$\binom{b+c}{c+k} \binom{c+a}{a+k} \binom{a+b}{b+k}$$

D'autre part si $v_{x_1, x_2} f = c + k$, alors

$$v f = b + c + v_{x_2, x_3} f = a + b + c + k.$$

Ainsi

$$\sum_{z \in \mathfrak{V}^f : f \in \alpha^{-1}h \cap \mathfrak{V}} = \sum_k \binom{b+c}{c+k} \binom{c+a}{a+k} \binom{a+b}{b+k} z^{a+b+c+k}.$$

D'autre part, d'après les relations (10.2.10) nous avons, en posant $n_{12} f = c - n$,

$$n_{23} f = a - n, \quad n_{13} f = b - n$$

$$n_{123} f + n_{132} f = 2n \quad \text{et} \quad 0 \le n \le \min\{a, b, c\}.$$

D'où, d'après (10.2.11), l'expression de $\xi f$ pour un mot

$$f \in \alpha^{-1}h \cap \mathfrak{V},$$

tel que $n_{12} f = c - n$ et $n_{132} f = k$, à savoir

$$\xi f = a + b + c + n - k \quad (0 \le k \le 2n).$$

Un mot $f \in \mathfrak{V} \cap \alpha^{-1}h$ tel que $n_{12} f = c - n$ a exactement $a+b+c+3n-2n=a+b+c+n$ mots de $\mathfrak{S}_1$ dans sa factorisation (en mots de $\mathfrak{S}_1$). Le nombre de mots $f \in \mathfrak{V} \cap \alpha^{-1}h$ tels que $n_{12} f = n + c$ et $n_{132} f = k$ est alors

$$\frac{(a+b+c+n)!}{(a-n)!(b-n)!(c-n)!k!(2n-k)!}$$

De là

$$\sum_{z \in \mathfrak{V}^f : f \in \alpha^{-1}h \cap \mathfrak{V}} = \sum_n \frac{(a+b+c+n)!}{(a-n)!(b-n)!(c-n)!(2n)!} z^{a+b+c-n} (z+1)^{2n}.$$

D'où la relation
$$
\begin{align*}
& \sum_k \binom{b+c}{c+k} \binom{c+a}{a+b} \binom{a+b}{b+k} z^{a+b+c+k} = \\
&= \sum_{n \ge 0} \frac{(a+b+c-n)!}{(a-n)!(b-n)!(c-n)!(2n)!} z^{a+b+c-n} (z+1)^{2n} \quad (10.4.2)
\end{align*}
$$

où $-\min\{a, b, c\} \le k \le \min\{a, b, c\}$ et $0 \le n \le \min\{a, b, c\}$.

Pour $z = -1$, on retrouve l'identité (10.4.1) de Fjeldstad, car le seul terme de la somme en $n$ qui ne disparaît pas est celui qui correspond à $n = 0$.

Pour $z = 1$, nous obtenons

$$
\sum_k \binom{b+c}{c+k} \binom{c+a}{a+k} \binom{a+b}{b+k} = \sum_{n \ge 0} \frac{(a+b+c-n)!}{(a-n)!(b-n)!(c-n)!(2n)!} 2^{2n} \quad (10.4.3)
$$

D'autres identités pourraient être déduites de la proposition 10.1. En particulier, pour un certain $h$ on peut écrire

$$
\sum \{ \nu f : f \in \alpha^{-1} h \cap \nu \} = \sum \{ \xi f : f \in \alpha^{-1} h \cap \xi \}
$$

ou encore

$$
\sum_{k \ge 0} \text{card} (\nu^{-1} k \cap \alpha^{-1} h \cap \nu) = \sum_{k \ge 0} \text{card} (\xi^{-1} k \cap \alpha^{-1} h \cap \xi)
$$

et en déduire d'autres identités.

Signalons pour terminer que de Bruijn ([6] p. 72) donne la forme
asymptotique de l'expression

$$
S(s, n) = \sum_{k=0}^{2n} (-1)^{k+n} \left(\binom{2n}{k}\right)^s .
$$

Celle-ci contient un facteur de la forme $(\cos \pi/2s)^{2ns}$ ; cette
quantité n'étant rationnelle que si $s=2$ ou $3$ ($s=3$ formule de
Dixon) et pour $s > 3$ n'apparaissant pas dans la formule de Stirling,
il remarque qu'il n'existe pas de généralisation simple de la for-
mule de Dixon pour $s > 3$, hypothèse qui est d'ailleurs confirmée
lorsqu'on veut appliquer les méthodes de ce chapitre pour un en-
semble $\mathcal{X}$ de cardinalité $> 3$.
Liste des principaux symboles utilisés

<table><thead><tr><th></th><th></th><th>§</th><th>n°</th></tr></thead><tbody><tr><td>x</td><td>étant un ensemble non vide, on désigne par</td><td></td><td></td></tr><tr><td>x*</td><td>le monoïde engendré par x</td><td>2</td><td>1</td></tr><tr><td>f = x<sub>i<sub>1</sub></sub> x<sub>i<sub>2</sub></sub> ... x<sub>i<sub>r</sub></sub></td><td>un élément ou mot de x*</td><td>2</td><td>1</td></tr><tr><td>λf</td><td>la longueur du mot f ∈ x*</td><td>2</td><td>1</td></tr><tr><td>1</td><td>le mot vide de x* (élément unité)</td><td>2</td><td>1</td></tr><tr><td>x**</td><td>x** = x* - {1}</td><td>2</td><td>1</td></tr><tr><td>x<sub>n</sub>*</td><td>le sous-ensemble des mots de x* de longueur n (n ≥ 0)</td><td>2</td><td>1</td></tr><tr><td>P et L</td><td>les applications de x** dans x qui au mot f = x<sub>i<sub>1</sub></sub> x<sub>i<sub>2</sub></sub> ... x<sub>i<sub>r</sub></sub> ∈ x** font correspondre ses première et dernière lettres, resp. (Pf = x<sub>i<sub>1</sub></sub> ; Lf = x<sub>i<sub>r</sub></sub>)</td><td>2</td><td>1</td></tr><tr><td>x*</td><td>le monoïde abélien libre engendré par x</td><td>2</td><td>2</td></tr><tr><td>α</td><td>l'homomorphisme canonique de x* sur x*</td><td>2</td><td>2</td></tr><tr><td>x**</td><td>x** = αx**</td><td>2</td><td>2</td></tr><tr><td>x&#773;</td><td>sous-ensemble des mots multilinéaires de x**</td><td>2</td><td>2</td></tr><tr><td>x&#773;</td><td>x&#773; = α<sup>-1</sup> x&#773;</td><td>2</td><td>2</td></tr><tr><td>x</td><td>étant un ensemble totalement ordonné, on désigne par</td><td></td><td></td></tr><tr><td>β'h</td><td>le mot non décroissant de la classe abélienne α<sup>-1</sup>h (h ∈ x**)</td><td>2</td><td>3</td></tr><tr><td>β</td><td>β = β'α</td><td>2</td><td>3</td></tr><tr><td>γ<sub>k</sub> (k > 0)</td><td>l'application γ<sub>k</sub>: x* → N telle que γ<sub>k</sub>f est 0 si λf < k et est égal au nombre de lettres égales à x<sub>i<sub>k</sub></sub> dans le facteur initial x<sub>i<sub>1</sub></sub> x<sub>i<sub>2</sub></sub> ... x<sub>i<sub>k</sub></sub></td><td>2</td><td>3</td></tr></tbody></table>
<table>
  <tbody>
    <tr>
      <td>α</td>
      <td>étant un ensemble quelconque et Ω un anneau commutatif (unitaire), on désigne par</td>
      <td>§ n°</td>
    </tr>
    <tr>
      <td>α = Ω[[X*]] l'algèbre large du monoïde X* relative à Ω</td>
      <td>2 4</td>
    </tr>
    <tr>
      <td>ᾱ = Ω[[X̄*]] l'algèbre large du monoïde abélien libre X̄* relative à Ω</td>
      <td>2 4</td>
    </tr>
    <tr>
      <td>Σ{faf : f ∈ X*} une série formelle de α</td>
      <td>2 4</td>
    </tr>
    <tr>
      <td>X₁, X₂, ..., Xₙ les n indéterminés de X̄* si X est fini = {x₁, x₂, ..., xₙ} (n > 0)</td>
      <td>2 4</td>
    </tr>
    <tr>
      <td>o l'ordre d'une série formelle</td>
      <td>2 4</td>
    </tr>
    <tr>
      <td>X</td>
      <td>étant un ensemble totalement ordonné, on désigne par</td>
      <td></td>
    </tr>
    <tr>
      <td>Γ une opération associative définie sur X*</td>
      <td>3 2</td>
    </tr>
    <tr>
      <td>X*<sub>Γ</sub> le monoïde d'intercalement (X*, Γ)</td>
      <td>3 2</td>
    </tr>
    <tr>
      <td>ζ : ℳ → {+1, -1}</td>
      <td>3 3</td>
    </tr>
    <tr>
      <td>b : X² → Ω</td>
      <td>3 3</td>
    </tr>
    <tr>
      <td>ν : X* → Ω</td>
      <td>3 3</td>
    </tr>
    <tr>
      <td>Ω[[X*<sub>Γ</sub>]] l'algèbre large du monoïde d'intercalement, relative à Ω</td>
      <td>3 3</td>
    </tr>
    <tr>
      <td>ν̄ : X̄* → Ω</td>
      <td>3 4</td>
    </tr>
    <tr>
      <td>μ̄ : X̄* → Ω</td>
      <td>3 4</td>
    </tr>
    <tr>
      <td>X</td>
      <td>étant un ensemble quelconque (≠ Ø), on désigne par</td>
      <td></td>
    </tr>
    <tr>
      <td>θ : Y → X*, une bijection</td>
      <td>4 2</td>
    </tr>
    <tr>
      <td>et on définit pour h ∈ X*<sup>++</sup>,</td>
      <td></td>
    </tr>
    <tr>
      <td>dim h, E(h), N(h), G(h)</td>
      <td>4 2</td>
    </tr>
    <tr>
      <td>e : G(h) → E(h)</td>
      <td>4 2</td>
    </tr>
    <tr>
      <td>δ : Y* → Y*</td>
      <td>4 3</td>
    </tr>
    <tr>
      <td>δ et δ̄</td>
      <td>4 3</td>
    </tr>
    <tr>
      <td>τ'' : ℳ → ℳ</td>
      <td>4 4</td>
    </tr>
    <tr>
      <td>τ' : θ⁻¹ τ'' θ</td>
      <td>4 4</td>
    </tr>
    <tr>
      <td>τ'<sub>p</sub> et τ<sub>p</sub> (p ≥ 1) des opérateurs de θ⁻¹ ℳ dans lui-même</td>
      <td>4 4</td>
    </tr>
    <tr>
      <td>T un monoïde d'opérateurs de θ⁻¹ ℳ dans lui-même</td>
      <td>4 4</td>
    </tr>
  </tbody>
</table>
Pour les notations qui suivent, $\mathcal{X}$ est un ensemble totalement ordonné et l'on utilise les symboles :

<table><thead><tr><th></th><th></th><th>§</th><th>n°</th></tr></thead><tbody><tr><td>π</td><td>π : α<sup>-1</sup> h —→ E(h), une bijection</td><td>4</td><td>5</td></tr><tr><td>ρ</td><td>ρ = π<sup>-1</sup> e : G(h) —→ α<sup>-1</sup> h</td><td>4</td><td>5</td></tr><tr><td>U<sub>f</sub></td><td>U<sub>f</sub> = ρ<sup>-1</sup> ∩ (θ<sup>-1</sup>π<sub>\</sub>)<sup>*</sup> (f ∈ <sub>\</sub>)<sup>*</sup></td><td>4</td><td>5</td></tr><tr><td>δ<sub>o</sub></td><td>un sous-ensemble totalement ordonné de π<sub>\</sub></td><td>4</td><td>5</td></tr><tr><td>δ</td><td>δ = θ<sup>-1</sup> δ<sub>o</sub></td><td>4</td><td>5</td></tr><tr><td>c</td><td>ensemble des mots canoniques de y<sup>*</sup></td><td>4</td><td>5</td></tr><tr><td>o</td><td>une opération associative définie sur c</td><td>4</td><td>5</td></tr><tr><td>C</td><td>C : X<sub>\</sub><sup>*</sup> —→ c (isomorphisme)</td><td>4</td><td>5</td></tr><tr><td>η</td><td>η : c —→ {+1, -1}</td><td>4</td><td>6</td></tr><tr><td>c</td><td>c = Cπ<sub>\</sub> ⊂ c</td><td>4</td><td>6</td></tr><tr><td>{Y<sub>j</sub> : j ∈ J}</td><td>une famille de sous-ensembles de X<sup>**</sup> où J est totalement ordonné</td><td>5</td><td>2</td></tr><tr><td>{π, ζ}</td><td>un sous-ensemble totalement ordonné de X<sup>**</sup></td><td>5</td><td>2</td></tr><tr><td>K<sub>o</sub></td><td>K<sub>o</sub> ⊂ K</td><td>5</td><td>3</td></tr><tr><td>K</td><td>K = θ<sup>-1</sup>K<sub>o</sub></td><td>6</td><td>1</td></tr><tr><td>δ'</td><td>δ' : y × θ<sup>-1</sup>π —→ y<sup>*</sup></td><td>6</td><td>2</td></tr><tr><td>(δ<sub>p</sub>) (p > 0)</td><td>famille d'opérateurs de y<sup>*</sup> dans lui-même</td><td>6</td><td>2</td></tr><tr><td>Δ'</td><td>Monoïde d'opérateurs engendré par les δ'<sub>p</sub></td><td>6</td><td>2</td></tr><tr><td>K<sub>1</sub></td><td>K<sub>1</sub> ⊂ y<sup>*</sup></td><td>6</td><td>2</td></tr><tr><td>ψ</td><td>ψ : X<sup>*</sup> —→ K<sub>1</sub> (bijection)</td><td>6</td><td>2</td></tr><tr><td>χ</td><td>χ : c —→ K<sub>1</sub> (bijection)</td><td>6</td><td>2</td></tr><tr><td>Φ</td><td>Φ = ψ<sup>-1</sup>χ C permutation de x<sup>*</sup></td><td>6</td><td>2</td></tr><tr><td>ν et ξ</td><td>des applications de x<sup>*</sup> dans N</td><td>6</td><td>3</td></tr><tr><td>ν<sub>,x'</sub>, et ξ<sub>,x'</sub>, (x, x' ∈ X<sup>2</sup>)</td><td>des applications de x<sup>*</sup> dans N</td><td>6</td><td>3</td></tr><tr><td>D = D(x)</td><td>le système algèbrique à une seule opération bi-naire sur X, notée []</td><td>7</td><td>1</td></tr><tr><td>δ*</td><td>δ* : D* —→ X<sup>*</sup> (décomposition)</td><td>7</td><td>1</td></tr><tr><td>σ</td><td>σ : D —→ J (J totalement ordonné)</td><td>7</td><td>2</td></tr><tr><td>H, H<sub>0</sub>, H<sub>1</sub></td><td>des ensembles tels que X ⊂ H ⊂ H<sub>0</sub> ⊂ H<sub>1</sub> ⊂ D<sup>*</sup></td><td>7</td><td>2</td></tr></tbody></table>
<table><thead><tr><th></th><th></th><th>§</th><th>n°</th></tr></thead><tbody><tr><td>θ</td><td>θ : X* → J (surjection) -utilisée seulement dans le chapitre 7</td><td>7</td><td>2</td></tr><tr><td>β</td><td>β ⊂ X*</td><td>7</td><td>2</td></tr><tr><td>β</td><td>β ensemble des mots primitifs de X*</td><td>7</td><td>2</td></tr><tr><td>μ<sub>x,x'</sub> ((x, x') ∈ X<sup>2</sup>)</td><td>famile d'applications de X* dans N</td><td>8</td><td>2</td></tr><tr><td>φ</td><td>une permutation de X*</td><td>8</td><td>3</td></tr><tr><td>ε<sub>p,l</sub> et c<sub>p,l</sub></td><td></td><td>8</td><td>3</td></tr><tr><td>X<sub>1</sub>, X<sub>2</sub>,..., X<sub>n</sub></td><td>une suite de variables aléatoires</td><td>9</td><td>1</td></tr><tr><td>X<sub>1</sub><sup>*</sup>, X<sub>2</sub><sup>*</sup>,..., X<sub>n</sub><sup>*</sup></td><td>la statistique d'ordre de la suite X<sub>1</sub>, X<sub>2</sub>,...,X<sub>n</sub></td><td>9</td><td>1</td></tr><tr><td>U, V</td><td>des applications de X<sub>n</sub><sup>*</sup> dans Ω</td><td>9</td><td>3</td></tr><tr><td>S, T</td><td>des applications de X<sub>n</sub><sup>*</sup> dans R, lorsque X=R</td><td>9</td><td>3</td></tr><tr><td>(τ<sub>f</sub>)<sub>f∈X<sub>n</sub><sup>*</sup></sub></td><td>famille de bijections de σ<sub>n</sub> sur σ<sub>n</sub></td><td>9</td><td>3</td></tr><tr><td>Y</td><td>Y = X × N (notation seulement utilisée dans le chapitre 9)</td><td>9</td><td>3</td></tr><tr><td>υ et ϖ</td><td>υ et ϖ des sous-ensembles de X*</td><td>10</td><td>2</td></tr></tbody></table>
Références

[1] ANDERSEN (E. Sparre). - The equivalence principle in the theory of fluctuations of sums of random variables, *Colloquium on Combinatorial Methods in Probability Theory*, [Août 1-10, 1962]. Aarhus Universitet Matematisk Institut, 13-16.

[2] ATKINSON (F.V.). - Some aspects of Baxter's functional equation, *J. Math. Anal. Appl.*, **7** (1963), 1-30.

[3] BARTON (D.E.) & MALLOWS (C. L.). - The randomization bases of the problem of the amalgamation of weighted means, *J. Roy. Statist. Soc. Ser. B*, **23** (1961), 423-433.

[4] BAXTER (G.). - An analytic approach to finite fluctuation problems in probability, *J. Analyse Math.*, **9** (1961), 31-70.

[5] BAXTER (G.). - An analytic problem whose solution follows from a simple algebraic identity, *Pacific J. Math.*, **10** (1960), 731-742.

[6] de BRUIJN (N.G.). - *Asymptotic Methods in Analysis*. North-Holland Publ. Co., Amsterdam (1958).

[7] BRUNK (H.D.). - A generalization of Spitzer's Combinatorial Lemma, *Z. Wahrscheinlichkeitstheorie*, **2** (1964), 395-405.

[8] CHEN (K.T.), FOX (R.H.) & LYNDON (R.C.). - Free differential calculus IV. The quotient groups of the lower central series, *Ann. of Math.*, **68** (1958), 81-95.

[9] DIXON (A.C.). - On the sum of the cubes of the coefficients in a certain expansion by the binomial theorem, *Messenger of Math.*, **20** (1890), 79-80.

[10] EASTMAN (W.L.). - On the construction of comma-free codes. Research Report SRRC-RR-64-27, Sperry Rand Research Center, Sudbury, Mass. (1964).

[11] FJELDSTAD (J.E.). - A generalization of Dixon's formula, *Math. Scand.*, **2** (1954), 46-48.
[12] FOATA (D.). - Un théorème combinatoire non commutatif, C.R. Acad. Sc. Paris, 258 (1964), 5128-5130.

[13] FOATA (D.). - Sur un énoncé de Mac Mahon, C.R. Acad. Sc. Paris, 258 (1964), 1672-1675.

[14] FOSTER (F. G.) & STUART (A.). - Distribution free test in time series based on the breaking of records, J. Roy. Statist. Soc. Ser. B, 16 (1954), 1-13.

[15] GOOD (I. J.). - A short proof of Mac Mahon's "Master Theorem", Proc. Cambridge Philos. Soc., 58 (1962), 160.

[16] GOOD (I. J.). - Generalizations to several variables of Lagrange's expansion with applications to stochastic processes, Proc. Cambridge Philos. Soc., 56 (1960), 367-380.

[17] GOOD (I. J.). - Proofs of some "binomial" identities by means of Mac Mahon's "Master Theorem", Proc. Cambridge Philos. Soc., 58 (1962), 161-162.

[18] HALL (Marshall Jr.). - A survey of Combinatorial Analysis, Survey in Applied Mathematics, IV. John Wiley, New York (1958), 35-104.

[19] HALL (Marshall Jr.). - The theory of Groups. Mac Millan, New York (1959), chapitre 11.

[20] HARDY (G.H.), LITTLEWOOD (J.E.) & PÓLYA (G.). - Inequalities. Cambridge University Press, Cambridge (1959).

[21] KINGMAN (J. F. C.). - Spitzer's identity and its use in probability theory, J. London Math. Soc., 37 (1962), 309-316.

[22] KUROŠ (A. G.). - Neassociativnye svobodnye algebry i svobonye proizvedenija algebr (Algèbres non associatives libres et produits libres d'algèbres), Mat. Sbornik, 20 (62) (1947), 239-262.

[23] LJUNGGREN (W.). - Et elementaert bevis for en formel av A.C. Dixon, Nordisk Mat. Tidsskr., 29 (1947), 35-38.

[24] LUCAS (E.). - Théorie des nombres. Gauthier-Villars, Paris (1891).

[25] LYNDON (R.C.). - On Burnside's problem, I, Trans. Amer. Math. Soc., 77 (1954), 202-215.

[26] LYNDON (R.C.) & SCHÜTZENBERGER (M.P.). - The equation $a^m = b^n$ $c^p$ in a free group, Michigan Math. J., 9 (1962), 289-298.

[27] MAC MAHON (P.A.). - Combinatory Analysis, 1. Cambridge University Press (1915).

[28] MEIER-WUNDERLI (H.). - Note on a basis of P. Hall for the higher commutators in free groups, Comment. Math. Helvetici, 26 (1952), 1-5.
[29] NANJUNDIAH (T.S.). - On a formula of A.C. Dixon, *Proc. Amer. Math. Soc.*, **9** (1958), 308-311.

[30] POLLACZEK (F.). - Fonctions caractéristiques de certaines répartitions définies au moyen de la notion d'ordre. Application à la théorie des attentes, *C.R. Acad. Sc. Paris*, **234** (1952), 2334-2336.

[31] RÉNYI (A.). - Théorie des éléments saillants d'une suite d'observations, *Colloquium on Combinatorial Methods in Probability Theory*, [Août 1-10, 1962]. Aarhus Universitet Matematisk Institut, 104-115.

[32] RICHMOND (H.W.). - The Sum of the cubes of the coefficients in $(1-x)^{2n}$, *Messenger of Math.*, **21** (1892), 77-78.

[33] RIORDAN (J.). - *An Introduction to Combinatorial Analysis*, John Wiley, New York (1958).

[34] SCHÜTZENBERGER (M.P.). - On a factorisation of free monoids, *Proc. Amer. Math. Soc.*, **16** (1965), 51-54.

[35] SCHÜTZENBERGER (M.P.). - Sur une propriété combinatoire des algèbres de Lie libres pouvant être utilisée dans un problème de Mathématiques Appliquées. Séminaire P. Dubreil (Algèbre et Théorie des Nombres), exposé n° 1, Faculté des Sciences de Paris (1958).

[36] SHERMAN (S.). - Fluctuation and Periodicity, *J. Math. Anal. Appl.*, **9** (1964), 468-476.

[37] ŠIRŠOV (A.I.). - O svobodnyh kol'cah Li (Sur les anneaux de Lie libres), *Mat. Sbornik*, **45** (1958), 113-122.

[38] SPITZER (F.). - A combinatorial lemma and its applications to Probability Theory, *Trans. Amer. Math. Soc.*, **82** (1956), 323-339.

[39] STAVER (Tor B.). - Om summasjon av potenser av binomial-koeffisientene, *Nordisk Mat. Tidsskr.*, **29** (1947), 97-103.

[40] SZÉP (J.). - Sui gruppi fattorizzabili, *Atti del Convegno sulla teoria dei gruppi finiti* [11-13 Aprile 1960], Firenze, 20-30.

[41] WENDEL (J.G.). - Spitzer's formula : a short proof, *Proc. Amer. Math. Soc.*, **9** (1958), 905-908.

Institut de Mathématiques
Faculté des Sciences de Lille
Lille

adresse actuelle : Département de Mathématique
Université de Strasbourg
Strasbourg

Reçu le 10 mars 1965

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