Given an urn of $k$ distinct balls. Do $n$ drawings with replacement. What is the probability that every ball is drawn at least once? The space of outcomes is $k^n$ since for each of the drawings, there are $k$ outcomes. Deciding the numerator seems harder. Originally the problem was "What is the probability that every ball is not drawn at least once?", but it seems easier to think of the complement, all different balls drawn at least once. I am thinking of employing the stars and bars method, which gives that there are $\frac{(n-1)!}{(k-1)!(n-k)!}$ different ways for each ball to come out at least once. 
This gives the answer to my original question as $1- \dfrac{\dfrac{(n-1)!}{(k-1)!(n-k)!}}{k^n}$. I think this is the exact answer, but I'm not sure. In my notes, my teacher just did something fancy and said we just need it to be $\leq \frac{k (k-1)^n}{k^n}$. Can someone help explain what approximation my teacher made?
 A: if you write down the inclusion-exclusion principle then the number of ways in which a given ball is not drawn is $ {(k-1)^n}$. you have $k$ balls from which you can pick the one that's not drawn which gives you $ k(k-1)^n$ so you're done. the probability that some ball is not drawn is less than the sum of probabilities that the $i$-th ball is not drawn which according to our calculations is $$ \frac{k(k-1)^n}{k^n}$$ cause we divided over the total number of possibilities $k^n$
in fact it's not so much an inclusion-exclusion kind of argument the way it's written now. I was first thinking about computing the probability of the event {all balls are drawn}. Here it's just something like that: let $A_i$ denote the event [$i$-th ball was not drawn] and let $A$ denote the event [some ball was not drawn]. then $$A \subset \bigcup_{i=1}^k A_i$$
so
$$ P(A) \leq \sum_{1}^k P(A_i)$$
and 
$$ P(A_i) = \frac{(k-1)^n}{k^n} $$ which ends the argument
A: Let our $k$-element set be $K=\{1,2,3,\dots,k\}$. Let $N=\{1,2,3,\dots,n\}$. 
Imagine that we have done $n$ draws. Let $f(i)$ be the ball drawn on the $i$-th trial. Then $f$ is a function from $N$ to $K$. We want the probability that the function $f$ is onto.
There are $k^n$ equally likely functions. The number of onto functions is $k!S(n,k)$, where $S(n,k)$ is the Stirling Number of the Second Kind. There is a wide variety of recurrences for $S(n,k)$, but no simple closed form. 
The required probability is therefore $\dfrac{k!S(n,k)}{k^n}$.
