As Henry pointed out in a comment, the probability has been determined elsewhere as
$$
\def\stir#1#2{\left\{#1\atop#2\right\}}
P(N=n)=\frac{m!}{m^n}\stir{n-1}{m-1}\;,
$$
where
$$\stir nk=\frac1{k!}\sum_{j=0}^k(-1)^{k-j}\binom kjj^n$$
is a Stirling number of the second kind and counts the number of partitions of a set of $n$ labeled objects into $k$ non-empty unlabeled subsets.
To get the expected value, it's slightly more convenient to work with the probability
$$
P(N\gt n)=1-\frac{m!}{m^n}\stir nm\;,
$$
which can be derived in much the same manner: There are $m^n$ sequences of length $n$; choose one of $\stir nm$ partitions into $m$ non-empty subsets and one of $m!$ assignments of the coupons types to the subsets.
Then
\begin{align}
E[N]={}&\sum_{n=0}^\infty P(N\gt n)\\
={}&\sum_{n=0}^\infty\left(1-\frac{m!}{m^n}\stir nm\right)\\
={}&\sum_{n=0}^\infty\left(1-\frac{m!}{m^n}\frac1{m!}\sum_{j=0}^m(-1)^{m-j}\binom mjj^n\right)\\
={}&\sum_{n=0}^\infty\frac1{m^n}\sum_{j=0}^{m-1}(-1)^{m-j+1}\binom mjj^n\\
={}&\sum_{j=0}^{m-1}(-1)^{m-j+1}\binom mj\sum_{n=0}^\infty\frac{j^n}{m^n}\\
={}&\sum_{j=1}^m(-1)^{j+1}\binom mj\sum_{n=0}^\infty\frac{(m-j)^n}{m^n}\\
={}&\sum_{j=1}^m(-1)^{j+1}\binom mj\frac mj\\
={}&-m\sum_{j=1}^m\int_0^{-1}\mathrm dq'\binom mjq'^{j-1}\\
={}&-m\int_0^{-1}\mathrm dq'\sum_{j=1}^m\binom mjq'^{j-1}\\
={}&-m\int_0^{-1}\mathrm dq'\frac{(1+q')^m-1}{q'}\\
={}&-m\int_0^{-1}\mathrm dq'\frac{(1+q')^m-1}{(1+q')-1}\\
={}&-m\int_0^{-1}\mathrm dq'\sum_{j=0}^{m-1}(-q')^j\\
={}&-m\sum_{j=0}^{m-1}\int_0^{-1}\mathrm dq'(-q')^j\\
={}&m\sum_{j=1}^m\frac1j\;.
\end{align}
I'll leave it to you to decide whether this counts as "using some sort of trick". :-)
It is possible to calculate the expectation for the total number of coupons needed when there are $n$ types of coupons and $s$ spare coupons can be swapped at the end for $1$ of a missing type. Clearly the minimum possible needed is $n$ when each coupon drawn is distinct and the maximum is $1+(n-1)s$ when each coupon drawn is the same; any integer in between these is a possible answer. Towards the top of that range the probabilities of needing that many become extremely small, and at the very top is $n^{-(n-1)s}$.
The following R code finds that, with $n=100,s=10$, the expected number is about $209.7689$
probneeded <- function(n, swap){
if(n==1){return(1)}
probtable <- rep(0,n*swap)
probs <- rep(0,n)
coupons <- 1
probs[1] <- 1
probstop <- 0
while (sum(probs) > 0){
coupons <- coupons + 1
probs <- (c(probs,0) * (1:(n+1))/n + c(0,probs) * (n:0)/n)[-(n+1)]
enough <- which(coupons + (1:n)*(swap-1) >= n * swap)
probstop[coupons] <- sum(probs[enough])
probs[enough] <- 0
}
probstop
}
expectedneeded <- function(n, swap){
probstop <- probneeded(n, swap)
sum((1:length(probstop)) * probstop)
}
expectedneeded(10,10)
# 20.63904
expectedneeded(100,10)
# 209.7689
expectedneeded(1000,10)
# 2100.671
expectedneeded(10000,10)
# 21009.7
Empirically this seems to suggest that with $n > s=10$ the expected number is something about $2.101 n -0.3$.
A handwaving approximate argument might suggest the $2.101$ is reasonable when $s=10$:
- If you have $x$ coupons, then the expected number of distinct types is $n(1-(1-\frac1n)^x)\approx n-ne^{-x/n}$
- and the expected number of surplus coupons is then about $x- n+ ne^{-x/n}$.
- That then suggest you might expect to be just be able to swap to get all $n$ distinct types when $n-ne^{-x/n} +\frac{x- n+ ne^{-x/n}}{s} = n$, i.e. when $\frac x n + (s-1)e^{-x/n} =1 $
- This has the solution $\frac{x}{n}= 1+ W\left(\frac{s-1}{e}\right)$ using the Lambert W function
- For $s=10$ you have $1+ W\left(\frac{9}{e}\right) \approx 2.101002997$ which is close to what was observed from the exact calculations; checking other values of $s$ suggests this approach works more generally.
The distribution of the number needed is slightly peculiar. When $n=100,s=10$, the standard deviation is about $11.79$, the median is $208$, as is the mode. The five most likely values are $208,217,199,226,190$ and together they have a probability just over $\frac 12$ of being the stopping point, even though intermediate values are also possible; what these five have in common is that if they are stopping points when there may be no surplus coupons after swapping - for example if you have $88$ distinct types and $120$ spare coupons to swap making to $208$ then you can exactly reach $88+\frac{120}{10}=100$ after swapping with no surplus.
Best Answer
Henning's solution is correct; but since we know not only $P(X_{n,1}=x)$ for the standard problem, but also $P(X_{n,1}\le x)$ (see e.g. Probability distribution in the coupon collector's problem), we can also write this without a sum:
\begin{align} \def\stir#1#2{\left\{#1\atop#2\right\}} P(X_{n,k}\le a)&=P(X_{n,1}\le ak)\\ &=\frac{n!}{n^{ak}}\stir{ak}n\;, \end{align}
and thus
\begin{align} P(X_{n,k}=a)&=P(X_{n,k}\le a)-P(X_{n,k}\le a-1)\\ &=P(X_{n,1}\le ak)-P(X_{n,1}\le(a-1)k)\\ &=\frac{n!}{n^{ak}}\stir{ak}n-\frac{n!}{n^{(a-1)k}}\stir{(a-1)k}n\\ &=\frac{n!}{n^{ak}}\left(\stir{ak}n-n^k\stir{(a-1)k}n\right)\;. \end{align}