Suppose I have $5$ vegetarian options to choose from, and $4$ options of meat,
and I have to select three entries for dinner, which should contain at least one vegetarian option. How many types of dinner menu can I come up with?
My solution) Since I have to choose three entries and one should be vegetarian all the time, it is the same as 5*(number of possible combinations of rest of the 4 vegetarian menu + 4 meat menu). so it would be $5\binom{ 8}{2} = 140$.
Answer) $\binom{5}{1}\binom{4}{2} + \binom{5}{2}\binom{4}{1} + \binom{5}{3} = 80$.
I understand the logic used to get the right answer, but I don't know what is wrong with my original answer. Any help please?
Best Answer
You have overcounted the cases with more than one vegetarian option. If you have vegetarian choices $a,b,c,d,e$ and meat choices $1,2,3,4$ you could have $a$ be the first choice and $b,2$ the next two or you could have $b$ be the first choice and $a,2$ the next two. These both result in the same meal, but you have counted them both.