
\catcode'32=9
\magnification=1200

\voffset=1cm
\hoffset=0cm
%\hoffset=1cm
\font\tenpc=cmcsc10
%\font\eightpc=cmcsc8

% Charge des fontes de 8 et 6 points :
\font\eightrm=cmr8
\font\eighti=cmmi8
\font\eightsy=cmsy8
\font\eightbf=cmbx8
\font\eighttt=cmtt8
\font\eightit=cmti8
\font\eightsl=cmsl8
\font\sixrm=cmr6
\font\sixi=cmmi6
\font\sixsy=cmsy6
\font\sixbf=cmbx6

\skewchar\eighti='177 \skewchar\sixi='177
\skewchar\eightsy='60 \skewchar\sixsy='60

% Chargement des fontes AMS

\font\tengoth=eufm10
\font\tenbboard=msbm10
\font\eightgoth=eufm7 at 8pt
\font\eightbboard=msbm8
\font\sevengoth=eufm7
\font\sevenbboard=msbm7
\font\sixgoth=eufm6
\font\fivegoth=eufm5

\newfam\gothfam
\newfam\bboardfam

\catcode`\@=11

\def\raggedbottom{\topskip 10pt plus 36pt
\r@ggedbottomtrue}
\def\pc#1#2|{{\bigf@ntpc #1\penalty
\@MM\hskip\z@skip\smallf@ntpc #2}}

\def\tenpoint{%
  \textfont0=\tenrm \scriptfont0=\sevenrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\tenrm}%
  \textfont1=\teni \scriptfont1=\seveni \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\teni}%
  \textfont2=\tensy \scriptfont2=\sevensy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\tengoth \scriptfont\gothfam=\sevengoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\tengoth}%
  \textfont\bboardfam=\tenbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\tenit
  \def\it{\fam\itfam\tenit}%
  \textfont\slfam=\tensl
  \def\sl{\fam\slfam\tensl}%
  \textfont\bffam=\tenbf \scriptfont\bffam=\sevenbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\tenbf}%
  \textfont\ttfam=\tentt
  \def\tt{\fam\ttfam\tentt}%
  \abovedisplayskip=12pt plus 3pt minus 9pt
  \abovedisplayshortskip=0pt plus 3pt
  \belowdisplayskip=12pt plus 3pt minus 9pt
  \belowdisplayshortskip=7pt plus 3pt minus 4pt
  \smallskipamount=3pt plus 1pt minus 1pt
  \medskipamount=6pt plus 2pt minus 2pt
  \bigskipamount=12pt plus 4pt minus 4pt
  \normalbaselineskip=12pt
  \setbox\strutbox=\hbox{\vrule height8.5pt depth3.5pt width0pt}%
  \let\bigf@ntpc=\tenrm \let\smallf@ntpc=\sevenrm
  \let\petcap=\tenpc
  \normalbaselines\rm}
\def\eightpoint{%
  \textfont0=\eightrm \scriptfont0=\sixrm \scriptscriptfont0=\fiverm
  \def\rm{\fam\z@\eightrm}%
  \textfont1=\eighti \scriptfont1=\sixi \scriptscriptfont1=\fivei
  \def\oldstyle{\fam\@ne\eighti}%
  \textfont2=\eightsy \scriptfont2=\sixsy \scriptscriptfont2=\fivesy
  \textfont\gothfam=\eightgoth \scriptfont\gothfam=\sixgoth
  \scriptscriptfont\gothfam=\fivegoth
  \def\goth{\fam\gothfam\eightgoth}%
  \textfont\bboardfam=\eightbboard \scriptfont\bboardfam=\sevenbboard
  \scriptscriptfont\bboardfam=\sevenbboard
  \def\bboard{\fam\bboardfam}%
  \textfont\itfam=\eightit
  \def\it{\fam\itfam\eightit}%
  \textfont\slfam=\eightsl
  \def\sl{\fam\slfam\eightsl}%
  \textfont\bffam=\eightbf \scriptfont\bffam=\sixbf
  \scriptscriptfont\bffam=\fivebf
  \def\bf{\fam\bffam\eightbf}%
  \textfont\ttfam=\eighttt
  \def\tt{\fam\ttfam\eighttt}%
  \abovedisplayskip=9pt plus 2pt minus 6pt
  \abovedisplayshortskip=0pt plus 2pt
  \belowdisplayskip=9pt plus 2pt minus 6pt
  \belowdisplayshortskip=5pt plus 2pt minus 3pt
  \smallskipamount=2pt plus 1pt minus 1pt
  \medskipamount=4pt plus 2pt minus 1pt
  \bigskipamount=9pt plus 3pt minus 3pt
  \normalbaselineskip=9pt
  \setbox\strutbox=\hbox{\vrule height7pt depth2pt width0pt}%
  \let\bigf@ntpc=\eightrm \let\smallf@ntpc=\sixrm
  \normalbaselines\rm}

\let\bb=\bboard

\tenpoint

% dactylographie fran\c caise 

\catcode`\;=\active
\def;{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font\kern -1.2 
\fontdimen3 \font\fi\string;}

\catcode`\:=\active
\def:{\relax\ifhmode\ifdim\lastskip>\z@\unskip\fi
\penalty\@M\ \fi\string:}

\catcode`\!=\active
\def!{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 
\font\fi\string!}

\catcode`\?=\active
\def?{\relax\ifhmode\ifdim\lastskip>\z@
\unskip\fi\kern\fontdimen2 \font \kern -1.1 \fontdimen3 
\font\fi\string?}

\def\^#1{\if#1i{\accent"5E\i}\else{\accent"5E #1}\fi}
\def\"#1{\if#1i{\accent"7F\i}\else{\accent"7F #1}\fi}

\frenchspacing

% format de sortie 

\newif\ifpagetitre
\newtoks\auteurcourant \auteurcourant={\hfil}
\newtoks\titrecourant \titrecourant={\hfil}

\def\appeln@te{}
\def\vfootnote#1{\def\@parameter{#1}\insert\footins
  \bgroup\eightpoint
  \interlinepenalty\interfootnotelinepenalty
  \splittopskip\ht\strutbox 
  \splitmaxdepth\dp\strutbox \floatingpenalty\@MM
  \leftskip\z@skip \rightskip\z@skip
  \ifx\appeln@te\@parameter\indent \else{\noindent #1\ }\fi
  \footstrut\futurelet\next\fo@t}

\pretolerance=500 \tolerance=1000 \brokenpenalty=5000
\newdimen\hmargehaute \hmargehaute=0cm
\newdimen\lpage \lpage=13.3cm
\newdimen\hpage \hpage=20cm
\newdimen\lmargeext \lmargeext=1cm
\hsize=11.25cm
\vsize=18cm
\parskip 0pt
\parindent=12pt

\def\margehaute{\vbox to \hmargehaute{\vss}}%
\def\margebasse{\vss}

\output{\shipout\vbox to \hpage{\margehaute\nointerlineskip
  \corpsdepage\margebasse}
  \advancepageno \global\pagetitrefalse
  \ifnum\outputpenalty>-20000 \else\dosupereject\fi}

\def\corpsdepage{\hbox to \lpage{\hss\pagetexte\hskip\lmargeext}}
\def\pagetexte{\vbox{\makeheadline\pagebody\makefootline}}
\headline={\ifpagetitre\titleheadline \else
  \ifodd\pageno\rightheadline \else\leftheadline\fi\fi}
\def\leftheadline{\eightpoint\hfil\the\auteurcourant\hfil}
\def\rightheadline{\eightpoint\hfil\the\titrecourant\hfil}
\def\titleheadline{\hfill}
\pagetitretrue

\def\footnoterule{\kern-6\p@
  \hrule width 2truein \kern 5.6\p@} % the \hrule is .4pt high



\let\rmpc=\sevenrm
\def\pd#1#2 {\pc#1#2| }

\def\pointir{\discretionary{.}{}{.\kern.35em---\kern.7em}\nobreak
\hskip 0em plus .3em minus .4em }

\def\resume#1{\vbox{\eightpoint \pc R\'ESUM\'E|\pointir #1}}
\def\abstract#1{\vbox{\eightpoint \pc ABSTRACT|\pointir #1}}

\def\titre#1|{\message{#1}
              \par\vskip 30pt plus 24pt minus 3pt\penalty -1000
              \vskip 0pt plus -24pt minus 3pt\penalty -1000
              \centerline{\bf #1}
              \vskip 5pt
              \penalty 10000 }

\def\section#1|{\par\vskip .3cm
                {\bf #1}\pointir}

\def\ssection#1|{\par\vskip .2cm
                {\it #1}\pointir}

\long\def\th#1|#2\finth{\par\medskip
              {\petcap #1\pointir}{\it #2}\par\smallskip}

\long\def\tha#1|#2\fintha{\par\medskip
                    {\petcap #1.}\par\nobreak{\it #2}\par\smallskip}
\def\cf{{\it cf}}

\def\rem#1|{\par\medskip
            {{\it #1}\pointir}}

\def\rema#1|{\par\medskip
             {{\it #1.}\par\nobreak }}

%
\def\ieme{\raise 1ex\hbox{\pc{}i\`eme|}}
\def\omini{\raise 1ex\hbox{\pc{}o|}}
\def\emini{\raise 1ex\hbox{\pc{}e|}}
\def\ermini{\raise 1ex\hbox{\pc{}er|}}
\def\remini{\raise 1ex\hbox{\pc{}re|}}

%reference pour un article :
\def\article#1|#2|#3|#4|#5|#6|#7|
    {{\leftskip=7mm\noindent
     \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3, {\sl #4}, t.\nobreak\ {\bf #5}, {\oldstyle #6},
     p.\nobreak\ #7.\par}}
%reference pour un livre :
\def\livre#1|#2|#3|#4|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
    \llap{[#1]\hskip.35em}{#2}\pointir
    {\sl #3}\pointir #4.\par}}
%reference complementaire :
\def\divers#1|#2|#3|
    {{\leftskip=7mm\noindent
    \hangindent=2mm\hangafter=1
     \llap{[#1]\hskip.35em}{#2}\pointir
     #3.\par}}
%
\mathchardef\conj="0365
\def\dem{\par{\it D\'emonstration}\pointir}
\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

\def\virg{\raise 2pt\hbox{,}}   % virgule apr\`es une fraction

\def\cqfd{\penalty 500 \hbox{\qed}\par\smallskip}

\long\def\entourer#1{\hbox{\vrule\vbox{\hrule\hbox{\kern15pt\vbox{\kern5pt
{#1}\kern5pt}\kern15pt}\hrule}\vrule}}
\def\\S {\vskip 5pt\hskip .5cm plus .1cm minus .1cm\relax}

\def\decale#1|{\par\noindent\hskip 28pt\llap{#1}\kern 5pt}
\def\decaledecale#1|{\par\noindent\hskip 34pt\llap{#1}\kern 5pt}

\def\titrea#1|#2|{\message{#1 #2}
  \par\vskip.5cm plus .1cm minus .1cm\penalty -1000
  \centerline{\bf #1}
  \centerline{\bf #2}
  \vskip 5pt
  \penalty 10000 }
\def\sectiona#1|{\par\vskip .3cm
  {\bf #1.}
  \par\nobreak\vskip 3pt }
\def\ssectiona#1|{\par\vskip .2cm
  {\it #1}
  \par\nobreak\vskip 2pt }

\def\rest#1{\ifinner\setbox1=\hbox{$\textstyle{#1}$}
            \else\setbox1=\hbox{$\displaystyle{#1}$}\fi
            \dimen1=\ht1
            \advance\dimen1 by\dp1
            \divide\dimen1 by 2
            \box1\lower 2pt\hbox{$\left|\vbox to\dimen1{}\right.$}}

\def\lfq{\leavevmode\raise.3ex\hbox{$\scriptscriptstyle
\langle\!\langle$}\thinspace}
\def\rfq{\leavevmode\thinspace\raise.3ex\hbox{$\scriptscriptstyle
\rangle\!\rangle$}}

\def\matrice#1{\left(\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\right)}

\def\petitematrice#1{\left(\null\vcenter {\normalbaselines \m@th
\ialign {\hfil $##$\hfil &&\thinspace  \hfil $##$\hfil\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip } #1\crcr
\mathstrut \crcr \noalign {\kern -\baselineskip }}}\right)}

\catcode`\@=12

\def\Pr{{\rm P}}

\def\card{\mathop{\rm card}}
\def\Log{\mathop{\rm Log}}
\def\Var{\mathop{\rm Var}}
\def\Cov{\mathop{\rm Cov}}
\def\Fr{{\rm F}}
\def\bfx{{\bf x}}

\def\Esp{{\bboard E}}

\def\sep{\,|\,} \def\cond{\,|\,}

\auteurcourant={D. FOATA, G.-N. HAN, B. LASS}
\titrecourant={NOMBRES HYPERHARMONIQUES}
\ifnum\day<0 \advance\day by 160 \fi

\def\fdate{\number\day\space
   \ifcase\month\or janvier\or f\'evrier\or 
mars\or avril\or mai\or 
   juin\or juillet\or ao\^ut\or septembre\or 
octobre\or novembre\or
   d\'ecembre\fi\space\number\year}

\def\Surj{\mathop{\rm Surj}\nolimits}
\def\surj{\mathop{\rm surj}\nolimits}
\def\bfn{{\bf n}}
\raggedbottom
\vglue 2.5cm
\bigskip\bigskip
\centerline{\bf Les nombres hyperharmoniques et}
\smallskip
\centerline{{\bf la fratrie du collectionneur de 
vignettes} \footnote{$(^*)$}{English title:
{\sl The hyperharmonic numbers and the phratry of the coupon
collector}.\hfil\break
\strut\hfil\break
\quad AMS 2000 Classification: 05A15, 05E05, 60C05,
60G42.\hfil\break\strut\hfil\break
\quad Keywords: Hyperharmonic numbers, Coupon
collector's problem, Surjection calculus, Formal Laplace Transform,
Finite-difference equations.} }
\bigskip
\centerline{\sl Dominique Foata, Guo-Niu Han et Bodo Lass}

\bigskip\bigskip

{\eightpoint
{\narrower\narrower
\noindent
{\bf R\'esum\'e}\pointir
Le probl\`eme traditionnel du collectionneur de vignettes
est prolong\'e au cas o\`u le collectionneur fait partager sa
moisson avec les membres de sa fratrie. Il reste le seul
acheteur, mais donne \`a ses fr\`eres les images qu'il obtient en
double. Quand son album est fini, les albums de ses fr\`eres ont
un certain nombre d'emplacements vides. En moyenne, combien ?
Nous apportons une r\'eponse \`a cette question et obtenons, en
outre, une expression pour la fonction g\'en\'eratrice multivari\'ee des
variables al\'eatoires en question. Le probl\`eme fait appara\^\i
tre les nombres hyperharmoniques, qu'il faut \'etudier sous
certains aspects, comme solutions d'\'equations aux diff\'erences
notamment.

\medskip
\noindent
{\bf Abstract}\pointir
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 finite-difference equations.

\bigskip
}
}

\section 1. Introduction|Le probl\`eme du collectionneur de
vignettes (\lfq coupon collector's problem\rfq) est un vieux
probl\`eme \'etudi\'e en Calcul des Probabilit\'es (voir Feller (1968)).
Chaque tablette de chocolat d'une marque donn\'ee contient une
vignette, qui peut \^etre coll\'ee dans un album. Celui-ci contient
$m$ emplacements qui correspondent aux $m$ vignettes \'edit\'ees.
Il s'agit d'estimer le nombre moyen de tablettes que doit
acheter un collectionneur pour remplir son album. Naturellement,
toutes les vignettes sont diff\'erenci\'ees et \`a chaque achat le
collectionneur a la probabilit\'e $1/m$ d'obtenir une vignette
donn\'ee. S'il a d\'ej\`a cette vignette, il la jette, s'il ne l'a pas, il la
colle dans son album \`a l'emplacement r\'eserv\'e pour celle-ci. Soit
$H_m$ le {\it nombre harmonique} d\'efini par
$H_m:=\displaystyle 1+{1\over 2}+\cdots +{1\over m}$, suivant
l'appellation d\'esormais classique (voir
Graham et al. (1989), \S\kern 2pt 6.3). On d\'emontre facilement,
par diverses m\'ethodes (simple comptage, en b\^atissant une 
cha\^\i ne de Markov adapt\'ee, \dots\thinspace) que le nombre 
moyen d'achats est : $m\,H_m$.

On doit \`a Pintacuda (1980) de s'\^etre int\'eress\'e au {\it
fr\`ere} du collectionneur, celui qui n'ach\`ete pas de vignette, mais
les re\c coit de son grand fr\`ere, lorsque celui-ci a des doublons.
Il a aussi un album, o\`u il colle les vignettes obtenues. Le
probl\`eme est alors d'estimer le nombre moyen d'emplacements
vides dans son album, lorsque son grand fr\`ere a termin\'e son
propre album. En utilisant le th\'eor\`eme des temps d'arr\^et pour les
martingales, Pintacuda ({\it op. cit.}) montre que ce nombre moyen
vaut $H_m$. 

Nous devons \`a notre coll\`egue Fuchs de nous avoir expliqu\'e la
m\'ethode probabiliste de Pintacuda, telle qu'elle lui avait
\'et\'e rapport\'ee par Letta (1992), pour trouver cette derni\`ere
valeur. Une discussion s'est alors engag\'ee entre les trois auteurs,
laquelle les a conduit \`a penser que ce probl\`eme, bien que tomb\'e
dans l'escarcelle des probabilistes, m\'eritait 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\'erer qu'un seul petit fr\`ere ?

Dans le probl\`eme de la fratrie, le collectionneur est l'a\^\i n\'e de
la famille, il a $r$ fr\`eres et reste toujours le seul acheteur.
Chaque fr\`ere 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\^\i n\'e
ach\`ete une tablette et qu'il obtient une nouvelle vignette, il la
colle dans son album. Sinon, il la donne au plus \^ag\'e de ses
fr\`eres. Si celui-ci n'a pas encore cette vignette, il la colle dans
son album ; sinon, il la donne au fr\`ere suivant, et ainsi de
suite. Si donc une vignette appara\^\i t plus de~$r$ fois avant que
l'a\^\i n\'e ait fini son album, cette vignette ira \`a la poubelle !

Soit~$T$ le nombre de tablettes que doit acheter l'a\^\i n\'e pour
compl\'eter son album. A cet instant, les fr\`eres, \`a qui on donne
les num\'eros 1, 2, \dots~,~$r$, ont encore, respectivement,
$M_T^{(1)}$, $M_T^{(2)}$, \dots~, $M_T^{(r)}$ emplacements
vides dans leurs albums. On sait que $\Esp[T]=m\,H_m$ et
$\Esp[M_T^{(1)}]=H_m$, d'apr\`es Pintacuda. Nous nous proposons de 
retrouver ce dernier r\'esultat, mais aussi d'\'etablir, pour $k\ge
2$, que l'on a 
$$
\Esp[M_T^{(k)}]=1+K^{(1)}_m+\cdots+K^{(k)}_m,\leqno(1.1)
$$
o\`u, pour tout $k\ge 0$ et $m\ge 1$, le nombre $K^{(k)}_m$ est
le {\it nombre hyperharmonique}, d\'efini par les relations 
suivantes :
$$\displaylines{\rlap{(1.2)}\hfill
K_1^{(k)}:=0,\ {\rm pour\ tout\ }k\ge 1;\quad
K_m^{(0)}:=1,\ {\rm pour\ tout\ }m\ge 1;\hfill\cr
\noalign{\hbox{et pour $k\ge 1$ et $m\ge 2$}}
\rlap{(1.3)}\hfill
K_m^{(k)}:={K_2^{(k-1)}\over 2}+\cdots+
{K_{m-1}^{(k-1)}\over m-1}
+{K_m^{(k-1)}\over m},\hfill\cr
\noalign{\hbox{que l'on peut encore r\'ecrire :}}
\rlap{(1.4)}\hfill
K_m^{(k)}-{K_m^{(k-1)}\over m}=K_{m-1}^{(k)}.\hfill\cr}
$$
En particulier, pour $k\ge 0$, on a : 
$K_2^{(k)}=1/2^k$.
Le tableau suivant donne une liste des premi\`eres valeurs de ces
nombres.

{\eightpoint
$$
\vbox{
\offinterlineskip
\halign{\strut\hfil$#$\hfil\ \vrule
&\ \hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil\kern4pt 
&\hfil$#$\hfil
\cr
m&1&2&3&4&5&10&15&20&25&30&35&40&45&50\cr
\noalign{\hrule}
K_m^{(0)}&\bf 1&\bf 1&\bf 1&\bf 1&\bf 1&\bf 1&\bf 1&\bf 1
&\bf 1&\bf 1&\bf 1&\bf 1&\bf 1&\bf 1\cr
K_m^{(1)}&0&0,\!50&0,\!83&\bf 1,\!08&\bf 1,\!28
&\bf 1,\!93&\bf 2,\!31
&\bf 2,\!60&\bf 2,\!82&\bf 3,\!00&\bf
3,\!15&\bf 3,\!28&\bf 3,\!39&\bf 3,\!50\cr
K_m^{(2)}&0&0,\!25&0,\!53&0,\!80&1,\!06&\bf 2,\!14&\bf  2,\!98
&\bf 3,\!67&\bf 4,\!27&\bf 4,\!79&\bf
5,\!26&\bf 5,\!68&\bf 6,\!07&\bf 6,\!43\cr
K_m^{(3)}&0&0,\!13&0,\!30&0,\!50&0,\!71&1,\!79&2,\!82
&\bf 3,\!76&\bf 4,\!64&\bf 5,\!46&\bf 6,\!23&\bf 6,96&
\bf 7,\!65&\bf 8,\!30\cr
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&\bf 8,\!47\cr
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\cr
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\cr }}
$$

}
Comme tous les nombres $K_m^{(0)}$ valent~1, on a :
$$
K_m^{(1)}=H_{m}-1\quad (m\ge 1).
$$
On a ainsi \lfq harmonicis\'e\rfq\ la suite dont tous les termes
sont \'egaux \`a~1, pour obtenir la suite des nombres harmoniques
(diminu\'es d'une unit\'e). L'appellation {\it hyperharmonique}
vient du fait que pour obtenir la suite
$K^{(k)}_m$ $(m\ge 2)$, on
\lfq harmonicise\rfq, de la m\^eme fa\c con, la suite
$K^{(k-1)}_m$ $(m\ge 2)$. 

En utilisant les s\'eries g\'en\'eratrices, la r\'ecurrence (1.4)
s'\'ecrit sous la forme :
$$\displaylines{
(1-t/m) \cdot \sum_{k \ge 0} K_m^{(k)} t^k = 
\sum_{k \ge 0} K_{m-1}^{(k)} t^k.\cr
\noalign{\hbox{Puisque $\sum\limits_{k \ge 0} K_{1}^{(k)} t^k = 1$,
on obtient :}}
\rlap{(1.5)}\hfill
\sum_{k \ge 0} K_m^{(k)} t^k = 
{1 \over (1-t/2) (1-t/3) \cdots (1-t/m)}.\hfill\cr}
$$

Dans le pr\'esent article, nous nous proposons de 
red\'emontrer le r\'esultat $\Esp[M_T^{(1)}]=H_m$ de Pintacuda, puis
d'\'etablir les formules~(1.1). En plus, nous donnons une expression
pour la {\it distribution} (voir Proposition~4.1) du vecteur
al\'eatoire  $(T,M_T^{(1)},M_T^{(2)},\ldots, M_T^{(r)})$, d'o\`u l'on
tire la distribution de chacune des variables et naturellement leurs
esp\'erances math\'ematiques. En fait, nous pr\'ef\'erons introduire
une suite de variables al\'eatoires $(X_T^{(k)})$ $(k=1,2,\ldots\,)$
telles que, pour tout $k\ge 1$, on ait :
$$
M_T^{(k)}=X_T^{(1)}+X_T^{(2)}+\cdots+X_T^{(k)},
$$
calculons la fonction g\'en\'eratrice du vecteur
$(T,X_T^{(1)},X_T^{(2)},\ldots, X_T^{(r)})$, puis montrons que
$$
\Esp[X_T^{(1)}]=1+K_m^{(1)}=H_m;\quad 
\Esp[X_T^{(k)}]=K_m^{(k)}\quad{\rm pour}\ k\ge 2.
\leqno(1.6)
$$

Le calcul de la fonction g\'en\'eratrice multivari\'ee fait appel
aux techniques classiques de la Combinatoire \'Enum\'erative, en
particulier, des propri\'et\'es de la {\it transformation de Laplace
formelle}. La m\'ethode de Pintacuda est reprise ensuite dans le cas
de la fratrie, pour permettre d'obtenir deux  autres d\'emonstations
des formules~(1.1). En fait, cette technique du th\'eor\`eme des temps
d'arr\^et pour les martingales ne fournit qu'une
{\it \'equation aux diff\'erences} pour les temps moyens.  La partie
la plus d\'elicate n'est plus probabiliste : elle consiste \`a trouver
une solution de cette {\it \'equation aux diff\'erences} et l\`a, il
n'existe pas de m\'ethode universelle. 

Nous donnons encore deux autres m\'ethodes de calcul, permettant
d'obtenir directement la fonction g\'en\'eratrice des nombres moyens
$\Esp[X_T^{(k)}]$. La premi\`ere de ces m\'ethodes fournit m\^eme
une formule dans le cas o\`u la vente des vignettes n'est plus
uniforme, o\`u la probabilit\'e d'acheter la vignette~$i$
est~$p_i>0$ $(p_1+\cdots+p_m=1)$. Comme on le verra, toutes
les m\'ethodes combinatoires d\'evelopp\'ees reposent sur des
d\'enombrements de {\it surjections}.

Nous terminons l'article par une \'etude asymptotique
des nombres hyperharmoniques. Comme il est bien connu, le nombre
harmonique $H_m$ est asymptotiquement \'equivalent \`a $\ln m$. On
montre que le nombre $k!\,K_m^{(k)}$ est asymptotiquement
\'equivalent \`a $(\ln m)^k$.

D\'ej\`a Feller (1968, p. 225) \'ecrivait qu'il y avait une \lfq
\'enorme litt\'erature traitant de variantes du probl\`eme du
collectionneur de vignettes\rfq. En consultant {\it MathSciNet}, nous
nous sommes rendu compte que cet int\'er\^et n'avait pas d\'ecru.
Pas moins de dix-sept titres. Ce mod\`ele a trouv\'e des applications
en informatique (Flajolet et al. (1992), Banderier et al. (2000)), mais
aussi en recherche op\'erationnelle (Boneh et al. (1997)). Nous
renvoyons \`a {\it MathSciNet} pour la liste compl\`ete de ces articles.

\goodbreak
\section 2. Les nombres hyperharmoniques|Ils ont \'et\'e d\'efinis en
(1.2) et (1.3), de fa\c con it\'erative. En d\'ecomposant la fraction
rationnelle, qui appara\^\i t dans (1.5), en \'el\'ements simples, on
d\'eduit, pour
$k\ge 0$ et $m\ge 2$, la formule explicite
$$\displaylines{\rlap{(2.1)}\hfill
K_m^{(k)}
=m(m-1)\sum_n {(-m+2)_n\over n!}{1\over (n+2)^{k+1}},\hfill\cr
\noalign{\hbox{o\`u $(a)_n$ d\'esigne la
{\it factorielle montante} :}}
(a)_n:=\cases{1,&si $n=0$ ;\cr
a(a+1)\cdots (a+n-1),&si $n\ge 1$.\cr}\cr}
$$
On reconna\^\i t dans la fraction rationnelle de l'identit\'e
(1.5) la fonction g\'en\'eratrice des {\it fonctions sym\'etriques
homog\`enes compl\`etes} $h_k(x_1,x_2,\ldots\,)$
(\cf. Macdonald (1995) p.~21), lorsque l'on substitue les
fractions $1\over 2$, $1\over 3$, \dots~, $1\over m$ aux
variables $x_1$, $x_2$, \dots~, $x_{m-1}$, ce qui \'etablit
l'identit\'e
$$
K_m^{(k)}=h_k\Bigl({1\over 2},{1\over 3},\ldots, {1\over m}\Bigr).
\leqno(2.2)
$$

On peut \'egalement obtenir une expression pour la fonction
g\'en\'eratrice des nombres $K_m^{(1)}$ $(m\ge 2)$, \`a savoir,
$$
\sum_{m\ge 2}
K_m^{(1)}s^m=(s-1)^{-1}\bigl({\rm ln}(1-s)+s\bigr).\leqno(2.3)
$$

Les propri\'et\'es des nombres $K_m^{(k)}$ donn\'ees dans la
proposition suivante sont faciles \`a \'etablir et donn\'ees sans
d\'emonstration. On observe, en particulier, que les nombres
$K_m^{(k)}$
$(k\ge 0)$ vont d'abord en croissant (valeurs reproduites en gras
dans le tableau de l'introduction).


\tha Proposition 2.1|
\decale{\rm (a)}|Pour tout $m\ge 2$, on a :
$\sum\limits_{k\ge 0}K_m^{(k)}=m$.

\decale{\rm (b)}|Pour tout $k\ge 1$, on a 
$K_m^{(k)}\rightarrow +\infty$, lorsque $m$ tend vers l'infini.

\decale {\rm (c)}|Pour tout $k\ge 1$, on a
$K_m^{(0)}<K_m^{(1)}<\cdots<K_m^{(k)}<m$ pour $m$ assez
grand.
\fintha

\rem Remarque|La r\'ecurrence (1.4), \`a savoir
$K_m^{(k)}-K_m^{(k-1)}/m=K_{m-1}^{(k)}$
$(k\ge 1, m\ge 2)$ appara\^\i t d\'ej\`a 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 {\it diff\'erentes} de
(1.2), \`a savoir :
$K_1^{(k)}:=1$ $(k\ge 1)$ et
$K_m^{(0)}:=1$ $(m\ge 1)$ et obtiennent donc d'autres suites de
nombres. Tous ces nombres, cependant, y compris les nombres
hyperharmoniques, ne sont que des variations des {\it nombres
harmoniques g\'en\'eralis\'es} 
$H_m^{(k)}:=\sum_{1\le j\le m}(1/j^k)$ (\cf. Graham et al.
(1989)).
Une autre extension, avec l'adjonction d'un nouveau param\`etre, a
\'et\'e introduite et utilis\'ee dans Flajolet et al. (1995) dans
l'\'etude statistique des \lfq quadtrees\rfq.

\goodbreak


\section 3. Un calcul de surjections|Le probl\`eme d\'ecrit dans
l'introduc\-tion, bien qu'il ait \'et\'e offert aux probabilistes, a
une tr\`es forte connotation combinatoire. Il s'agit, en fait, de
d\'enombrer des classes particuli\`eres de {\it surjections}. Pour tout
entier~$n$, posons
$[n]:=\{1,2,\ldots,n\}$ et notons $\Surj(l,m)$ l'ensemble des
surjections de $[l]$ sur $[m]$. Si $f$ appartient \`a
$\Surj(l,m)$, pour tout $i\ge 1$, on note $\nu_i(f)$ le nombre
d'\'el\'ements $j\in [m]$ tels que l'image r\'eciproque $f^{-1}(j)$
est de cardinal~$i$. A tout vecteur d'entiers positifs
$\bfn=(n_1,n_2,\ldots\,)$, on associe le sous-ensemble
$\Surj(l,m;\bfn)$ des surjections $f\in \Surj(l,m)$ telles que pour
tout $i\ge 1$ on ait $\nu_i(f)=n_i$ et on note
$\surj(l,m;\bfn)$ le cardinal de $\Surj(l,m;\bfn)$.

Soit $(t,s_1,s_2,\ldots\,)$ une suite infinie de variables
commutatives. Le {\it poids} $\pi(f)$ de~$f$ est d\'efini par :
$\pi(f):=\smash{\prod\limits_{i\ge 1}}s_i^{\nu_i(f)}$ ;
on a ainsi les
relations :
$\sum\limits_i\nu_i(f)=m$ et $\sum\limits_i i\,\nu_i(f)=l$.

L'identit\'e
$$
\leqalignno{
\Bigl(\sum_{i\ge 1}s_i\,{t^i\over i!}\Bigr)^m
&=\sum_{l\ge m} {t^l\over l!}
\sum_{f\in \Surj(l,m)} \pi(f),&(3.1)\cr
\noalign{\hbox{qui peut encore s'\'ecrire}}
\Bigl(\sum_{i\ge 1}s_i\,{t^i\over i!}\Bigr)^m
&=\sum_{l\ge m} {t^l\over l!}
\sum_\bfn\surj(l,m;\bfn) \prod_{i\ge 1} s_i^{n_i},&(3.2)\cr
}
$$
peut \^etre \'etablie par diff\'erentes m\'ethodes, par exemple, par les
techniques du compos\'e partitionnel. Elle est d\'emontr\'ee dans
Foata (1974), p.~59-60. On peut aussi utiliser la technique des
esp\`eces 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;\bfn)$ de
$\Surj(l,m,\bfn)$ form\'e par toutes les surjections~$f$ ayant
la propri\'et\'e suivante :

la restriction $f\mid_{[l-1]}$ de $f$ \`a l'intervalle $[l-1]$
est elle-m\^eme une surjection de $[l-1]$ sur $[m]\setminus
\{f(l)\}$, {\it mais pas} sur $[m]$, i.e. $f(j)\not=f(l)$ pour
$j\le l-1$.


Si donc $f$ est dans $A(l,m;\bfn)$, on a $\nu_1(f)\ge 1$ et son
poids $\pi(f)$ est divisible par~$s_1$. D\'esignons par
$a(l,m;\bfn)$ le nombre des \'el\'ements de $A(l,m;\bfn)$. 

Si $f$ est dans $A(l,m;\bfn)$, posons $g:=f\mid_{[l-1]}$. Alors
$\pi(f)=\pi(g)\,s_1$, comme il a \'et\'e not\'e plus haut. D'autre
part, on a la relation
$$
\sum_{\bfn}\sum_{f\in A(l,m;\bfn)}\pi(f)=m\,s_1\sum_{g\in
\Surj(l-1,m-1)} \pi(g).\leqno(3.3)
$$
On en tire :
$$\displaylines{
\sum_{l\ge m}{t^{l-1}\over (l-1)!}\sum_{\bfn}
\sum_{f\in A(l,m;\bfn)}\pi(f)
=\sum_{l\ge m}{t^{l-1}\over (l-1)!}\times
m\,s_1\kern-20pt\sum_{g\in \Surj(l-1,m-1)}
\pi(g)\cr
\hfill{}=m\,s_1\sum_{k\ge m-1}{t^k\over k!}
\sum_{g\in \Surj(k,m-1)}\pi(g)
=m\,s_1\Bigl(\sum_{i\ge 1}
s_i{t^i\over i!}\Bigr)^{m-1}.\hfill\cr}
$$
Avec $s_i:=1$ pour tout $i\ge r+1$, l'identit\'e
pr\'ec\'edente prend la forme
$$\displaylines{\quad
m\,s_1(e^t-1+t(s_1-1)+{t^2\over 2!}(s_2-1)+
\cdots +{t^r\over r!}(s_r-1))^{m-1}\hfill\cr
\hfill{}
=\sum_{l\ge m}{t^{l-1}\over (l-1)!}\sum_{\bfn}
\sum_{f\in A(l,m;\bfn)}\pi(f).\quad\cr}
$$
En d\'eveloppant le membre de gauche par la formule du
multin\^ome, on en d\'eduit :
$$\displaylines{\quad ms_1\kern-15pt
\sum_{a+b+c_1+\cdots+c_r=m-1}
{m-1\choose a,b,c_1,\ldots,c_r}
e^{at}(-1)^b\prod_{i=1}^r\Bigl({t^i(s_i-1)\over i!}\Bigr)^{c_i}
\hfill\cr
\hfill{}
=\sum_{l\ge m}{t^{l-1}\over (l-1)!}\sum_{\bfn}
\sum_{f\in A(l,m;\bfn)}\pi(f).\quad\cr}
$$
La {\it transformation de Laplace formelle}, $\cal L$, par
rapport \`a la variable~$t$ remplace le terme $d(l)t^l/l!$ d'une
s\'erie par le terme $d(l)t^l$. En particulier,
${\cal L}(e^{at}t^n)=n!\,t^n/(1-at)^{1+n}$. On applique la
transformation~$\cal L$ \`a la derni\`ere identit\'e et on trouve :
$$\displaylines{(3.4)\quad
ms_1t\sum
%_{a+b+c_1+\cdots+c_r=m-1}
{m-1\choose a,b,c_1,\ldots,c_r}
(-1)^b
\left(\prod_{k=1}^r\Bigl({s_k-1\over k!}
\Bigr)^{c_k}\right)\hfill\cr
\hfill{}\times
{t^{\Sigma kc_k}\over (1-at)^{1+\Sigma kc_k}}\,
\,({\textstyle \sum\limits_k}kc_k)!
=\sum_{l\ge m}t^{l}
\sum_{\bfn}a(l,m;\bfn)\prod_{k=1}^r s_k^{n_k}.\quad\cr}
$$

\section 4. La fonction g\'en\'eratrice multivari\'ee|Comme d\'ej\`a
indiqu\'e dans l'introduction, $T$~d\'esigne l'instant o\`u l'a\^\i n\'e
termine son album. Pour chaque~$n=0,1,\ldots$,
notons $X_n^{(0)}$ le nombre d'emplacements vides dans l'album
de l'a\^\i n\'e \`a l'instant~$n$, de sorte que $X^{(0)}_0=m$ et
$X_T^{(0)}=0$. Pour $k=1,2,\ldots$, notons aussi $X_n^{(k)}$ le
nombre de vignettes qui sont apparues exactement~$k$ fois,
jusqu'\`a la date~$n$ incluse. Alors
$\sum\limits_{k\ge 1}X_T^{(k)}=m$. De plus,
le nombre d'emplacements vides
dans l'album du fr\`ere d'indice~$k\ge 1$, \`a cet instant~$T$, 
un nombre qui avait \'et\'e not\'e $M_T^{(k)}$ dans l'introduction,
est \'egal \`a : $M_T^{(k)}=X_T^{(1)}+\cdots+X_T^{(k)}$. 
La distribution du vecteur $(T,M_T^{(1)}, \ldots, M_T^{(r)})$
se d\'eduit donc imm\'ediatement de celle du vecteur
$(T,X_T^{(1)}, \ldots, X_T^{(r)})$. C'est celle-ci que nous
d\'eterminons. 

\goodbreak
Notons $Y_1$, $Y_2$, \dots\ les num\'eros (compris
entre~1 et~$m$) des vignettes que trouve l'a\^\i n\'e dans les achats
successifs de ses tablettes. On suppose ainsi que les $Y_n$
$(n\ge 1)$ sont des variables al\'eatoires ind\'ependantes, chacune
uniform\'ement r\'epartie sur $\{1,2,\ldots,m\}$.
Alors l'a\^\i n\'e finit son album apr\`es
l'achat de la $l$\ieme~tablette et pour chaque $k=1,\ldots,r$, le
nombre $X_n^{(k)}$ de vignettes qui sont apparues
exactement~$k$ fois, jusqu'\`a la date~$n$ incluse est~$n_k$, si
et seulement si l'application $f:i\mapsto Y_i$ $(1\le i\le l)$
est une surjection appartenant \`a $A(l,m;\bfn)$. Cet \'ev\`enement
s'exprime comme $\{T=l,X_T^{(1)}=n_1,\ldots, X_T^{(r)}=n_r\}$
et sa probabilit\'e est \'evidemment \'egale \`a
$a(l,m;\bfn)/m^l$. La proposition suivante est donc une
cons\'equence de la relation~(3.4).

\th Proposition 4.1|La fonction g\'en\'eratrice du vecteur al\'eatoire
$(T,X_T^{(1)},\ldots, X_T^{(r)})$ est donn\'ee par :
$$\displaylines{\sum_{l\ge m,\bfn} 
\Pr\{T=l,X_T^{(1)}=n_1,\ldots, X_T^{(r)}=n_r\}
t^ls_1^{n_1}\ldots s_r^{n_r}\hfill\cr
\hfill{}\!=\!
s_1t\kern-2pt \sum\!\! {m-1\choose a,b,c_1,\ldots,c_r}\!
(-1)^b\!\!\left(\prod_{k=1}^r\Bigl({s_k-1\over k!}\Bigr)^{c_k}
\!\!\!\right)
\!\!
{(t/m)^{\Sigma kc_k}\over (1-at/m)^{1+\Sigma kc_k}}
({\textstyle \sum\limits_k}kc_k)!\cr}
$$
\finth


De cette expression, on retrouve la fonction g\'en\'eratrice usuelle
de~$T$ et donc imm\'ediatement son esp\'erance 
$\Esp[T]=m\,H_m$. Cependant, le~fait important est, qu'une fois
obtenues les fonctions g\'en\'eratrices des variables $X_T^{(k)}$
$(k\ge 1)$, on puisse, gr\^ace \`a
la formule explicite (2.1), {\it sommer} leurs d\'eriv\'ees en~1,  et
ainsi d\'eterminer leurs esp\'erances. En effet, on~a
$$
\leqalignno{\quad
G_{X_T^{(1)}}(s)&:=
\sum_{n\ge 1}\Pr\{X_T^{(1)}=n\}s^n&(4.1)\cr
&=
s\sum_{a+b+c=m-1}
{m-1\choose a,b,c}(-1)^b{m(s-1)^c\over (m-a)^{1+c}}c!\,;\cr
\noalign{\hbox{et pour $k\ge 2$}}
G_{X_T^{(k)}}(s)&:=
\sum_{n\ge 1}\Pr\{X_T^{(k)}=n\}s^n&(4.2)\cr
&=\sum_{a+b+c=m-1}
{m-1\choose a,b,c}(-1)^b{(s-1)^c\over k!^c}
{m\over 
(m-a)^{1+kc}}(kc)!\cr
}
$$
D'o\`u
$$\eqalignno{\Esp[X_T^{(1)}]&=
G'_{X_T^{(1)}}(1)=-\sum_{b=0}^{m-1}{(-m)_{b+1}\over (b+1)!}
+m(m-1)\sum_b{(-m+2)_b\over b!}{1\over (b+2)^2}\cr
&=1+K_m^{(1)}=H_m,\cr}
$$
le r\'esultat d\'ej\`a prouv\'e par Pintacuda (1980). 

\goodbreak
De plus, pour $k\ge 2$, 
$$\leqalignno{\Esp[X_T^{(k)}]&=
G'_{X_T^{(k)}}(1)
=m(m-1)\sum_b{(-m+2)_b\over b!}{1\over (b+2)^{1+k}}
=K_m^{(k)}.\cr
}$$

\section 5. La m\'ethode des martingales|Nous r\'eutilisons la
m\'ethode probabiliste de Pintacuda ({\it op. cit.}), telle qu'elle
nous avait \'et\'e rapport\'ee par Letta, pour l'appliquer au calcul
des nombres moyens $\Esp[X_T^{(k)}]$, pour {\it tout}~$k\ge 1$.
Conservons les notations du paragraphe pr\'ec\'edent et utilisons les
notations suivantes : si $(x^{(0)},\ldots,x^{(r)})$ est un vecteur
de~$r$ composantes r\'eelles, posons, pour $k\ge 0$,
$$
\delta^{(k)}(x^{(0)},\ldots,x^{(r)})
=\cases{(x^{(0)},\ldots,x^{(k)}-1,x^{(k+1)}+1,\ldots,x^{(r)}),&\cr
\kern4cm {\rm si}\  
0\le k\le r-1;\cr
(x^{(0)},\ldots,x^{(r)}-1),\qquad\quad{\rm si}\ k=r;&\cr
(x^{(0)},\ldots,x^{(r)}),\qquad\qquad\kern7pt{\rm si}\ k\ge r+1.&\cr
}
$$
Maintenant si $f$ est une
fonction r\'eelle d\'efinie sur ${\bboard N}^{r+1}$,
formons, pour chaque entier $n\ge 0$, la variable al\'eatoire
$$
V_n:=f(X_n^{(0)},X_n^{(1)}, \ldots, X_n^{(r)}).
$$
Traditionnellement, $W:=V^{\sep T}$ d\'esigne le {\it processus
arr\^et\'e} en~$T$, c'est-\`a-dire la suite des variables
al\'eatoires 
$(W_n)$ $(n\ge 0)$ d\'efinies par :
$$
W_n:=V_{T\wedge n}:=V_n\,I_{\{n<T\}}+V_T\,I_{\{n\ge T\}},
$$
o\`u le symbole $I_A$ d\'esigne l'{\it indicatrice} de l'\'ev\`enement $A$.
Or,
$W_{n+1}-W_n=V_{n+1}\,I_{\{n+1<T\}}+V_T\,I_{\{n+1\ge T\}}
-V_n\,I_{\{n<T\}}-V_T\,I_{\{n\ge T\}}
=(V_{n+1}-V_n)\,I_{\{n<T\}}
+V_{n+1}(I_{\{n+1<T\}}-I_{\{n<T\}})
+V_T(I_{\{n+1\ge T\}}-I_{\{n\ge 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 $\Delta W_n:=W_{n+1}-W_n$, est le m\^eme que
l'accroissement $\Delta V_n$ des~$V_n$, tant que l'album de l'a\^\i n\'e
n'est pas termin\'e, soit
$$
\Delta W_n=\Delta V_n\,I_{\{X_n^{(0)}>0\}}.
$$

Consid\'erons la variation du vecteur
$X_n:=(X_n^{(0)},X_n^{(1)}, \ldots, X_n^{(r)})$ de l'instant~$n$ \`a
l'instant $(n+1)$. Si la vignette achet\'ee \`a l'instant~$(n+1)$
a d\'ej\`a \'et\'e acquise $k\ge 0$~fois pr\'ec\'edemment,
alors
$$
X_{n+1}
=\delta^{(k)}X_n.
$$
Les \'ev\`enements
$\{\Delta X_{n}^{(k)}=-1\}$  $(0\le k\le r)$ et
$\{\Delta X_n=0\}$ forment ainsi un syst\`eme complet
d'\'ev\`e\-ne\-ments. On peut donc \'ecrire 
$$
\Delta V_n=\sum_{k=0}^r
I_{\{\Delta X_{n}^{(k)}=-1\}}
\bigl(f(\delta^{(k)}X_n)
-f(X_n)\bigr)
$$
puisque $\Delta V_n\,I_{\{\Delta X_n=0\}}=0$.

Comme l'\'ev\`enement
$\{\Delta X_{n}^{(k)}=-1\}$ est r\'ealis\'e si et seulement si la
vignette, achet\'ee \`a
l'instant $(n+1)$, a \'et\'e pr\'ec\'edemment acquise $k$~fois
$(0\le k\le r)$, l'esp\'erance conditionnelle de la variable
$I_{\{\Delta X_{n}^{(k)}=-1\}}$, par rapport \`a la suite 
$(Y_0,Y_1,\ldots, Y_n)$ est simplement
$X^{(k)}_n/m$. (Par convention, $Y_0:=0$.)

L'esp\'erance conditionnelle de la variation $\Delta V_n$, par
rapport \`a la suite $(Y_0,Y_1,\ldots, Y_n)$, est donc \'egale \`a :
$$
\Esp[\Delta V_n\sep Y_0,\ldots, Y_n]
=\sum_{k=0}^r
{X_{n}^{(k)}\over m}
\bigl(f(\delta^{(k)}X_n)
-f(X_n)\bigr).
$$
Supposons que l'on trouve une fonction~$f$ telle que cette
expression soit nulle. Alors, on aura aussi
$\Delta W_n=0$ et~$W$ sera une {\it martingale} (consulter, par
exemple, Bauer (1995), \S\kern2pt17).

\th Proposition 5.1|Supposons que pour chaque $k=1,\ldots,r$ il
existe une fonction r\'eelle $f^{(k)}$, d\'efinie sur ${\bboard
N}^{k+1}$, ayant les propri\'et\'es suivantes :

{\rm (a)}
$\displaystyle
\sum_{i=0}^k
x_i\bigl(f^{(k)}(\delta^{(i)}(x_0,\ldots,x_k))
-f^{(k)}(x_0,\ldots,x_k)\bigr)=0$ pour $x_0\ge 1$ ;

{\rm (b)} $f^{(k)}(0,x_1,\ldots,x_k)=x_k$.

\smallskip
\noindent
Alors, $\Esp[X^{(k)}_T]=f^{(k)}(m,0,\ldots,0)$
pour $k=1,\ldots, r$.
\finth

\dem
En effet, pour tout $k=1,\ldots, r$, on a
$W_0=V_0=
f^{(k)}(X_0^{(0)},X_0^{(1)}, \ldots, X_0^{(k)})
=f^{(k)}(m,0,\ldots,0)$ et 
$W_T=V_T=
f^{(k)}(X_T^{(0)},X_T^{(1)}, \ldots, X_T^{(k)})
=f^{(k)}(0,X_T^{(1)}, \ldots, X_T^{(k)})=X_T^{(k)}$, d'apr\`es~(b).
Le th\'eor\`eme d'arr\^et pour les martingales donne alors
$\Esp[X_T^{(k)}]=\Esp[W_T]=\Esp[W_0]
=W_0=f^{(k)}(m,0,\ldots,0)$.\cqfd

\medskip
Lorsque $k=1$, la m\'ethode ci-dessus est due \`a
Pintacuda ({\it op. cit.}). Il a trouv\'e, de plus, pour $k=1$, la
fonction
$f^{(1)}(x_0,x_1):=H_{x_0}+\displaystyle{x_1\over 1+x_0}$.
En effet, la propri\'et\'e~(a) s'\'ecrit, en posant $f:=f^{(1)}$, $x:=x_0$,
$y:=x_1$ :
$$\displaylines{\quad
x(f(x-1,y+1)-f(x,y))+y(f(x,y-1)-f(x,y))\hfill\cr
\kern1cm{}=
x\Bigl(H_{x-1}+{y+1\over x}-H_x-{y\over 1+x}\Bigr)
+y\Bigl(H_x+{y-1\over 1+x}-H_x-{y\over 1+x}\Bigr)\hfill
\cr
\kern1cm{}=
x\Bigl(-{1\over x}+{y+1\over x}-{y\over 1+x}\Bigr)
+y\,{-1\over 1+x}
=y\Bigl(1-{x\over 1+x}-{1\over 1+x}\Bigr)
=0.
\hfill
\cr
}
$$
Aussi, $f(m,0)=H_m$, d'o\`u $\Esp[X_T^{(1)}]=H_m$.

\goodbreak
Pour r\'esoudre le probl\`eme de la fratrie du collectionneur par
cette m\'ethode, il suffit donc de trouver pour chaque
$k=1,2,\ldots,r$ une fonction r\'eelle
$f^{(k)}$ de $(k+1)$ variables enti\`eres
ayant les propri\'et\'es suivantes :

{\rm (a)}
$\displaystyle
\sum_{i=0}^k
x_i\bigl(f^{(k)}(\delta^{(i)}(x_0,\ldots,x_k))
-f^{(k)}(x_0,\ldots,x_k)\bigr)=0$ pour $x_0\ge 1$ ;

{\rm (b)} $f^{(k)}(0,x_1,\ldots,x_k)=x_k$ ;

(c) $f^{(1)}(m,0)=H_m$ (c'est d\'ej\`a fait!), mais pour
$k=2,\ldots,r$ telle que
$f^{(k)}(m,0,\ldots,0)=K_m^{(k)}$. 

\section 6. La solution de l'\'equation aux diff\'erences
finies|R\'esoudre une \'equation aux diff\'erences finies, telle que~(a),
qui plus est, \`a plusieurs variables, n'est pas ais\'e. D'abord,
qu'entend-on par \lfq r\'esoudre\rfq? Selon les canons
traditionnels, il s'agit de trouver une solution qui s'exprime
dans l'alg\`ebre des fonctions sp\'eciales. En l'absence de techniques
universelles, il faut beaucoup t\^atonner. C'est la dure m\'ethode
{\it symbolique} d\'ecrite par Cartier (2000) dans son article de
synth\`ese. D\'ej\`a la solution trouv\'ee
par Pintacuda relevait du {\it deus ex machina}. En fait, une longue
familiarit\'e avec l'\'equation elle-m\^eme va mener \`a la
solution. Nous donnons deux solutions, une solution \lfq locale\rfq \ 
(qui fournit la valeur de $f^{(k)}$),
puis \lfq globale\rfq \ (qui donne l'expression de la fonction
g\'en\'eratrice $\sum_{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
\lfq automatique\rfq.

\ssection $6.1.$ La solution locale| Elle consiste \`a r\'esoudre
l'\'equation~(a), que l'on r\'ecrit sous la forme
$$
\displaylines{(6.1)\ 
(x_0+\cdots+x_k)f^{(k)}(x_0,\ldots, x_k)
=\,\,
\sum_{i=0}^k
x_if^{(k)}(\delta^{(i)}(x_0,\ldots,x_k)),
\cr}
$$
pour chaque $k\ge 2$ avec $x_0\ge 1$. D'apr\`es cette \'equation,
on voit que la valeur de~$f^{(k)}$ en 
$x=(x_0,x_1,\ldots, x_k)$ est parfaitement d\'etermin\'ee, si l'on
conna\^\i t la valeur de~$f^{(k)}$ en tous les points 
$x'=(x'_0,x'_1,\ldots, x'_k)$ plus petits, pour l'{\it ordre
lexicographique}. On voit aussi, par
it\'eration, que chaque $f^{(k)}(x_0,\ldots,x_r)$,
o\`u $x_0+\cdots+x_k\ge 1$, s'exprime, de
fa\c con unique, comme une combinaison lin\'eaire de
valeurs de la forme $f^{(k)}(0,x'_1,\ldots, x'_k)$ avec
$x_1'+\cdots+x_k'\le x_0+x_1+\cdots+x_k$ et $x_k'\ge 1$. Si on
se donne les valeurs de~$f^{(k)}$ en les points $(0,x'_1,\ldots,
x'_k)$, o\`u
$(x'_1,\ldots, x'_k)\in {\bboard N}^k$
et $x_k'\ge 1$, la fonction~$f^{(k)}$ est
{\it parfaitement d\'etermin\'ee}.

\th Proposition 6.1|Pour $k\ge 2$, la fonction~$f^{(k)}$ d\'efinie par
$$\displaylines{(6.2)\quad
f^{(k)}(x_0,x_1,\ldots,x_k)
:=K_{x_0}^{(k)}+
{x_1K_{x_0+1}^{(k-1)}+\cdots+
x_{k-1}K_{x_0+1}^{(1)}+x_k\over x_0+1}\hfill\cr
\qquad\qquad{}:=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\hfill\cr
\hfill{}+\cdots+
(K_{x_0+1}^{(1)}-K_{x_0}^{(1)})x_k\cr
\noalign{\hbox{est l'unique fonction satisfaisant
l'\'equation~$(6.1)$, de conditions initiales}}
f^{(k)}(0,x_1,\ldots, x_k)=x_k,\cr
\noalign{\hbox{pour tout $(x_1,\ldots,x_k)\in {\bboard N}^k$. Elle
satisfait, de plus,}}
f^{(k)}(x_0,0,\ldots,0)=K_{x_0}^{(k)}.\cr}
$$
\finth

\goodbreak
\dem 
L'unicit\'e a d\'ej\`a \'et\'e \'etablie par l'argument pr\'ec\'edant la
proposition. Il suffit donc de v\'erifier que la fonction d\'efinie en
(6.2) satisfait l'\'equation~(6.1). Il s'agit d'une simple
v\'erification, qui utilise pleinement la r\'ecurrence (1.4) des
nombres hyperharmoniques. Nous nous dispensons d'\'ecrire les
d\'etails de cette v\'erification facile.\cqfd


\medskip
Les Propositions 5.2 et 6.1 fournissent ainsi une seconde
d\'emonstration des identit\'es
$\Esp[X^{(k)}_T]=f^{(k)}(m,0,\ldots,0)=K_m^{(k)}$
pour $k=2,\ldots, r$. 

\ssection $6.2.$ La solution globale|On r\'ecrit l'identit\'e (a)
du paragraphe~6 sous la forme
$$
\sum_{i=0}^k x_i\,N_i\, f^{(k)}(x_0,\ldots, x_k)=0,
$$
de sorte que, pour tout $i\ge 0$, on a d\'efini l'op\'erateur
$N_i$ par :
$$
N_i\,f^{(k)}(x_0,\ldots, x_k)
:=f^{(k)}(\delta^{(i)}(x_0,\ldots, x_k))
-f^{(k)}(x_0,\ldots, x_k).
$$
On forme, ensuite, l'alg\`ebre des s\'eries formelles
$f:=\sum\limits_{k\ge 0}f^{(k)}\,t^k$, o\`u chaque
coefficient $f^{(k)}$ est une fonction r\'eelle d\'efinie sur
${\bboard N}^{k+1}$. On prolonge la d\'efinition de~$N_i$ 
\`a cette alg\`ebre, en
posant
$$\displaylines{
N_i\,f:=\sum_{k\ge 0} N_i\,f^{(k)}t^k=
\sum_{k\ge i} N_i\,f^{(k)}t^k,\cr
\noalign{\hbox{puis, on d\'efinit l'op\'erateur :}}
N:=\sum_{i\ge 0}x_i\,N_i.\cr
\noalign{\hbox{Il s'agit alors de r\'esoudre}}
\rlap{(6.3)}\hfill
N\,f=0.\hfill\cr}
$$
D'abord, on \'etudie l'action de~$N$ sur des s\'eries
formelles particuli\`eres. Si $g(x_0)$ est une s\'erie formelle dont
les coefficients~$g^{(k)}(x_0)$ ne d\'ependent que de
l'argument~$x_0$ et si $1\le i\le k$, alors
$N_i\,g^{(k)}(x_0)=0$ ; d'o\`u $N_i\,g(x_0)=\sum\limits_{k\ge
i}N_i\,g^{(k)}(x_0)\,t^k=0$ pour $i\ge 1$. De plus, pour tout
$k\ge 0$, on a :
$N_0\,g^{(k)}(x_0)=g^{(k)}(x_0-1)-g^{(k)}(x_0)$ ; d'o\`u
$N_0\,g(x_0)=g(x_0-1)-g(x_0)$ et
$$
N\,g(x_0)=x_0(g(x_0-1)-g(x_0)).\leqno(6.4)
$$ 
D'autre part, si $s$ est une s\'erie formelle et si $i\ge 1$, on a :
$$
N_i\,g(x_0)s=g(x_0)N_i\,s.\leqno(6.5)
$$
 
L'argument $x_0$ jouant un r\^ole privil\'egi\'e, on cherche une
solution de (6.3) de la forme $f=g(x_0)(h(x_0)+s)$, o\`u $g(x_0)$
et $h(x_0)$ ne d\'ependent que de~$x_0$ et la s\'erie~$s$ que de
$x_1,x_2,\ldots$ La s\'erie~$s$ la plus simple \`a consid\'erer est 
$s:=\smash{\sum\limits_{k\ge 1}} x_k\,t^k$. En \'evaluant
$N\,g(x_0)s$ pour une telle s\'erie, on trouve :
$$
N\,g(x_0)s=x_0
g(x_0-1)s-x_0g(x_0)s+x_0t\,g(x_0-1)+g(x_0)(t-1)s.\leqno(6.6)
$$
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_0g(x_0)(h(x_0)+s)+(t-1)sg(x_0)+
x_0g(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\'eduit
l'\'equation pr\'ec\'edente \`a
$$
{g(x_0)\over g(x_0-1)}={x_0\over x_0+1-t}.
$$
Prenant alors $g(0):=1$, on obtient, par it\'eration,
si $x_0$ est un entier positif,
$$\displaylines{
g(x_0)={1\over (1-t/2)(1-t/3)\cdots (1-t/x_0)(x_0+1-t)}\cr
\noalign{\hbox{et la solution}}
\rlap{(6.7)}\hfill
f=g(x_0)\cdot \bigl((x_0+1)+(x_1-1)t+x_2t^2+x_3t^3+\cdots\,
\bigr).
\hfill\cr } 
$$

\th Proposition 6.2|La s\'erie formelle donn\'ee en $(6.7)$ est solution
de l'\'equation $N\,f=0$ et satisfait les conditions initiales
$f^{(1)}(0,x_1)=x_1-1$ et
$f^{(k)}(0,x_1,\ldots,x_k)=x_k$ pour $k\ge 2$. De plus, avec
$x_0=m$ et les autres
$x_k$ \'egaux \`a~$0$, on obtient
$$
f={1\over (1-t/2)\cdots (1-t/m)}
=\sum_{k\ge 0}K_m^{(k)}t^k.\leqno(6.8)
$$
\finth

\dem
La v\'erification de ces propri\'et\'es a \'et\'e faite 
pr\'e\-c\'e\-dem\-ment et l'identit\'e r\'esulte de (2.2).\cqfd

\medskip
La pr\'ec\'edente proposition donne ainsi une autre d\'emonstration de
$\Esp[X_T^{(k)}]=K_m^{(k)}$ pour $k\ge 2$. Pour $k=1$, on
reprend la d\'emonstration 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\`u
$\Esp[X_T^{(1)}]-1=\Esp[W_T]=\Esp[W_0]=W_0=f^{(1)}(m,0)
=K_m^{(1)}$.
D'o\`u $\Esp[X_T^{(1)}]=K_m^{(1)}+1=H_m$.

\def\bfp{{\bf p}}

\section 7. Distribution non-uniforme des vignettes|On suppose
maintenant qu'\`a tout instant~$n$, la probabilit\'e que la
variable~$Y_n$ soit \'egale \`a~$i$ est un nombre $p_i>0$
$(i=1,2,\ldots,m)$ et non plus n\'ecessairement $1/m$. Par commodit\'e,
pour tout sous-ensemble $A\subset[m]:=\{1,2,\ldots,m\}$, on pose :
$\bfp_A:=\sum_{i\in A}p_i$. Pour 
$k\ge 1$, $n\ge 1$ et $i=1,2,\ldots, m$, on pose 
\'egalement $X_{n,i}^{(k)}:=1$
si la vignette num\'erot\'ee~$i$ est apparue exactement~$k$ fois
jusqu'\`a et y compris la date~$n$ et
$X_{n,i}^{(k)}:=0$, sinon. De l\`a,
$X_{n}^{(k)}=\sum\limits_{1\le i\le m}X_{n,i}^{(k)}$ est le
nombre de vignettes qui sont apparues exactement~$k$ fois jusqu'\`a
et y compris la date~$n$. 

\th Proposition 7.1|Soit $T$ l'instant o\`u l'a\^\i n\'e
termine son album. Alors, la fonction g\'en\'eratrice $G(t)$ des
nombres 
$\Esp[X_{T}^{(k)}]$ est donn\'ee par :
$$
G(t):=1+\sum_{k\ge 1}\Esp[X_{T}^{(k)}]\,t^k
=t + \sum_{i=1}^m \sum_{A \subset [m] \setminus \{i\}}\!\!
(-1)^{m-|A|} {1-p_i-\bfp_A \over 1-tp_i-\bfp_A}.\leqno(7.1)
$$
\finth

\dem
D'abord,
$$\eqalignno{
G(t)&=1+\sum_{k\ge 1}\sum_{1\le i\le m}
\Esp[X_{T,i}^{(k)}]\,t^k
=1+\sum_{k\ge 1}\sum_{1\le i\le m}
\Pr\{X_{T,i}^{(k)}=1\}\,t^k\cr
&=1+\sum_{k\ge 1}\sum_{1\le i\le m}
\sum_{n\ge 1}\sum_{1\le j\le m}
\Pr\{X_{n,i}^{(k)}=1, T=n,Y_n=j\}\,t^k,\cr}
$$
puisque $T$ est presque
s\^urement fini. Pour tout entier $n\ge 1$ et tout sous-ensemble
$A\subset [m]$, notons $\Surj(n,A)$ l'\'ev\`enement 
\lfq $f:l\mapsto Y_l$ est, pour $l=1,2,\ldots, n$, une 
{\it surjection} de
$[n]$ sur~$A$\rfq. Alors, pour $k\ge 1$ et $i\not=j$, l'\'ev\`enement
$\{X_{n,i}^{(k)}=1, T=n,Y_n=j\}$ s'\'ecrit encore
$\{\Surj(n-1,[m]\setminus\{j\}), X_{n-1,i}^{(k)}=1,Y_n=j\}$.
Pour $k\ge 1$ et $i=j$, on a, en revanche,
$$
\{X_{n,i}^{(k)}=1, T=n,Y_n=j\}
=\cases{\{\Surj(n-1,[m]\setminus\{i\}),Y_n=i\},
\kern-7pt&si $k=1$ ;\cr
\noalign{\smallskip}
\emptyset,&si $k\ge 2$.\cr}
$$
Comme $T$ est presque s\^urement fini, on a aussi
$$\displaylines{
\sum_{n\ge 1}\sum_i
\Pr\{\Surj(n-1,[m]\setminus\{i\}),Y_n=i\}=1.\cr
\noalign{\hbox{D'o\`u}}
(7.2)\quad
G(t)-1-t\hfill\cr
\qquad{}
=\sum_{n\ge 1}\sum_{k\ge 1}\sum_{j}
\sum_{i\not=j}
\Pr\{\Surj(n-1,[m]\setminus\{j\}), 
X_{n-1,i}^{(k)}=1,Y_n=j\}\,t^k\hfill\cr
\qquad{}
=\sum_{n\ge 1}\sum_jp_j\sum_{i\not=j}\sum_{k\ge 1}
\Pr\{\Surj(n-1,[m]\setminus\{j\}), X_{n-1,i}^{(k)}=1\}\,t^k
\hfill\cr
\qquad{}=
\sum_jp_j\sum_{i\not=j}\sum_{n\ge 1}\sum_{f\in 
\Surj(n-1,[m]\setminus\{j\})}
w_i(f),\hfill\cr
}
$$
avec
$$
w_i(f):= t^{|f^{-1}(i)|} \prod_{h\in f([n-1])} p_h^{|f^{-1}(h)|},
$$
pour chaque fonction $f:[n-1] \to [m]$. Le principe 
d'inclusion-exclusion 
permet d'\'ecrire :
$$
\sum_{f\in \Surj(n-1,[m]\setminus\{j\})} w_i(f) =
\sum_{A\subset [m]\setminus\{j\}}(-1)^{m-1-|A|}
\sum_{f:[n-1] \to A} w_i(f), 
$$
o\`u
$$
\sum_{f:[n-1] \to A} w_i(f)
=\cases{\displaystyle\Bigl(tp_i+\sum_{h\in
A\setminus\{i\}}p_h\Bigr)^{n-1},&si $i\in A$ ;\cr
\noalign{\smallskip}
\displaystyle\Bigl(\sum_{h\in A}p_h\Bigr)^{n-1},&si $i\not\in
A$.\cr}
$$
On en tire : 
$$\eqalignno{
&G(t)-1-t \cr
&= \sum_jp_j\sum_{i\not=j}\sum_{n\ge 1}\sum_{A\subset 
[m]\setminus\{i,j\}}
   (-1)^{m-1-|A|}\Bigl(\bfp_A^{n-1} - (tp_i + \bfp_A)^{n-1}\Bigr) \cr
&= \sum_jp_j\sum_{i\not=j}\sum_{A\subset [m]\setminus\{i,j\}} 
   (-1)^{m-1-|A|}\Bigl({1 \over 1-\bfp_A}-{1 \over 
1-tp_i-\bfp_A}\Bigr), \cr
}$$
d'o\`u la formule (7.1) en sommant sur~$j$ et sur le terme
$1/(1-\bfp_A)$.\cqfd


\medskip
La formule (7.1) se sp\'ecialise \'evidemment en la
formule obtenue pour l'\'equir\'epartition. Nous ne reproduisons
pas le calcul.

\goodbreak

\def\bfc{{\bf c}}
\def\bfg{{\bf g}}

\section 8. Autre m\'ethode de calcul de la fonction
g\'en\'eratrice|Dans le cas de l'\'equir\'epartition, la formule (7.2)
devient :
$$
G(t)=1+t+(m-1)\sum_n\sum_{k\ge 1}
\Pr\{\Surj(n-1,[m-1]),X_{n-1,1}^{(k)}=1\}t^k.
$$
Une surjection de l'\'ev\`enement $\Surj(n-1,[m-1])$ est
caract\'eris\'ee par une suite $(\sigma,\bfc,\bfg):=
(\sigma,(c_1,\ldots,c_{m-1}),(g_1,\ldots, g_{m-1}))$, o\`u~$\sigma$
est la suite des vignettes telles qu'elles apparaissent pour la
premi\`ere fois, disons aux dates
$d_1,d_2,\ldots, d_{m-1}$ ($1=d_1<d_2<\cdots<d_{m-1}\le n-1$),
les $c_j$ sont les nombres $d_2-d_1-1$, $d_3-d_2-1$, \dots~, 
$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\'eros des vignettes d\'ej\`a sorties $(j=1,\ldots, m-1)$. On peut
alors \'ecrire
$$\displaylines{\quad
G(t)=1+t+(m-1)(m-2)!\hfill\cr
\hfill{}\times \sum_n\sum_{k\ge 1}
\Pr\{\Surj'(n-1,[m-1]),X_{n-1,1}^{(k)}=1\}t^k,\quad\cr}
$$
o\`u l'\'ev\`enement $\Surj'(n-1,[m-1])$ est restreint aux seules
surjections $(\sigma,\bfc,\bfg)$ telles que les vignettes 2, 3, \dots,
$(m-1)$ arrivent dans cet ordre (il y en a bien $(m-2)!$). 
Pour~$n\ge m$
fix\'e, on a alors
$$\displaylines{\quad
\sum_{k\ge 1}
\Pr\{\Surj'(n-1,[m-1]),X_{n-1,1}^{(k)}=1\}t^k\hfill\cr
\hfill{}
=\sum_{c_1+\cdots+c_{m-1}=n-m}
\Bigl({t\over m}\Bigr)^{c_1}
{1\over m}\Bigl({t+1\over m}\Bigr)^{c_2}
\cdots
{1\over m}\Bigl({t+m-2\over m}\Bigr)^{c_{m-1}}\cr
\hfill{}
-\sum_{c_2+\cdots+c_{m-1}=n-m}
{1\over m}\Bigl({1\over m}\Bigr)^{c_2}
\cdots
{1\over m}\Bigl({m-2\over m}\Bigr)^{c_{m-1}},\cr
 }
$$
puisque les seules vignettes qui contribuent un facteur~$t$ sont les
vignettes not\'ees~1 et que la variable~$t$ doit appara\^\i tre au
moins une fois. En sommant cette somme pour
$n\ge m$, on obtient :
$$
\Bigl({1\over m}\Bigr)^{m-2}
{1\over 1-t/m}{1\over 1-(t+1)/m}\cdots {1\over 1-(t+m-2)/m}
-{1\over( m-1)!}.
$$
D'o\`u
$$
G(t)=t+{1\over (1-t/2)(1-t/3)\cdots (1-t/m)},
$$
qui est bien la formule cherch\'ee.


\section 9. Les entiers hyperharmoniques|Multiplions le nombre
harmonique $K^{(k)}_m$ par $m!^k$. Par construction, nous
obtenons un entier positif, not\'e
$$
J^{(k)}_m:=K^{(k)}_m\,m!^k,\leqno(9.1)
$$
que nous d\'esignons par {\it entier hyperharmonique}. Les
premi\`eres valeurs de ces entiers sont reproduites dans le tableau
ci-apr\`es.


{\eightpoint

$$
\vbox{\offinterlineskip
\halign{\vrule\kern4pt \strut\vrule height 10pt
depth 3pt width0pt\hfil$#$\hfil\ 
&\vrule\kern4pt \hfil$#$\hfil\kern4pt 
&\vrule\kern4pt\hfil$#$\hfil\kern4pt 
&\vrule\kern4pt\hfil$#$\hfil\kern4pt 
&\vrule\kern4pt\hfil$#$\hfil\kern4pt 
&\vrule\kern4pt\hfil$#$\hfil\kern4pt 
&\vrule\kern4pt\hfil$#$\hfil\kern4pt\vrule 
\cr
\noalign{\hrule}
m&2&3&4&5&6&7\cr
\noalign{\hrule}
J_m^{(0)}&1&1&1&1&1&1\cr
\noalign{\hrule}
J_m^{(1)}&1&5&26&154&1044&8028\cr
\noalign{\hrule}
J_m^{(2)}&1&19&460&15196&672336&38724624\cr
\noalign{\hrule}
J_m^{(3)}&1&65&6920&1229704&346296384&146661388992\cr
\noalign{\hrule}
J_m^{(4)}&1&211&95536&89222896&157188439296
&483005642823936\cr
\noalign{\hrule}
J_m^{(5)}&1&665&1254176&6060649504&65990223258624
&%1456861745140927488\cr
\cdots\cr
\noalign{\hrule}
J_m^{(6)}&1&2059&15958720&394810588096&26339109589241856
&\cdots\cr
%4147710360566182907904\cr
\noalign{\hrule}
}
}$$

}

Une de nos premi\`eres t\^aches a \'et\'e de regarder si certaines
lignes, colonnes ou diagonales de ce tableau figurent d\'ej\`a dans
l'{\it On-Line Encyclopedia of Integer Sequences} de
Sloane. Dans cette encyclop\'edie en
ligne, on trouve, en effet, la {\it ligne} se r\'ef\'erant aux entiers
$J_m^{(1)}$ $(m\ge 2)$ et les {\it colonnes} se rapportant aux
entiers $J_3^{(k)}$
$(k\ge 0)$ et $J_4^{(k)}$ $(k\ge 0)$. Sloane
indique que le d\'eveloppement
$$
(1-x)^{-2}\,{\rm ln}(1/(1-x))
=x+{x^2\over 2!}5+{x^3\over 3!}26+{x^4\over 4!}154
+{x^5\over 5!}1044+\cdots\leqno(9.2)
$$
appara\^\i t dans un article des Mitrinovi\'c (1962), qui en ont donn\'e
une interpr\'etation combinatoire en termes de nombres de
Stirling g\'en\'eralis\'es. On voit que le pr\'ec\'edent
d\'eveloppement s'obtient par d\'erivation, par rapport \`a~$s$, de
l'identit\'e (2.3). Le membre de droite de~(9.2) est donc
\'egal \`a $\sum\limits_{m\ge
2}J^{(1)}_m\,x^{m-1}/(m-1)!$

Par ailleurs, la s\'erie
$$
{1\over (1-2x)(1-3x)}=
1+5x+ 19x^2 + 65x^3 + 211 x^4 +  665x^5 
+\cdots\leqno(9.3)
$$
appara\^\i t dans un article de Kreweras (1969), qui en a donn\'e une
interpr\'etation en termes de relations binaires connexes. 
C'est naturellement, d'apr\`es l'identit\'e (1.5), un d\'eveloppement
qui est \'egal \`a : 
$\sum\limits_{k\ge 0}J^{(k)}_3x^k$ ({\it cf.} colonne $m=3$
dans le tableau pr\'ec\'edent). Enfin, la colonne $m=4$, dont la
fonction g\'en\'eratrice, d'apr\`es l'identit\'e (1.5), est \'egale \`a
$$
{1\over (1-4!\,x/2)(1-4!\,x/3)(1-4!\,x/4)},
$$
est simplement dans la liste de l'encyclop\'edie sans r\'ef\'erence
particuli\`ere.

\section 10. Une asymptotique pour les nombres
hyperharmoniques|Cette asymptotique d\'ecoule, \'evidemment, de
l'asymptotique des nombres harmoniques g\'en\'eralis\'es. Nous
tenons simplement \`a indiquer comment on peut l'obtenir \`a
l'aide des formules de changement de base des fonctions
sym\'etriques homog\`enes compl\`etes aux fonctions sym\'etriques de
puissances $p_k=\sum x_i^k$ (\cf. Macdonald (1995) p.~28). Pour
$m$ fix\'e, le nombre
$K_m^{(k)}$ est la fonction sym\'etrique homog\`ene compl\`ete $h_k$ de
degr\'e~$k$ en les variables $1\over 2$, \dots~,
$1\over m$.

D'abord, $K_m^{(1)}=h_1=p_1$ et $p_1-\ln m$ tend vers
$\gamma-1\approx -0,4227$, o\`u $\gamma$ est la constante
d'Euler. D'o\`u $K_m^{(1)}/\ln m$ tend vers~1. D'autre part, pour
$k\ge 2$, on a $p_k\rightarrow \zeta(k)-1$. Comme
$$K_m^{(k)}=
h_k={1\over k!}p_1^k+\sum a(i_1,i_2,\ldots, i_k)\,
p_1^{i_1}p_2^{i_2}\cdots p_k^{i_k},
$$
o\`u la somme est sur toutes les suites $(i_1,i_2,\ldots, i_k)$
d'entiers telles que $1\cdot i_1+2\cdot i_2+\cdots +k\cdot i_k=k$
et $i_2+\cdots +i_k\ge 1$, on a, pour chaque terme de cette
somme, 
$$\displaylines{
{p_1^{i_1}p_2^{i_2}\cdots p_k^{i_k}\over (\ln m)^{i_1}
(\ln m)^{i_2+\cdots +i_k}}\rightarrow 0.\cr
\noalign{\hbox{D'o\`u}}
\rlap{(10.1)}\hfill
{k!\,K_m^{(k)}\over (\ln m)^k}\rightarrow
1\qquad(m\rightarrow +\infty).\hfill\cr}
$$

Connaissant les valeurs de la fonction $\zeta$ en les entiers et aussi
les coefficients de la matrice de passage de la base des $h_\lambda$
\`a la base des $p_\lambda$, on
peut aussi obtenir les formules asymptotiques suivantes, o\`u les
constantes sont des valeurs {\it approch\'ees} :
$$
\eqalignno{K_m^{(1)}&\approx \ln m-0,4227;\cr
K_m^{(2)}&\approx 0,5\,\ln^2 m-0,4227\,\ln m+0,4118;\cr
K_m^{(3)}&\approx0,1666\,\ln^3m-0,2113\,\ln^2 m+0,4118\,\ln
m-0,0815;\cr 
K_m^{(4)}&\approx 0,0417\,\ln^4 m-0,0704\,\ln^3 m+0,2059\,\ln^2
m\cr
&\kern5cm {}
-0,0815\,\ln m+0,0742.
\cr
}
$$

\bigskip
{\bf Remerciements}\pointir
Les auteurs remercient Aim\'e Fuchs de leur avoir communiqu\'e la
m\'ethode des martingales pour le calcul de $\Esp[X_T^{(1)}]$
d'apr\`es la version qu'en avait donn\'ee Giorgio Letta. Ils
remercient aussi Philippe Flajolet, qui a attir\'e leur attention sur
les variations des nombres harmoniques g\'en\'eralis\'es et les
travaux de Bentley et al. (1978) et Buchta (1989),
ainsi que Christian Krattenthaler pour sa relecture attentive.

\vglue 25pt
\centerline{\eightbf BIBLIOGRAPHIE}
\bigskip
Banderier, Cyril; Dobrow, Robert P. (2000)\pointir A Generalized Cover
Time for Random Walks on Graphs, Proc. FPSAC'00, Springer-Verlag.

Bauer, Heinz (1995)\pointir {\it Wahrscheinlichkeitstheorie}\pointir
Walter de Gruyter, Berlin.

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

Bergeron, Fran\c cois; Labelle, Gilbert; Leroux, Pierre
(1994)\pointir{\sl Th\'eo\-rie des esp\`eces et combinatoire des
structures arborescentes}\pointir Publ. LACIM, vol.~19, Montr\'eal.

Boneh, Arnon; Hofri, Micha (1997)\pointir
The coupon-collector problem
revisited---a survey of engineering problems and 
computational methods,
{\it Comm. Statist. Stochastic Models}, {\bf 13}, no.~1,
p.~39--66. 

Buchta, Christian (1989)\pointir
On the average number of maxima in a set of vectors, {\sl
Information Proc. Letters}, {\bf 33}, p.~63--65.

Cartier, Pierre (2000)\pointir
Mathemagics, {\sl S\'em. Lothar. Combin.}, B44d, 71~pp.
({\tt http\kern-5pt://www.mat.univie.ac.at/$\sim$slc/}).

%Comtet, Louis (1970)\pointir {\sl Analyse Combinatoire},
%vol.~2\pointir Presses Universitaires de France, Paris.

Feller, William (1968)\pointir {\sl An Introduction to Probability
Theory and its Applications}, Third edition, vol.~1\pointir John
Wiley \& Sons, New York.

Flajolet, Philippe; Gardy, Dani\`ele; Thimonier, Lo\"ys (1992)\pointir
 Birthday paradox, coupon collectors, caching algorithms and
self-organizing search, {\it Discrete Appl. Math.}, {\bf 39},
p.~207--229.

Flajolet, Philippe ; Labelle, Gilbert ; Laforest, Louise ; Salvy, Bruno
(1995)\pointir
Hypergeometrics and the Cost Structure of Quadtrees,
{\sl Random Structures and Algorithms}, {\bf 7}, p.~117--144.

Foata, Dominique (1974)\pointir {\sl La s\'erie
g\'en\'eratrice exponentielle dans les probl\`emes
d'\'enum\'eration}\pointir Les Presses de l'Universit\'e de
Montr\'eal, Montr\'eal.

Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren
(1989)\pointir
{\sl Concrete Mathematics}\pointir Addison-Wesley, Reading.

Kreweras, Germain (1969)\pointir\ 
Inversion des polyn\^omes de Bell
bidimen\-sionnels et application au d\'enombrement des relations
binaires connexes, {\sl C. R. Acad. Sci. Paris Ser. A-B}, {\bf 268},
A577-A579.

Lass, Bodo (2001)\pointir Calcul combinatoire ensembliste.
Th\`ese doctorat Aachen-Strasbourg, en pr\'eparation.

Letta, Giorgio (1992)\pointir Communication personnelle \`a 
Aim\'e Fuchs.

Macdonald, I. G. (1995)\pointir {\sl Symmetric Functions and Hall
Polynomials}, Second Edition\pointir Clarendon Press, Oxford.

Mitrinovi\'c, D. S., Mitrinovi\'c, R. S. (1962)\pointir Tableaux d'une
classe de nombres reli\'es aux nombres de Stirling, {\sl Univ.
Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz.}, {\bf 77}, 77~pp.

Pintacuda N. (1980)\pointir Coupon Collectors via the Martingales,
{\sl Boll. Un. Mat. Ital. A}, {\bf 17}, p.~174--177.

Sloane, Neil, J. A\pointir {\sl On-Line Encyclopedia of Integer
Sequences}, {\tt http\kern-5pt://www.research.att.com/$\sim$njas}

Strehl, Volker (2001a)\pointir Calcul automatique des identit\'es
hyperg\'eo\-m\'etriques, Colloquium, Univ. Louis Pasteur,
Strasbourg.

Strehl, Volker (2001b)\pointir Ten years of special function
computer algebra, {\sl S\'em. Lothar. Combin.}, en pr\'eparation.

Zeilberger, Doron (1990)\pointir Holonomic system approach to
special function identities, {\sl J. of Computational and Appl. Math.},
{\bf 32}, p.~321-368.


\bigskip\bigskip
\halign{#\hfill\cr
Dominique Foata, Bodo Lass\cr
et Guo-Niu Han\cr
D\'epartement de math\'ematique\cr
et I.R.M.A.-C.N.R.S.\cr
Universit\'e Louis Pasteur\cr
7, rue Ren\'e-Descartes\cr
F-67084 Strasbourg\cr
\noalign{\smallskip}
{\tt foata@math.u-strasbg.fr}\cr
{\tt lass@math.u-strasbg.fr}\cr
{\tt guoniu@math.u-strasbg.fr}\cr
}


\bye
