# E.T. Jaynes probability theory exercise 3.2

Suppose an urn contains $N = \sum_{i=1}^k N_i$ balls, $N_1$ of color $1$, $N_2$ of color $2$, $\dots$, $N_k$ of color $k$. We draw $m$ balls without replacement; what is the probability that we have at least one of each color?

Can someone please explain to me why the following is not a correct solution and propose an alternative? Thanks much.

$$N_1\cdot N_2\cdot \cdots \cdot N_k \cdot \frac{\binom{N-k}{m-k}}{N \choose m}$$.

I think the given answer is double-counting. Take a simple example with

\begin{align} k &= \text{$2$ colors} \\ N_1 &= 2 \\ N_2 &= 1 \\ N &= N_1+N_2 = 3 \\ m &= 3. \end{align}

Of course, with $m=N$, there is only $1$ way to select the balls. However,

$$N_1\cdot N_2\cdot\binom{N-k}{m-k} = 2\cdot 1\cdot\binom{3-2}{3-2} = 2.$$

The problem is that, for any particular color $c$, each selection is counted once for each $c$-color ball being the designated mandatory one for that color. Instead, the selection should be only counted once.

One solution is to use the Inclusion-Exclusion principle. Define set:

$$A_i = \{\text{Selections that exclude balls of color i}\}.$$

Then the required probability is

$$\dfrac{\left|\bigcap_{i=1}^{k} A_i^c \right|}{\binom{N}{m}}.$$

Using the IE principle, and with $\Omega$ the universal set of all possible selections:

\begin{align} \left|\bigcap_{i=1}^{k} A_i^c \right| &= \left|\left(\bigcup_{i=1}^{k} A_i\right)^c \right| \\ &= \left|\Omega\right| - \left|\bigcup_{i=1}^{k} A_i \right| \\ &= \binom{N}{m} - \sum_{i=1}^{k} |A_i| + \sum_{i\lt j} |A_i\cap A_j| - \cdots + (-1)^k\left|\cap_{i=1}^{k}A_i\right|. \end{align}

Here,

\begin{align} |A_i| &= \binom{N-N_i}{m} \\ |A_i\cap A_j| &= \binom{N-N_i-N_j}{m}\text{, and so on.} \end{align}