1
$\begingroup$

Problem: Jane must select $3$ different items for each dinner she will serve. The items are to be chosen from $5$ different vegetarian and $4$ different meat selections. If at least one of the selected items must be vegetarian, how many different dinners could Jane create?

So my attempt to solve this problem is as follows. It seems that the solution is just a slightly varied application of the multiplication principle

So if we assume the first item is the one mandatory vegetarian one, then the first one has $5$ possible choices. The second item has $(5-1)+4 = 8$ choices (since at this point it doesn't matter if we choose vegetarian or meat) and the third has $((5-1)+4)-1 = 7$ choices. Applying the multiplication princple we see that there are

$$5\cdot 8\cdot 7 = 280$$ possible dinners.

However the correct answer is $80$ dinners. What have I done wrong? Also while any answer would be specific to the question above, more generally is there a counting principle that I have missed here or used incorrectly?

$\endgroup$
  • 3
    $\begingroup$ Please take into account that ABC is the same meal as BAC $\endgroup$ – David Jul 10 at 14:38
  • 2
    $\begingroup$ Your answer is the correct answer to the wrong problem. The problem that you answered is "How many three-course meals can Jane serve where courses are brought out one at a time (and so order of courses is relevant), cannot be repeated, and the first course must be vegetarian?" This is different than the problem "How many three-course meals can Jane serve where courses are brought out simultaneously (and so order of courses is not relevant), courses cannot be repeated, and at least one course must be vegetarian (but it doesn't matter which one)?" $\endgroup$ – JMoravitz Jul 10 at 14:52
  • 1
    $\begingroup$ As they just said, you're work (what some call "boxes method") has the same idea as using permutation $P^n_r$, but here since order is not important you must be using combination $C^n_r$. $\endgroup$ – Fareed AF Jul 10 at 14:56
3
$\begingroup$

You are counting meals with more than one vegetarian item multiple times. Also, the order in which the courses are selected does not matter.

Method 1: Direct count.

Since there are five different vegetarian options and four different meat options, the number of ways of selecting $k$ vegetarian options and $3 - k$ meat options is $$\binom{5}{k}\binom{4}{3 - k}$$ Since at least one of the three courses must be vegetarian, the number of ways Jane could select at least one vegetarian course when selecting three courses is \begin{align*} \sum_{k = 1}^{3} \binom{5}{k}\binom{4}{3 - k} & = \binom{5}{1}\binom{4}{2} + \binom{5}{2}\binom{4}{1} + \binom{5}{3}\binom{4}{0}\\ & = 5 \cdot 6 + 10 \cdot 4 + 10 \cdot 1\\ & = 30 + 40 + 10\\ & = 80 \end{align*}

Method 2: Complementary counting.

The number of ways of selecting at least one vegetarian course can be found by subtracting the number of ways of selecting only meat courses from the total number of ways of selecting three courses. There are $\binom{5 + 4}{3} = \binom{9}{3}$ ways to select three of the nine courses. There are $\binom{4}{3}$ ways to select three of the four meat courses. Hence, the number of ways of selecting at least one vegetarian course is $$\binom{9}{3} - \binom{4}{3} = 84 - 4 = 80$$

Your errors:

You are counting each meal with two vegetarian courses twice, once for each way you could designate one of the two courses as the vegetarian course. You are counting each meal with three vegetarian courses three times, once for each way you could designate one of the three courses as the vegetarian course. Observe that $$\binom{5}{1}\binom{4}{2} + \color{red}{\binom{2}{1}}\binom{5}{2}\binom{4}{1} + \color{red}{\binom{3}{1}}\binom{5}{3}\binom{4}{0} = 140$$

Then why did you obtain $280$?

Suppose that the meal Jane selects consists of vegetarian chili, avocado and tomato salad, and green salad. If you designate vegetarian chili as the vegetarian course, you get the same meal whether you select avocado and tomato salad for the second course and green salad as the third course or whether you select green salad as the second course and avocado and tomato salad as the third course. Therefore, by taking the order in which Jane selects the additional courses into account, you have counted each pair of additional courses twice, which doubles your meal count. Notice that $$\color{red}{2}\left[\binom{5}{1}\binom{4}{2} + \color{red}{\binom{2}{1}}\binom{5}{2}\binom{4}{1} + \color{red}{\binom{3}{1}}\binom{5}{3}\binom{4}{0}\right] = 280$$

$\endgroup$
1
$\begingroup$

I would try a simpler two-step approach:

  • Get the number of total 3-item combinations: $\frac{9\cdot8\cdot7}{3!}=84$
  • Get the number of 3-all-meat-item combinations: $4$

You can easily figure out where that $80$ comes form

$\endgroup$
1
$\begingroup$

To get more sight on your error do the same with $1$ vegetarian item $V$ and $2$ meat items $M_1,M_2$.

Then it is obvious that there is only one possibility, but the answer according to your reasoning gives: $1\times2\times1=2$ possibilities.

$VM_1M_2$ and $VM_2M_1$ are counted by you as $2$ distinct possibilities.


Hint:

Without constraints are $\binom{5+4}3$ possibilities.

Exactly $\binom43$ of them do not contain a vegetarian item, so are forbidden.

Then how many are not forbidden?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.