I have 23 marbles of 7 different colors. I want to know how many different color combinations there could there be?
Possible marble color combinations.
-
0Yes, color is the only distinguishable attribute. – 2012-02-26
2 Answers
I assume you consider the colors to be distinct and the marbles to be otherwise identical. (If the marbles were distinct before being colored, then you would have $7^{23}$ possibilities.)
This is a classic stars and bars question. We are essentially placing 23 objects into 7 distinct categories. To do this, we order the 23 marbles along with 6 "dividers" any way we like. All those marbles that occur before any dividers are given color #1, those between the first and second divider get color #2, etc. So there are $\binom{23+6}{6}$ color combinations.
If you want at least one marble of each color, simply set aside one marble for each color and arrange the others along with the dividers. There are $\binom{(23-7)+6}{6}$ ways to do this.
If you wanted to have at least 2 or at least 3 of each color, or if you wanted to have at least a certain number of marbles in a specific color, you just set those aside and arrange the rest the same manner.
Call the colours $1$, $2$, and so on up to $7$. Line up $23$ uncoloured marbles in a row.
This creates $22$ "gaps."
Choose $6$ of these gaps to put separators into. This can be done in $\dbinom{22}{6}$ ways.
Paint all the marbles up to first separator with colour $1$, then the ones between the first separator and the second with colour $2$, and so on. That will create all possible colour combinations in which there is at least one marble of each colour.
If you allow the possibility that some colours might not occur, a similar analysis holds. Add $7$ marbles to your collection. So now you have $30$ marbles. Do the painting as described above. It can be done in $\dbinom{29}{6}$ ways.
So now you have $30$ marbles, with at least one of each colour. Give away $7$ marbles, one of each colour. You are left with $23$ marbles. Every colour combination of $7$ colours (including the combinations where some colours may be missing) is uniquely produced in this way.
Thus the answers are:
$\dbinom{22}{6}$ if there must be at least one of each colour, and
$\dbinom{29}{6}$ if one or more colours could be absent.
For more about the idea used above, please see the Wikipedia entry Stars and Bars.
-
0@Henry: I think you're right, but it isn't 100% unambiguous to me, so I thought a clarifying comment was in order. +1. – 2012-02-26