We are given 4 different items with the following frequency:
Item A: 9 times
Item B: 9 times
Item C: 6 times
Item D: 3 times
How many combinations of these items can we produce that contain at most 3 different items, e.g.
Combination 1: 0 times item A, 1 times item B, 3 times item C, 3 times item D.
My solution is $10*10*7*4-9*9*6*3$. We have 10 ways of taking item A (either 0 times, 1, times, …, 9 times), 10 ways of taking item B, 7 of taking item C and 3 of taking item D. From this solution I subtract all the combinations that take exactly 4 different items.
But my friend states that the solution should be $2*(10*7*4)+10*10*7+10*10*4$ where you count the possible combination for each case of leaving this item out.
Which one of us is right?
Best Answer
$2 \cdot (10 \cdot 7 \cdot 4) + 10 \cdot 10 \cdot 7 + 10 \cdot 10 \cdot 4 ~$ has duplicates.
For example, when you leave out item $A$ and count combinations with items $B, C$ and $D$, it also counts combinations where there are only items $C$ and $D$.Now when you leave out item $B$ and count combinations with items $A, C$ and $D$, it again counts combinations where only items $C$ and $D$ are present.
Your work is correct. Also note it includes combination where you do not pick any of the items. In case you must pick at least one item, you will have to subtract $1$ from your answer.