Unique draws from a pool, with replacement I am attempting to find the probability of selecting $m$ unique items from a total of $n$ items with $k$ draws, with replacement. Let's denote this $P(n, m, k)$. Here's my thought process:
$P(n, 1, k)$ is equivalent to drawing the same item $k$ times. The first draw is always unique. Thus:
$$P(n, 1, k) = \left(\frac{1}{n}\right)^{k-1}$$
$P(n, 2, k)$ is equivalent to first draw a random item, then in the remaining $k-1$ draws draw one more unique item. There are $k-1$ ways which draw would produce this second unique item, with probability $\frac{n-1}{n}$. Thus:
$$P(n, 2, k) = (k-1)\left(\frac{1}{n}\right)^{k-2}\frac{n-1}{n}$$
By now it looks like a variation of binomial expansion, except the probability of drawing the next unique item is always decreasing. I went ahead and did a third case:
$P(n, 3, k)$ is equivalent to first draw a random item, then in the remaining $k-1$ draws draw two more unique items. There are ${k-1\choose2}$ ways which draws would produce these two unique items, with probabilities $\frac{n-1}{n}$ and $\frac{n-2}{n}$. Thus:
$$P(n, 3, k) = {k-1\choose2} \left(\frac{1}{n}\right)^{k-3}\frac{n-1}{n}\frac{n-2}{n}$$
I went ahead and generalized the formula. I got:
$$P(n, m, k) = {k-1\choose m-1} \left(\frac{1}{n}\right)^{k-1}\frac{(n-1)!}{(n-m)!}$$
I thought I had the logic right, but when I checked by calculating $P(3,1,3)+P(3,2,3)+P(3,3,3)$, which should give $1$, I got $7/9$ instead. Where did I miss?
 A: You already went wrong for $m=2$, since you assumed that only one of the remaining $k-1$ draws would yield the second item, whereas the remaining draws could all be either of the first or of the second item. You can get the correct probability e.g. by choosing a second item in one of $n-1$ ways, taking the probability that the remaining $k-1$ items will be drawn only from among these two items, and then subtracting the probability that all draws are the same:
$$
P(n,2,k)=(n-1)\left(\frac2n\right)^{k-1}-\left(\frac1n\right)^{k-1}\;.
$$
Systematically applying this approach for arbitrary $m$ using inclusion-exclusion leads to the Stirling numbers of the second kind, 
$$
\def\stir#1#2{\left\{#1\atop#2\right\}}
\stir nk=\frac1{k!}\sum_{j=0}^k(-1)^{k-j}\binom kj j^n\;,
$$
which count the number of way of partitioning a set with $n$ elements into $k$ non-empty subsets. To obtain the probability to draw $m$ out of $n$ items in $k$ draws, choosen $m$ items in $\binom nm$ ways, count the number of ways of partitioning the $k$ draws into $m$ non-empty subsets and assign the subsets to the items, yielding
$$
P(n,m,k)=\frac{\binom nm\stir kmm!}{n^k}=\binom nm\sum_{j=0}^m(-1)^{m-j}\binom mj\left(\frac jn\right)^k\;.
$$
For instance,
$$
P(n,2,k)=\binom n2\left(\binom22\left(\frac2n\right)^k-\binom21\left(\frac1n\right)^k\right)\;,
$$
in agreement with the above result.
