Question: A grocery store sells apples, oranges, and grapefruits. Assume that each kind of fruit is identical and that the chosen order does not matter. Suppose that there are an unlimited of grapefruits but only 9 apples and 10 oranges in the
store. In how many ways can 12 fruits be chosen.
My idea is to start from all the possible cases without restriction and subtract the cases that don't match the requirement. Suppose there're unlimited supplies for all fruits, then there will be $\binom{12+3-1}{3-1}$ ways to choose fruits (is that correct?). Then I'll subtract the cases with more than 9 apples or 10 oranges. For example:
10 apples: there're $\newcommand\mchoose[2]{\left(\!\!\left({#1}\atop{#2}\right)\!\!\right)}\mchoose 22$ ways (consider oranges and grapefruits)
11 apples or 11 oranges: $\mchoose 21$ ways
Am I on the right track? Thanks!
Best Answer
You are on the right track except that the all fruits of the same kind are identical. $3^{12}$ would be right if all fruits were different.
So you should instead be using stars and bars. You are looking for solution to
$x_1 + x_2 + x_3 = 12$
where $x_1, x_2, x_3$ are number of apples, oranges and grapefruits.
That is given by, $\displaystyle {12 + 3 - 1 \choose 3 - 1} = {14 \choose 2}$
Now subtract all unfavorable cases from it as you mentioned.