Currently I am struggling to undestand Combination with repetition, and I feel confused if the task changes just a bit.
It seems like distinguishing the patterns and being able to split the task into the sub-tasks and count them separately is crucial (however, the combinatorics calculator do help).
EXAMPLE-1:
The bag has
3 cyan,3 magenta,3 yellowand3 key/black
(CMYK) balls.I can choose
3 balls.How many combinations can I get?
Answer: The problem can be re-formulated as how many combinations can I get if I choose 3 balls from cyan, magenta, yellow and key/black categories (four colors), since I've got enough balls of each color. So I have k=3 balls to choose from n=4 colors.
SOLUTION-1: Then the straightforward way is to use Combination with repetition formula [which can be easily transformed into combination without repetition formula]:
$$C_r(n,k)=\left[{_{k+n-1}C_{k}}=\binom{k+n-1}{k}={_{k+n-1}C_{n-1}}\binom{k+n-1}{n-1}\right]=\frac{(k+n-1)!}{k!(n-1)}=\frac{(3+4-1)!}{3!(4-1)!}=\frac{3!\times6\times5\times4}{3!\times6}=20$$
That is more or less evident.
SOLUTION-2: Spliting into sub-tasks of Combination without repetition (I've found a similar approch here).
a). All colors are different (CMY,CMK,…) = ${_nC_k} = \frac{n!}{k!(n-k)!} = {_4C_3} = 4$
b). Only two colors are the same (CCM,CCY,…) = ${_4C_1} \times {_3C_1} = 4\times3 = 12$
c). All colors are the same (CCC,MMM,…) = ${_4C_1} = 4$
Total = $4+12+4=20$, right?
I use the sum of Combinations without repetition to get the same result. Are there any other ways to get the same result with some other formulas (permutation with repetition minus something probably)?
EXAMPLE-2:
The bag has
1 cyan,3 magenta,3 yellowand3 key/black
(CMYK) balls.I can choose
3 balls.How many combinations can I get?
Am I right that I should tackle the problem like in Solution-2 only?
a). All colors are different (CMY,CMK,…) = ${_nC_k} = \frac{n!}{k!(n-k)!} = {_4C_3} = 4$
b). Only two colors are the same (cyan not counting) (MMC,MMY,…) = ${_4C_1} \times {_3C_1}-3 = 4\times3-3 = 9$
c). All colors are the same (cyan not counting) (MMM,YYY…) = ${_4C_1}-1 = 4-1 = 3$
Total = $4+9+3=16$, or do I miss anything? Or, if you were me, would you tackle the problem in any other, probably more efficient/interesting, way?
Thank you!
Best Answer
All the work you did is correct.
For the second example, there are a couple of approaches you could take.
Method 1: Consider cases, depending on how many cyan balls are selected. Let $c, m, y, k$ denote, respectively, the number of selected balls which are cyan, magenta, yellow, key/black.
If no cyan balls are selected, then $$m + y + k = 3,$$ which is an equation in the nonnegative integers with $$\binom{3 + 3 - 1}{3 - 1} = \binom{5}{2}$$ solutions.
If exactly one cyan ball is selected, then two balls must be selected from the remaining three colors, so $$m + y + k = 2,$$ which is an equation in the nonnegative integers with $$\binom{2 + 3 - 1}{3 - 1} = \binom{4}{2}$$ solutions.
In total, the number of ways three balls can be selected from one cyan ball, three magenta balls, three yellow balls, and three key/black balls is $$\binom{5}{2} + \binom{4}{2} = 10 + 6 = 16$$ as you found.
Method 2: We subtract the number of selections with at least two cyan balls from the number of ways we could select three balls if there were (at least) three balls of each color.
If there were (at least) three balls of each color, then the number of ways we could select three balls from the available colors is the number of solutions of the equation $$c + m + y + k = 3 \tag{1}$$ in the nonnegative integers, which has $$\binom{3 + 4 - 1}{4 - 1} = \binom{6}{3}$$ solutions, as you found in your first example.
From these, we subtract those selections in which $c \ge 2$. If $c \ge 2$, then $c' = c - 2$ is a nonnegative integer. Substituting $c' + 2$ for $c$ in equation $1$ and simplifying yields $$c' + m + y + k = 1 \tag{2}$$ Equation $2$ is an equation in the nonnegative integers with four solutions.
Hence, the number of ways three balls may be selected from one cyan ball, three magenta balls, three yellow balls, and three key/black balls is $$\binom{3 + 4 - 1}{4 - 1} - \binom{1 + 4 - 1}{4 - 1} = \binom{6}{3} - \binom{4}{3} = 16$$ which agrees with the answer we obtained above.