% Les nombres hyperharmoniques et la fratrie du % collectionneur de vignettes % % Dominique Foata, Guo-Niu Han et Bodo Lass % Plain Tex, 20 pages \bigskip\bigskip \catcode'32=9 \magnification=1200 %First page headline in Plain-TeX for the %S\'eminaire Lotharingien de Combinatoire for the special Strasbourg macros \font\rms=cmr8 \font\its=cmti8 \font\bfs=cmbx8 \def\titleheadline{\its S\'eminaire Lotharingien de Combinatoire \bfs 47 \rms (2001), Article~B47a\hfill} %Below, any redefinitions of \titleheadline have to be deleted. \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 sdfsdf\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)}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