I have 4 red {A, B, C, D}, 3 green {E, F, G} and 2 blue books {H, I}. How many ways to stack them is there? What is the formula for computing this?
Stack 4 red, 3, green and 2 blue books
-
0(1) How many ways would there be to stack the books if they were all different colors? (2) If two are the same color, how many fewer unique possibilities are there? (Hint: each possibility happens twice) (3) What about if three are the same color? – 2012-02-04
4 Answers
Your notation is confusing because you make it seems like all the books are distinguishable, but I think you mean they are not?
However, let's start with distinguishable. If you had 9 different books, I think you would agree that there are $9 * 8 * 7 * \dots * 2 * 1 = 9!$ ways to stack them.
But now some of them are the same. So you need use the multinomial formula. The idea is that if you have the red books arranged in some way, you could rearrange just the red and it doesn't change the outcome. So you need to effectively divide out the duplicates.
\begin{equation} \dfrac{9!}{4!3!2!} \end{equation}
The $4!$ for the number of ways you could rearrange just the red, then the 3 for just the green, and the 2 for just the blue. You are basically saying "If I could distinguish these same-color books, how many ways could I rearrange them to get the same answer.
-
0The multinomial coefficient is the answer – 2012-02-04
Assume that books of the same colour are indistinguishable. The positions of the $2$ blue books can be chosen in $\dbinom{9}{2}$ ways. For each such choice, the positions of the $3$ green books can be chosen in $\dbinom{7}{3}$ ways. Once we have done that, the positions of the red books are determined. So the total number of ways is $\binom{9}{2}\binom{7}{3}.$
Remark: The above was not precisely a formula, it was more a procedure, a way of thinking. For this exact type of problem, there is, as was pointed out in other posts, a formula, since the answer is a multinomial coefficient. However, for many problems, there is no single formula that deals with the problem, so one has to thread together two or more ideas.
The number of ways of doing the task is given by the mutinomial coefficient $\dfrac{9!}{4!3!2!}$.
Imagine you put sticky-notes with labels 1-9 on the books. In this case, the books are all distinct, so there are 9! ways to order them. Now remove the labels from the red books. There are 4! ways to label these books; we see that the count of 9! counts every ordering of the books is counted 4! times when we strip of the labels from the red books. Now repeat this for the green and the blue books and you get a result of ${9!\over 4!3!2!}.$