Probability of drawing three different colours without order

Question

I have a bag filled with $10$ balls each of different colours. Now I have picked one ball randomly and after looking at the colour, I will drop the ball again in the bag. I have repeated this for $10$ times. For all $10$ drawings, I will note the colour of the ball that is drawn. What is the probability that I will draw balls of only three different colours in the $10$ drawings (the colour of balls don't matter).

My attempt is that we can have a probability of $$\frac{10 \cdot 9 \cdot 8 \cdot 3^7}{10^{10}}$$ Is this the correct answer? Else please explain the correct one.

Answer 1

There are $\tfrac{10\cdot 9\cdot 8}{3\cdot 2\cdot 1}$ ways to select three distinct colours.   That is also written as $\binom {10}3$ or $^{10}\mathrm C_3$.

There is a probability of $\tfrac{3^{10}}{10^{10}}$ for obtaining a drawing no more than those three distinct colours when selecting from $10$ distinct items with replacement.

However, that includes drawings of only one or two of those three colours - it does not ensure the selection contains all three.

So use the Principle of Inclusion and Exclusion.

Answer 2

I think this problem is more complicated than I first thought. First, let's figure out the probability of having exactly 3 distinct colors among the draws. We can break this down into 36 disjoint events. The events are the position of when the second and third colors first appear. You can have any of the following: $(2,3),\ldots, (2,10), (3,4),\ldots, (3,10), \ldots, (9,10)$. When you calculate this out, you get: $$\dfrac{\displaystyle \sum_{1<a<b\le 10} \prod_{i=1}^{10}\begin{cases}1, & 1<i<a \\ 2, & a<i<b \\ 3, & b<i \\ 8, & b=i \\ 9, & a=i \\ 10, & i=1\end{cases}}{10^{10}} = \dfrac{6,717,600}{10^{10}} = \dfrac{8,397}{12,500,000} \neq \dfrac{10\cdot 9\cdot 8\cdot 3^7}{10^{10}}$$

So, your answer is not correct. Since I have broken the problem down into disjoint cases, and any example of a draw where there are exactly 3 distinct colors must fall into one of these cases.

This can also be done with Inclusion/Exclusion.

Choose 3 colors: $\dbinom{10}{3}$

Of those three colors, choose 0, 1 or 2 that will not be used:

$$\dbinom{3}{0}, \dbinom{3}{1}\text{ or }\dbinom{3}{2}$$

So, the number of ways to select exactly 3 colors:

$$\dbinom{10}{3}\left(\dbinom{3}{0}\dfrac{3^{10}}{10^{10}} - \dbinom{3}{1}\dfrac{2^{10}}{10^{10}}+\dbinom{3}{2}\dfrac{1^{10}}{10^{10}}\right) = \dfrac{8,397}{12,500,000}$$

Answer 3

Since upon recording the color, you put back the extracted ball, then a sequence of extractions is a sequence of $10$ i.i.d. uniform random variables, which can take up one of the colors.

Let's go more general, and fix that there are $m$ colors, a sequence of $n$ extractions, and that we are asking for the probability that the extraction contains exactly $q$ different colors.

The various different extractions, the universe of events, are given by the $n$-tuples representing the ordered sequence of extracted colors (coded $1, \cdots,m$).
So each sequence can be encoded as one of the products in the expansion of $$ \begin{array}{l} \left( {x_{\,1} + x_{\,2} + \cdots + x_{\,m} } \right)^{\,n} = \\ = \cdots + \underbrace {x_{\,q_{\,1} } \cdot x_{\,q_{\,2} } \cdot \cdots \cdot x_{\,q_{\,n} } }_{n\,{\rm terms}} + \cdots \quad \left| {\;\left( {\,q_{\,1} ,\,q_{\,2} ,\; \cdots ,\,q_{\,n} } \right) \in \left[ {1,m} \right]^{\,n} } \right.\quad = \\ = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,k} } \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,n} \, = \,n} \\\end{array}} \right.\;} {\left( \begin{array}{c} n \\ j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,n} \\ \end{array} \right)\;x_{\,1} ^{j_{\,1} } \;x_{\,2} ^{j_{\,2} } \; \cdots \;x_{\,m} ^{j_{\,m} } } \\ \end{array} $$ where the multinomial is counting the sequences with the same "frequency histogram".

Now we have $\binom{m}{q}$ ways to choose the $q$ colors that shall appears, and $$ \sum\limits_{\left\{ {\begin{array}{*{20}c} {1\, \le \,j_{\,k} } \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,q} \, = \,n} \\ \end{array}} \right.\;} {\left( \begin{array}{c} n \\ j_{\,1} ,\,j_{\,2} ,\, \cdots ,\,j_{\,q} \\ \end{array} \right)\;} = \sum\limits_{\left\{ {\begin{array}{*{20}c} {0\, \le \,j_{\,k} } \\ {j_{\,1} + \,j_{\,2} + \, \cdots + \,j_{\,q} \, = \,n - q} \\ \end{array}} \right.\;} {\left( \begin{array}{c} n \\ j_{\,1} + 1,\,j_{\,2} + 1,\, \cdots ,\,j_{\,n} + 1 \\ \end{array} \right)\;} $$ willl give the number of sequences where they will appears, at least once, and no other color.

Answer 4

From the discussion in comments I take it that by “only three different colours” you mean “exactly three different colours” (and not “at most three different colours”).

I will answer a more general question. When you make $n$ draws with replacement from a bag with $m$ different colored balls, what is the the probability of $k$ different colors appearing? Equivalently, when you roll a fair $m$-sided die $n$ times, what is the probability that $k$ different faces appear?

There are $\left\{n\atop k\right\}$ ways to partition $n$ draws into $k$ sets, where $\left\{n\atop k\right\}$ is a Stirling number of the second kind; there are $\binom mk$ ways to choose $k$ colours from $m$ colours; and there are $k!$ ways to assign those $k$ colours to the $k$ sets. Thus the probability to draw exactly $k$ out of $m$ colours in $n$ draws is

$$ m^{-n}\left\{n\atop k\right\}\binom mkk!\;. $$

In your case, $n=10$, $m=10$ and $k=3$, so this is

$$ 10^{-10}\left\{10\atop 3\right\}\binom{10}33!=10^{-10}\cdot9330\cdot120\cdot6=\frac{8397}{12500000}\;. $$

This corresponds to the result you get by directly applying inclusion–exclusion, as you can see by using the inclusion–exclusion expression for the Stirling numbers,

$$ \left\{n\atop k\right\}=\frac1{k!}\sum_{i=0}^k(-1)^i\binom ki(k-i)^n\;. $$