# Choose 4 types of soup from 10 varieties, with constraint?

We have to choose 4 types of soup from a supermarket's 10 varieties, such that at least 2 are identical. In how many ways can we do this ?

We have 10 varieties of soup like so {v1, .. v10}. We can partition our choices into those with 4 identical (e.g. {v1, v1, v1, v1}), those with 3 identical (e.g. {v1, v1, v1, v2}), and those with 2 identical (e.g. {v1, v1, v2, v3}). Our total number of choices is then:

10 + 10.9 + 10.9C2 = 10 + 90 + 360 = 460

The textbook answer is 505. Can anyone point out my error ?

-

You're missing a case!

Here's a hint: you're 45 below the right answer, 45 = 10C2. What choice can you make that requires you to pick two varieties where the order is not important?

-
Thanks. Yes, I missed the cases like {v1, v1, v2, v2} with 10C2 possibilities. I'm not sure combinatorics tests mathematical ability as much as pattern recognition. (Good hint, BTW, but why, oh, why does this forum accept comments on hitting return) –  user7597 Mar 2 '11 at 12:46
@ukmaths: a number of us have complained about comments being posted when you hit return. The site operators claim others like it, so it won't be changed. –  Ross Millikan Mar 2 '11 at 14:40

One could alternatively find the total number of sub-multisets of size $4$, namely $$\left(\binom{10}{4}\right)=\binom{10+4-1}{4}=715$$ (the first function is the multichoose function; refs: MathWorld, Wikipedia) and subtract the number of sub-multisets of size $4$ with no duplicates, namely $$\binom{10}{4}=210$$ which gives $$505.$$

-