

%%%%%%%%%%%%%%%%%%%%%
%% TeX plain file for the paper entitled
%% The Collector's Brotherhood
%% by D. Foata, D. Zeilberger
%% An output of 9 pages
%%%%%%%%%%%%%%%%%%%%%
\catcode'32=9
\magnification=1200

%\voffset=1cm
\voffset=.5cm
\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


\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\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}.\quad }

\def\cf{{\it cf}}

\mathchardef\conj="0365

\def\qed{\quad\raise -2pt\hbox{\vrule\vbox to 10pt{\hrule width 4pt
\vfill\hrule}\vrule}}

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


\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\bfs{{\bf s}}

\def\Esp{{\bboard E}}

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

\auteurcourant={D. FOATA, D. ZEILBERGER}
\titrecourant={THE COLLECTOR'S BROTHERHOOD}
\ifnum\day<0 \advance\day by 160 \fi

\def\Surj{\mathop{\rm Surj}\nolimits}
\def\surj{\mathop{\rm surj}\nolimits}
\def\bfn{{\bf n}}
\raggedbottom
\vglue 2cm
\bigskip\bigskip
\centerline{\bf The Collector's Brotherhood\footnote{}{\kern-12pt {\bf AMS
2000 Classification}: 05A15, 05E05, 60C05.\strut\hfil\break
{\bf Keywords}: Coupon collector's problem, Surjection calculus,
Newman-Shepp symbolic method, Hyperharmonic numbers.}}

\bigskip
\centerline{\sl Dominique Foata,\footnote{$^1$}{Supported in
part by the NSF, as a consultant on Zeilberger's grant.} Doron
Zeilberger\footnote{$^2$}{Supported in part by the NSF.}}
\bigskip\bigskip

{\eightpoint
{\narrower\narrower
\noindent
{\bf Abstract}.\quad Further computations are made on the traditional
coupon collector's problem when the collector shares his harvest with his
younger brothers. When the book of the $p$-th brother of the
collector is completed, the books of the younger brothers have
certain numbers of empty spots. On the average, how many?
Several answers can be brought to that question.

\bigskip
}
}

\section 1. Introduction|Suppose that $m$ different coupons are
needed for a collector, to complete his picture-book. Each time,
that is, at each purchase, he can get a given coupon with
probability $1/m$. If he does not have it yet, he sticks it on his
book. Otherwise, he gives it to his younger brother. In his turn,
the younger brother sticks it on his own book, if the coupon is
new for him. Otherwise, the next younger brother will receive it
and try to complete his own picture-book, using the same policy.
The collector is labelled~0, the younger brother~1, the next
younger brother~2, etc. 

For $p\ge 0$ let $T_p$ be the time at which the person
labelled~$p$ completes his book. Also for each $k\ge 1$, $n\ge 1$
and
$1\le i\le m$ let 
$$X_{n,i}^{(k)}
=\cases{1,&if coupon~$i$ has occurred $k$ times\cr 
&\qquad\qquad\qquad up to
and including time~$i$;\cr
0,&otherwise.}
$$
Thus, $X_n^{(k)}=\sum\limits_{1\le i\le m} X_{n,i}^{(k)}$ is the
number of coupons that have occurred $k$ times (exactly) up to
and including time~$n$. For each $n\ge 1$ let 
$X_n^{(0)}$ be the number of empty spots in the collector's book
at time~$n$; by convention $X_0^{(0)}=m$.

For each $p\ge 0$ we have $X_{T_p}^{(p)}=0$ and for each $k\ge
p+1$ the number of coupons that have occurred~$k$ times up to
and including time~$T_p$ is $X_{T_p}^{(k)}$. Consequently, the
number of empty spots in the book of the brother labelled $k\ge
p+1$ at time~$T_p$ is
$X_{T_p}^{(p+1)}+X_{T_p}^{(p+2)}+\cdots +X_{T_p}^{(k)}$.

Several methods have been used to derive the probability
distribution of~$T_0$ and its expected value $\Esp[T_0]$.
The evaluation $\Esp[T_0]=m\,H_m$, where $H_m$ is the {\it
harmonic number} $H_m=1+{1\over 2}+\cdots+{1\over m}$, is a
classic (see Feller (1968)). 
The evaluation $\Esp[X^{(1)}_{T_0}]=H_m$ is due to Pintacuda
(1980) using a method based on the martingale stopping time
theorem. Recently, Foata, Han and Lass (2001) have derived the
generating function for the vector $(T_0,
X_{T_0}^{(1)},X_{T_0}^{(2)},\ldots,X_{T_0}^{(k)})$
$(k\ge 1)$ and obtained the evaluations
$\Esp[X_{T_0}^{(k)}]=K_m^{(k)}$, where $K_m^{(k)}$ is the {\it
hyperharmonic number} that can be defined by
the generating function:
$$
\sum_{k \ge 0} K_m^{(k)} t^k = 
{1 \over (1-t/2) (1-t/3) \cdots (1-t/m)}.\leqno(1.1)
$$

Now the natural question to ask is the following: what can be
said when the stopping time $T_0$ is replaced by $T_p$ for an
arbitrary $p\ge 0$? Back to the early sixties Newman and
Shepp (1960) obtained the integral expression
$$\displaylines{\rlap{(1.2)}\hfill
\Esp[T_p]=m\int_0^{+\infty}
\bigl(1-(1-S_{p+1}(x)e^{-x})^m\bigr)\,dx,
\hfill\cr
\noalign{\hbox{where}}
\rlap{(1.3)}\hfill
S_{p+1}(x):=1+
{x\over 1!}+\cdots+{x^p\over p!}\quad (p\ge 0).\hfill\cr
}
$$
The purpose of this paper is to make use of the {\it symbolic
method} developed by Newman and Shepp ({\it op. cit.\/}) to obtain
the following formulas, all of them expressed in terms of 
{\it integrals}. For each $0\le p<r$ consider the generating
functions:
$$\leqalignno{
H_{T_p}(t)&:=\sum_{i\ge 0} \Pr\{T_p>i\}\,t^i;&(1.4)\cr
G_{T_p}(t)&:=\sum_{i\ge 0}\Pr\{T_p=i\}\,t^i;&(1.5)\cr
\qquad\quad
G_{T_p,X}(t,\bfs)&:=\kern-8pt\sum_{n,n_1,\ldots,n_r}\kern-8pt
\Pr\{T_p=n,X_{T_p}^{(p+1)}=n_{p+1},\ldots,
X_{T_p}^{(r)}=n_r\}&(1.6)\cr
\noalign{\vskip-10pt}
&\kern6cm{}\times
t^n s_{p+1}^{n_{p+1}}\cdots s_r^{n_r};\cr
G_{X}^{(p)}(t)&:=\sum_{k\ge p+1} \Esp[X_{T_p}^{(k)}]\,t^k.
&(1.7)\cr
}
$$
We then establish the formulas:
$$\displaylines{(1.8)\quad
H_{T_p}(t)=m\int_0^{+\infty}
\bigl(e^{-mx(1-t)}-(e^{-x(1-t)}-S_{p+1}(tx)e^{-x})^m\bigr)\,dx;
\hfill\cr
(1.9)\quad
G_{T_p}(t)=m(1-t)\int_0^{+\infty}
\bigl(e^{-x(1-t)}-e^{-x}S_{p+1}(tx)\bigr)^m\,dx;
\hfill\cr
(1.10)\quad
G_{T_p,X}(t,\bfs)
={ms_{p+1}t^{p+1}\over p!}
\int_0^{+\infty}
x^pe^{-mx}\hfill\cr
\hfill{}\times
\Bigl(e^{xt}-S_{r+1}(xt)
+{(xt)^{p+1}\over (p+1)!}s_{p+1}+\cdots+
{(xt)^r\over r!}s_r\Bigr)^{m-1}\,dx;\cr
(1.11)\quad
G_X^{(p)}(t)
=t^{p+1}\hfill\cr
\hfill{}
+m(m-1)\int_0^{+\infty}\kern-2pt e^{-mx}{x^p\over p!}
\bigl(e^{xt}-S_{p+1}(xt)
\bigr)
\bigl(e^{x}-S_{p+1}(x)
\bigr)^{m-2}\,dx.\cr}
$$
By expanding the different integrands using the multinomial
theorem we can express those integrals as finite sums
over~${\bboard N}^{r+2}$ for some~$r$. For instance, (1.10) may
be rewritten as
$$\displaylines{
(1.12)\quad
G_{T_p,X}(t,\bfs)
={s_{p+1}t\over p!}
 \sum {m-1\choose a,b_0,\ldots,b_r}
(-1)^{b_0+\cdots +b_r}
\left(\prod_{i=0}^p\Bigl({1\over i!}\Bigr)^{b_i}\right)\hfill\cr
\hfill{}\times
\left(\prod_{i=p+1}^r\Bigl({s_i-1\over i!}\Bigr)^{b_i}\right)
{(t/m)^{p+ 1\cdot b_1+\cdots+r\cdot b_r}\over
(1-at/m)^{1+p+1\cdot b_1+\cdots+r\cdot b_r}} ({\textstyle
p+\sum\limits_{i=1}^r}ib_i)!,\cr}
$$
that specializes to the formula derived by Foata et al. (2001) for
the case $p=0$. However the main difference between the latter
case and the general case $p\ge 1$ is the fact that when $p=0$
identity (1.12) can directly lead to the {\it explicit} evaluations
$\Esp[X_{T_0}^{(k)}]=K_m^{(k)}$ (the hyperharmonic number),
while for $k\ge 1$ the {\it integral form} that can be obtained
from (1.10) has no further simplification.

In section 2 we discuss certain salient features of Surjection
Calculus. In section~3 we recall the {\it symbolic method} developed
by Newman and Shepp ({\it op. cit.\/})  and use it to
prove identities (1.8) and (1.9). Identities (1.10) and (1.11) are
proved in sections~4 and~5, respectively. We conclude the paper
by some remarks on the holonomic aspects of the above integral
identities.

Notice that the asymptotics of $\Esp[T_p]$ for an
arbitraary $p\ge 0$ have been derived by Newman and Shepp
({\it op. cit.\/}) and the asymptotic probability distribution
of~$T_p$ has been calculated by Erd\H os and R\'enyi (1961).
More recent work along those lines is due to  Wilf (2001).

\section 2. Surjection calculus|Let
$(t,s_1,s_2,\ldots\,)$ be a sequence of commuting variables. 
If~$f$ maps a finite set~$A$ of integers into a (finite) set~$B$
of integers, let $\nu_i(f)$ denote the number of elements
$j\in B$ such that the preimage $f^{-1}(j)$ is of
cardinality~$i$. Then, the {\it weight} $\pi(f)$ of~$f$ is defined
by:
$\pi(f):=\smash{\prod\limits_{i\ge 1}}s_i^{\nu_i(f)}$ ;
so that the relations
$\smash{\sum\limits_i}\nu_i(f)=\#B$ et $\smash{\sum\limits_i}
i\,\nu_i(f)=\# A$. hold.

For each integer~$n$ let $[n]:=\{1,2,\ldots,n\}$ and for each pair
of finite sets
$(A,B)$ let
$\Surj_{\ge p+1}(A,B)$  denote the set of all {\it surjections} 
$f:A\rightarrow B$ such that for all $j\in B$ the inequality
$\#f^{-1}(j)\ge p+1$ holds. 
The following identity is the basic identity in Surjection Calculus
(see, e.g., Foata (1974), p.~60):
$$\displaylines{\rlap{(2.1)}\hfill
\Bigl(\sum_{i\ge p+1}s_i{t^i\over i!}\Bigr)^m
=\sum_{n\ge (p+1)m}{t^n\over n!}
\sum_{f\in \Surj_{\ge p+1}([n],[m])} \pi(f).\hfill\cr
\noalign{\hbox{This implies, when all the $s_i$'s are equal to 1,}}
\rlap{(2.2)}\hfill
(e^t-S_{p+1}(t))^m
=\sum_{n\ge (p+1)m}{t^n\over n!}
\#\Surj_{\ge p+1}([n],[m]).\hfill\cr}
$$
Next consider the subset $A(n,m)$ of all surjections~$f$
in $\Surj_{\ge p+1}([n],[m])$ such that if
$f(n)=j$ then $\#f^{-1}(j)=p+1$. In other words, all values are
taken at least $p+1$ times, but the value taken at~$n$
occurs exactly~$p$ times in $(f(1),f(2),\ldots, f(n-1))$. Then,
identity (2.1) implies 
$$
\sum_{n\ge m(p+1)} {t^{n-1}\over (n-1)!}
\sum_{f\in A(n,m)}\pi(f)
=ms_{p+1}{t^p\over p!}
\Bigl(\sum_{i\ge p+1}s_i{t^i\over i!}\Bigr)^{m-1}.\leqno(2.3)
$$
Let $0\le p<r$, $\bfn:=(n_{p+1},n_{p+2},\ldots,n_r)$
and let $A(n,m;\bfn)$ be the subset of all surjections~$f$ in
$A(n,m)$ such that
$$
\pi(f)=\prod_{p+1\le i\le r} s_i^{n_i}.
$$
When $s_i:=1$ for all $i\ge r+1$, identity (2.3) rewrites as:
$$\displaylines{(2.4)\quad
\sum_{n\ge m(p+1)} {t^{n-1}\over (n-1)!}
\sum_{\bfn}\#A(n,m;\bfn)
\prod_{p+1\le i\le r}\kern-8pt s_i^{n_i}\hfill\cr
\hfill{}
=ms_{p+1}{t^p\over p!}
\Bigl(e^t-S_{r+1}(t)
+s_{p+1}{t^{p+1}\over (p+1)!}+\cdots+s_r
{t^{r}\over r!}\Bigr)^{m-1}.\cr}
$$

Now let $i,j$ be two distinct integers in $[m]$ and
for each $n\ge (p+1)m$ let $B(n-1,i,j)$ be the set of
surjections $f:[n-1]\rightarrow [m]$ with the following properties:
with $I(f):=f^{-1}(i)$, $J(f):=f^{-1}(j)$ then
$\#J(f)=p$ and the restriction of~$f$ to $[n-1]\setminus J(f)$
belongs to $\Surj_{\ge p+1}([n-1]\setminus
J(f),[m]\setminus\{j\})$. Then form the generating polynomial
$$
F_{n-1}(t)=\sum_{f\in B(n-1,i,j)} t^{\#I(f)}.\leqno(2.5)
$$
Still using (2.1) a little reflection shows that the following
identity holds:
$$
\sum_{n\ge (p+1)m}{u^{n-1}\over (n-1)!}F_{n-1}(t)
={u^p\over p!}
\bigl(e^{ut}-S_{p+1}(ut)\bigr)
\bigl(e^u-S_{p+1}(u)
\bigr)^{m-2}.\leqno(2.6)
$$

\section 3. The Newman-Shepp symbolic method|Let $m\ge 1$
and consider the algebra of power series in the variables $u_1$,
$u_2$, \dots~, $u_n$. If $a=a(u_1,\ldots,u_n)$ is such a series,
write it as
$$
a(u_1,\ldots,u_n)=\sum_{i\ge 0} {1\over i!}\, a_i(u_1,\ldots,u_n),
$$
where $a_i(u_1,\ldots,u_n)$ is the sum of all monomials of
degree~$i$ in~$a$. Now define
$$
N_m\,a(u_1,\ldots,u_n):=\sum_{i\ge 0} {1\over m^i}\,
a_i(u_1,\ldots,u_n),
$$
so that the {\it exponential} normalization has be replaced by
the {\it power} normalization. We next reproduce the integral
expression for 
$N_m\,a(u_1,\ldots,u_n)$ as derived by Newman
and Shepp ({\it op. cit.\/}).

\proclaim Lemma 3.1. We have the identity:
$$
N_m\,a(u_1,\ldots,u_n)
=m\int_0^{+\infty}e^{-mx}\,
a(xu_1,\ldots,xu_n)\,dx.
$$


For each $n=1,2,\dots$ let $Y_n$ be the label of the coupon
which is obtained at time~$n$. By
assumption, the random variables $Y_n$ $(n=1,2,\dots\,)$ are
assumed to be independent and uniformly distributed on the
coupon label set $\{1,2,\ldots,m\}$. The event $\{T_p>n\}$ is
realized if and only if the mapping $f:i\mapsto Y_i$ $(1\le
i\le n)$ belongs to the set $\Surj^c_{\ge p+1}([n],[m])
:=[m]^n\setminus \Surj_{\ge p+1}([n],[m])$. 
Hence $\Pr\{T_p>n\}=\#\Surj^c_{\ge p+1}([n],[m])/m^n$. But
it follows from (2.2) that
$$
e^{mt}-
(e^t-S_{p+1}(t))^m
=\sum_{n\ge 0}{t^n\over n!}
\#\Surj^c_{\ge p+1}([n],[m]),$$
\goodbreak

\noindent so that
$$\leqalignno{
N_m\,\bigl(e^{mt}-
(e^t-S_{p+1}(t))^m\bigr)
&=\sum_{n\ge 0}{t^n\over m^n}
\#\Surj^c_{\ge p+1}([n],[m])\cr
&=\sum_{n\ge 0}\Pr\{T_p>n\}t^n=H_{T_p}(t).\cr}
$$
Hence, by Lemma 3.1
$$
H_{T_p}(t)
=m\int_0^{+\infty}e^{-mx}
(e^{mtx}-\bigl(e^{tx}-S_{p+1}(tx))^m\bigr)\,dx,
$$
which reduces to (1.8).
To get (1.9) we make use of the traditional relation
$G_{T_p}(t)=1-(1-s)\,H_{T_p}(t)$. Finally, when we plug $t=1$ in
(1.8), we recover formula (1.2) already derived by 
Newman and Shepp ({\it op. cit.\/}).

\section 4. The multivariable generating function|Keep the same
notations for the sequence $(Y_n)$ $(n=1,2,\ldots\,)$ of coupon
labels that occur at time $n=1,2,\ldots$ and for the variables
$X_n^{(k)}$ defined in the introduction. Then, the event
$\{T_p=n,X_{T_p}^{(p+1)}=n_{p+1},\ldots, X_{T_p}^{(r)}=n_r\}$
is realized if and only if the mapping $f:i\mapsto Y_i$
$(1\le i\le n)$ belongs to the set $A(n,m;\bfn)$ introduced
in~(2.4). Hence,
$\Pr\{T_p=n,X_{T_p}^{(p+1)}=n_{p+1},\ldots, X_{T_p}^{(r)}=n_r\}
=\#A(n,m;\bfn)/m^n$. It follows from (2.4) that
$$\displaylines{\quad
N_m\Bigl(
ms_{p+1}{t^p\over p!}
\Bigl(e^t-S_{r+1}(t)
+s_{p+1}{t^{p+1}\over (p+1)!}+\cdots+s_r
{t^{r}\over r!}\Bigr)^{m-1}\Bigr)\hfill\cr
\hfill{}
=\sum_{n\ge m(p+1)} {t^{n-1}\over m^{n-1}}
\sum_{\bfn}\#A(n,m;\bfn)
\prod_{p+1\le i\le r}\kern-8pt s_i^{n_i},\cr
\noalign{\hbox{so that, by multiplying both members by $t/m$,}}
\quad t\,N_m\Bigl(
s_{p+1}{t^{p}\over p!}
\Bigl(e^t-S_{r+1}(t)
+s_{p+1}{t^{p+1}\over (p+1)!}+\cdots+s_r
{t^{r}\over r!}\Bigr)^{m-1}\Bigr)\hfill\cr
\quad\qquad{}
=\sum_{n\ge m(p+1)} {t^{n}\over m^{n}}
\sum_{\bfn}\#A(n,m;\bfn)
\prod_{p+1\le i\le r}\kern-8pt s_i^{n_i}\hfill\cr\cr
\quad\qquad{}=\sum_{n,\bfn}
\Pr\{T_p=n,X_{T_p}^{(p+1)}=n_{p+1},\ldots, X_{T_p}^{(r)}=n_r\}
t^ns_{p+1}^{n_{p+1}}\cdots s_r^{n_r}\hfill\cr
\quad\qquad{}=G_{T_p,X}(t,\bfs).\hfill\cr
}
$$
This establishes identity (1.10) by using again Lemma~3.1.

\section 5. A generating function for the expected times|We may
write
$$\eqalignno{G_{X}^{(p)}(t)&:=\sum_{k\ge p+1}
\Esp[X_{T_p}^{(k)}]\,t^k=\sum_{k\ge p+1}\sum_{1\le i\le
m}
\Esp[X_{T_p,i}^{(k)}]\,t^k\cr
&=\sum_{k\ge p+1}\sum_{1\le i\le m}
\Pr\{X_{T_p,i}^{(k)}=1\}\,t^k\cr
&=\sum_{k\ge p+1}\sum_{1\le i\le m}
\sum_{n\ge (p+1)m}\sum_{1\le j\le m}
\Pr\{X_{n,i}^{(k)}=1, T_p=n,Y_n=j\}\,t^k\cr
&=t^{p+1}+\sum_{n\ge (p+1)m}\sum_i
\sum_{j\not=i}
\sum_{k\ge p+1}
\Pr\{X_{n-1,i}^{(k)}=1, T_p=n,Y_n=j\}\,t^k.\cr}
$$
Now the event $\{X_{n-1,i}^{(k)}=1, T_p=n,Y_n=j\}$ is realized if
and only if the mapping $f:k\mapsto Y_k$
$(1\le k\le n-1)$ belongs to the set $B(n-1,i,j)$ introduced
in (2.5)--(2.6) and if $Y_n=j$. Hence, keeping the same notations,
$$\displaylines{
\sum_{k\ge p+1}\Pr\{X_{n-1,i}^{(k)}=1,
T_p=n,Y_n=j\}t^k={1\over m^n}F_{n-1}(t),\cr
\noalign{\hbox{so that}}
G_{X}^{(p)}(t)
=t^{p+1}+m(m-1)\kern-5pt \sum_{n\ge (p+1)m}
{1\over m^n}F_{n-1}(t).\cr}
$$
With the introduction of a new variable~$u$ define:
$$\displaylines{
G_{X}^{(p)}(t,u):=t^{p+1}+(m-1)\kern-5pt \sum_{n\ge (p+1)m}
{u^{n-1}\over m^{n-1}}F_{n-1}(t).\cr
\noalign{\hbox{Then}}
\eqalign{
G_{X}^{(p)}(t,u)
&=N_m\Bigl(t^{p+1}+(m-1)\kern-5pt \sum_{n\ge (p+1)m}
{u^{n-1}\over (n-1)!}F_{n-1}(t)\Bigr)\cr
&=N_m\Bigl(t^{p+1}+(m-1)
{u^p\over p!}
\bigl(e^{ut}-S_{p+1}(ut)\bigr)
\bigl(e^u-S_{p+1}(u)
\bigr)^{m-2}\Bigr)\cr}\cr}
$$
by using (2.6). Next applying Lemma 3.1 we get:

$$\displaylines{
G_{X}^{(p)}(t,u)=t^{p+1}\hfill\cr
\hfill{}
+m(m-1)\int_0^{+\infty}e^{-mx}{(ux)^p\over p!}
\bigl(e^{uxt}-S_{p+1}(uxt)
\bigr)
\bigl(e^{ux}-S_{p+1}(ux)
\bigr)^{m-2}\,dx,\cr
}$$
which reduces to (1.11) by making $u=1$.

\goodbreak
\section 6. Concluding Remarks|Identity (1.1) together with the
evaluations
$\Esp[X_{T_0}^{(k)}]=K_m^{(k)}$ $(k\ge 1)$ can be rewritten
as
$$G_X^{(0)}(t)=
\sum_{k\ge 1}\Esp[X_{T_0}^{(k)}]t^k=-1+t+
{1 \over (1-t/2) (1-t/3) \cdots (1-t/m)}.\leqno(6.1)
$$
That identity, derived by Foata et al. ({\it op. cit.\/}), can also
be obtained from its integral form (1.11). When $p=0$, the factor
$x^p$ in the integrand vanishes. With the change of
variables $u=e^{-x}$ the integral in (1.11) reduces to the 
evaluation of two b\^eta integrals:
$$\eqalignno{
G_X^{(0)}(t)&=t+m(m-1)\int_0^1(u^{-t+1}-u)(1-u)^{m-2}\,du\cr
&=t+m(m-1)\Bigl({\Gamma(2-t)\Gamma(m-1)\over \Gamma(m-t+1}
-{\Gamma(2)\Gamma(m-1)\over\Gamma(m+1)}\Bigr)\cr
&=t+{m!\over (m-t)(m-t-1)\cdots (2-t)}-1\cr
&=-1+t+
{1 \over (1-t/2) (1-t/3) \cdots (1-t/m)}.\qed\cr
}
$$

Unfortunately, for $p >0$, it does not seem to be possible to
evaluate the integral in closed form, since then the integral
representation is {\it hybrid}, involving a polynomial
in the variable and its exponential. Hence it lies outside
the jurisdiction of the {\it holonomic paradigm}, and in general
there is no reason why the integral should evaluate to
something `nice', and indeed it, most probably, does not!

\bigskip
{\bf Acknowledgements}.\quad We owe to the search sagacity of
Herb Wilf to have found track of the paper by Newman and Shepp.
Those authors had entitled their paper ``Double Dixie Cup
Problem" without reference to the traditional Coupon
Collector lore, which explains our difficulty to locate it through
{\sl MathSciNet}.

\vfill\eject
\vglue 25pt
\centerline{\eightbf REFERENCES}
\bigskip
Erd\H os, Paul; R\'enyi, Alfred (1961).\quad On a classical problem
of probability theory, {\sl Magyar. Tud. Akad. Mat. Kutat\'o Int.
K\H ozl.}, {\bf 6}, p.~215--220.



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

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

Foata, Dominique; Han Guo-Niu; Lass, Bodo (2001).\quad Les
nombres hyperharmoniques et la fratrie du collectionneur de
vignettes, submitted for publication, see: {\tt
http://www-irma.u-strasbg.fr/$\sim$foata/paper}.

Newman, Donald J.; Shepp, Lawrence (1960).\quad
The Double Dixie Cup Problem, {\sl Amer. Math. Monthly},
{\bf 67}, p.~58--61.

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

Wilf, Herb (2001).\quad Some finie structures of the coupon
collector's problem. Preprint.

\bigskip\bigskip
\halign{#\hfill\cr
Dominique Foata \cr
D\'epartement de math\'ematique\cr
Universit\'e Louis Pasteur\cr
7, rue Ren\'e-Descartes\cr
F-67084 Strasbourg, France\cr
\noalign{\smallskip}
{\tt foata@math.u-strasbg.fr}\cr
\noalign{\medskip}
Doron Zeilberger\cr
Department of Mathematics\cr
Hill Center-Busch Campus\cr
Rutgers, The State University of New Jersey\cr
110 Frelinghuysen Rd\cr
Piscataway, NJ 08854-8019, USA \cr
\noalign{\smallskip}
{\tt zeilberg@math.rutgers.edu}\cr
}


\bye



