If I roll a 3-sided die $n$ times, what is the probability that each side shows up at least once? I have been racking my brain over this one, but I can't figure it out. The probability of at least one of the rolls being a 1 is
$$ 1 - (\frac{2}{3})^n$$
The probability of at least one of the remaining rolls being a two should be
$$ 1 - (\frac{2}{3})^{n-1}$$
Similarly, the probability of at least one of the remaining rolls being a three should be
$$ 1 - (\frac{2}{3})^{n-2}$$
Putting it all together, we get
$$ (1 - (\frac{2}{3})^n) \cdot (1 - (\frac{2}{3})^{n-1}) \cdot (1 - (\frac{2}{3})^{n-2})$$
This seems right to me, and also conveniently handles having an $ n < 3 $ equals 0. However, when I plug in $n = 3$, I get
$$ \frac {95}{729} $$
When I know that the answer should be 
$$ \frac {2}{9} $$
What am I doing wrong? 
 A: Using the Principle of Inclusion and Exclusion:
$$\frac{3^n-3\cdot 2^n+3}{3^n} = 1-\frac{2^n-1}{3^{n-1}} \textsf{ when }n\geq 3$$
A: Assume that we record the result as a sequence of length $n\ge 3$. We count the bad sequences, in which at least one number is missing.
There are $2^n$ sequences in which $1$ is missing, $2^n$ where $2$ is missing, and $2^n$ where $3$ is missing.
However, the sum $2^n+2^n+2^n$ counts twice each sequence where two of the numbers are missing.
So the number of bad sequences is $3\cdot 2^n-3$.
Remark: Solving the problem along your path seems difficult. The conditional probability that there is at least one $2$, given that there is at least one $1$, is not given by your expression.
A: here we have to put constraint on $n$ whether it is even or odd.
Let $A$ is an event that each side shows up atleast once, then
$$P(A)=1-(P(1)+P(2)+P(3)+P(1,2)+P(1,3)+P(2,3))$$ where $P(i)$ is the probability that number $i$ occurs on all the throws. $P(i,j)$ is the probability that only the numbers $i$ and $j$ occurs each atleast once.
Trivially
$$P(i)=\frac{1}{3^n}$$
Now $$P(i,j)=\frac{n!}{(n-1)!1!}+\frac{n!}{2!(n-2)!}+\frac{n!}{3!(n-3)!}+\cdots+\frac{n!}{(n-2)!2!}+\frac{n!}{1!(n-1)!}$$ $\implies$
$$P(i,j)=\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+\cdots+\binom{n}{n-2}+\binom{n}{n-1}=2\left(\binom{n}{1}+\binom{n}{2}+\cdots\right)$$ $\implies$
$$P(i,j)=2S-2$$ where $$S=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots$$ i.e., $S$ denotes first half sum of binomial coefficients.
If $n$ is even
$$S=2^{n-1}-\frac{\binom{n}{\frac{n}{2}}}{2}$$ and
If $n$ is Odd
$$S=2^{n-1}$$
Now $$P(A)=1-\frac{3+3(2S-2)}{3^n}=1-\frac{2S-1}{3^{n-1}}$$
Finally if $n$ is Even
$$P(A)=1-\frac{2^n-\binom{n}{\frac{n}{2}}-1}{3^{n-1}}$$
if $n$ is Odd
$$P(A)=1-\frac{2^n-1}{3^{n-1}}$$
