Bounds for die roll Given a $n$-sided fair die, show that the probability $P$ that all faces from $1$ to $11$ show when doing $3n$-rolls is bounded by
$1 - 11 \cdot \frac{(n-1)^{3n}}{n^{3n}} \leq P \leq 1 -  11 \cdot \frac{11(n-1)^{3n}}{n^{3n}} + 5 \cdot 11 \cdot \frac{(n-2)^{3n}}{n^{3n}}$
I am really stuck on this one. I figured that the exact probability is very hard to find and stirling numbers are involved. So the only chance I have is to figure out what events where used for that bounds. My guess is that the left one comes from the assumtion that (Edit: Warning this is not quite correct, check the comments)
$\mathbb{P}($Faces 1-11 don't occur at all$)=\frac{|E|}{|Q|}=\frac{11 \cdot (n-1)^{3n}}{n^{3n}}$
And if you look at the complement it is that all faces 1-11 at least occur once. Surely this is a lower bound but how could I get the upper bound, I hope that I did not overlook something very easy.
 A: The answer can be arrived at via a pretty standard application of the Bonferroni inequalities. We generalize this problem ever so slightly. Fix $1 \leq m \leq n$ and $M \geq m$. We want to find the probability of seeing each element of the set $\{1,\ldots,m\}$ within $M$ rolls of our $n$-sided die.
Let $A_i$ be the event that the $i$th outcome was not rolled in the first $M$ throws of the die. Let $A = \cup_{i=1}^m A_i$ be the event that not all of $\{1,\ldots,m\}$ are seen in the first $M$ throws. We are interested in the complement, $\bar{A}$, of this event.
A straightforward application of the Bonferroni inequalities shows that
$$
\renewcommand{\Pr}{\mathbb{P}}
\sum_{i=1}^m \;\Pr(A_i) - \sum_{1 \leq i < j \leq m} \Pr(A_i \cap A_j) \leq \Pr(A) \leq \sum_{i=1}^m \;\Pr(A_i) \> .
$$
But, $\Pr(A_i) = (1-1/n)^M$ for each $i$ and $\Pr(A_i \cap A_j) = (1-2/n)^M$ for each pair $i \neq j$. This yields
$$
m\Big(1-\frac{1}{n}\Big)^M - \frac{m(m-1)}{2}\Big(1-\frac{2}{n}\Big)^M \leq \Pr(A) \leq m \Big(1-\frac{1}{n}\Big)^M
$$
Using the fact that $\Pr(\bar{A}) = 1 - \Pr(A)$ and plugging in $m = 11$ and $M = 3 n$ gives the result.

Note that if $M$ is relatively large with respect to $n$ and $m$, then we can get an exponential bound. In particular, if, for $c > 0$, $M = n \log m + c n$, then
$$
m(1-1/n)^M = m (1 - 1/n)^{n \log m + c n} \leq e^{-c}
$$
and so the probability of seeing all elements of $\{1,\ldots,m\}$ within $M = n \log m + c n$ throws is
$$
\Pr(\bar{A}) \geq 1 - e^{-c} \> .
$$
