text:
# Ellipsoidal Tight Frames and Projection Decompositions of Operators

## Introduction

Frames were first introduced by Dufflin and Schaeffer  in 1952 as a component in the development of non-harmonic Fourier series, and a paper by Daubechies, Grossmann, and Meyer  in 1986 initiated the use of frame theory in signal processing. A frame on a separable Hilbert space $``$ is defined to be a complete collection of vectors $`\{x_i\}`$ for which there exists constants $`0<AB`$ such that for any $`x`$,

$$Ax^2\underset{i}{}|x,x_i|^2Bx^2$$

The constants $`A`$ and $`B`$ are known as the frame bounds. The collection is called a tight frame if $`A=B`$, and a Parseval frame if $`A=B=1`$. (In some of the existing literature, Parseval frames have been called normalized tight frames, however it should be noted that other authors have used the term normalized to describe a frame consisting only of unit vectors.) The length of a frame is the number of vectors it contains, which cannot be less than the Hilbert space dimension. References in the study of frames include , , and .

Hilbert space frames are used in a variety of signal processing applications, often demanding additional structure. Tight frames may be constructed having specified length, components having a predetermined sequence of norms, or with properties making them resilient to erasures. For examples, see , , , and . One area of rapidly advancing research lies in describing tight frames in which all the vectors are of equal norm, and thus are elements of a sphere. ,

Since frame theory is geometric in nature, it is natural to ask which other surfaces in a finite or infinite dimensional Hilbert space contain tight frames. By an ellipsoidal surface we mean the image of the unit sphere $`𝒮_1=\{x:x=1\}`$ under a bounded invertible operator $`T()`$. Let $`_T`$ denote the ellipsoidal surface $`_T=T𝒮_1`$. A frame contained in $`_T`$ is called an ellipsoidal frame, and if it is tight it is called an ellipsoidal tight frame (ETF) for that surface. We say that a frame bound K is attainable for $`_T`$ if there is an ETF for $`_T`$ with frame bound K. If an ellipsoid $``$ is a sphere we will call a frame in $``$ spherical.

Given an ellipsoid $``$, we can assume $`=_T`$ where $`T`$ is a positive invertible operator. Given $`A`$ an invertible operator, let $`A^{}=U|A^{}|`$ be the polar decomposition where $`|A^{}|=(AA^{})^{\frac{1}{2}}`$. Then $`A=|A^{}|U^{}`$. By taking $`T=|A^{}|`$, we that $`T𝒮_1=A𝒮_1`$. Moreover it is easily seen that the positive operator $`T`$ for which $`=_T`$ is unique.

Throughout the paper, $``$ will be a separable real or complex Hilbert space and for $`x,y,u`$, we will use the notation $`xy`$ to denote the rank-one operator $`uu,yx`$. Note that $`x=1`$ implies that $`xx`$ is a rank-1 projection.

Special thanks are given to our colleagues Pete Casazza, Vern Paulsen (see Remark 15), and Nicolaas Spronk for useful conversations concerning the material in this paper, and also to undergraduate REU/VIGRE research students Emily King, Nate Strawn and Justin Turner for taking part in discussions on ellipsoidal frames. This research project began in an REU/VIGRE seminar course at Texas A&M University in Summer 2002 in which all the co-authors were participants.

## 1. Theorems

There are three theorems in this paper. The first gives an elementary construction of ETF’s when $`=^n`$, and is proved in Section 2.

###### Theorem 1.

Let $`n,k`$ with $`nk`$, let $`a_1,\mathrm{},a_n0`$ be such that $`r:=_1^na_j>0`$ and consider the (possibly degenerate) ellipsoid

$$=\{𝐱=(x_1,\mathrm{},x_n)^t^n\underset{1}{\overset{n}{}}a_jx_j^2=1\}.$$

Then there is a tight frame for $`^n`$ consisting of $`k`$ vectors $`𝐮_1,\mathrm{},𝐮_k`$.

This result is valid for degenerate ellipsoids (in which some of the major axes are infinitely long). Our method of proof provides geometric insight to the problem, but does not extend to infinite dimensions.

We note that, in the non-degenerate case, the definition of an ellipsoidal surface $``$ given in Theorem 1, is equivalent to the definition given in the introduction, specifying that the Hilbert space be $`^n`$. Indeed, if $`a_i>1`$ for all $`i=1,\mathrm{},n`$ and if $`D=\text{diag}(a_1,a_2,\mathrm{}a_n)`$, then $`_{i=1}^na_ix_i^2=1`$ iff $`Dx,x=1`$ iff $`D^{\frac{1}{2}}x=1`$ iff $`D^{\frac{1}{2}}x𝒮_1(^n)`$ iff $`xD^{\frac{1}{2}}𝒮_1(^n)`$. So $`=_T`$ for $`T=D^{\frac{1}{2}}`$, and thus $``$ has the requisite form. To reverse this argument for a non-diagonal positive operator $`T`$, first diagonalize it by an orthogonal transformation given by rotations. Reversing the steps will then show that $`_T`$ is equivalent to $``$ for some choice of positive constants $`\{a_1,\mathrm{}a_n\}`$.

The second theorem is used to prove Theorem 3 in the infinite dimensional case. It has independent interest to operator theory, and to our knowledge is a new result. The proof, as well as a the corresponding result in finite dimensions (Proposition 6), is contained in Section 3. Some preliminaries are required before we state Theorem 2.

It is well-known (see ) that a separably acting positive operator $`A`$ decomposes as the direct sum of a positive operator $`A_1`$ with nonatomic spectral measure and a positive operator $`A_2`$ with purely atomic spectral measure (i.e. a diagonalizable operator). For $`B()`$, the essential norm of $`B`$ is:

$$B_{ess}:=inf\{BK:K\text{is a compact operator in}()\}$$

In the proof of Proposition 11, we have the special case where $`A`$ is a diagonal operator, $`A=\text{diag}(a_1,a_2,\mathrm{})`$, with respect to some orthonormal basis. In this case, it is clear that

$$A_{ess}=sup\{\alpha >0:|a_i|\alpha \text{for infinitely many}i\}$$

For a positive operator $`A`$ with spectrum $`\sigma (A)`$, we have $`A=sup\{\lambda :\lambda \sigma (A)\}`$ and if $`A`$ is invertible, then $`A^1^1=inf\{\lambda :\lambda \sigma (A)\}`$. Similarly, $`A_{ess}=sup\{\lambda :\lambda \sigma _{ess}(A)\}`$ and $`A^1_{ess}^1=inf\{\lambda :\lambda \sigma _{ess}(A)\}`$. In particular, $`A^1^1A^1_{ess}^1A_{ess}A`$.

For $`A`$ a positive operator, we say that $`A`$ has a projection decomposition if $`A`$ can be expressed as the sum of a finite or infinite sequence of (not necessarily mutually orthogonal) self-adjoint projections, with convergence in the strong operator topology.

###### Theorem 2.

Let $`A`$ be a positive operator in $`()`$ for $``$ a real or complex Hilbert space with infinite dimension, and suppose $`A_{ess}>1`$. Then $`A`$ has a projection decomposition.

Note that in this theorem, $`A`$ need not be invertible. There are theorems in the literature (e.g. ) expressing operators as linear combinations of projections and as sums of idempotents (non self-adjoint projections). The decomposition in Theorem 2 is different in that each term is a self-adjoint projection rather than a scalar multiple of a projection.

The next theorem states that every ellipsoidal surface contains a tight frame. We also include some detailed information about the nature of the set of attainable frame bounds.

###### Theorem 3.

Let T be a bounded invertible operator on a real or complex Hilbert space. Then the ellipsoidal surface $`_T`$ contains a tight frame. If $``$ is finite dimensional with n = dim $``$, then for any integer $`kn`$, $`_T`$ contains a tight frame of length $`k`$, and every ETF on $`_T`$ of length $`k`$ has frame bound $`K=k\left[\text{trace}(T^2)\right]^1`$. If $`\text{dim}=\mathrm{}`$, then for any constant $`K>T^2_{ess}^1`$, $`_T`$ contains a tight frame with frame bound $`K`$.

## 2. A Construction of ETFs in $`^n`$

We begin by showing that every ellipsoid can be scaled to contain an orthonormal basis.

###### Lemma 4.

Let $`n`$, let $`a_1,\mathrm{},a_n0`$ be such that $`_1^na_j=n`$ and let

$$=\{𝐱=(x_1,\mathrm{},x_n)^t^n\underset{1}{\overset{n}{}}a_jx_j^2=1\}.$$

Then there is an orthonormal basis $`𝐯_1,\mathrm{},𝐯_n`$ for $`^n`$ consisting of vectors $`𝐯_j`$.

###### Proof.

Proceed by induction on $`n`$. The case $`n=1`$ is trivial. Assume $`n2`$ and without loss of generality suppose $`a_11`$ and $`a_21`$. Let $`\theta `$ be such that $`a_1(\mathrm{cos}\theta )^2+a_2(\mathrm{sin}\theta )^2=1`$ and let $`b_2=a_1(\mathrm{sin}\theta )^2+a_2(\mathrm{cos}\theta )^2`$. Consider the rotation matrix

$$R=\left(\begin{array}{cc}\mathrm{cos}\theta & \mathrm{sin}\theta \\ \mathrm{sin}\theta & \mathrm{cos}\theta \\ & & 1\\ & & & \mathrm{}\\ & & & & 1\end{array}\right).$$

Then

$$R^1=\{(y_1,\mathrm{},y_n)^t^ny_1^2+2(a_1a_2)y_1y_2\mathrm{cos}\theta \mathrm{sin}\theta +b_2y_2^2+\underset{3}{\overset{n}{}}a_jy_j^2=1\}.$$

We have $`b_2+_3^na_j=n1`$. Let $`𝒱`$ be the subspace of $`^n`$ consisting of all vectors of the form $`(0,x_2,\mathrm{},x_n)^t`$ By the induction hypothesis, there is an orthonormal basis $`𝐮_2,\mathrm{},𝐮_n`$ for $`𝒱`$ consisting of vectors $`𝐮_jR^1`$. Let $`𝐮_1=(1,0,\mathrm{},0)^t^n`$, and let $`𝐯_j=R𝐮_j`$. Then $`𝐯_1,\mathrm{},𝐯_n`$ is an orthonormal basis for $`^n`$ consisting of vectors $`𝐯_j`$. ∎

In the case of a general ellipsoid, where $`_{j=1}^na_j=r>0`$, the lemma gives a constant multiple of an orthonormal basis on the ellipsoid.

###### Proof of Theorem 1.

Consider the isometry $`W:^n^k`$ and the projection $`P=W^{}:^k^n`$ given by

$`W(x_1,\mathrm{},x_n)^t`$ $`=(x_1,\mathrm{},x_n,0,\mathrm{},0)^t`$
$`P(x_1,\mathrm{},x_k)^t`$ $`=(x_1,\mathrm{},x_n)^t.`$
Let $`a_j=0`$ for $`n+1jk`$ and let

$$^{}=\{𝐲=(y_1,\mathrm{},y_k)^t^k\underset{1}{\overset{k}{}}a_jy_j^2=1\}.$$

By Lemma 4, there is a multiple of an orthonormal basis $`𝐯_1,\mathrm{},𝐯_k`$ for $`^k`$ consisting of vectors $`𝐯_j^{}`$. Let $`𝐮_j=P𝐯_j`$. Then $`𝐮_j`$. Moreover, $`𝐮_1,\mathrm{},𝐮_k`$ is a tight frame for $`^n`$, because if $`𝐱^n`$, then

$$\underset{j=1}{\overset{k}{}}|𝐱,𝐮_j|^2=\underset{j=1}{\overset{k}{}}|W𝐱,𝐯_j|^2=\frac{k}{r}W𝐱^2=\frac{k}{r}𝐱^2.$$

###### Remark 5.

It is an elementary result in matrix theory \[11, Thm. 1.3.4\] that for any real $`n\times n`$ matrix $`B`$ acting on $`^n`$ there is an orthonormal basis $`\{u_1,\mathrm{}u_n\}`$ for $`^n`$ so that the diagonal elements $`Bu_i,u_i`$ of $`B`$ with respect to $`\{u_1,\mathrm{}u_n\}`$ are all equal to $`\frac{1}{n}\left[\text{trace}(B)\right]`$. If we let $`D=\text{diag}(a_1,\mathrm{}a_n)`$, where the numbers $`a_i`$ are as in Lemma 4, then the condition $`Dv,v=1`$ for a vector $`v`$ is exactly the condition for $`v`$ to be on the ellipsoid $``$. Thus, letting $`B=D`$ and $`v_i=u_i`$ yields another proof of Lemma 4. The merit of the proof we give is that it is algorithmic and relates well to the paper. It was obtained by the second author in an undergraduate research (REU) program in which the other co-authors were mentors.

## 3. Projection Decompositions for Positive Operators

The arguments in the remainder of this paper hold for $``$ either a real or complex Hilbert space.

###### Proposition 6.

Let $`A()`$ be a finite rank positive operator with integer trace $`k`$. If $`krank(A)`$, then $`A`$ is the sum of k projections of rank one.

###### Proof.

We will construct unit vectors $`x_1,x_2,\mathrm{}x_k`$ so that $`A`$ is the sum of the projections $`x_ix_i`$ . The proof uses induction on $`k`$. Let $`n=\text{rank}(A)`$ and write $`_n=\text{range}(A)`$. If $`k=1`$, then $`A`$ must itself be a rank-1 projection. Assume $`k2`$. Select an orthonormal basis $`\{e_i\}_{i=1}^n`$ for $`_n`$ such that $`A`$ can be written on $`_n`$ as a diagonal matrix with positive entries $`a_1a_2\mathrm{}a_n>0`$.

Case 1: $`(k>n)`$ In this case, we have $`a_1>1`$, so we can take $`x_k=e_1`$. The remainder on $`_n`$

$$A(x_kx_k)=\text{diag}(a_11,a_2,\mathrm{},a_n)$$

has positive diagonal entries, still has rank $`n`$, and now has trace $`k1n`$. By the inductive hypothesis, the result holds.

Case 2: $`(k=n)`$ We now have that $`a_11`$ and $`a_n1`$. Given any finite rank, self-adjoint $`R()`$, let $`\mu _n(R)`$ denote the $`n`$-th largest eigenvalue of $`R`$ counting multiplicity. Note that $`\mu _n(A(e_1e_1))0`$, $`\mu _n(A(e_ne_n))0`$, and $`\mu _n(A(xx))`$ is a continuous function of $`x_n`$. Hence, there exists $`y_n`$ such that $`\mu _n(A(yy))=0`$. Choose $`x_k=y`$. Note the remainder $`(A(x_kx_k))0`$ and

$`\text{trace}(A(x_kx_k))`$ $`=`$ $`n1`$
$`\text{rank}(A(x_kx_k))`$ $`=`$ $`n1=k1`$
Again, by the inductive hypothesis, the result holds.

###### Lemma 7.

Let $`P_1,P_2,\mathrm{}P_n`$ be mutually orthogonal projections on a Hilbert space $``$, all of the same nonzero rank $`k`$, where $`k`$ can be finite or infinite. Let $`r_1,r_2,\mathrm{},r_n`$ be nonnegative real numbers, and let $`r=_1^nr_i`$. Define the operator:

$$A=r_1P_1+r_2P_2+\mathrm{}+r_nP_n$$

If the sum $`r`$ is an integer and $`rn`$, then there exist rank-$`k`$ projections $`Q_1,\mathrm{},Q_r`$ such that:

$$A=Q_1+Q_2+\mathrm{}+Q_r$$

###### Proof.

If $`k=1`$, then $`r=\text{trace}(A)`$ and we have $`\text{rank}(A)nr`$, so the result follows from Proposition 6. If $`k>1`$, each projection $`P_i`$ can be written as a sum of $`k`$ mutually orthogonal rank-1 projections:

$$P_i=P_{i1}+P_{i2}+\mathrm{}+P_{ik}$$

(Here and elsewhere in this proof, sums with indices running from $`1`$ to $`k`$ should be interpreted as infinite sums in the case where $`k=\mathrm{}`$.) All rank-1 projections $`P_{ij}`$ are thus mutually orthogonal. Define operators $`A_1,\mathrm{},A_k`$:

$$A_j=r_1P_{1j}+r_2P_{2j}+\mathrm{}+r_nP_{nj}$$

Now, $`A=A_1+\mathrm{}+A_k`$ and each $`A_j`$ has rank $`n`$ and trace $`r`$. By Proposition 6, each $`A_j`$ can be written as a sum of $`r`$ rank-1 projections:

$$A_j=T_{j1}+T_{j2}+\mathrm{}+T_{jr}$$

Note that projections $`T_{jl}`$ and $`T_{mp}`$ are orthogonal if $`jm`$. Define the rank-k projections $`Q_1,\mathrm{},Q_r`$ by:

$$Q_l=T_{1l}+T_{2l}+\mathrm{}+T_{kl}$$

This gives $`A=Q_1+Q_2+\mathrm{}+Q_r`$. ∎

###### Lemma 8.

Let $`A`$ be a positive operator with finite spectrum contained in the rationals $``$, such that all spectral projections are infinite dimensional, and also such that $`A>1`$. Then $`A`$ is a finite sum of self-adjoint projections.

###### Proof.

By hypothesis, there are mutually orthogonal infinite-rank projections $`P_1,\mathrm{},P_n`$ and positive rational numbers $`r_1r_2\mathrm{}r_n`$ such that

$$A=r_1P_1+\mathrm{}+r_nP_n$$

By hypothesis $`A>1`$, hence $`r_1>1`$.

Write $`r_i=s_i/t_i`$ with $`s_i`$ and $`t_i`$ positive integers, and let $`s=_{i=1}^ns_i,t=_{i=1}^nt_i`$. We may assume $`st`$, for otherwise we can choose $`m`$ such that

$$ms_1+s_2+\mathrm{}+s_nmt_1+t_2+\mathrm{}+t_n$$

and replace $`s_1`$ with $`ms_1`$ and $`t`$ with $`mt_1`$.

Each $`P_i`$ can be written as a sum of $`t_i`$ mutually orthogonal infinite rank projections $`P_{ij};j=1,\mathrm{}t_i`$ which then allows us to write:

$$A=\underset{i=1}{\overset{n}{}}\underset{j=1}{\overset{t_i}{}}r_iP_{ij}$$

The operator is now a linear combination of $`t_i=t`$ mutually orthogonal projections of infinite rank, and the sum of the coefficients is now an integer $`t_ir_i=s_i=s`$. Since $`st`$, Lemma 7 implies that A can be written as a sum of $`s`$ projections.

###### Lemma 9.

Let $`A`$ be a positive operator which has a projection-decomposition. Then either $`A`$ is a projection or $`A>1`$.

###### Proof.

Suppose, to obtain a contradiction, that $`A1`$ and that $`A`$ is not a projection. By assumption, $`A=P_i`$ with the series converging strongly. Thus $`AP_i0`$ for all $`i`$. Then $`P_i(AP_i)P_i0`$, so $`P_iAP_iP_i`$.

Let $`𝒦_i=P_i`$ and $`B=P_iA|_{𝒦_i}`$. Then $`B_i`$ is positive and $`B_iI_{𝒦_i}`$ (the identity operator on $`𝒦_i`$). Since $`B_i1`$, this implies $`B_i=I_{𝒦_i}`$, and thus $`P_iAP_i=P_i`$.

Now, $`P_i=P_i(_jP_j)P_i=P_i+_{ji}P_iP_jP_i`$, so $`_{ji}P_iP_jP_i=0`$. Since each $`P_iP_jP_i0`$, this implies $`P_iP_jP_i=0`$. Thus, $`(P_jP_i)^{}(P_jP_i)=0`$, so $`P_jP_i=0`$. Since this is true for arbitrary $`i,j`$ with $`ij`$, this shows that $`A`$ is the sum of mutually orthogonal projections, and hence is itself a projection. The contradiction proves the result. ∎

###### Proposition 10.

Let $`A`$ be a positive operator in $`()`$ with the property that all nonzero spectral projections for $`A`$ are of infinite rank. If $`A>1`$, then $`A`$ admits a projection decomposition as a sum of infinite rank projections.

###### Proof.

We will show that $`A`$ can be written as a sum $`A=_{i=1}^{\mathrm{}}A_i`$ of positive operators, each satisfying the hypotheses of Lemma 8, where the sum converges in the strong operator topology. We can then decompose each of the operators $`A_i`$ as a finite sum of projections $`A_{ij}`$ and then re-enumerate with a single index to obtain a sequence $`Q_i`$ of projections which sum to $`A`$ in SOT. Indeed, the partial sums of $`Q_i`$ are dominated by $`A`$, hence $`Q_i`$ converges strongly to some operator $`C`$, and since the partial sums of $`A_i`$ are also partial sums of $`Q_i`$, the sequence of partial sums of $`Q_i`$ has a subsequence which converges to $`A`$, and hence $`C=A`$.

By hypothesis, we have $`A>1`$. We may choose a positive rational number $`\alpha >1`$ and a nonzero spectral projection $`G`$ for $`A`$ such that $`A\alpha G`$. Let $`B=A\alpha G`$, so that $`B0`$. Using a standard argument, we can write $`B=_{i=1}^{\mathrm{}}B_i`$, where each $`B_i`$ is a positive rational multiple of a spectral projection for $`A`$, with convergence in the SOT.

We can write $`G=G_i`$ as an infinite direct sum of nonzero infinite rank projections, with the requirement that $`G_i`$ be a subprojection of $`G`$ which commutes with all the spectral projections for $`A`$. (This can clearly be done when the spectral projections for $`A`$ are all of infinite rank.) Now, let $`A_i=\alpha G_i+B_i`$. We have $`A_i\alpha >1`$.

By Lemma 8, it follows that $`A_i`$ is a finite sum of projections. By the construction, we have the requisite form $`A=A_i`$.

###### Proposition 11.

Let $`A`$ be a positive operator in $`()`$ which is diagonal with respect to some orthonormal basis $`\{e_i\}`$ for the Hilbert space $``$. Suppose $`A_{ess}>1`$. Then there is a sequence of rank-1 projections $`\{P_i\}_{i=1}^{\mathrm{}}`$ such that $`A=P_i`$, where the sum converges in the strong operator topology.

###### Proof.

Write $`A`$ as diag$`(a_0,a_1,\mathrm{})`$ and let $`E_n=e_ne_n`$. Since $`A_{ess}>1`$, there is a constant $`\alpha >1`$ such that $`a_i\alpha `$ for infinitely many i. Let $`k2`$ be an integer such that $`1+\frac{2}{k1}\alpha `$. Permuting if necessary, we can without loss of generality assume that the indices $`n`$ for which $`a_n<\alpha `$ are all multiples of $`k`$.

Let $`B_0=a_0E_0+\mathrm{}+a_{k1}E_{k1}`$. Therefore, we have rank$`(B_0)k`$ and

$`\text{trace}(B_0)`$ $`=`$ $`{\displaystyle \underset{0}{\overset{k1}{}}}a_i`$
$``$ $`a_0+(k1)\alpha `$
$``$ $`a_0+(k1)\left(1+{\displaystyle \frac{2}{k1}}\right)`$
$`=`$ $`a_0+k+1`$
Let $`L_0`$ be the greatest integer less than trace $`(B_0)`$. Then $`L_0k+1`$. Define $`a_{k1}^{}`$ to be the real number $`0a_{k1}^{}a_{k1}`$ such that if

$$B_0^{}=a_0E_0+\mathrm{}+a_{k2}E_{k2}+a_{k1}^{}E_{k1}$$

then

$$\text{trace}(B_0^{})=L_0k+1>\text{rank}(B_0^{})$$

By Proposition 6, $`B_0^{}`$ can be written as a sum of $`L_0`$ rank-1 projections.

In the next step, let $`a_{k1}^{\prime \prime }=a_{k1}a_{k1}^{}`$ and let

$$B_1=a_{k1}^{\prime \prime }E_{k1}+a_kE_k+a_{k+1}E_{k+1}+\mathrm{}+a_{2k1}E_{2k1}$$

Thus rank $`(B_1)k+1`$ and

$`\text{trace}(B_1)`$ $`=`$ $`a_{k1}^{\prime \prime }+a_k+(a_{k+1}+\mathrm{}+a_{2k1})`$
$``$ $`a_{k1}^{\prime \prime }+a_k+(k1)\alpha `$
$``$ $`a_{k1}^{\prime \prime }+a_k+(k1)\left(1+{\displaystyle \frac{2}{k1}}\right)`$
$`=`$ $`a_{k1}^{\prime \prime }+a_k+k+1`$
$``$ $`\text{rank}(B_1)`$
Construct $`B_1^{}`$ in a similar manner, so that its trace is an integer greater than or equal to its rank. Then $`B_1^{}`$ can be written as a sum of rank-1 projections using Proposition 6.

Proceeding recursively in a like manner, we may write $`A=_{j=1}^{\mathrm{}}B_j^{}`$ converging in SOT, where each $`B_j^{}`$ is a positive operator supported in $`E_{jk1}+\mathrm{}+E_{(j+1)k1}`$ and with trace$`(B_j^{})`$ an integer that is greater than or equal to rank$`(B_j^{})`$. Invoking Proposition 6 again to write each $`B_j^{}`$ as a sum of rank-1 projections, the proposition is proved.

###### Proof of Theorem 2.

Write $`A=A_1+A_2`$, where $`A_1`$ and $`A_2`$ respectively denote the nonatomic and purely atomic parts of $`A`$. Then $`A_1_{ess}=A_1`$, and $`A_{ess}=\mathrm{max}\{A_1,A_2_{ess}\}`$. So $`A_{ess}>1`$ implies $`A_1>1`$ or $`A_2_{ess}>1`$. Suppose first that $`A_1>1`$. Then there is a nonzero spectral projection $`P`$ for $`A_1`$ and a constant $`\alpha >1`$ such that $`A_1P\alpha P`$. Let $`Q`$ be a nonzero spectral projection for $`A_1`$ dominated by $`P`$ such that $`PQ0`$. Then $`A_1\alpha Q`$ satisfies the hypotheses of Proposition 10, so is projection decomposable. Also, $`QA_2=A_2Q=0`$, so $`A_2+\alpha Q`$ is a diagonal operator with essential norm greater than or equal to $`\alpha `$, and so it is projection decomposable by Proposition 11. The result follows by decomposing $`A_1\alpha Q`$ and $`A_2+\alpha Q`$ as sums of projections and combining the series.

For the case $`A_11`$ and $`A_2_{ess}>1`$, we use a similar argument. There is a constant $`\alpha >1`$ and an infinite rank spectral projection $`P`$ for $`A_2`$ such that $`A_2\alpha P0`$. Then $`P`$ dominates a projection $`Q`$ that commutes with $`A_2`$ such that both $`Q`$ and $`PQ`$ are of infinite rank. Then $`A_2\alpha Q`$ satisfies Proposition 11 and hence has a projection decomposition. The operator $`A_1+\alpha Q`$ has norm greater than or equal to $`\alpha `$ and all of its nonzero spectral projections have infinite rank, so it satisfies the hypotheses of Proposition 10. Thus, $`A_1+\alpha Q`$ has a projection decomposition, and we combine with the decomposition of $`A_2\alpha Q`$ to get a projection decomposition for $`A`$. ∎

## 4. Ellipsoidal Tight Frames

Let $``$ be a finite or countably infinite dimensional Hilbert space. Let $`\{x_j\}_{j𝕁}`$ be a frame for $``$, where $`𝕁`$ is some index set. Consider the standard frame operator defined by:

$$Sw=\underset{j𝕁}{}w,x_jx_j=\underset{j𝕁}{}\left(x_jx_j\right)w$$

Thus, $`S=_𝕁x_jx_j`$, where this series of positive rank-1 operators converges in the strong operator topology (i.e. the topology of pointwise convergence). In the special case where each $`x_j=1`$, $`S`$ is the sum of the rank-1 projections $`P_j=x_jx_j`$. If we let $`y_j=S^{\frac{1}{2}}x_j`$, then it is well-known that $`\{y_j\}_{j𝕁}`$ is a Parseval frame (i.e. tight with frame bound 1). If each $`x_j=1`$, then $`\{y_j\}_{j𝕁}`$ is an ellipsoidal tight frame for the ellipsoidal surface $`_{S^{\frac{1}{2}}}=S^{\frac{1}{2}}𝒮_1`$. Moreover, it is well-known (see ) that a sequence $`\{x_j\}j𝕁`$ is a tight frame for $``$ if and only if the frame operator $`S`$ is a positive scalar multiple of the identity, i.e. $`S=KI`$, and in this case $`K`$ is the frame bound.

###### Remark 12.

From the above paragraph, it is clear that a positive invertible operator is the frame operator for a frame of unit vectors if and only if it admits a projection decomposition. (Each projection can be further decomposed into rank-1 projections, as needed.)

The link between Theorem 2 and Theorem 3 is the following:

###### Proposition 13.

Let $`T`$ be a positive invertible operator in $`()`$, and let $`K>0`$ be a positive constant. The ellipsoidal surface $`_T=T𝒮_1`$ contains a tight frame $`\{y_j\}`$ with frame bound $`K`$ if and only if the operator $`R=KT^2`$ admits a projection decomposition. In this case, $`R`$ is the frame operator for the spherical frame $`\{T^1y_j\}`$.

###### Proof.

We present the proof in the infinite-dimensional setting, and note that the calculations in the finite dimensional case are identical but do not require discussion of convergence. Let $`𝕁`$ be a finite or infinite index set. Assume $`_T`$ contains a tight frame $`\{y_j\}_{j𝕁}`$ with frame bound $`K`$. Then $`_{j𝕁}y_jy_j=KI`$, with the series converging in the strong operator topology. Let $`x_j:=T^1y_j𝒮_1`$, so $`x_jx_j`$ are projections. We can then compute:

$`R=KT^2`$ $`=`$ $`T^1\left({\displaystyle \underset{j𝕁}{}}y_jy_j\right)T^1`$
$`=`$ $`{\displaystyle \underset{j𝕁}{}}T^1y_jT^1y_j={\displaystyle \underset{j𝕁}{}}x_jx_j`$
This shows that $`R`$ can be decomposed as required. Conversely, suppose $`R`$ admits a projection decomposition $`R=P_j`$, where $`\{P_j\}`$ are self-adjoint projections and convergence is in the strong operator topology. We can assume that the $`P_j`$ have rank-1, for otherwise we can decompose each $`P_j`$ as a strongly convergent sum of rank-1 projections, and re-enumerate appropriately. Since $`P_j0`$, the convergence is independent of the enumeration used. Write $`P_j=x_jx_j`$ for some unit vector $`x_j`$. Letting $`y_j=Tx_j`$, we have $`y_j_T`$, and we also have:

$`KI=TRT`$ $`=`$ $`T\left({\displaystyle \underset{j𝕁}{}}x_jx_j\right)T`$
$`=`$ $`{\displaystyle \underset{j𝕁}{}}Tx_jTx_j={\displaystyle \underset{j𝕁}{}}y_jy_j`$
This shows that $`y_jy_j`$ converges in the strong operator topology to $`KI`$. Thus, $`\{y_j\}_{j𝕁}`$ is a tight frame on $`_T`$, as required.

###### Proof of Theorem 3.

Let $``$ be an ellipsoid. Then $`=_T=T𝒮_1`$ for some positive invertible $`T()`$. Let $`K`$ be a positive constant, and let $`R=KT^2`$.

The condition $`K>T^2_{ess}^1`$ implies $`R_{ess}>1`$. So, by Theorem 2, $`R`$ admits a projection decomposition, and thus Proposition 13 implies that $``$ contains a tight frame with frame bound $`K`$.

In the finite dimensional case, let $`n=\text{dim}`$. Proposition 13 states that $``$ will contain a tight frame with frame bound $`D`$ if and only if $`KT^2`$ admits a projection decomposition, and by Proposition 6 this happens if and only if trace $`(KT^2)`$ is an integer $`kn`$, and in this case $`k`$ is the length of the frame. Thus, we have $`K=k[\text{trace}(T^2)]^1`$. Therefore, every ellipsoid $`=_T`$ contains a tight frame of every length $`kn`$, and every such tight frame has frame bound $`k[\text{trace}(T^2)]^1`$. ∎

###### Corollary 14.

Every positive invertible operator $`S`$ on a separable Hilbert space $``$ is the frame operator for a spherical frame. If $``$ has finite dimension $`n`$, then for every integer $`kn`$, $`S`$ is the frame operator for a spherical frame of length $`k`$, and the radius of the sphere is $`\sqrt{\frac{\text{trace}(S)}{k}}`$. If $``$ is infinite-dimensional, the radius of the sphere can be taken to be any positive number $`r<S_{\text{ess}}^{\frac{1}{2}}`$.

###### Proof.

In the finite dimensional case, let $`c=\frac{k}{\text{trace}(S)}`$ and $`A=cS`$, so that $`\text{trace}(A)=k`$. Then, by Proposition 6, $`A`$ has a projection decomposition into $`k`$ rank-1 projections, making $`A`$ the frame operator for the frame of unit vectors $`\{x_i\}_{i=1}^k`$. Thus, $`S`$ is the frame operator for $`\left\{\frac{x_i}{\sqrt{c}}\right\}_{i=1}^k`$.

When $``$ has infinite dimension, let $`c`$ be any constant greater than $`S_{\text{ess}}^1`$, and let $`A=cS`$. The hypotheses of Theorem 2 are satisfied, so $`A`$ admits a projection decomposition. Then $`A`$ is the frame operator for a frame $`\{x_i\}`$ of unit vectors, so $`S`$ is the frame operator for the spherical frame $`\left\{{\displaystyle \frac{x_i}{\sqrt{c}}}\right\}`$. ∎

###### Remark 15.

We know of at least two groups who have independently and simultaneously proved our finite-dimensional ellipsoidal tight frame results. Paulsen and Holmes have a proof similar to the discussion in Remark 5.  Casazza and Leon have shown in  the existence of “spherical frames for $`^n`$ with a given frame operator”, which is an equivalent problem.


format: text

text:
# Accurate Charge-Dependent Nucleon-Nucleon Potential at Fourth Order of Chiral Perturbation Theory

## Abstract

We present the first nucleon-nucleon potential at next-to-next-to-next-to-leading order (fourth order) of chiral perturbation theory. Charge-dependence is included up to next-to-leading order of the isospin-violation scheme. The accuracy for the reproduction of the $`NN`$ data below 290 MeV lab. energy is comparable to the one of phenomenological high-precision potentials. Since $`NN`$ potentials of order three and less are known to be deficient in quantitative terms, the present work shows that the fourth order is necessary and sufficient for a reliable $`NN`$ potential derived from chiral effective Lagrangians. The new potential provides a promising starting point for exact few-body calculations and microscopic nuclear structure theory (including chiral many-body forces derived on the same footing).

The theory of nuclear forces has a long history. Based upon the Yukawa idea , first field-theoretic attempts  to derive the nucleon-nucleon ($`NN`$) interaction focused on pion-exchange, resulting in the $`NN`$ potentials by Gartenhaus  and by Signell and Marshak . However, even qualitatively, these potentials barely agreed with empirical information on the nuclear force. So, these “pion theories” of the 1950s are generally judged as failures—for reasons we understand today: pion dynamics is constrained by chiral symmetry, a crucial point that was unknown in the 1950s.

Historically, the experimental discovery of heavy mesons  in the early 1960s saved the situation. The one-boson-exchange (OBE) model  emerged which is still the most economical and quantitative phenomenology for describing the nuclear force . The weak point of this model, however, is the scalar-isoscalar “sigma” or “epsilon” boson, for which the empirical evidence remains controversial. Since this boson is associated with the correlated (or resonant) exchange of two pions, a vast theoretical effort that occupied more than a decade was launched to derive the 2$`\pi `$-exchange contribution of the nuclear force, which creates the intermediate range attraction. For this, dispersion theory as well as field theory were invoked producing the Paris  and the Bonn  potentials.

The nuclear force problem appeared to be solved; however, with the discovery of quantum chromo-dynamics (QCD), all “meson theories” had to be relegated to models and the attempts to derive the nuclear force started all over again.

The problem with a derivation from QCD is that this theory is non-perturbative in the low-energy regime characteristic of nuclear physics, which makes direct solutions impossible. Therefore, during the first round of new attempts, QCD-inspired quark models  became popular. These models were able to reproduce qualitatively some of the gross features of the nuclear force. However, on a critical note, it has been pointed out that these quark-based approaches were nothing but another set of models and, thus, did not represent any fundamental progress. Equally well, one may then stay with the simpler and much more quantitative meson models.

A major breakthrough occurred when the concept of an effective field theory (EFT) was introduced and applied to low-energy QCD. As outlined by Weinberg in a seminal paper , one has to write down the most general Lagrangian consistent with the assumed symmetry principles, particularly the (broken) chiral symmetry of QCD. At low energy, the effective degrees of freedom are pions and nucleons rather than quarks and gluons; heavy mesons and nucleon resonances are “integrated out”. So, in a certain sense we are back to the 1950s, except that we are smarter by 40 years of experience: broken chiral symmetry is a crucial constraint that generates and controls the dynamics and establishes a clear connection with the underlying theory, QCD.

The chiral effective Lagrangian is given by an infinite series of terms with increasing number of derivatives and/or nucleon fields, with the dependence of each term on the pion field prescribed by the rules of broken chiral symmetry . Applying this Lagrangian to $`NN`$ scattering generates an unlimited number of Feynman diagrams, which may suggest again an untractable problem. However, Weinberg showed  that a systematic expansion of the nuclear amplitude exists in terms of $`(Q/\mathrm{\Lambda }_\chi )^\nu `$, where $`Q`$ denotes a momentum or pion mass, $`\mathrm{\Lambda }_\chi 1`$ GeV is the chiral symmetry breaking scale, and $`\nu 0`$. For a given order $`\nu `$, the number of contributing terms is finite and calculable; these terms are uniquely defined and the prediction at each order is model-independent. By going to higher orders, the amplitude can be calculated to any desired accuracy. The scheme just outlined has become known as chiral perturbation theory ($`\chi `$PT).

Following the first initiative by Weinberg , pioneering work was performed by Ordóñez, Ray, and van Kolck  who constructed a $`NN`$ potenial in coordinate space based upon $`\chi `$PT at next-to-next-to-leading order (NNLO; $`\nu =3`$). The results were encouraging and many researchers  became attracted to the new field. Kaiser, Brockmann, and Weise  presented the first model-independent prediction for the $`NN`$ amplitudes of peripheral partial waves at NNLO. Epelbaum et al.  developed the first momentum-space $`NN`$ potential at NNLO.

In the 1990s, unrelated, parallel research showed that, for conclusive few-body calculations and meaningful microscopic nuclear structure predictions, the input $`NN`$ potential must be of the highest precision; i. e., it must reproduce the $`NN`$ data below about 300 MeV lab. energy with a $`\chi ^2/`$datum $`1`$. The family of high-precision $`NN`$ potentials  was developed which fulfills this requirement. Due to the outstanding accuracy of these $`NN`$ potentials, it was possible to pin down cases of few-body scattering and of nuclear structure that clearly require three-nucleon forces (3NF) for their miscroscopic explanation. Famous examples are the $`A_y`$ puzzle of $`N`$-$`d`$ scattering  and the ground state of 10.

One important advantage of $`\chi `$PT is that it makes specific predictions for many-body forces. For a given order of $`\chi `$PT, both 2N and 3N forces are generated on the same footing. At next-to-leading order (NLO), all 3NF cancel ; however, at NNLO and higher orders, well-defined, nonvanishing 3NF terms occur. As discussed, since 3NF effects are in general very subtle, it is only possible to demonstrate their necessity and relevance when the 2NF is of high precision.

$`NN`$ potentials based upon $`\chi `$PT at NNLO are poor in quantitative terms; they reproduce the $`NN`$ data below 290 MeV lab. energy with a $`\chi ^2`$/datum of more than 20 which is totally unacceptable. Clearly, there is a strong need for more precision, implying that going to higher order is necessary.

It is the purpose of this note to present the first $`NN`$ potential that is based consistently on $`\chi `$PT at next-to-next-to-next-to-leading order (N3LO; fourth order). We will show that, at this order, the accuracy is comparable to the one of the high-precision phenomenological potentials. Thus, the $`NN`$ potential at N3LO is the first to meet the requirements for a reliable input-potential for exact few-body and microscopic nuclear structure calculations (including chiral 3NF consistent with the chiral 2NF).

In $`\chi `$PT, the $`NN`$ amplitude is uniquely determined by two classes of contributions: contact terms and pion-exchange diagrams. At N3LO, there are two contacts of order $`Q^0`$ \[$`𝒪(Q^0)`$\], seven of $`𝒪(Q^2)`$, and 15 of $`𝒪(Q^4)`$, resulting in a total of 24 contact terms, which generate 24 parameters that are crucial for the fit of the partial waves with orbital angular momentum $`L2`$ .

Now, turning to the pion contributions: At leading order \[LO, $`𝒪(Q^0)`$, $`\nu =0`$\], there is only the wellknown static one-pion exchange (OPE). Two-pion exchange (TPE) starts at next-to-leading order (NLO, $`\nu =2`$), and there are further TPE contributions in any higher order. While TPE at NNLO was known for a while , TPE at N3LO has been calculated only recently by Kaiser . All $`2\pi `$ exchange contributions up to N3LO are summarized in a pedagogical and systematic fashion in Ref.  where the model-independent results for $`NN`$ scattering in peripheral partial waves are also shown. We use the analytic expressions published in Ref. . Finally, there is also three-pion exchange, which shows up for the first time at N3LO (two loops). In Ref. , it was demonstrated that the 3$`\pi `$ contributions at this order are negligible, which is why we leave them out.

For an accurate fit of the low-energy $`pp`$ and $`np`$ data, charge-dependence is important. We include charge-dependence up to next-to-leading order of the isospin-violation scheme (NLØ, in the notation of Ref. ). Thus, we include the pion mass difference in OPE and the Coulomb potential in $`pp`$ scattering, which takes care of the LØ contributions. At order NLØ we have pion mass difference in the NLO part of TPE, $`\pi \gamma `$ exchange , and two charge-dependent contact interactions of order $`Q^0`$ which make possible an accurate fit of the three different $`{}_{}{}^{1}S_{0}^{}`$ scattering lengths, $`a_{pp}`$, $`a_{nn}`$, and $`a_{np}`$.

Chiral perturbation theory is a low-momentum expansion. It is valid only for momenta $`Q\mathrm{\Lambda }_\chi 1`$ GeV. To enforce this, we multiply all expressions (contacts and irreducible pion exchanges) with a regulator function,

$$\mathrm{exp}\left[\left(\frac{p}{\mathrm{\Lambda }}\right)^{2n}\left(\frac{p^{}}{\mathrm{\Lambda }}\right)^{2n}\right],$$
(1)
where $`p`$ and $`p^{}`$ denote, respectively, the magnitudes of the initial and final nucleon momenta in the center-of-mass frame. We use $`\mathrm{\Lambda }=0.5`$ GeV throughout. The exponent $`2n`$ is chosen to be sufficiently large so that the regulator generates powers which are beyond the order ($`\nu =4`$) at which our calculation is conducted; i. e., terms up to $`Q^4`$ are not affected.

The contact terms plus irreducible pion-exchange expressions at N3LO, multiplied by the above regulator, define the $`NN`$ potential at N3LO. This potential is applied in a Lippmann-Schwinger equation to obtain the $`T`$-matrix from which phase shifts and $`NN`$ observables are calculated. The corresponding homogenous equation determines the properties of the two-nucleon bound state (deuteron).

The peripheral partial waves of $`NN`$ scattering with $`L3`$ are exclusively determined by OPE and TPE because the N3LO contacts contribute to $`L2`$ only. OPE and TPE at N3LO depend on the axial-vector coupling constant, $`g_A`$ (we use $`g_A=1.29`$), the pion decay constant, $`f_\pi =92.4`$ MeV, and eight low-energy constants (LEC) that appear in the dimension-two and dimension-three $`\pi N`$ Lagrangians (cf. Ref. ). In the optimization process, we varied three of them, namely, $`c_2`$, $`c_3`$, and $`c_4`$. We found that the other LEC are not very effective in the $`NN`$ system and, therefore, we kept them at the values determined from $`\pi N`$ (cf. Table I). The most influential constant is $`c_3`$, which has to be chosen on the low side (slightly more than one standard deviation below its $`\pi N`$ determination) for an optimal fit of the $`NN`$ data. Our choice for $`c_4`$, which is substantially above the value determined in $`\pi N`$, is necessary to bring the $`{}_{}{}^{3}F_{2}^{}`$ phase shift down.

The most important set of fit parameters are the ones associated with the 24 contact terms that rule the partial waves with $`L2`$. In addition, we have two charge-dependent contacts, which brings the number of contact parameters to 26. Since we treated three LEC as semi-free, the total number of parameters of the N3LO potential is 29.

In the optimization procedure, we fit first phase shifts, and then we refine the fit by minimizing the $`\chi ^2`$ obtained from a direct comparison with the data. The phase shifts at N3LO for $`np`$ scattering below 300 MeV lab. energy are displayed in Fig. 1. The $`\chi ^2/`$datum for the fit of the $`np`$ data below 290 MeV is shown in Table II, and the corresponding one for $`pp`$ is given in Table III. The $`\chi ^2`$ tables demonstrate a dramatic improvement of the $`NN`$ interaction order by order. It is clearly revealed that, at NLO and NNLO, the reproduction of the $`NN`$ data is of unacceptably poor quality. However, at N3LO, the quantitative character is comparable to the phenomenological high-precision Argonne $`V_{18}`$ potential .

In conclusion, we have developed the first $`NN`$ potential at fourth order of $`\chi `$PT . This potential is as quantitative as some so-called high-precision phenomenological potentials. Due to its basis in $`\chi `$PT, the many-body forces associated with this two-body force are well-defined. Thus, we have a promising starting point for exact few-body calculations and microscopic nuclear structure theory.

This work was supported by the U.S. National Science Foundation under Grant No. PHY-0099444 and by three Spanish foundations: the Ministerio de Ciencia y Tecnología under Contract No. BFM2001-3563, the Junta de Castilla y León under Contract No. SA-109/01, and the Ramón Areces Foundation.


text:
# Some New Aspects of the Coupon-Collector’s Problem

## 1 Introduction and results

The classical coupon collector’s problem is the following. Suppose that a breakfast cereal manufacturer offers a souvenir (“coupon”) hidden in each package of cereal, and there are $`d`$ different kinds of souvenirs altogether. The collector wants to have a complete collection of all $`d`$ souvenirs. What is the probability $`p(n,d)`$ that exactly $`n`$ boxes of cereal will have to be purchased in order to obtain, for the first time, a complete collection of at least one of each of the $`d`$ kinds of souvenir coupons?

The answer to that question is well known (e.g., , p. 132) to be

$$p(n,d)=\frac{d!}{d^n}\left\{\genfrac{}{}{0pt}{}{n1}{d1}\right\},$$
(1)
where the $`\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}`$’s are the Stirling numbers of the second kind.

We study, in this paper, a number of other aspects of this problem, as well as a generalization of it to a two-player game.

First, suppose we have two coupon collectors, drawing coupons simultaneously, and each seeking to obtain a complete collection of $`d`$ coupons. We ask for the probability that the two games are completed at the same time. The answer is given by (7) below. That answer is expressed in finite terms, owing to the closed form evaluation of the ordinary power series generating function for the squares of the Stirling numbers of the second kind, contained in (6).

Next we consider the following two-person game. Again two coupon collectors are simultaneously drawing coupons at random. This time we are interested in a ballot-like problem: what is the probability that the player who first completed a collection (the winner) was never behind (i.e., never had fewer distinct coupons) at any intermediate stage of the play? Here we give a complete answer to a slightly easier question, namely the following: what is the probability that after an initial segment of play in which the players are tied, one of them takes the lead and keeps the lead until the end. The answer is in eq. (2.8) below, and is obtained by the Gessel-Viennot theory of nonintersecting lattice paths.

In each of these cases the answer can first be written as an infinite series whose coefficients involve various products of Stirling numbers. What is interesting, though, is that in all such cases we are able to express the answers in finite terms. Indeed, one of our main results here is the observation that infinite series whose coefficients involve various powers and products of Stirling numbers of the second kind can readily be evaluated in finite terms.

In section 3 we return to the original collecting problem of obtaining at least one copy of each coupon, but now we study the variant of the problem in which a single collector wants to obtain at least $`h1`$ copies of each coupon. We obtain the generating function (35) for the probability that exactly $`n`$ trials are needed, the exact value of the average number of trials (40), and the asymptotic behavior (45) of these quantities as $`n\mathrm{}`$.

Finally, in section 4 we study the number of coupons that have been collected only once, at the end of a collection sequence. We find the distribution function (49) for this number, and show that the average number of these singletons is just the harmonic number $`H_d=1+1/2+\mathrm{}+1/d`$.

## 2 The two-person collecting competition

### 2.1 Simultaneous completion

We find now the probability of simultaneous completion of two independent coupon collecting sequences. Evidently this is,

$$\underset{n0}{}p(n,d)^2=\underset{n0}{}\frac{d!^2}{d^{2n}}\left\{\genfrac{}{}{0pt}{}{n1}{d1}\right\}^\text{2},$$
(2)
which expresses the answer as an infinite sum. We can rewrite this as a finite sum by finding a finite expression for the generating function for the squares of the Stirling numbers of the second kind,

$$F_k(x)=\text{def}\underset{nk}{}\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}^\text{2}x^n,$$

analogously to the well known generating function for these numbers themselves,

$$\underset{nk}{}\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}x^n=\frac{x^k}{(1x)(12x)\mathrm{}(1kx)}.$$
(3)
The easiest way to do this is via the standard explicit formula for these Stirling numbers, viz.

$`\left\{{\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right\}`$ $`=`$ $`{\displaystyle \frac{1}{k!}}{\displaystyle \underset{r=1}{\overset{k}{}}}(1)^{kr}\left({\displaystyle \genfrac{}{}{0pt}{}{k}{r}}\right)r^n(1kn)`$
$`=\text{def}`$ $`{\displaystyle \underset{r=1}{\overset{k}{}}}A_{k,r}r^{nk},`$
where we have written

$$A_{k,r}=\frac{(1)^{kr}r^k}{k!}\left(\genfrac{}{}{0pt}{}{k}{r}\right).$$
(5)
It follows that

$`F_k(x)=\text{def}{\displaystyle \underset{nk}{}}\left\{{\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right\}^\text{2}x^n`$ $`=`$ $`{\displaystyle \underset{nk}{}}x^n{\displaystyle \underset{r,s=1}{\overset{k}{}}}A_{k,r}A_{k,s}r^{nk}s^{nk}`$ (6)
$`=`$ $`x^k{\displaystyle \underset{r,s=1}{\overset{k}{}}}A_{k,r}A_{k,s}{\displaystyle \underset{nk}{}}(rsx)^{nk}`$
$`=`$ $`x^k{\displaystyle \underset{r,s=1}{\overset{k}{}}}{\displaystyle \frac{A_{k,r}A_{k,s}}{1rsx}},(|x|<{\displaystyle \frac{1}{k^2}}).`$
Thus for the simultaneous completion probability we obtain, from (2),

$$\underset{n0}{}p(n,d)^2=\frac{d!^2}{d^{2d}}\underset{r,s=1}{\overset{d1}{}}\frac{A_{d1,r}A_{d1,s}}{1\frac{rs}{d^2}},$$
(7)
by (6), where the $`A`$’s given by (5). This sequence of probabilities, for $`d=1,2,\mathrm{}`$, begins as

$$1,\frac{1}{3},\frac{11}{70},\frac{9}{91},\frac{688877}{9561123},\frac{358555}{6330324},\frac{2730269557627901}{58560931675094420},\frac{146271649897951}{3695016639410525},\mathrm{},$$

i.e., as

$$1,0.33333..,0.15714..,0.098901..,0.072049..,0.056640..,0.046622..,0.039586..,\mathrm{}.$$

### 2.2 Neck-and-neck, then always ahead

We encode a sequence of $`n`$ draws as a path $`\omega `$ with $`n`$ vertices in the lattice $``$ consisting of vertices $`(i,j)`$, and edges $`\{(i,j),(i+1,j)\},\{(i,j),(i+1,j+1)\}`$, for all $`i,j0`$. The first coordinate of a vertex in the path gives the number of draws, or steps, and the second coordinate gives the number of distinct coupons the collector has at that step. Thus $`\omega `$ starts at $`(0,0)`$ indicating the collector has 0 coupons at draw 0, proceeds to $`(1,1)`$ (the collector has 1 coupon after 1 draw), and ends at $`(n,d)`$, $`nd`$ (the collector has a complete collection at step $`n`$). We write $`\omega =(0,0)\overline{\omega }(n,d)`$, where $`\overline{\omega }`$ is a path from $`(1,1)`$ to $`(n1,d1)`$, to indicate that $`\omega `$ starts at the vertex $`(0,0)`$, continues with the first vertex $`(1,1)`$ in $`\overline{\omega }`$, then follows $`\overline{\omega }`$ through to $`(n1,d1)`$, and finally ends with the vertex $`(n,d)`$.

We assign a weight of $`i/d`$ to each horizontal edge $`\{(i,j),(i+1,j)\}`$ in the lattice $``$. This is the probability that at the $`(j+1)^{\mathrm{st}}`$ step, the collector draws one of the $`i`$ distinct coupons already collected at step $`j`$. We assign a weight of $`1i/d`$ to each northeast edge $`\{(i,j),(i+1,j+1)\}`$. The probability that the collector draws the particular sequence of coupons encoded by the path $`\omega `$ is given by the product of the weights on the edges of $`\omega `$. We let $`P(\omega )`$ denote this probability.

Suppose one collector, the winner, collects all $`d`$ distinct coupons for the first time at step $`n.`$ (At step $`n1`$ the winner had $`d1`$ distinct coupons.) Let $`\omega _1`$ be the lattice path which encodes the winner’s sequence of draws. Let $`\omega _2`$ encode the other collector’s draws. We compute the probability $`p(d)`$ that $`\omega _1`$ and $`\omega _2`$ are identical until some point at which the winner takes the lead and the other collector never catches up.

To do this, we begin by supposing $`\omega _1`$ is identical to $`\omega _2`$ until step $`k`$, at which point both collectors have $`d_1`$ distinct coupons. The argument splits into two cases, namely $`kn2`$ and $`k=n1`$. In both cases, at step $`k+1`$ the winner collects one additional distinct coupon while the other collector does not. After step $`k`$, the two paths never intersect again. The winner collects all $`d`$ distinct coupons for the first time at step $`n`$. Suppose the other collector has $`d_2`$ distinct coupons at this point. The probability we seek is

$$p(d)=\underset{n=d}{\overset{\mathrm{}}{}}\underset{k=1}{\overset{n1}{}}\underset{d_1=1}{\overset{d1}{}}\underset{d_2=d_1}{\overset{d1}{}}\underset{(\omega _1,\omega _2)}{}P(\omega _1)P(\omega _2)$$
(8)
where the innermost sum ranges over all pairs $`(\omega _1,\omega _2)`$ described above.

### 2.3 The case $`kn2`$

Write $`\omega _1=\alpha \overline{\omega _1}(n,d)`$, where $`\alpha `$ denotes a lattice path from $`(0,0)`$ to $`(k,d_1)`$, and $`\overline{\omega _1}`$ denotes a path from $`(k+1,d_1+1)`$ to $`(n1,d1)`$. Similarly, set $`\omega _2=\alpha \overline{\omega _2}`$, where $`\alpha `$ is as above, and $`\overline{\omega _2}`$ is a path from $`(k+1,d_1)`$ to $`(n,d_2)`$. Note that $`\overline{\omega _1}`$ and $`\overline{\omega _2}`$ are nonintersecting paths in the lattice $``$. In terms of these we have $`P(\omega _1)=P(\alpha )(1d_1/d)P(\overline{\omega _1})(1/d)`$ and $`P(\omega _2)=P(\alpha )(d_1/d)P(\overline{\omega _2})`$. Hence from (8) we find for the combined probability of all pairs if $`kn2`$,

$`p(d)_{kn2}`$ $`=`$ $`{\displaystyle \underset{n=d}{\overset{\mathrm{}}{}}}{\displaystyle \underset{k=1}{\overset{n2}{}}}{\displaystyle \underset{d_1=1}{\overset{d1}{}}}{\displaystyle \underset{d_2=d_1}{\overset{d1}{}}}{\displaystyle \underset{(\omega _1,\omega _2)}{}}\left[P(\alpha )\left(1{\displaystyle \frac{d_1}{d}}\right)P(\overline{\omega _1})\left({\displaystyle \frac{1}{d}}\right)\right]\left[P(\alpha )\left({\displaystyle \frac{d_1}{d}}\right)P(\overline{\omega _2})\right]`$ (9)
$`=`$ $`{\displaystyle \underset{n=d}{\overset{\mathrm{}}{}}}{\displaystyle \underset{k=1}{\overset{n2}{}}}{\displaystyle \underset{d_1=1}{\overset{d1}{}}}{\displaystyle \underset{d_2=d_1}{\overset{d1}{}}}\left(1{\displaystyle \frac{d_1}{d}}\right)\left({\displaystyle \frac{1}{d}}\right)\left({\displaystyle \frac{d_1}{d}}\right){\displaystyle \underset{\alpha }{}}P(\alpha )^2{\displaystyle \underset{(\overline{\omega _1},\overline{\omega _2})}{}}P(\overline{\omega _1})P(\overline{\omega _2})`$
At this point we have translated a question about coupon collecting into a problem involving nonintersecting paths in a lattice. We have set the stage for application of the Gessel-Viennot theorem . This result concerns pairs of nonintersecting lattice paths with no constraints on vertices or edges in the paths. For this reason we have written $`\omega _1`$ and $`\omega _2`$ in terms of $`\overline{\omega _1}`$ and $`\overline{\omega _2}`$.

The theorem refers to an arbitrary set $``$, which we will take to be the lattice defined earlier, and a weight (or valuation) $`v`$, which we take to be $`P`$. The theorem equates a sum of weights of paths with the determinant of a matrix $`(a_{ij})_{1i,jl}`$. The entries of this matrix are defined by $`a_{ij}=_\omega v(\omega )`$, where $`\omega `$ ranges over all paths from $`A_i`$ to $`B_j`$.

The theorem requires that two given sequences, $`(A_1,A_2,\mathrm{},A_l)`$ and $`(B_1,B_2,\mathrm{},B_l)`$, of vertices in $``$, the sets $`\mathrm{\Omega }_{ij}`$, $`1i,jl`$, of all paths in $``$ between $`A_i`$ and $`B_j`$, and the weight $`v`$ satisfy both the finiteness and crossing conditions. The finiteness condition requires the set of paths in $`\mathrm{\Omega }_{ij}`$ with nonzero weight be finite. The crossing condition requires that paths in $`\mathrm{\Omega }_{ij^{}}`$ and $`\mathrm{\Omega }_{i^{}j}`$, $`i<i^{}`$ and $`j<j^{}`$, with nonzero weight share a common vertex. Both conditions hold for the paths we consider.

###### Theorem 1

(Gessel-Viennot) Suppose $``$, $`v`$, $`(A_1,A_2,\mathrm{},A_l)`$, and $`(B_1,B_2,\mathrm{},B_l)`$ satisfy both the finiteness and crossing conditions. Then the determinant of the matrix $`(a_{ij})_{1i,jl}`$ is the sum of the weights of all configurations of paths $`(\omega _1,\omega _2,\mathrm{},\omega _l)`$ satisfying the following two conditions:
(i) The paths $`\omega _k`$ are pairwise nonintersecting, and
(ii) $`\omega _k`$ is a path from $`A_k`$ to $`B_k`$.
In other words,

$$det\left(\left\{a_{ij}\right\}_{i,j=1}^l\right)=\underset{(\omega _1,\omega _2,\mathrm{},\omega _l)}{}v(\omega _1)v(\omega _2)\mathrm{}v(\omega _l).$$

Application of this theorem to our problem requires the computation of only a $`2\times 2`$ determinant! Let $`A_1=(k+1,d_1+1)`$, $`A_2=(k+1,d_1)`$, $`B_1=(n1,d1)`$, and $`B_2=(n,d_2)`$. Then

$$\underset{(\overline{\omega _1},\overline{\omega _2})}{}P(\overline{\omega _1})P(\overline{\omega _2})=det\left[\begin{array}{cc}a_{11}\hfill & a_{12}\hfill \\ a_{21}\hfill & a_{22}\hfill \end{array}\right]$$
(10)
where $`a_{ij}`$ is the sum $`_\omega P(\omega )`$ over all paths $`\omega `$ from $`A_i`$ to $`B_j`$.

### 2.4 Paths from $`A`$ to $`B`$

In this section, we compute the probability $`P(\omega )`$ of an arbitrary path $`\omega `$ from a vertex $`A=(a_1,b_1)`$ to a vertex $`B=(a_2,b_2)`$, as well as the sum over all such paths. Such a path contains $`b_2b_1`$ northeast edges $`\{(i,j),(i+1,j+1)\}`$ and $`(a_2a_1)(b_2b_1)`$ horizontal edges. The weights assigned to northeast edges in order from left to right are $`1\frac{b_1}{d},1\frac{b_1+1}{d},\mathrm{},1\frac{b_21}{d}`$. The weight assigned to a horizontal edge depends its coordinates. Consider the edge $`\{(i,j),(i+1,j)\}`$. This edge indicates the collector has $`j`$ distinct coupons at step $`i`$ and draws one of the same $`j`$ coupons at step $`i+1`$. The probability of this (weight of the edge) is $`\frac{j}{d}`$. Thus the probability of a path $`\omega `$ from $`A`$ to $`B`$ is

$`P(\omega )`$ $`=`$ $`\left({\displaystyle \frac{b_1}{d}}\right)^{e_1}\left(1{\displaystyle \frac{b_1}{d}}\right)\left({\displaystyle \frac{b_1+1}{d}}\right)^{e_2}\left(1{\displaystyle \frac{b_1+1}{d}}\right)\mathrm{}\left(1{\displaystyle \frac{b_21}{d}}\right)\left({\displaystyle \frac{b_2}{d}}\right)^{e_{b_2b_1+1}}`$ (11)
$`=`$ $`{\displaystyle \frac{1}{d^{a_2a_1}}}{\displaystyle \frac{(db_1)!}{(db_2)!}}(b_1)^{e_1}(b_1+1)^{e_2}\mathrm{}(b_2)^{e_{b_2b_1+1}}`$
where $`e=(e_1,e_2,\mathrm{},e_{b_2b_1+1})`$ is an ordered partition, a composition, of $`(a_2a_1)(b_2b_1)`$ into $`b_2b_1+1`$ nonnegative integer parts. With this we compute the sum of the probabilities of all paths from $`A`$ to $`B`$.

$`{\displaystyle \underset{\omega =A\mathrm{}B}{}}P(\omega )`$ $`=`$ $`{\displaystyle \underset{e}{}}\left({\displaystyle \frac{b_1}{d}}\right)^{e_1}\left(1{\displaystyle \frac{b_1}{d}}\right)\left({\displaystyle \frac{b_1+1}{d}}\right)^{e_2}\left(1{\displaystyle \frac{b_1+1}{d}}\right)\mathrm{}\left(1{\displaystyle \frac{b_21}{d}}\right)\left({\displaystyle \frac{b_2}{d}}\right)^{e_{b_2b_1+1}}`$ (12)
$`=`$ $`{\displaystyle \frac{1}{d^{a_2a_1}}}{\displaystyle \frac{(db_1)!}{(db_2)!}}{\displaystyle \underset{e}{}}(b_1)^{e_1}(b_1+1)^{e_2}\mathrm{}(b_2)^{e_{b_2b_1+1}}`$
where the sum is over all compositions $`e=(e_1,e_2,\mathrm{},d_{b_2b_1+1})`$ of $`(a_2a_1)(b_2b_1)`$ into $`b_2b_1+1`$ nonnegative integer parts. This is the coefficient of $`x^{(a_2a_1)(b_2b_1)}`$ in the series expansion of

$$\frac{1}{(1b_1x)(1(b_1+1)x)\mathrm{}(1b_2x)}$$

so we can find a simpler formula for it by looking at the partial fraction expansion

$$\frac{1}{_{m=a}^b(1mx)}=\underset{m=a}{\overset{b}{}}\frac{B_m}{1mx},$$
(13)
where

$$B_m=\frac{(1)^{bm}m^{ba}}{(ba)!}\left(\genfrac{}{}{0pt}{}{ba}{ma}\right).$$

From this and (12) we obtain

$`{\displaystyle \underset{\omega =A\mathrm{}B}{}}P(\omega )`$ $`=`$ $`{\displaystyle \frac{1}{d^{a_2a_1}}}{\displaystyle \frac{(db_1)!}{(db_2)!}}[x^{(a_2a_1)(b_2b_1)}]\left\{{\displaystyle \underset{m=b_1}{\overset{b_2}{}}}{\displaystyle \frac{B_m}{1mx}}\right\}`$ (14)
$`=`$ $`{\displaystyle \frac{1}{d^{a_2a_1}}}{\displaystyle \frac{(db_1)!}{(db_2)!}}{\displaystyle \underset{m=b_1}{\overset{b_2}{}}}B_mm^{(a_2a_1)(b_2b_1)}`$
$`=`$ $`{\displaystyle \frac{1}{d^{a_2a_1}}}{\displaystyle \frac{(db_1)!}{(db_2)!}}{\displaystyle \underset{m=b_1}{\overset{b_2}{}}}{\displaystyle \frac{(1)^{b_2m}m^{a_2a_1}}{(b_2b_1)!}}\left({\displaystyle \genfrac{}{}{0pt}{}{b_2b_1}{mb_1}}\right)`$
### 2.5 Evaluating the determinant

We use the results of the previous section to evaluate the determinant in (10). To compute $`a_{11}`$, we substitute $`A=A_1=(k+1,d_1+1)`$ and $`B=B_1=(n1,d1)`$ in (14). This yields

$`a_{11}`$ $`=`$ $`{\displaystyle \frac{1}{d^{nk2}}}(dd_11)!{\displaystyle \underset{m=d_1+1}{\overset{d1}{}}}{\displaystyle \frac{\left(1\right)^{dm1}m^{nk2}}{(dd_12)!}}\left({\displaystyle \genfrac{}{}{0pt}{}{dd_12}{md_11}}\right)`$ (15)
In a similar manner we obtain

$`a_{12}`$ $`=`$ $`{\displaystyle \frac{1}{d^{nk1}}}{\displaystyle \frac{(dd_11)!}{(dd_2)!}}{\displaystyle \underset{m=d_1+1}{\overset{d_2}{}}}{\displaystyle \frac{\left(1\right)^{d_2m}m^{nk1}}{(d_2d_11)!}}\left({\displaystyle \genfrac{}{}{0pt}{}{d_2d_11}{md_11}}\right)`$ (16)
$`a_{21}`$ $`=`$ $`{\displaystyle \frac{1}{d^{nk2}}}(dd_1)!{\displaystyle \underset{m=d_1}{\overset{d1}{}}}{\displaystyle \frac{\left(1\right)^{dm1}m^{nk2}}{(dd_11)!}}\left({\displaystyle \genfrac{}{}{0pt}{}{dd_11}{md_1}}\right)`$ (17)
$`a_{22}`$ $`=`$ $`{\displaystyle \frac{1}{d^{nk1}}}{\displaystyle \frac{(dd_1)!}{(dd_2)!}}{\displaystyle \underset{m=d_1}{\overset{d_2}{}}}{\displaystyle \frac{\left(1\right)^{d_2m}m^{nk1}}{(d_2d_1)!}}\left({\displaystyle \genfrac{}{}{0pt}{}{d_2d_1}{md_1}}\right)`$ (18)
Using (15)-(18) we compute the determinant of our $`2\times 2`$ matrix.

$`det\left[\begin{array}{cc}a_{11}\hfill & a_{12}\hfill \\ a_{21}\hfill & a_{22}\hfill \end{array}\right]`$ $`=`$ $`{\displaystyle \frac{(dd_1)!(dd_11)!}{d^{2n2k3}(dd_2)!}}\times `$
$`{\displaystyle \underset{l=d_1}{\overset{d}{}}}{\displaystyle \underset{m=d_1}{\overset{d_2}{}}}{\displaystyle \frac{m(lm)^{nk2}(1)^{d_1+d_2}(ld)(m^2l^2)}{(dd_11)!(d_2d_1)!}}\left({\displaystyle \genfrac{}{}{0pt}{}{dd_11}{ld_1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{d_2d_1}{md_1}}\right)`$
$`=\text{def}`$ $`det(d,d_1,d_2,k,n)`$ (22)
Substituting (22) in (10), we obtain

$$\underset{(\overline{\omega _1},\overline{\omega _2})}{}P(\overline{\omega _1})P(\overline{\omega _2})=det(d,d_1,d_2,k,n)$$
(23)
### 2.6 The initial common segment

In the previous section we evaluated the determinant in (10). In this section we compute the sum $`_\alpha P(\alpha )^2`$ in (9). Recall $`\alpha `$ is a path from $`(0,0)`$ to $`(k,d_1)`$.

Equation (11) gives the probability of an arbitrary path from $`A`$ to $`B`$. Substituting $`A=(0,0)`$ and $`B=(k,d_1)`$ gives the probability

$$P(\alpha )=\frac{d!}{d^k(dd_1)!}1^{e_1}2^{e_2}\mathrm{}d_{1}^{}{}_{}{}^{e_{d_1}}$$

of an arbitrary path $`\alpha `$ from $`(0,0)`$ to $`(k,d_1)`$. It follows that

$`{\displaystyle \underset{\alpha =(0,0)\mathrm{}(k,d_1)}{}}P(\alpha )^2`$ $`=`$ $`{\displaystyle \frac{d!^2}{d^{2k}(dd_1)!^2}}{\displaystyle \underset{e_1+\mathrm{}+e_{d_1}=kd_1}{}}1^{2e_1}2^{2e_2}\mathrm{}d_1^{2e_{d_1}}`$ (24)
$`=`$ $`{\displaystyle \frac{d!^2}{d^{2k}(dd_1)!^2}}[x^{kd_1}]\left\{{\displaystyle \frac{1}{(11^2x)(12^2x)\mathrm{}(1d_1^2x)}}\right\}`$
$`=`$ $`{\displaystyle \frac{d!^2}{d^{2k}(dd_1)!^2}}{\displaystyle \underset{m=1}{\overset{d_1}{}}}C_mm^{2k2d_1}(\mathrm{as}\mathrm{in}(\text{13}))`$
$`=`$ $`{\displaystyle \frac{2d!^2}{(dd_1)!^2d^{2k}(2d_1)!}}{\displaystyle \underset{m1}{}}(1)^{d_1m}\left({\displaystyle \genfrac{}{}{0pt}{}{2d_1}{d_1+m}}\right)m^{2k}.`$
$`=\text{def}`$ $`\mathrm{init}(d,d_1,k)`$ (25)
### 2.7 The case $`k=n1`$

Suppose now that the two walks are identical up to the point $`(n1,d1)`$. Since step $`n`$ is the finish, the next step for the winning player will be to $`(n,d)`$, and for the loser, to $`(n,d1)`$. These last steps have respective probabilities $`1/d`$ and $`11/d`$. Hence the probability of the complete pair of walks in this case is the probability of two identical walks from $`(0,0)`$ to $`(n1,d1)`$ (which is given by (24) with $`(k,d_1):=(n1,d1)`$) multiplied by $`(d1)/d^2`$.

### 2.8 Putting it together

We now substitute (22) and (25) into (9) to obtain the probability of all pairs of paths that we are considering,

$`p(d)`$ $`=`$ $`{\displaystyle \underset{n=d}{\overset{\mathrm{}}{}}}{\displaystyle \underset{k=1}{\overset{n2}{}}}{\displaystyle \underset{d_1=1}{\overset{d1}{}}}{\displaystyle \underset{d_2=d_1}{\overset{d1}{}}}\left(1{\displaystyle \frac{d_1}{d}}\right)\left({\displaystyle \frac{d_1}{d}}\right)\left({\displaystyle \frac{1}{d}}\right)\mathrm{init}(d,d_1,k)\mathrm{det}(d,d_1,d_2,k,n)`$ (26)
$`+{\displaystyle \frac{d1}{d^2}}{\displaystyle \underset{n=d}{\overset{\mathrm{}}{}}}\text{init}(d,d1,n1),`$
$`=\text{def}`$ $`\mathrm{\Sigma }_1+\mathrm{\Sigma }_2`$ (27)
It turns out that the sums over the indices $`d_2,n,k`$ can all be carried out in explicit closed form. Hence we can obtain an expression which is in finite terms for the total probability.

First, the sum on $`d_2`$ in $`\mathrm{\Sigma }_1`$ above can be done in closed form since

$$\underset{d_2=d_1}{\overset{d1}{}}(1)^{d_2}\left(\genfrac{}{}{0pt}{}{dd_1}{dd_2}\right)\left(\genfrac{}{}{0pt}{}{d_2d_1}{td_1}\right)=(1)^{d+1}\left(\genfrac{}{}{0pt}{}{dd_1}{dt}\right).$$

Next, the remaining sum over the indices $`n`$ and $`k`$, in the first summation, $`\mathrm{\Sigma }_1`$ is

$$\psi (d,r,s,t)=\text{def}\underset{n=d}{\overset{\mathrm{}}{}}\underset{k=1}{\overset{n2}{}}\frac{r^{2k}t^{nk1}s^{nk2}}{d^{2n}}=\{\begin{array}{cc}\frac{r^{2d}(d^32d^2r^2d+3r^2)}{d^{2d2}(d^2r^2)^2s^2t},\hfill & \text{if }r^2=st\text{;}\hfill \\ \frac{r^4(st)^{d1}(r^2d^2)+str^{2d}(d^2st)}{d^{2d2}(d^2st)(d^2r^2)(r^2st)r^2s},\hfill & \text{otherwise.}\hfill \end{array}$$
(28)
The sum over $`n`$ in $`\mathrm{\Sigma }_2`$ is trivial, and so there remain no infinite sums in our final expression for the probability $`p(d)`$, which is

$`{\displaystyle \underset{d_1=1}{\overset{d1}{}}}{\displaystyle \frac{2d!^2d_1(dd_1)}{(dd_1)!^2(2d_1)!}}{\displaystyle \underset{r,s,t1}{}}(1)^{d_1rst}(st)\left({\displaystyle \genfrac{}{}{0pt}{}{2d_1}{d_1+r}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{dd_11}{sd_1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{dd_1}{dt}}\right)\psi (d,r,s,t)`$
$`+{\displaystyle \frac{4(d1)d!^2}{d^{2d2}(2d2)!}}{\displaystyle \underset{r=1}{\overset{d1}{}}}(1)^{d1r}\left({\displaystyle \genfrac{}{}{0pt}{}{2d2}{d1+r}}\right){\displaystyle \frac{r^{2d2}}{d^2r^2}}+\delta _{d,1}`$ (29)
where $`\psi `$ is given by (28).

This is the probability that the game is of the type we described, namely where the players are tied for some initial segment of trials and then the player who pulls ahead remains ahead always, expressed as a finite sum (albeit a complicated one!). More precisely, the values of $`p(d)`$ can be calculated, as rational numbers, with $`O(d^4)`$ evaluations of the above summand. The exact values of $`p(d)`$, for $`d=1,2,3,4,5,\mathrm{}`$ are

$$\{1,\frac{2}{3},\frac{43}{70},\frac{986}{2275},\frac{5672893}{1912246},\mathrm{}.\}$$

As decimals, the values of $`\{p(d)\}_{d=1}^{10}`$ are

$$\{1.0,0.66667,0.61429,0.43341,0.29667,0.21177,0.16016,0.12748,0.10551,0.08988\}.$$

### 2.9 One collector never behind

In contrast to the problem of staying ahead as soon as the tie is broken, which we have solved in the preceding sections, the problem in which the ultimate winner has never been behind is unsolved.

Suppose the winner collects all $`d`$ distinct coupons for the first time at step $`n`$, at which point the other collector has $`d^{}<d`$ distinct coupons. We discuss the probability $`b(d)`$ the winner has never been behind. We use $`b`$ for “ballot” since this version of the problem has a distinct ballot-problem flavor (see ).

Let $`w_1`$ be the lattice path which encodes the winner’s sequence of draws. Let $`\omega _2`$ encode the other collector’s sequence of draws. Then $`b(d)`$ is the probability that $`\omega _2`$ does not cross $`\omega _1`$. To say $`\omega _2`$ does not cross $`\omega _1`$ means for each horizontal coordinate $`i`$ shared by vertices $`(i,j_1)`$ in $`\omega _1`$ and $`(i,j_2)`$ in $`\omega _2`$, we have $`j_2j_1`$. In the case $`j_2=j_1`$, we say $`\omega _1`$ and $`\omega _2`$ intersect at $`(i,j_1)=(i,j_2)`$. Thus we seek all pairs $`(\omega _1,\omega _2)`$ such that $`\omega _1`$ is a path from $`(0,0)`$ to $`(n,d)`$ including the vertex $`(n1,d1)`$, $`\omega _2`$ is a path from $`(0,0)`$ to $`(n,d^{})`$ for $`1d^{}d`$, and $`\omega _2`$ does not cross $`\omega _1`$. Such a pair $`(\omega _1,\omega _2)`$ is illustrated by Figure 1. Note that $`\omega _1`$ and $`\omega _2`$ may intersect several times. The probability we seek is

$$b(d)=\underset{n=d}{\overset{\mathrm{}}{}}\underset{d^{}=1}{\overset{d1}{}}\underset{(\omega _1,\omega _2)}{}P(\omega _1)P(\omega _2)$$

where the innermost sum ranges over all pairs described above.

Look again at Figure 1. A pair $`(\omega _1,\omega _2)`$ appears to form a chain of flying kites anchored to the ground at $`(0,0)`$. The highest kite has two ribbons attached to its tip. Their loose ends are at $`(n,d)`$ and $`(n,d^{})`$.

Each kite consists of a frame together with a tail. See Figure 2. A frame from $`(i_1,j_1)`$ to $`(i_2,j_2)`$ consists of a pair of paths from $`(i_1,j_1)`$, the lower tip of the frame, to $`(i_2,j_2)`$, the upper tip, which intersect only at the endpoints. A tail from $`(i_1,j_1)`$ to $`(i_2,j_2)`$ consists of two identical paths between these endpoints. The length of a tail is the number of vertices in the tail minus one, i.e., the number of edges.

A pair $`(\omega _1,\omega _2)`$ such that $`\omega _2`$ does not cross $`\omega _1`$ forms an alternating sequence of tails and frames, beginning with a tail. Note that tails may have length zero.

The upper tip of the final frame in this sequence is the common endpoint for two paths which intersect only at this common endpoint (these are the “ribbons” described above). One path ends at $`(n,d)`$, this is the top ribbon, and the other ends at $`(n,d^{})`$, the bottom ribbon.

Below we compute the probability of a frame from $`(i_1,j_1)`$ to $`(i_2,j_2)`$, a tail from $`(i_1,j_1)`$ to $`(i_2,j_2)`$, and a pair of ribbons with common initial point $`(k,d^{\prime \prime })`$ and terminal points at $`(n,d)`$ and $`(n,d^{})`$, respectively.

Let $`f_{(i_1,j_1)}^{(i_2,j_2)}(d)`$ denote the probability of a frame from $`(i_1,j_1)`$ to $`(i_2,j_2)`$. Note for $`f_{(i_1,j_1)}^{(i_2,j_2)}(d)0`$, we must have $`i_2i_1+2`$, $`j_2>j_1`$, and $`j_2j_1i_2i_11`$. Assuming these conditions, we write

$$f_{(i_1,j_1)}^{(i_2,j_2)}(d)=\underset{(\alpha ,\beta )}{}P(\alpha )P(\beta )$$
(30)
where $`(\alpha ,\beta )`$ is a pair of paths from $`(i_1,j_1)`$ to $`(i_2,j_2)`$ intersecting only at the endpoints such that $`\beta `$ does not cross $`\alpha `$ (i.e., $`\alpha `$ forms the upper edge of the frame, and $`\beta `$ forms the lower edge).

We convert the sum above into a determinant using the Gessel-Viennot thereom. Evaluation of the determinant gives

$$f_{(i_1,j_1)}^{(i_2,j_2)}(d)=\frac{j_1j_2(dj_1)!^2}{d^{2(i_2i_1)}(j_2j_1)!^2(dj_2)!^2}\underset{l,m=j_1}{\overset{j_2}{}}(1)^{l+m}(lm)^{i_2i_12}(lj_1)(mj_2)\left(\genfrac{}{}{0pt}{}{j_2j_1}{mj_1}\right)\left(\genfrac{}{}{0pt}{}{j_2j_1}{lj_1}\right)$$

We compute the probability $`t_{(i_1,j_1)}^{(i_2,j_2)}(d)`$ of a tail from $`(i_1,j_1)`$ to $`(i_2,j_2)`$ in a manner analogous to the computation of $`_\alpha P(\alpha )^2`$ in section 2.6. We obtain

$$t_{(i_1,j_1)}^{(i_2,j_2)}(d)=\frac{(dj_1)!^2}{d^{2(i_2i_1)}(2j_2)!(dj_2)!^2}\underset{m=1}{\overset{j_2}{}}(1)^{j_2j_1}m^{2(i_2i_1)}(2m)!\left(\genfrac{}{}{0pt}{}{2j_2}{j_2+m}\right)\left(\genfrac{}{}{0pt}{}{m+j_11}{j_1m}\right)$$

Finally we compute the probability $`r(d,d^{},d^{\prime \prime },k,n)`$ of a pair of ribbons with common initial point $`(k,d^{\prime \prime })`$ and terminal points $`(n,d^{})`$ and $`(n,d)`$. The probability is given by a determinant similar to the one in (10). In the present case, we have $`d^{\prime \prime }`$ in place of $`d_1`$ and $`d^{}`$ in place of $`d_2`$. Thus

$$r(d,d^{},d^{\prime \prime },k,n)=det(d,d^{},d^{\prime \prime },k,n)$$

## 3 The “double dixie-cup problem,” of Newman and Shepp, revisited

Here we consider a different generalization of the coupon collector’s problem. Let integers $`h,d1`$ be fixed. Again we are sampling with replacement from $`d`$ kinds of coupons, but now $`T`$ is the epoch at which we have collected at least $`h`$ copies of each of the $`d`$ coupons, for the first time (for example, my $`h1`$ siblings and I might each want to have our own copy of every one of the available baseball cards). We study the expectation, the probability generating function, and the asymptotic behavior of the expectation, of this generalized problem.

These questions were investigated by Newman and Shepp  and the asymptotics were refined by Erdős-Rényi . It is interesting to note that this problem is equivalent to one about the evolution of a random graph. Suppose we fix $`n`$ vertices, and then we begin to collect from among $`n`$ kinds of coupons. If we collect a particular sequence, say, $`\{c_1,c_2,c_3,\mathrm{}\}`$ then we add the edges $`(c_1,c_2)`$,$`(c_3,c_4)\mathrm{}`$. That is, we add an edge each time we choose a new pair of coupons. Our problem about collecting at least $`h`$ copies of each kind of coupon is thereby equivalent to the question of obtaining a minimum degree of at least $`h`$ in an evolving random graph.<sup>1</sup><sup>1</sup>1Our thanks to Ed Bender and to a helpful referee for pointing this out. In this section we will not add anything new to the asymptotics of this problem. Instead we claim only a simpler derivation than the original, and an explicit generating function, which gives a nice road to the asymptotics. We deal only with generating functions in one variable, whereas in  multivariate generating functions were used. We obtain not only the expectation of the time to reach a collection that has at least $`h`$ copies of each kind of coupon, but also the complete probability distribution of that time.

For $`n`$ fixed, consider a sequence of $`n`$ drawings of coupons that constitutes, for the first time at the $`n`$th drawing, a complete collection of at least $`h`$ copies of each of the $`d`$ kinds of coupons.

There are $`d`$ possibilities for the coupon that completes the collection on the $`n`$th drawing. There are $`\left(\genfrac{}{}{0pt}{}{n1}{h1}\right)`$ ways to choose the set of earlier drawings on which that last coupon type occurred. On the remaining $`nh`$ drawings we can define, as usual, an equivalence relation: two drawings $`i,j`$ are equivalent if the same kind of coupon was drawn at the $`i`$th and the $`j`$th drawings. The number of such equivalence relations is equal to the number of ordered partitions of a set of $`nh`$ elements into $`d1`$ classes, each class containing at least $`h`$ elements. We will denote this latter number by $`(d1)!\left\{\genfrac{}{}{0pt}{}{nh}{d1}\right\}_h`$, where the $`\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}_h`$’s count the unordered partitions of an $`n`$-set into $`k`$ classes of at least $`h`$ elements each.

The number of sequences of $`n`$ drawings for which we achieve a complete collection for the first time at the $`n`$th drawing is therefore

$$d\left(\genfrac{}{}{0pt}{}{n1}{h1}\right)(d1)!\left\{\genfrac{}{}{0pt}{}{nh}{d1}\right\}_h.$$

Since there are $`d^n`$ possible drawing sequences of length $`n`$, the probability that $`T=n`$ is

$$p_n=\frac{d!}{d^n}\left(\genfrac{}{}{0pt}{}{n1}{h1}\right)\left\{\genfrac{}{}{0pt}{}{nh}{d1}\right\}_h,$$
(31)
and the probability generating function is

$`P_h(x)`$ $`=\text{def}`$ $`{\displaystyle \underset{n0}{}}p_nx^n={\displaystyle \underset{n0}{}}{\displaystyle \frac{d!}{d^n}}\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{h1}}\right)\left\{{\displaystyle \genfrac{}{}{0pt}{}{nh}{d1}}\right\}_hx^n`$ (32)
$`=`$ $`d!\left({\displaystyle \genfrac{}{}{0pt}{}{xD1}{h1}}\right){\displaystyle \underset{n0}{}}\left\{{\displaystyle \genfrac{}{}{0pt}{}{nh}{d1}}\right\}_h\left({\displaystyle \frac{x}{d}}\right)^n,`$
where $`D=/x`$.

It remains to find the ordinary power series generating function of the $`\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}_h`$’s. The exponential formula gives us immediately their exponential generating function, as

$$\underset{n0}{}\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}_h\frac{x^n}{n!}=\frac{1}{k!}\left(e^x1x\mathrm{}\frac{x^{h1}}{(h1)!}\right)^k$$
(33)
We can convert this into an ordinary power series generating function by applying the Laplace transform operator

$$_0^{\mathrm{}}e^{sx}\mathrm{}𝑑x$$

to both sides, which yields

$$\underset{n0}{}\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}_h\frac{1}{s^{n+1}}=\frac{1}{k!}_0^{\mathrm{}}e^{sx}\left(e^x1x\mathrm{}\frac{x^{h1}}{(h1)!}\right)^k𝑑x,$$

or finally

$$\underset{n0}{}\left\{\genfrac{}{}{0pt}{}{n}{k}\right\}_ht^n=\frac{1}{k!t}_0^{\mathrm{}}e^{x/t}\left(e^x1x\mathrm{}\frac{x^{h1}}{(h1)!}\right)^k𝑑x.$$
(34)
Now if we substitute (34) into (32) we obtain the probability generating function of the generalized coupon collector’s problem in the form

$$P_h(x)=\frac{1}{d^{h2}}_0^{\mathrm{}}\left\{\left(\genfrac{}{}{0pt}{}{xD1}{h1}\right)x^{h1}e^{td/x}\right\}\left(e^t1t\mathrm{}\frac{t^{h1}}{(h1)!}\right)^{d1}𝑑t.$$
(35)
In the above, $`\left(\genfrac{}{}{0pt}{}{xD1}{h1}\right)`$ is the differential operator that is defined by

$$\left(\genfrac{}{}{0pt}{}{xD1}{h1}\right)f(x)=\frac{1}{(h1)!}\left(x\frac{d}{dx}1\right)\left(x\frac{d}{dx}2\right)\mathrm{}\left(x\frac{d}{dx}h\right)f(x).$$

However, it is easy to establish, by induction on $`h`$, the interesting fact that

$$\left(\genfrac{}{}{0pt}{}{xD1}{h1}\right)x^{h1}e^{td/x}=\frac{(td)^{h1}}{(h1)!}e^{td/x}.$$
(36)
Hence we have proved the following evaluation.

###### Theorem 2

The probability generating function for the coupon collecting problem in which at least $`h`$ copies of each coupon are needed is given by

$$P_h(x)=\frac{d}{(h1)!}_0^{\mathrm{}}t^{h1}e^{td/x}\left(e^t1t\mathrm{}\frac{t^{h1}}{(h1)!}\right)^{d1}𝑑t.$$
(37)
### 3.1 Two examples

Let’s look at the cases $`h=1`$, the classical case, and $`h=2`$, where we want to collect at least two specimens of each of the $`d`$ kinds of coupons.

If $`h=1`$ then (37) takes the form

$$P_1(x)=d_0^{\mathrm{}}e^{td/x}(e^t1)^{d1}𝑑t.$$

If we expand the power of $`(e^t1)`$ by the binomial theorem and integrate termwise we obtain

$$P_1(x)=xd\underset{j=0}{\overset{d1}{}}\left(\genfrac{}{}{0pt}{}{d1}{j}\right)\frac{(1)^{d1j}}{djx},$$

which is precisely the partial fraction expansion of the classical generating function (3).

To see something new, let $`h=2`$. Then

$$P_2(x)=d_0^{\mathrm{}}te^{td/x}\left(e^t1t\right)^{d1}𝑑t.$$
(38)
Again, by termwise integration this can be made fairly explicit, but since the most interest attaches to the expectation, let’s look at the average number of trials that are needed to collect at least two samples of each of $`d`$ coupons. This is $`P_2^{}(1)`$, which after some simplification takes the form

$$P_2^{}(1)=d^2_0^{\mathrm{}}\left(\frac{t^2}{e^t1t}\right)(1(1+t)e^t)^d𝑑t.$$
(39)
From this we can go in either of two directions, an exact evaluation or an asymptotic approximation. By termwise integration it is easy to obtain the following exact formula, which is a finite sum, for $`T_2`$, the average number of trials needed to collect at least two of each of the $`d`$ kinds of coupons:

$$T_2=d^2\underset{m,j}{}(1)^m\left(\genfrac{}{}{0pt}{}{d1}{m}\right)\left(\genfrac{}{}{0pt}{}{m}{j}\right)\frac{(j+2)!}{(m+1)^{j+3}}$$
(40)
For $`d=2,3,4,5`$ these are $`2,11/2,347/36,12259/864`$. To facilitate comparison with the classical ($`h=1`$) case, we show below, for $`1d10`$, a table of the expected numbers of trials needed when $`h=1,2`$.

$$\begin{array}{ccccccccccc}d:& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\ T_1:& 1.0000& 3.0000& 5.5000& 8.3333& 11.417& 14.700& 18.150& 21.743& 25.460& 29.290\\ T_2:& 2.0000& 5.5000& 9.6389& 14.189& 19.041& 24.134& 29.425& 34.885& 40.492& 46.230\end{array}$$

### 3.2 Asymptotics

Now we investigate the asymptotic behavior of (39), for large $`d`$, to compare it with the $`d\mathrm{log}d`$ behavior of the classical case where $`h=1`$.

###### Theorem 3

If there are $`d`$ different kinds of coupons, and if at each step we sample one of the $`d`$ kinds with uniform probability, let $`T_h`$ denote the average number of samples that we must take until, for the first time, we have collected at least $`h`$ specimens of each of the $`d`$ kinds of coupons. Then for every $`h1`$, we have $`T_hd\mathrm{log}d(d\mathrm{})`$.

Consider first the case $`h=2`$. In (39) we make the substitution

$$e^u=1(1+t)e^t,$$
(41)
where $`u`$ is a new variable of integration. We then find that

$$P_2^{}(1)=d^2_0^{\mathrm{}}t(u)e^{ud}𝑑u,$$
(42)
where $`t(u)`$ is the inverse function of the substitution (41), which is well defined since the right side of (41) increases steadily from 0 to 1 as $`t`$ increases from 0 to $`\mathrm{}`$.

The main contribution to $`P_2^{}(1)`$ comes from values of $`u`$ near $`u=0`$, and when $`u`$ is near 0 we have

$$t(u)=\mathrm{log}u+O(\mathrm{log}\mathrm{log}u).$$

Following the arguments in , sec. 2.2, we see that $`P_2^{}(1)`$ of (42) has the same asymptotic behavior as

$$d^2_0^c(\mathrm{log}u)e^{ud}𝑑u,(0<c<1)$$

and in  this is shown to be

$$d^2\frac{\mathrm{log}d}{d}=d\mathrm{log}d.$$

Now we consider the asymptotic behavior of the expected number of trials for general values of $`h`$. From (37) we see that this expected number of trials can be written in the form

$$\frac{d^2}{(h1)!}_0^{\mathrm{}}\left\{\frac{t^h}{e^t1t\mathrm{}\frac{t^{h1}}{(h1)!}}\right\}\left\{1\left(1+t+\frac{t^2}{2}+\mathrm{}+\frac{t^{h1}}{(h1)!}\right)e^t\right\}^d𝑑t$$
(43)
Again we make the change of variable

$$e^u=1\left(1+t+\frac{t^2}{2}+\mathrm{}+\frac{t^{h1}}{(h1)!}\right)e^t$$
(44)
in the integral, and it takes the remarkably simple form (compare (42))

$$P_h^{}(1)=d^2_0^{\mathrm{}}t(u)e^{ud}𝑑u,$$

where $`t(u)`$ is the inverse function of the substitution (44). Again the main contribution to the integral comes from small values of $`u`$, and when $`u`$ is small and positive we have

$$t(u)=\mathrm{log}u+(h1)\mathrm{log}(\mathrm{log}u)+\mathrm{}.$$

Using the method of sec. II.2 of  once more, we find that

$$T_h=d\mathrm{log}d+(h1)d\mathrm{log}\mathrm{log}d(1+o(1))(d\mathrm{}).$$
(45)
We remark that in the case of $`d=200`$ coupons, the correct expected number of trials to obtain two of each coupon is 1614 trials, the approximation $`d\mathrm{log}d`$ is $`1175`$, and the approximation $`d\mathrm{log}d+(h1)d\mathrm{log}\mathrm{log}d`$ is $`1393`$, each rounded to the nearest integer.

## 4 The number of singletons

In view of the asymptotics in the preceding section we realize that at the moment when a coupon collector sequence terminates with a complete collection, ‘most’ coupons will have been collected more than once, and only ‘a few’ will have been collected just once. We call a coupon that has been seen just once a singleton. We will now look at the distribution of singletons.

In more detail, let $`j`$ be the number of singletons in a collecting sequence that terminates successfully at the $`n`$th step. We first want the joint distribution $`f(n,j)`$ of $`n`$ and $`j`$, i.e., the probability that a collecting sequence halts successfully at the $`n`$th step, and has exactly $`j`$ singletons at that moment. We claim that

$$f(n,j)=\frac{d!}{d^n}\left(\genfrac{}{}{0pt}{}{n1}{j1}\right)\left\{\genfrac{}{}{0pt}{}{nj}{dj}\right\}_2.$$
(46)
Indeed, the last coupon to be collected can be chosen in $`d`$ ways, the other $`j1`$ singleton coupons can be chosen in $`\left(\genfrac{}{}{0pt}{}{d1}{j1}\right)`$ ways, and can be presented in an ordered sequence in $`(j1)!\left(\genfrac{}{}{0pt}{}{d1}{j1}\right)`$ ways. This ordered sequence can appear among the first $`n1`$ trials in $`\left(\genfrac{}{}{0pt}{}{n1}{j1}\right)`$ ways, and the remaining $`nj`$ trials constitute an ordered partition of $`nj`$ elements into $`dj`$ classes, no class having fewer than two elements, which can be chosen in $`(dj)!\left\{\genfrac{}{}{0pt}{}{nj}{dj}\right\}_2`$ ways. If we multiply these together and divide by $`d^n`$, the number of $`n`$-sequences, we obtain the result (46) claimed above.

Next we compute the probability that a completed collecting sequence contains exactly $`j`$ singletons, whatever the length of the sequence may be. That is we find $`F(j)=_nf(n,j)`$, where $`f`$ is given by (46). We have, after using the generating function (34),

$`F(j)`$ $`=`$ $`{\displaystyle \underset{n}{}}{\displaystyle \frac{d!}{d^n}}\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{j1}}\right)\left\{{\displaystyle \genfrac{}{}{0pt}{}{nj}{dj}}\right\}_2`$ (47)
$`=`$ $`{\displaystyle \frac{d!}{(dj)!d^j}}\left\{{\displaystyle _0^{\mathrm{}}}\left\{\left({\displaystyle \genfrac{}{}{0pt}{}{t\frac{}{t}+j1}{j1}}\right)\left({\displaystyle \frac{e^{xt}}{t}}\right)\right\}(e^x1x)^{dj}𝑑x\right\}_{t1/d}`$ (48)
But using the fact that, analogously to (36), we have

$$\left(\genfrac{}{}{0pt}{}{t\frac{}{t}+j1}{j1}\right)\left(\frac{e^{xt}}{t}\right)=\frac{x^{j1}}{(j1)!t^j}e^{x/t},$$

we can simplify the expression for $`F(j)`$ to

$$F(j)=j\left(\genfrac{}{}{0pt}{}{d}{j}\right)_0^{\mathrm{}}x^{j1}(e^x1x)^{dj}e^{xd}𝑑x,(j=1,2,3,\mathrm{})$$
(49)
which is the desired distribution of the number of singletons in a successfully terminated coupon collecting sequence.

Now if we multiply by $`j`$ and sum over $`j`$, we’ll get the average number of singletons that appear in a completed collection of $`d`$ coupons. This is, after some termwise integration,

$$\overline{j}(d)=d\underset{m}{}(1)^m\left(\genfrac{}{}{0pt}{}{d2}{m}\right)\frac{d(m+1)+1}{(m+2)^2(m+1)}.$$

If we expand the summand in partial fractions, viz.,

$$\overline{j}(d)=d\underset{m}{}(1)^m\left(\genfrac{}{}{0pt}{}{d2}{m}\right)\left(\frac{1}{m+1}\frac{1}{m+2}+\frac{d1}{(m+2)^2}\right),$$

then each of the three sums indicated can be expressed in closed form, in two cases by using the identity

$$\underset{k}{}(1)^k\left(\genfrac{}{}{0pt}{}{n}{k}\right)\frac{1}{x+k}=\frac{1}{x\left(\genfrac{}{}{0pt}{}{x+n}{n}\right)},$$
(50)
directly, with $`x=1`$ and $`x=2`$, and in the third case by differentiating (50) w.r.t. $`x`$, and using the result with $`x=2`$. The identity (50) is itself certified, after multiplying by the denominator on the right, by the WZ proof certificate $`R(n,k)=k(x+k)/((n+1)(kn1))`$.

What results is that $`\overline{j}(d)=H_d`$, the $`d`$th harmonic number. That is, the average number of singleton coupons in a completed collection sequence of $`d`$ coupons is the harmonic number $`H_d`$.