Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes (^{∗})

Dominique Foata, Guo-Niu Han et Bodo Lass

Résumé. — Le problème traditionnel du collectionneur de vignettes est prolongé au cas où le collectionneur fait partager sa moisson avec les membres de sa fratrie. Il reste le seul acheteur, mais donne à ses frères les images qu’il obtient en double. Quand son album est fini, les albums de ses frères ont un certain nombre d’emplacements vides. En moyenne, combien ? Nous apportons une réponse à cette question et obtenons, en outre, une expression pour la fonction génératrice multivariée des variables aléatoires en question. Le problème fait apparaître les nombres hyperharmoniques, qu’il faut étudier sous certains aspects, comme solutions d’équations aux différences notamment.

Abstract. — The traditional coupon collector’s problem is extended to the case where the collector shares his harvest with his own phratry. He remains the only coupon provider, but gives his brothers the coupons that have already appeared in his picture-book. When his book is completed, the books of the other brothers have certain numbers of empty spots. On the average, how many ? We bring an answer to this question and also derive the multivariable generating function for the random variables involved. The problem gives rise to the hyperharmonic numbers that are to be studied under various aspects, in particular as solutions of finitedifference equations.

1. Introduction. — Le problème du collectionneur de vignettes (^{⟨⟨} coupon collector’s problem^{⟩⟩}) est un vieux problème étudié en Calcul des Probabilités (voir Feller (1968)). Chaque tablette de chocolat d’une marque donnée contient une vignette, qui peut être collée dans un album. Celui-ci contient m emplacements qui correspondent aux m vignettes éditées. Il s’agit d’estimer le nombre moyen de tablettes que doit acheter un

(^{∗}) English title : The hyperharmonic numbers and the phratry of the coupon collector.

AMS 2000 Classification : 05A15, 05E05, 60C05, 60G42.

Keywords : Hyperharmonic numbers, Coupon collector’s problem, Surjection calculus, Formal Laplace Transform, Finite-difference equations.

D. FOATA, G.-N. HAN, B. LASS

collectionneur pour remplir son album. Naturellement, toutes les vignettes sont différenciées et à chaque achat le collectionneur a la probabilité 1/m d’obtenir une vignette donnée. S’il a déjà cette vignette, il la jette, s’il ne l’a pas, il la colle dans son album à l’emplacement réservé pour celle-

ci. Soit H_{m} le nombre harmonique défini par H_{m} := 1 + \frac{1}{2} + ⋯ + \frac{1}{m}, suivant l’appellation désormais classique (voir Graham et al. (1989), § 6.3). On démontre facilement, par diverses méthodes (simple comptage, en bâtissant une chaîne de Markov adaptée, …) que le nombre moyen d’achats est : m H_{m}.

On doit à Pintacuda (1980) de s’être intéressé au frère du collectionneur, celui qui n’achète pas de vignette, mais les reçoit de son grand frère, lorsque celui-ci a des doublons. Il a aussi un album, où il colle les vignettes obtenues. Le problème est alors d’estimer le nombre moyen d’emplacements vides dans son album, lorsque son grand frère a terminé son propre album. En utilisant le théorème des temps d’arrêt pour les martingales, Pintacuda (op. cit.) montre que ce nombre moyen vaut H_{m}.

Nous devons à notre collègue Fuchs de nous avoir expliqué la méthode probabiliste de Pintacuda, telle qu’elle lui avait été rapportée par Letta (1992), pour trouver cette dernière valeur. Une discussion s’est alors engagée entre les trois auteurs, laquelle les a conduit à penser que ce problème, bien que tombé dans l’escarcelle des probabilistes, méritait un traitement combinatoire complet. C’est ce que nous nous proposons de faire, en donnant aussi un prolongement au cas d’une fratrie. Pourquoi, en effet, ne considérer qu’un seul petit frère ?

Dans le problème de la fratrie, le collectionneur est l’aîné de la famille, il a r frères et reste toujours le seul acheteur. Chaque frère a aussi un exemplaire personnel de l’album et colle aussi les vignettes lorsqu’il en obtient une nouvelle. La source d’approvisionnement est la suivante : chaque fois que l’aîné achète une tablette et qu’il obtient une nouvelle vignette, il la colle dans son album. Sinon, il la donne au plus âgé de ses frères. Si celui-ci n’a pas encore cette vignette, il la colle dans son album ; sinon, il la donne au frère suivant, et ainsi de suite. Si donc une vignette apparaît plus de r fois avant que l’aîné ait fini son album, cette vignette ira à la poubelle !

Soit T le nombre de tablettes que doit acheter l’aîné pour compléter son album. A cet instant, les frères, à qui on donne les numéros 1, 2, …, r, ont encore, respectivement, M_{T}^{(1)}, M_{T}^{(2)}, …, M_{T}^{(r)} emplacements vides dans leurs albums. On sait que 𝔼[T] = m H_{m} et 𝔼[M_{T}^{(1)}] = H_{m}, d’après Pintacuda. Nous nous proposons de retrouver ce dernier résultat, mais aussi d’établir, pour k ≥ 2, que l’on a

(1.1)  𝔼[M_{T}^{(k)}] = 1 + K_{m}^{(1)} + ⋯ + K_{m}^{(k)},

NOMBRES HYPERHARMONIQUES

où, pour tout k ≥ 0 et m ≥ 1, le nombre K_{m}^{(k)} est le nombre hyperharmonique, défini par les relations suivantes :

(1.2) K_{1}^{(k)} := 0, pour tout k ≥ 1; K_{m}^{(0)} := 1, pour tout m ≥ 1; et pour k ≥ 1 et m ≥ 2

(1.3) K_{m}^{(k)} := \frac{K_{2}^{(k−1)}}{2} + ⋯ + \frac{K_{m−1}^{(k−1)}}{m − 1} + \frac{K_{m}^{(k−1)}}{m} ,

que l’on peut encore récrire :

(1.4) K_{m}^{(k)} − \frac{K_{m}^{(k−1)}}{m} = K_{m−1}^{(k)}.

En particulier, pour k ≥ 0, on a : K_{2}^{(k)} = 1/2^{k}. Le tableau suivant donne une liste des premières valeurs de ces nombres.

\begin{matrix}m & 1 & 2 & 3 & 4 & 5 & 10 & 15 & 20 & 25 & 30 & 35 & 40 & 45 & 50 \\ K_{m}^{(0)} & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ K_{m}^{(1)} & 0 & 0,50 & 0,83 & 1,08 & 1,28 & 1,93 & 2,31 & 2,60 & 2,82 & 3,00 & 3,15 & 3,28 & 3,39 & 3,50 \\ K_{m}^{(2)} & 0 & 0,25 & 0,53 & 0,80 & 1,06 & 2,14 & 2,98 & 3,67 & 4,27 & 4,79 & 5,26 & 5,68 & 6,07 & 6,43 \\ K_{m}^{(3)} & 0 & 0,13 & 0,30 & 0,50 & 0,71 & 1,79 & 2,82 & 3,76 & 4,64 & 5,46 & 6,23 & 6, 96 & 7,65 & 8,30 \\ K_{m}^{(4)} & 0 & 0,06 & 0,16 & 0,29 & 0,43 & 1,27 & 2,20 & 3,14 & 4,08 & 4,99 & 5,89 & 6,77 & 7,63 & 8,47 \\ K_{m}^{(5)} & 0 & 0,03 & 0,09 & 0,16 & 0,24 & 0,81 & 1,51 & 2,28 & 3,08 & 3,91 & 4,75 & 5,59 & 6,44 & 7,29 \\ K_{m}^{(6)} & 0 & 0,02 & 0,04 & 0,08 & 0,13 & 0,48 & 0,95 & 1,49 & 2,09 & 2,73 & 3,40 & 4,09 & 4,80 & 5,52 \end{matrix}

Comme tous les nombres K_{m}^{(0)} valent 1, on a :

K_{m}^{(1)} = H_{m} − 1 (m ≥ 1).

On a ainsi ^{⟨⟨} harmonicisé^{⟩⟩} la suite dont tous les termes sont égaux à 1, pour obtenir la suite des nombres harmoniques (diminués d’une unité). L’appellation hyperharmonique vient du fait que pour obtenir la suite K_{m}^{(k)} (m ≥ 2), on ^{⟨⟨} harmonicise^{⟩⟩}, de la même façon, la suite K_{m}^{(k−1)} (m ≥ 2).

En utilisant les séries génératrices, la récurrence (1.4) s’écrit sous la forme :

(1 − t/m) · ∑_{k≥0} K_{m}^{(k)}t^{k} = ∑_{k≥0} K_{m−1}^{(k)}t^{k}.

Puisque ∑_{k≥0} K_{1}^{(k)}t^{k} = 1, on obtient :

(1.5)  ∑_{k≥0} K_{m}^{(k)}t^{k} = \frac{1}{(1 − t/2)(1 − t/3) ⋯ (1 − t/m)}.

Dans le présent article, nous nous proposons de redémontrer le résultat 𝔼[M_{T}^{(1)}] = H_{m} de Pintacuda, puis d’établir les formules (1.1). En plus, nous donnons une expression pour la distribution (voir Proposition 4.1) du vecteur aléatoire (T, M_{T}^{(1)}, M_{T}^{(2)}, …, M_{T}^{(r)}), d’où l’on tire la distribution de chacune des variables et naturellement leurs espérances mathématiques. En fait, nous préférons introduire une suite de variables aléatoires (X_{T}^{(k)}) (k = 1, 2, …) telles que, pour tout k ≥ 1, on ait :

M_{T}^{(k)} = X_{T}^{(1)} + X_{T}^{(2)} + ⋯ + X_{T}^{(k)},

calculons la fonction génératrice du vecteur (T, X_{T}^{(1)}, X_{T}^{(2)}, …, X_{T}^{(r)}), puis montrons que

(1.6)  𝔼[X_{T}^{(1)}] = 1 + K_{m}^{(1)} = H_{m}; 𝔼[X_{T}^{(k)}] = K_{m}^{(k)} pour k ≥ 2.

Le calcul de la fonction génératrice multivariée fait appel aux techniques classiques de la Combinatoire Énumérative, en particulier, des propriétés de la transformation de Laplace formelle. La méthode de Pintacuda est reprise ensuite dans le cas de la fratrie, pour permettre d’obtenir deux autres démonstations des formules (1.1). En fait, cette technique du théorème des temps d’arrêt pour les martingales ne fournit qu’une équation aux différences pour les temps moyens. La partie la plus délicate n’est plus probabiliste : elle consiste à trouver une solution de cette équation aux différences et là, il n’existe pas de méthode universelle.

Nous donnons encore deux autres méthodes de calcul, permettant d’obtenir directement la fonction génératrice des nombres moyens 𝔼[X_{T}^{(k)}]. La première de ces méthodes fournit même une formule dans le cas où la vente des vignettes n’est plus uniforme, où la probabilité d’acheter la vignette i est p_{i} > 0 (p_{1} + ⋯ + p_{m} = 1). Comme on le verra, toutes les méthodes combinatoires développées reposent sur des dénombrements de surjections.

Nous terminons l’article par une étude asymptotique des nombres hyperharmoniques. Comme il est bien connu, le nombre harmonique H_{m} est asymptotiquement équivalent à ln m. On montre que le nombre k! K_{m}^{(k)} est asymptotiquement équivalent à (ln m)^{k}.

Déjà Feller (1968, p. 225) écrivait qu’il y avait une ^{⟨⟨} énorme littérature traitant de variantes du problème du collectionneur de vignettes^{⟩⟩}. En consultant MathSciNet, nous nous sommes rendu compte que cet intérêt n’avait pas décru. Pas moins de dix-sept titres. Ce modèle a trouvé des applications en informatique (Flajolet et al. (1992), Banderier et al. (2000)), mais aussi en recherche opérationnelle (Boneh et al. (1997)). Nous renvoyons à MathSciNet pour la liste complète de ces articles.

2. Les nombres hyperharmoniques. — Ils ont été définis en (1.2) et (1.3), de façon itérative. En décomposant la fraction rationnelle, qui apparaît dans (1.5), en éléments simples, on déduit, pour k ≥ 0 et m ≥ 2, la formule explicite

(2.1) K_{m}^{(k)} = m(m − 1) ∑_{n} \frac{(−m + 2)_{n}}{n!} \frac{1}{(n + 2)^{k+1}} ,

où (a)_{n} désigne la factorielle montante :

(a)_{n} := \{ \begin{matrix}1, & si n = 0 ; \\ a(a + 1) ⋯ (a + n − 1), & si n ≥ 1. \end{matrix}

On reconnaît dans la fraction rationnelle de l’identité (1.5) la fonction génératrice des fonctions symétriques homogènes complètes h_{k}(x_{1}, x_{2}, …) (cf. Macdonald (1995) p. 21), lorsque l’on substitue les fractions \frac{1}{2}, \frac{1}{3}, …, \frac{1}{m} aux variables x_{1}, x_{2}, …, x_{m−1}, ce qui établit l’identité

(2.2)  K_{m}^{(k)} = h_{k}(\frac{1}{2}, \frac{1}{3}, …, \frac{1}{m}).

On peut également obtenir une expression pour la fonction génératrice des nombres K_{m}^{(1)} (m ≥ 2), à savoir,

(2.3)  ∑_{m≥2} K_{m}^{(1)}s^{m} = (s − 1)^{−1}(ln(1 − s) + s).

Les propriétés des nombres K_{m}^{(k)} données dans la proposition suivante sont faciles à établir et données sans démonstration. On observe, en particulier, que les nombres K_{m}^{(k)} (k ≥ 0) vont d’abord en croissant (valeurs reproduites en gras dans le tableau de l’introduction).

Proposition 2.1.

(a) Pour tout m ≥ 2, on a : ∑_{k≥0} K_{m}^{(k)} = m.

(b) Pour tout k ≥ 1, on a K_{m}^{(k)} → +∞, lorsque m tend vers l’infini.

(c) Pour tout k ≥ 1, on a K_{m}^{(0)} < K_{m}^{(1)} < ⋯ < K_{m}^{(k)} < m pour m assez grand.

Remarque. — La récurrence (1.4), à savoir K_{m}^{(k)} − K_{m}^{(k−1)}/m = K_{m−1}^{(k)} (k ≥ 1, m ≥ 2) apparaît déjà dans Bentley et al. (1978) et Buchta (1989) pour permettre le calcul du nombre moyen de maxima dans un ensemble de vecteurs. Ces auteurs utilisent des conditions initiales différentes de (1.2), à savoir : K_{1}^{(k)} := 1 (k ≥ 1) et K_{m}^{(0)} := 1 (m ≥ 1) et obtiennent donc d’autres suites de nombres. Tous ces nombres, cependant, y compris les nombres hyperharmoniques, ne sont que des variations des nombres harmoniques généralisés H_{m}^{(k)} := ∑_{1≤j≤m}(1/j^{k}) (cf. Graham et al. (1989)). Une autre extension, avec l’adjonction d’un nouveau paramètre, a été introduite et utilisée dans Flajolet et al. (1995) dans l’étude statistique des^{⟨⟨} quadtrees^{⟩⟩}.

3. Un calcul de surjections. — Le problème décrit dans l’introduction, bien qu’il ait été offert aux probabilistes, a une très forte connotation combinatoire. Il s’agit, en fait, de dénombrer des classes particulières de surjections. Pour tout entier n, posons [n] := {1, 2, …, n} et notons Surj(l, m) l’ensemble des surjections de [l] sur [m]. Si f appartient à Surj(l, m), pour tout i ≥ 1, on note ν_{i}(f) le nombre d’éléments j ∈ [m] tels que l’image réciproque f^{−1}(j) est de cardinal i. A tout vecteur d’entiers positifs n = (n_{1}, n_{2}, …), on associe le sous-ensemble Surj(l, m; n) des surjections f ∈ Surj(l, m) telles que pour tout i ≥ 1 on ait ν_{i}(f) = n_{i} et on note surj(l, m; n) le cardinal de Surj(l, m; n).

Soit (t, s_{1}, s_{2}, …) une suite infinie de variables commutatives. Le poids π(f) de f est défini par : π(f) := ∏_{i≥1}s_{i}^{ν_{i}(f)} ; on a ainsi les relations :

∑_{i} ν_{i}(f) = m et ∑_{i} i ν_{i}(f) = l.

L’identité

(3.1)  (∑_{i≥1} s_{i} \frac{t^{i}}{i!} )^{m} = ∑_{l≥m} \frac{t^{l}}{l!} ∑_{f∈Surj(l,m)} π(f),

qui peut encore s’écrire

(3.2)  (∑_{i≥1} s_{i} \frac{t^{i}}{i!} )^{m} = ∑_{l≥m} \frac{t^{l}}{l!} ∑_{n} surj(l, m; n) ∏_{i≥1} s_{i}^{n_{i}},

peut être établie par différentes méthodes, par exemple, par les techniques du composé partitionnel. Elle est démontrée dans Foata (1974), p. 59-60. On peut aussi utiliser la technique des espèces de nos amis canadiens (cf. Bergeron et al. (1994)) ou les fonctions d’ensembles (cf. Lass (2001)).

Introduisons maintenant le sous-ensemble A(l, m; n) de Surj(l, m, n) formé par toutes les surjections f ayant la propriété suivante :

la restriction f |_{[l−1]} de f à l’intervalle [l−1] est elle-même une surjection de [l − 1] sur [m] \ {f(l)}, mais pas sur [m], i.e. f(j) ≠ f(l) pour j ≤ l − 1.

Si donc f est dans A(l, m; n), on a ν_{1}(f) ≥ 1 et son poids π(f) est divisible par s_{1}. Désignons par a(l, m; n) le nombre des éléments de A(l, m; n).

Si f est dans A(l, m; n), posons g := f |_{[l−1]}. Alors π(f) = π(g) s_{1}, comme il a été noté plus haut. D’autre part, on a la relation

(3.3)  ∑_{n} ∑_{f∈A(l,m;n)} π(f) = m s_{1} ∑_{g∈Surj(l−1,m−1)} π(g).

On en tire :

∑_{l≥m} \frac{t^{l−1}}{(l − 1)!} ∑_{n} ∑_{f∈A(l,m;n)} π(f) = ∑_{l≥m} \frac{t^{l−1}}{(l − 1)!} × m s_{1} ∑_{g∈Surj(l−1,m−1)} π(g)

= m s_{1} ∑_{k≥m−1} \frac{t^{k}}{k!} ∑_{g∈Surj(k,m−1)} π(g) = m s_{1}(∑_{i≥1} s_{i} \frac{t^{i}}{i!} )^{m−1}.

Avec s_{i} := 1 pour tout i ≥ r + 1, l’identité précédente prend la forme

m s_{1}(e^{t} − 1 + t(s_{1} − 1) + \frac{t^{2}}{2!} (s_{2} − 1) + ⋯ + \frac{t^{r}}{r!} (s_{r} − 1))^{m−1}

= ∑_{l≥m} \frac{t^{l−1}}{(l − 1)!} ∑_{n} ∑_{f∈A(l,m;n)} π(f).

En développant le membre de gauche par la formule du multinôme, on en déduit :

ms_{1} ∑_{a+b+c_{1}+···+c_{r}=m−1} \binom{m − 1}{a, b, c_{1}, …, c_{r}}e^{at}(−1)^{b} ∏_{i=1}^{r}(\frac{t^{i}(s_{i} − 1)}{i!})^{c_{i}}

= ∑_{l≥m} \frac{t^{l−1}}{(l − 1)!} ∑_{n} ∑_{f∈A(l,m;n)} π(f).

La transformation de Laplace formelle, L, par rapport à la variable t remplace le terme d(l)t^{l}/l! d’une série par le terme d(l)t^{l}. En particulier, L(e^{at}t^{n}) = n! t^{n}/(1−at)^{1+n}. On applique la transformation L à la dernière identité et on trouve :

(3.4) ms_{1}t ∑ \binom{m − 1}{a, b, c_{1}, …, c_{r}}(−1)^{b} (∏_{k=1}^{r}(\frac{s_{k} − 1}{k!})^{c_{k}})

× \frac{t^{Σkc_{k}}}{(1 − at)^{1+Σkc_{k}}} (∑_{k}kc_{k})! = ∑_{l≥m} t^{l} ∑_{n} a(l, m; n) ∏_{k=1}^{r} s_{k}^{n_{k}}.

4. La fonction génératrice multivariée. — Comme déjà indiqué dans l’introduction, T désigne l’instant où l’aîné termine son album. Pour chaque n = 0, 1, …, notons X_{n}^{(0)} le nombre d’emplacements vides dans l’album de l’aîné à l’instant n, de sorte que X_{0}^{(0)} = m et X_{T}^{(0)} = 0. Pour k = 1, 2, …, notons aussi X_{n}^{(k)} le nombre de vignettes qui sont apparues exactement k fois, jusqu’à la date n incluse. Alors ∑_{k≥1} X_{T}^{(k)} = m. De plus,

le nombre d’emplacements vides dans l’album du frère d’indice k ≥ 1, à cet instant T, un nombre qui avait été noté M_{T}^{(k)} dans l’introduction, est égal à : M_{T}^{(k)} = X_{T}^{(1)}+⋯+X_{T}^{(k)}. La distribution du vecteur (T, M_{T}^{(1)}, …, M_{T}^{(r)}) se déduit donc immédiatement de celle du vecteur (T, X_{T}^{(1)}, …, X_{T}^{(r)}). C’est celle-ci que nous déterminons.

Notons Y_{1}, Y_{2}, … les numéros (compris entre 1 et m) des vignettes que trouve l’aîné dans les achats successifs de ses tablettes. On suppose ainsi que les Y_{n} (n ≥ 1) sont des variables aléatoires indépendantes, chacune uniformément répartie sur {1, 2, …, m}. Alors l’aîné finit son album après l’achat de la l^{ième} tablette et pour chaque k = 1, …, r, le nombre X_{n}^{(k)} de vignettes qui sont apparues exactement k fois, jusqu’à la date n incluse est n_{k}, si et seulement si l’application f : i ↦ Y_{i} (1 ≤ i ≤ l) est une surjection appartenant à A(l, m; n). Cet évènement s’exprime comme {T = l, X_{T}^{(1)} = n_{1}, …, X_{T}^{(r)} = n_{r}} et sa probabilité est évidemment égale à a(l, m; n)/m^{l}. La proposition suivante est donc une conséquence de la relation (3.4).

Proposition 4.1. — La fonction génératrice du vecteur aléatoire (T, X_{T}^{(1)}, …, X_{T}^{(r)}) est donnée par :

∑_{l≥m,n} P{T = l, X_{T}^{(1)} = n_{1}, …, X_{T}^{(r)} = n_{r}}t^{l}s_{1}^{n_{1}} … s_{r}^{n_{r}}

=s_{1}t∑\binom{m − 1}{a, b, c_{1}, …, c_{r}}(−1)^{b}(∏_{k=1}^{r}(\frac{s_{k} − 1}{k!})^{c_{k}})\frac{(t/m)^{Σkc_{k}}}{(1 − at/m)^{1+Σkc_{k}}} (∑_{k}kc_{k})!

De cette expression, on retrouve la fonction génératrice usuelle de T et donc immédiatement son espérance 𝔼[T] = m H_{m}. Cependant, le fait important est, qu’une fois obtenues les fonctions génératrices des variables X_{T}^{(k)} (k ≥ 1), on puisse, grâce à la formule explicite (2.1), sommer leurs dérivées en 1, et ainsi déterminer leurs espérances. En effet, on a

(4.1) G_{X_{T}^{(1)}}(s) := ∑_{n≥1} P{X_{T}^{(1)} = n}s^{n}

= s ∑_{a+b+c=m−1} \binom{m − 1}{a, b, c}(−1)^{b} \frac{m(s − 1)^{c}}{(m − a)^{1+c}} c! ;

et pour k ≥ 2

(4.2) G_{X_{T}^{(k)}}(s) := ∑_{n≥1} P{X_{T}^{(k)} = n}s^{n}

= ∑_{a+b+c=m−1} \binom{m − 1}{a, b, c}(−1)^{b} \frac{(s − 1)^{c}}{k!^{c}} \frac{m}{(m − a)^{1+kc}} (kc)!

D’où

𝔼[X_{T}^{(1)}] = G′_{X_{T}^{(1)}}(1) = − ∑_{b=0}^{m−1} \frac{(−m)_{b+1}}{(b + 1)!} + m(m − 1) ∑_{b} \frac{(−m + 2)_{b}}{b!} \frac{1}{(b + 2)^{2}}
= 1 + K_{m}^{(1)} = H_{m},

le résultat déjà prouvé par Pintacuda (1980).

De plus, pour k ≥ 2,

𝔼[X_{T}^{(k)}] = G′_{X_{T}^{(k)}}(1) = m(m − 1) ∑_{b} \frac{(−m + 2)_{b}}{b!} \frac{1}{(b + 2)^{1+k}} = K_{m}^{(k)}.

5. La méthode des martingales. — Nous réutilisons la méthode probabiliste de Pintacuda (op. cit.), telle qu’elle nous avait été rapportée par Letta, pour l’appliquer au calcul des nombres moyens 𝔼[X_{T}^{(k)}], pour tout k ≥ 1. Conservons les notations du paragraphe précédent et utilisons les notations suivantes : si (x^{(0)}, …, x^{(r)}) est un vecteur de r composantes réelles, posons, pour k ≥ 0,

δ^{(k)}(x^{(0)}, …, x^{(r)}) = \{ \begin{matrix}(x^{(0)}, …, x^{(k)} − 1, x^{(k+1)} + 1, …, x^{(r)}), \\ si 0 ≤ k ≤ r − 1; \\ (x^{(0)}, …, x^{(r)} − 1),  si k = r; \\ (x^{(0)}, …, x^{(r)}),  si k ≥ r + 1. \end{matrix}

Maintenant si f est une fonction réelle définie sur ℕ^{r+1}, formons, pour chaque entier n ≥ 0, la variable aléatoire

V_{n} := f(X_{n}^{(0)}, X_{n}^{(1)}, …, X_{n}^{(r)}).

Traditionnellement, W := V ^{| T} désigne le processus arrêté en T, c’est-à-dire la suite des variables aléatoires (W_{n}) (n ≥ 0) définies par :

W_{n} := V_{T ∧n} := V_{n} I_{{n<T }} + V_{T} I_{{n≥T }},

où le symbole I_{A} désigne l’indicatrice de l’évènement A. Or, W_{n+1} − W_{n} = V_{n+1} I_{{n+1<T }} + V_{T} I_{{n+1≥T }} − V_{n} I_{{n<T }} − V_{T} I_{{n≥T }} = (V_{n+1} − V_{n}) I_{{n<T }}+V_{n+1}(I_{{n+1<T }}−I_{{n<T }})+V_{T} (I_{{n+1≥T }}−I_{{n≥T }}) = (V_{n+1}− V_{n}) I_{{n<T }} = (V_{n+1} − V_{n}) I_{{X_{n}^{(0)}>0}}. Ainsi, l’accroissement des variables W_{n}, qu’il est commode de noter ΔW_{n} := W_{n+1} − W_{n}, est le même que l’accroissement ΔV_{n} des V_{n}, tant que l’album de l’aîné n’est pas terminé, soit

ΔW_{n} = ΔV_{n} I_{{X_{n}^{(0)}>0}}.

Considérons la variation du vecteur X_{n} := (X_{n}^{(0)}, X_{n}^{(1)}, …, X_{n}^{(r)}) de l’instant n à l’instant (n + 1). Si la vignette achetée à l’instant (n + 1) a déjà été acquise k ≥ 0 fois précédemment, alors

X_{n+1} = δ^{(k)}X_{n}.

Les évènements {ΔX_{n}^{(k)} = −1} (0 ≤ k ≤ r) et {ΔX_{n} = 0} forment ainsi un système complet d’évènements. On peut donc écrire

ΔV_{n} = ∑_{k=0}^{r} I_{{ΔX_{n}^{(k)}=−1}}(f(δ^{(k)}X_{n}) − f(X_{n}))

puisque ΔV_{n} I_{{ΔX_{n}=0}} = 0.

Comme l’évènement {ΔX_{n}^{(k)} = −1} est réalisé si et seulement si la vignette, achetée à l’instant (n+1), a été précédemment acquise k fois (0 ≤ k ≤ r), l’espérance conditionnelle de la variable I_{{ΔX_{n}^{(k)}=−1}}, par rapport à

la suite (Y_{0}, Y_{1}, …, Y_{n}) est simplement X_{n}^{(k)}/m. (Par convention, Y_{0} := 0.)

L’espérance conditionnelle de la variation ΔV_{n}, par rapport à la suite (Y_{0}, Y_{1}, …, Y_{n}), est donc égale à :

𝔼[ΔV_{n} | Y_{0}, …, Y_{n}] = ∑_{k=0}^{r} \frac{X_{n}^{(k)}}{m} (f(δ^{(k)}X_{n}) − f(X_{n})).

Supposons que l’on trouve une fonction f telle que cette expression soit nulle. Alors, on aura aussi ΔW_{n} = 0 et W sera une martingale (consulter, par exemple, Bauer (1995), § 17).

Proposition 5.1. — Supposons que pour chaque k = 1, …, r il existe une fonction réelle f^{(k)}, définie sur ℕ^{k+1}, ayant les propriétés suivantes :

(a) ∑_{i=0}^{k} x_{i}(f^{(k)}(δ^{(i)}(x_{0}, …, x_{k})) − f^{(k)}(x_{0}, …, x_{k})) = 0 pour x_{0} ≥ 1 ;

(b) f^{(k)}(0, x_{1}, …, x_{k}) = x_{k}.

Alors, 𝔼[X_{T}^{(k)}] = f^{(k)}(m, 0, …, 0) pour k = 1, …, r.

Démonstration. — En effet, pour tout k = 1, …, r, on a W_{0} = V_{0} = f^{(k)}(X_{0}^{(0)}, X_{0}^{(1)}, …, X_{0}^{(k)}) = f^{(k)}(m, 0, …, 0) et W_{T} = V_{T} = f^{(k)}(X_{T}^{(0)}, X_{T}^{(1)}, …, X_{T}^{(k)}) = f^{(k)}(0, X_{T}^{(1)}, …, X_{T}^{(k)}) = X_{T}^{(k)}, d’après (b). Le théorème d’arrêt pour les martingales donne alors 𝔼[X_{T}^{(k)}] = 𝔼[W_{T}] = 𝔼[W_{0}] = W_{0} = f^{(k)}(m, 0, …, 0).

Lorsque k = 1, la méthode ci-dessus est due à Pintacuda (op. cit.). Il a trouvé, de plus, pour k = 1, la fonction f^{(1)}(x_{0}, x_{1}) := H_{x_{0}} + \frac{x_{1}}{1 + x_{0}} . En

effet, la propriété (a) s’écrit, en posant f := f^{(1)}, x := x_{0}, y := x_{1} : x(f(x − 1, y + 1) − f(x, y)) + y(f(x, y − 1) − f(x, y))

= x(H_{x−1} + \frac{y + 1}{x} − H_{x} − \frac{y}{1 + x}) + y(H_{x} + \frac{y − 1}{1 + x} − H_{x} − \frac{y}{1 + x})

= x(−\frac{1}{x} + \frac{y + 1}{x} − \frac{y}{1 + x}) + y \frac{−1}{1 + x} = y(1 − \frac{x}{1 + x} − \frac{1}{1 + x}) = 0.

Aussi, f(m, 0) = H_{m}, d’où 𝔼[X_{T}^{(1)}] = H_{m}.

Pour résoudre le problème de la fratrie du collectionneur par cette méthode, il suffit donc de trouver pour chaque k = 1, 2, …, r une fonction réelle f^{(k)} de (k + 1) variables entières ayant les propriétés suivantes :

(a) ∑_{i=0}^{k} x_{i}(f^{(k)}(δ^{(i)}(x_{0}, …, x_{k})) − f^{(k)}(x_{0}, …, x_{k})) = 0 pour x_{0} ≥ 1 ;

(b) f^{(k)}(0, x_{1}, …, x_{k}) = x_{k};

(c) f^{(1)}(m, 0) = H_{m} (c’est déjà fait !), mais pour k = 2, …, r telle que f^{(k)}(m, 0, …, 0) = K_{m}^{(k)}.

6. La solution de l’équation aux différences finies. — Résoudre une équation aux différences finies, telle que (a), qui plus est, à plusieurs variables, n’est pas aisé. D’abord, qu’entend-on par ^{⟨⟨} résoudre^{⟩⟩}? Selon les canons traditionnels, il s’agit de trouver une solution qui s’exprime dans l’algèbre des fonctions spéciales. En l’absence de techniques universelles, il faut beaucoup tâtonner. C’est la dure méthode symbolique décrite par Cartier (2000) dans son article de synthèse. Déjà la solution trouvée par Pintacuda relevait du deus ex machina. En fait, une longue familiarité avec l’équation elle-même va mener à la solution. Nous donnons deux solutions, une solution ^{⟨⟨} locale^{⟩⟩} (qui fournit la valeur de f^{(k)}), puis ^{⟨⟨} globale^{⟩⟩} (qui donne l’expression de la fonction génératrice ∑_{k>0} f^{(k)}t^{k}), en attendant que nos amis du Calcul Formel (cf. Zeilberger (1990) ou Strehl (2001a), (2001b)) nous fournissent une solution ^{⟨⟨} automatique^{⟩⟩}.

6.1. La solution locale. — Elle consiste à résoudre l’équation (a), que l’on récrit sous la forme

(6.1) (x_{0} + ⋯ + x_{k})f^{(k)}(x_{0}, …, x_{k}) = ∑_{i=0}^{k} x_{i}f^{(k)}(δ^{(i)}(x_{0}, …, x_{k})),

pour chaque k ≥ 2 avec x_{0} ≥ 1. D’après cette équation, on voit que la valeur de f^{(k)} en x = (x_{0}, x_{1}, …, x_{k}) est parfaitement déterminée, si l’on connaît la valeur de f^{(k)} en tous les points x′ = (x′_{0}, x′_{1}, …, x′_{k}) plus petits, pour l’ordre lexicographique. On voit aussi, par itération, que chaque f^{(k)}(x_{0}, …, x_{r}), où x_{0} + ⋯ + x_{k} ≥ 1, s’exprime, de façon unique, comme une combinaison linéaire de valeurs de la forme f^{(k)}(0, x′_{1}, …, x′_{k}) avec x′_{1} + ⋯ + x′_{k} ≤ x_{0} + x_{1} + ⋯ + x_{k} et x′_{k} ≥ 1. Si on se donne les valeurs de f^{(k)} en les points (0, x′_{1}, …, x′_{k}), où (x′_{1}, …, x′_{k}) ∈ ℕ^{k} et x′_{k} ≥ 1, la fonction f^{(k)} est parfaitement déterminée.

Proposition 6.1. — Pour k ≥ 2, la fonction f^{(k)} définie par

(6.2) f^{(k)}(x_{0}, x_{1}, …, x_{k}) := K_{x_{0}}^{(k)} + \frac{x_{1}K_{x_{0}+1}^{(k−1)} + ⋯ + x_{k−1}K_{x_{0}+1}^{(1)} + x_{k}}{x_{0} + 1}

:= K_{x_{0}}^{(k)} + (K_{x_{0}+1}^{(k)} − K_{x_{0}}^{(k)})x_{1} + (K_{x_{0}+1}^{(k−1)} − K_{x_{0}}^{(k−1)})x_{2}

+ ⋯ + (K_{x_{0}+1}^{(1)} − K_{x_{0}}^{(1)})x_{k}

est l’unique fonction satisfaisant l’équation (6.1), de conditions initiales

f^{(k)}(0, x_{1}, …, x_{k}) = x_{k},

pour tout (x_{1}, …, x_{k}) ∈ ℕ^{k}. Elle satisfait, de plus, f^{(k)}(x_{0}, 0, …, 0) = K_{x_{0}}^{(k)}.

Démonstration. — L’unicité a déjà été établie par l’argument précédant la proposition. Il suffit donc de vérifier que la fonction définie en (6.2) satisfait l’équation (6.1). Il s’agit d’une simple vérification, qui utilise pleinement la récurrence (1.4) des nombres hyperharmoniques. Nous nous dispensons d’écrire les détails de cette vérification facile.

Les Propositions 5.2 et 6.1 fournissent ainsi une seconde démonstration des identités 𝔼[X_{T}^{(k)}] = f^{(k)}(m, 0, …, 0) = K_{m}^{(k)} pour k = 2, …, r.

6.2. La solution globale. — On récrit l’identité (a) du paragraphe 6 sous la forme

∑_{i=0}^{k} x_{i} N_{i} f^{(k)}(x_{0}, …, x_{k}) = 0,

de sorte que, pour tout i ≥ 0, on a défini l’opérateur N_{i} par :

N_{i} f^{(k)}(x_{0}, …, x_{k}) := f^{(k)}(δ^{(i)}(x_{0}, …, x_{k})) − f^{(k)}(x_{0}, …, x_{k}).

On forme, ensuite, l’algèbre des séries formelles f := ∑_{k≥0} f^{(k)} t^{k}, où chaque

coefficient f^{(k)} est une fonction réelle définie sur ℕ^{k+1}. On prolonge la définition de N_{i} à cette algèbre, en posant

N_{i} f := ∑_{k≥0} N_{i} f^{(k)}t^{k} = ∑_{k≥i} N_{i} f^{(k)}t^{k},

puis, on définit l’opérateur :

N := ∑_{i≥0} x_{i} N_{i}.

Il s’agit alors de résoudre (6.3) N f = 0.

D’abord, on étudie l’action de N sur des séries formelles particulières. Si g(x_{0}) est une série formelle dont les coefficients g^{(k)}(x_{0}) ne dépendent que de l’argument x_{0} et si 1 ≤ i ≤ k, alors N_{i} g^{(k)}(x_{0}) = 0 ; d’où N_{i} g(x_{0}) = ∑_{k≥i} N_{i} g^{(k)}(x_{0}) t^{k} = 0 pour i ≥ 1. De plus, pour tout k ≥ 0, on

a : N_{0} g^{(k)}(x_{0}) = g^{(k)}(x_{0} −1)−g^{(k)}(x_{0}) ; d’où N_{0} g(x_{0}) = g(x_{0} −1)−g(x_{0}) et

(6.4)  N g(x_{0}) = x_{0}(g(x_{0} − 1) − g(x_{0})).

D’autre part, si s est une série formelle et si i ≥ 1, on a :

(6.5)  N_{i} g(x_{0})s = g(x_{0})N_{i} s.

L’argument x_{0} jouant un rôle privilégié, on cherche une solution de (6.3) de la forme f = g(x_{0})(h(x_{0}) + s), où g(x_{0}) et h(x_{0}) ne dépendent que de x_{0} et la série s que de x_{1}, x_{2}, … La série s la plus simple à considérer est s := ∑_{k≥1}x_{k} t^{k}. En évaluant N g(x_{0})s pour une telle série, on trouve :

(6.6) N g(x_{0})s = x_{0}g(x_{0} − 1)s − x_{0}g(x_{0})s + x_{0}t g(x_{0} − 1) + g(x_{0})(t − 1)s.

Si donc il existe des solutions f de (6.3) de la forme f = g(x_{0})(h(x_{0}) + s), on doit avoir : N g(x_{0})h(x_{0}) + N g(x_{0})s = 0 ; soit

−x_{0}g(x_{0})(h(x_{0}) + s) + (t − 1)sg(x_{0}) + x_{0}g(x_{0} − 1)(h(x_{0} − 1) + s + t) = 0.

On voit alors qu’en prenant h(x_{0}) := x_{0} + 1 − t, on réduit l’équation précédente à

\frac{g(x_{0})}{g(x_{0} − 1)} = \frac{x_{0}}{x_{0} + 1 − t}.

Prenant alors g(0) := 1, on obtient, par itération, si x_{0} est un entier positif,

g(x_{0}) = \frac{1}{(1 − t/2)(1 − t/3) ⋯ (1 − t/x_{0})(x_{0} + 1 − t)}

et la solution (6.7) f = g(x_{0}) · ((x_{0} + 1) + (x_{1} − 1)t + x_{2}t^{2} + x_{3}t^{3} + ⋯).

Proposition 6.2. — La série formelle donnée en (6.7) est solution de l’équation N f = 0 et satisfait les conditions initiales f^{(1)}(0, x_{1}) = x_{1} − 1 et f^{(k)}(0, x_{1}, …, x_{k}) = x_{k} pour k ≥ 2. De plus, avec x_{0} = m et les autres x_{k} égaux à 0, on obtient

(6.8)  f = \frac{1}{(1 − t/2) ⋯ (1 − t/m)} = ∑_{k≥0} K_{m}^{(k)}t^{k}.

Démonstration. — La vérification de ces propriétés a été faite précédemment et l’identité résulte de (2.2).

La précédente proposition donne ainsi une autre démonstration de 𝔼[X_{T}^{(k)}] = K_{m}^{(k)} pour k ≥ 2. Pour k = 1, on reprend la démonstration de la Proposition 5.1. On a W_{0} = f^{(1)}(X_{0}^{(0)}, X_{1}^{(0)}) = f^{(1)}(m, 0) et W_{T} = f^{(1)}(X_{t}^{(0)}, X_{T}^{(1)}) = f^{(1)}(0, X_{T}^{(1)}) = X_{T}^{(1)} − 1. D’où 𝔼[X_{T}^{(1)}] − 1 = 𝔼[W_{T}] = 𝔼[W_{0}] = W_{0} = f^{(1)}(m, 0) = K_{m}^{(1)}. D’où 𝔼[X_{T}^{(1)}] = K_{m}^{(1)} + 1 = H_{m}.

7. Distribution non-uniforme des vignettes. — On suppose maintenant qu’à tout instant n, la probabilité que la variable Y_{n} soit égale à i est un nombre p_{i} > 0 (i = 1, 2, …, m) et non plus nécessairement 1/m. Par commodité, pour tout sous-ensemble A ⊂ [m] := {1, 2, …, m}, on pose : p_{A} := ∑_{i∈A} p_{i}. Pour k ≥ 1, n ≥ 1 et i = 1, 2, …, m, on pose également X_{n,i}^{(k)} := 1 si la vignette numérotée i est apparue exactement k fois jusqu’à et y compris la date n et X_{n,i}^{(k)} := 0, sinon. De là, X_{n}^{(k)} = ∑_{1≤i≤m} X_{n,i}^{(k)} est le nombre de vignettes qui sont apparues

exactement k fois jusqu’à et y compris la date n.

Proposition 7.1. — Soit T l’instant où l’aîné termine son album. Alors, la fonction génératrice G(t) des nombres 𝔼[X_{T}^{(k)}] est donnée par :

(7.1) G(t) := 1+∑_{k≥1} 𝔼[X_{T}^{(k)}] t^{k} = t+∑_{i=1}^{m} ∑_{A⊂[m]\\{i\}}(−1)^{m−|A|} \frac{1 − p_{i} − p_{A}}{1 − tp_{i} − p_{A}} .

Démonstration. — D’abord,

G(t) = 1 + ∑_{k≥1} ∑_{1≤i≤m} 𝔼[X_{T,i}^{(k)}] t^{k} = 1 + ∑_{k≥1} ∑_{1≤i≤m} P{X_{T,i}^{(k)} = 1} t^{k}

= 1 + ∑_{k≥1} ∑_{1≤i≤m} ∑_{n≥1} ∑_{1≤j≤m} P{X_{n,i}^{(k)} = 1, T = n, Y_{n} = j} t^{k},

puisque T est presque sûrement fini. Pour tout entier n ≥ 1 et tout sous-ensemble A ⊂ [m], notons Surj(n, A) l’évènement ^{⟨⟨} f : l ↦ Y_{l} est, pour l = 1, 2, …, n, une surjection de [n] sur A^{⟩⟩}. Alors, pour k ≥ 1 et i ≠ j, l’évènement {X_{n,i}^{(k)} = 1, T = n, Y_{n} = j} s’écrit encore {Surj(n − 1, [m] \ {j}), X_{n−1,i}^{(k)} = 1, Y_{n} = j}. Pour k ≥ 1 et i = j, on a, en revanche,

\{X_{n,i}^{(k)} = 1, T = n, Y_{n} = j\} = \{ \begin{matrix}\{Surj(n − 1, [m] \ \{i\}), Y_{n} = i\}, & si k = 1 ; \\ ∅, & si k ≥ 2. \end{matrix}

NOMBRES HYPERHARMONIQUES

Comme T est presque sûrement fini, on a aussi

∑_{n≥1} ∑_{i} P{Surj(n − 1, [m] \ {i}), Y_{n} = i} = 1.

D’où (7.2) G(t) − 1 − t

= ∑_{n≥1} ∑_{k≥1} ∑_{j} ∑_{i≠j} P{Surj(n − 1, [m] \ {j}), X_{n−1,i}^{(k)} = 1, Y_{n} = j} t^{k}

= ∑_{n≥1} ∑_{j} p_{j} ∑_{i≠j} ∑_{k≥1} P{Surj(n − 1, [m] \ {j}), X_{n−1,i}^{(k)} = 1} t^{k}

= ∑_{j} p_{j} ∑_{i≠j} ∑_{n≥1} ∑_{f∈Surj(n−1,[m]\{j})} w_{i}(f),

avec

w_{i}(f) := t^{|f^{−1}(i)|} ∏_{h∈f([n−1])} p_{h}^{|f^{−1}(h)|},

pour chaque fonction f : [n − 1] → [m]. Le principe d’inclusion-exclusion permet d’écrire :

∑_{f∈Surj(n−1,[m]\{j})} w_{i}(f) = ∑_{A⊂[m]\{j}}(−1)^{m−1−|A|} ∑_{f:[n−1]→A} w_{i}(f),

où

∑_{f:[n−1]→A} w_{i}(f) = \{ \begin{matrix}(tp_{i} + ∑_{h∈A\\{i\}} p_{h})^{n−1}, & si i ∈ A; \\ (∑_{h∈A} p_{h})^{n−1}, & si i ∉ A. \end{matrix}

On en tire :

G(t) − 1 − t

= ∑_{j} p_{j} ∑_{i≠j} ∑_{n≥1} ∑_{A⊂[m]\{i,j}}(−1)^{m−1−|A|}(p_{A}^{n−1} − (tp_{i} + p_{A})^{n−1})

= ∑_{j} p_{j} ∑_{i≠j} ∑_{A⊂[m]\\{i,j\}}(−1)^{m−1−|A|}(\frac{1}{1 − p_{A}} − \frac{1}{1 − tp_{i} − p_{A}} ),

d’où la formule (7.1) en sommant sur j et sur le terme 1/(1 − p_{A}).

La formule (7.1) se spécialise évidemment en la formule obtenue pour l’équirépartition. Nous ne reproduisons pas le calcul.

8. Autre méthode de calcul de la fonction génératrice. — Dans le cas de l’équirépartition, la formule (7.2) devient :

G(t) = 1 + t + (m − 1) ∑_{n} ∑_{k≥1} P{Surj(n − 1, [m − 1]), X_{n−1,1}^{(k)} = 1}t^{k}.

Une surjection de l’évènement Surj(n − 1, [m − 1]) est caractérisée par une suite (σ, c, g) := (σ, (c_{1}, …, c_{m−1}), (g_{1}, …, g_{m−1})), où σ est la suite des vignettes telles qu’elles apparaissent pour la première fois, disons aux dates d_{1}, d_{2}, …, d_{m−1} (1 = d_{1} < d_{2} < ⋯ < d_{m−1} ≤ n − 1), les c_{j} sont les nombres d_{2} − d_{1} − 1, d_{3} − d_{2} − 1, …, n − 1 − d_{m−1} et g_{j} est l’application qui envoie l’intervalle [d_{j} + 1, d_{j+1} − 1] (par convention, d_{m} := n) sur l’ensemble des numéros des vignettes déjà sorties (j = 1, …, m − 1). On peut alors écrire

G(t) = 1 + t + (m − 1)(m − 2)!

× ∑_{n} ∑_{k≥1} P{Surj′(n − 1, [m − 1]), X_{n−1,1}^{(k)} = 1}t^{k},

où l’évènement Surj′(n − 1, [m − 1]) est restreint aux seules surjections (σ, c, g) telles que les vignettes 2, 3, …, (m − 1) arrivent dans cet ordre (il y en a bien (m − 2)!). Pour n ≥ m fixé, on a alors

∑_{k≥1} P{Surj′(n − 1, [m − 1]), X_{n−1,1}^{(k)} = 1}t^{k}

= ∑_{c_{1}+···+c_{m−1}=n−m}(\frac{t}{m})^{c_{1}} \frac{1}{m}(\frac{t + 1}{m})^{c_{2}} ⋯ \frac{1}{m}(\frac{t + m − 2}{m})^{c_{m−1}}

− ∑_{c_{2}+···+c_{m−1}=n−m} \frac{1}{m}(\frac{1}{m})^{c_{2}} ⋯ \frac{1}{m}(\frac{m − 2}{m})^{c_{m−1}},

puisque les seules vignettes qui contribuent un facteur t sont les vignettes notées 1 et que la variable t doit apparaître au moins une fois. En sommant cette somme pour n ≥ m, on obtient :

(\frac{1}{m})^{m−2} \frac{1}{1 − t/m} \frac{1}{1 − (t + 1)/m} ⋯ \frac{1}{1 − (t + m − 2)/m} − \frac{1}{(m − 1)!}.

D’où

G(t) = t + \frac{1}{(1 − t/2)(1 − t/3) ⋯ (1 − t/m)},

qui est bien la formule cherchée.

9. Les entiers hyperharmoniques. — Multiplions le nombre harmonique K_{m}^{(k)} par m!^{k}. Par construction, nous obtenons un entier positif, noté

(9.1)  J_{m}^{(k)} := K_{m}^{(k)} m!^{k},

que nous désignons par entier hyperharmonique. Les premières valeurs de ces entiers sont reproduites dans le tableau ci-après.

\begin{matrix}m & 2 & 3 & 4 & 5 & 6 & 7 \\ J_{m}^{(0)} & 1 & 1 & 1 & 1 & 1 & 1 \\ J_{m}^{(1)} & 1 & 5 & 26 & 154 & 1044 & 8028 \\ J_{m}^{(2)} & 1 & 19 & 460 & 15196 & 672336 & 38724624 \\ J_{m}^{(3)} & 1 & 65 & 6920 & 1229704 & 346296384 & 146661388992 \\ J_{m}^{(4)} & 1 & 211 & 95536 & 89222896 & 157188439296 & 483005642823936 \\ J_{m}^{(5)} & 1 & 665 & 1254176 & 6060649504 & 65990223258624 & ⋯ \\ J_{m}^{(6)} & 1 & 2059 & 15958720 & 394810588096 & 26339109589241856 & ⋯ \end{matrix}

Une de nos premières tâches a été de regarder si certaines lignes, colonnes ou diagonales de ce tableau figurent déjà dans l’On-Line Encyclopedia of Integer Sequences de Sloane. Dans cette encyclopédie en ligne, on trouve, en effet, la ligne se référant aux entiers J_{m}^{(1)} (m ≥ 2) et les colonnes se rapportant aux entiers J_{3}^{(k)} (k ≥ 0) et J_{4}^{(k)} (k ≥ 0). Sloane indique que le développement

(9.2) (1 − x)^{−2} ln(1/(1 − x)) = x + \frac{x^{2}}{2!} 5 + \frac{x^{3}}{3!} 26 + \frac{x^{4}}{4!} 154 + \frac{x^{5}}{5!} 1044 + ⋯

apparaît dans un article des Mitrinović (1962), qui en ont donné une interprétation combinatoire en termes de nombres de Stirling généralisés. On voit que le précédent développement s’obtient par dérivation, par rapport à s, de l’identité (2.3). Le membre de droite de (9.2) est donc

égal à ∑_{m≥2} J_{m}^{(1)} x^{m−1}/(m − 1)!

Par ailleurs, la série

(9.3) \frac{1}{(1 − 2x)(1 − 3x)} = 1 + 5x + 19x^{2} + 65x^{3} + 211x^{4} + 665x^{5} + ⋯

apparaît dans un article de Kreweras (1969), qui en a donné une interprétation en termes de relations binaires connexes. C’est naturellement, d’après l’identité (1.5), un développement qui est égal à : ∑_{k≥0} J_{3}^{(k)}x^{k} (cf. colonne m = 3 dans le tableau précédent). Enfin, la colonne m = 4, dont la fonction génératrice, d’après l’identité (1.5), est égale à

\frac{1}{(1 − 4! x/2)(1 − 4! x/3)(1 − 4! x/4)},

est simplement dans la liste de l’encyclopédie sans référence particulière.

10. Une asymptotique pour les nombres hyperharmoniques. Cette asymptotique découle, évidemment, de l’asymptotique des nombres harmoniques généralisés. Nous tenons simplement à indiquer comment on peut l’obtenir à l’aide des formules de changement de base des fonctions symétriques homogènes complètes aux fonctions symétriques de puissances p_{k} = ∑ x_{i}^{k} (cf. Macdonald (1995) p. 28). Pour m fixé, le nombre K_{m}^{(k)} est la fonction symétrique homogène complète h_{k} de degré k en les variables \frac{1}{2}, …, \frac{1}{m}.

D’abord, K_{m}^{(1)} = h_{1} = p_{1} et p_{1} − ln m tend vers γ − 1 ≈ −0, 4227, où γ est la constante d’Euler. D’où K_{m}^{(1)}/ ln m tend vers 1. D’autre part, pour k ≥ 2, on a p_{k} → ζ(k) − 1. Comme

K_{m}^{(k)} = h_{k} = \frac{1}{k!}p_{1}^{k} + ∑ a(i_{1}, i_{2}, …, i_{k}) p_{1}^{i_{1}}p_{2}^{i_{2}} ⋯ p_{k}^{i_{k}},

où la somme est sur toutes les suites (i_{1}, i_{2}, …, i_{k}) d’entiers telles que 1 · i_{1} + 2 · i_{2} + ⋯ + k · i_{k} = k et i_{2} + ⋯ + i_{k} ≥ 1, on a, pour chaque terme de cette somme,

\frac{p_{1}^{i_{1}}p_{2}^{i_{2}} ⋯ p_{k}^{i_{k}}}{(ln m)^{i_{1}}(ln m)^{i_{2}+···+i_{k}}} → 0.

D’où

(10.1)  \frac{k! K_{m}^{(k)}}{(ln m)^{k}} → 1  (m → +∞).

Connaissant les valeurs de la fonction ζ en les entiers et aussi les coefficients de la matrice de passage de la base des h_{λ} à la base des p_{λ}, on peut aussi obtenir les formules asymptotiques suivantes, où les constantes sont des valeurs approchées :

K_{m}^{(1)} ≈ ln m − 0, 4227;
K_{m}^{(2)} ≈ 0, 5 ln^{2} m − 0, 4227 ln m + 0, 4118;
K_{m}^{(3)} ≈ 0, 1666 ln^{3} m − 0, 2113 ln^{2} m + 0, 4118 ln m − 0, 0815;
K_{m}^{(4)} ≈ 0, 0417 ln^{4} m − 0, 0704 ln^{3} m + 0, 2059 ln^{2} m
− 0, 0815 ln m + 0, 0742.

Remerciements. — Les auteurs remercient Aimé Fuchs de leur avoir communiqué la méthode des martingales pour le calcul de 𝔼[X_{T}^{(1)}] d’après la version qu’en avait donnée Giorgio Letta. Ils remercient aussi Philippe Flajolet, qui a attiré leur attention sur les variations des nombres harmoniques généralisés et les travaux de Bentley et al. (1978) et Buchta (1989), ainsi que Christian Krattenthaler pour sa relecture attentive.

BIBLIOGRAPHIE

Banderier, Cyril ; Dobrow, Robert P. (2000). — A Generalized Cover Time for Random Walks on Graphs, Proc. FPSAC’00, Springer-Verlag.

Bauer, Heinz (1995). — Wahrscheinlichkeitstheorie. — Walter de Gruyter, Berlin.

Bentley, J.L. ; Kung, H.T. ; Schkolnick, M. ; Thompson, C.D. (1978). On the average number of maxima in a set of vectors and applications, J. ACM, 25, p. 536–543.

Bergeron, François ; Labelle, Gilbert ; Leroux, Pierre (1994). — Théorie des espèces et combinatoire des structures arborescentes. — Publ. LACIM, vol. 19, Montréal.

Boneh, Arnon ; Hofri, Micha (1997). — The coupon-collector problem revisited—a survey of engineering problems and computational methods, Comm. Statist. Stochastic Models, 13, no. 1, p. 39–66.

Buchta, Christian (1989). — On the average number of maxima in a set of vectors, Information Proc. Letters, 33, p. 63–65.

Cartier, Pierre (2000). — Mathemagics, Sém. Lothar. Combin., B44d,

71 pp. (http://www.mat.univie.ac.at/∼slc/).

Feller, William (1968). — An Introduction to Probability Theory and its Applications, Third edition, vol. 1. — John Wiley & Sons, New York.

Flajolet, Philippe ; Gardy, Danièle ; Thimonier, Loÿs (1992). — Birthday paradox, coupon collectors, caching algorithms and self-organizing search, Discrete Appl. Math., 39, p. 207–229.

Flajolet, Philippe ; Labelle, Gilbert ; Laforest, Louise ; Salvy, Bruno (1995). — Hypergeometrics and the Cost Structure of Quadtrees, Random Structures and Algorithms, 7, p. 117–144.

Foata, Dominique (1974). — La série génératrice exponentielle dans les problèmes d’énumération. — Les Presses de l’Université de Montréal, Montréal.

Graham, Ronald L. ; Knuth, Donald E. ; Patashnik, Oren (1989). Concrete Mathematics. — Addison-Wesley, Reading.

Kreweras, Germain (1969). — Inversion des polynômes de Bell bidimensionnels et application au dénombrement des relations binaires connexes, C. R. Acad. Sci. Paris Ser. A-B, 268, A577-A579.

Lass, Bodo (2001). — Calcul combinatoire ensembliste. Thèse doctorat Aachen-Strasbourg, en préparation.

Letta, Giorgio (1992). — Communication personnelle à Aimé Fuchs. Macdonald, I. G. (1995). — Symmetric Functions and Hall Polynomi-

als, Second Edition. — Clarendon Press, Oxford.

Mitrinović, D. S., Mitrinović, R. S. (1962). — Tableaux d’une classe de nombres reliés aux nombres de Stirling, Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz., 77, 77 pp.

Pintacuda N. (1980). — Coupon Collectors via the Martingales, Boll. Un. Mat. Ital. A, 17, p. 174–177.

Sloane, Neil, J. A. — On-Line Encyclopedia of Integer Sequences,

http://www.research.att.com/∼njas

Strehl, Volker (2001a). — Calcul automatique des identités hypergéométriques, Colloquium, Univ. Louis Pasteur, Strasbourg.

Strehl, Volker (2001b). — Ten years of special function computer algebra, Sém. Lothar. Combin., en préparation.

Zeilberger, Doron (1990). — Holonomic system approach to special function identities, J. of Computational and Appl. Math., 32, p. 321-368.

Dominique Foata, Bodo Lass et Guo-Niu Han Département de mathématique et I.R.M.A.-C.N.R.S. Université Louis Pasteur 7, rue René-Descartes F-67084 Strasbourg

foata@math.u-strasbg.fr
lass@math.u-strasbg.fr
guoniu@math.u-strasbg.fr