Let's say we had a sack with exactly 4 green marbles, 4 orange marbles, 4 black marbles and 4 violet marbles. [closed]

How many different picks are there having exactly 8 marbles that have at least one marble of each color?

I'm not quite sure whether this is a permutation or a combination. Going with the assumption that it is a combination I'm guessing the sample space is $\binom{16}{8}$ . To find at least one marble of each color we could go with the complement of this statement. Not quite sure how to express it.

Perhaps $\binom{16}{8}$ $-4 \binom{12}{4}$ with the assumption that the complement of "at least one of each color" could be expressed as $-4\binom{12}{4}$ But even that seems lacking.

Solution 1:

Assuming order does not matter and each marble were uniquely identifiable, approach by inclusion-exclusion, getting rid of the "bad" outcomes which were missing one or more colors. We start with the total number of ways to pick, then subtracting those ways where at least one color was missing, adding back in the ways where two colors were missing.

$$\binom{16}{8}-4\binom{12}{8}+\binom{4}{2}\binom{8}{8}$$

This answer which uses marbles as all distinct is the most likely answer to be helpful when answering the related probability question under the most common assumptions about distribution and such, the probability being this answer divided by $\binom{16}{8}$.

The more likely question if we were purely concerned with practicing our counting skills is where order does not matter and marbles are all identical except perhaps by color. For this, we use stars-and-bars.

Relate your problem to the problem of counting the number of integer solutions to the system $\begin{cases}x_1+x_2+x_3+x_4=8 \\1\leq x_i\leq 4~~\forall i\end{cases}$

By ignoring the upperlimit, this becomes a question of stars-and-bars. We imagine laying out eight stars in a row and then simultaneously choosing three of the available gaps between the stars to place bars having not repeated a choice and interpreting the result as an arrangement we are interested in (or interpreting as a solution to the linear system above). The stars to the left of the first bar will correspond to the number of marbles of the first color we used. The stars between the first and second bar will correspond to the number of marbles of the second color we used etc...

There are seven available gaps and we want to choose three of them so there are $\binom{7}{3}$ different ways to pick marbles here.

Now we take into consideration the upper bounds... some of these ways we counted were bad because we used more marbles than were possible for a color. In this problem we see that the only way to have picked eight marbles with more than four marbles of a color while also having at least one of every marble would be if we picked exactly five marbles of a color and one marble of each of the others. There are thus exactly four "bad" outcomes we counted.

$$\binom{7}{3}-4$$

To emphasize again, the outcomes counted by stars-and-bars will generally not be equally likely (unless the problem explicitly states otherwise) and so this is generally unhelpful for most probability questions. Also, as problems get more complicated, there may have been greater challenges here at the last step in counting how many outcomes were bad. For the general approach, you may need to repeat the stars-and-bars argument multiple times having performed some algebraic manipulations or changes of variable and iterated through a more full inclusion-exclusion argument. For more on that, search elsewhere on this site for larger examples.

Note also the use of stars-and-bars for solving systems. The number of solutions to the system $\begin{cases}x_1+x_2+\dots+x_a = b\\0\leq x_i\end{cases}$ will be $\binom{a+b-1}{a-1}$

The number of solutions to the system $\begin{cases}x_1+x_2\dots+x_a = b\\1\leq x_i\end{cases}$ will be $\binom{b-1}{a-1}$

Be warned that some books will write the above system where the number of variables is $n$ and they sum to $r$. Other authors may write it where the number of variables is instead $r$ and they sum to $n$. This can lead to some confusion in whether you were meant to use $\binom{n+r-1}{r-1}$ or if you were meant to use $\binom{n+r-1}{r}$. If you remember the derivation and where the formula comes from in the first place, you should be able to keep it straight in your head.