Expected number of draws of m objects at a time out of n objects with replacement The question is as follows: Consider an urn of n distinct objects. At each time, m (m < n) objects are drawn randomly at once. The objects obtained are noted and then placed back in the urn. What is the expected number of draws I have to make until all of the objects have drawn at least once?
 A: Let's take a look at a random draw log. In each line, we have all $n$ objects, where $1$ means it has been drawn and $0$ means it hasn't been. Here, $n=5$ and $m=3$:
1 1 1 0 0
0 1 1 0 1
1 0 1 0 1
0 1 1 1 0

Now we will try to find the probability, that all objects have been drawn after $k$ draws. This is achieved when each object has been drawn at least once. We can denote this as $1-\text{[probability that it has never been drawn]}$. In each draw, there is probability $\frac{n-m}{n}$ that the object isn't drawn, so after $k$ draws, there is probability $\left(\frac{n-m}{n}\right)^k$ that the object hasn't been drawn.
Okay, so we know that each object is after $k$ draws drawn at least once with probability $1-\left(\frac{n-m}{n}\right)^k$. If we have $n$ objects, then probability, that all of them have been drawn at least once after $k$ draws is obviously $\left(1-\left(\frac{n-m}{n}\right)^k\right)^n$.
If we want to know, what is the probability, that we got the state "each object has been drawn at least once" exactly after $k$ draws, we need to subtract probability, that it was achieved after $k-1$ draws or sooner:
$$P_{\text{exactly after $k$}}=\left(1-\left(\frac{n-m}{n}\right)^k\right)^n-\left(1-\left(\frac{n-m}{n}\right)^{k-1}\right)^n$$
Now if you lok at definition of expected value, our expected number of draws is sum of expressions $k\times\text{[probability of ending exactly after $k$]}$. Namely,
$$\sum_{k=0}^\infty k\cdot\left(\left(1-\left(\frac{n-m}{n}\right)^k\right)^n-\left(1-\left(\frac{n-m}{n}\right)^{k-1}\right)^n\right)$$
And this can be simplified to:
$$\sum_{k=0}^\infty 1-\left(1-\left(\frac{n-m}{n}\right)^k\right)^n$$
I'm convinced it can't be simplified any more (and WolframAlpha agrees). If you're interested in any specific step of this solution, just write in comments.
Edit: My answer is not totally correct, see comments.
A: This answer is a work in progress.
Case 1: $m=n-1$
In this case, all but one are drawn on the first draw, and we're just looking for the expected number of attempts to get the last one. Since the probability of getting it on any particular draw is $\frac{n-1}{n}$, the expected number of draws after the first to get it is $\frac{n}{n-1}=1+\frac{1}{m}$. Adding to this the original draw, we have $E=2+\frac{1}{m}$.

Case 2: $m=1$
The probability that the number of draws required is $k$ is given by $n\times\frac1n\times K$, where $K$ is the probability that the other $n-1$ objects were all drawn in the first $k-1$ draws. (The first $n$ picks the final object drawn, and the $\frac1n$ gives us that it shows up in draw number $k$.) We can write a formula for $K$ using inclusion-exclusion:
$$K=\frac{(n-1)^{k-1} - \binom{n-1}{n-2}(n-2)^{k-1}+\binom{n-1}{n-3}(n-3)^{k-1}+\cdots + (-1)^n\binom{n-1}{1}(1)^{k-1}}{n^{k-1}}$$
Letting $E_n$ denote the resulting expected value for $n$ objects drawn $m=1$ at a time, we have:
$$E_2=3, E_3=\frac{11}{2}, E_4=\frac{25}{3}, E_5=\frac{137}{12}, E_6=\frac{147}{10}$$
I don't yet have a general formula for $E_n$ in the $m=1$ case, but it seems possibly tractable.
Edit: The case $m=1$ is the Coupon collector's problem, which is a wheel I'm going to now stop re-inventing. We have $E_n=n(1+\frac12+\cdots+\frac1n)$, which confirms the answers I'd found so far.

Another approach: The number of objects not yet chosen after $k$ steps is approximately $U_k=n\cdot\left(\frac{n-m}{n}\right)^k$. (That value is actually precise for $k=0$ and $k=1$, and approximate after that.) We might expect all objects to have been chosen at some point where $U_k<1$. How far below $1$ is not entirely clear, but maybe we can get an idea by looking at cases where we know the answer. Thus, for $m=n-1$, we have $U_{E_n}=n\cdot\left(\frac1{n}\right)^{2+\frac1{n-1}}$. This quantity is $\frac14$ for $n=2$, and goes to $0$ as $n\to\infty$. On the other hand, for $m=1$, the quantity $U_{E_n}$ goes up from $\frac14$ and approaches $\frac12$ as $n\to\infty$.
