If at least one of the selected items must be vegetarian, how many different dinners could Jane create

combinatorics

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?

Best Answer

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$$

Related Solutions

Wrong with the method of computing combinations for this GRE question

You've correctly identified the flaw in your reasoning, which is that you are possibly double counting.

Here's an alternative approach: Count the total number of dinners with no restriction, which will be $9 \choose 3$, and subtract off the number of disallowed dinners, which will be those that are all meat, namely $4\choose 3$. The answer is then $84 - 4=80$.

Combinatorics with ordering significance

The number of permutations will be a sum that starts with $s$ factors and goes up to $5$ factors (the number of containers). In other words:

1st possibility = 50 * 40                <-- chooses from two containers
2nd possibility = 50 * 40 * 30           <-- chooses from three containers
3rd possibility = 50 * 40 * 30 * 20      <-- chooses from four containers
4th possibility = 50 * 40 * 30 * 20 * 10 <-- chooses from five containers

Total number of possibilities = 13262000

In Javascript, the code would look like this:

var CONTAINER_COUNT = 5;
var NUMBERS_PER_CONTAINER = 10;

function calculatePermutations(s) {
    var result = 0;
    for (var i = s; i <= CONTAINER_COUNT; i++) {
        var permutations = 1;
        var containersAvailable = CONTAINER_COUNT;
        var choices = 0;
        while (choices < i) {
            permutations *= containersAvailable * NUMBERS_PER_CONTAINER;
            containersAvailable--;
            choices++;
        }
        result += permutations;
    }
    return result;
}

console.log(calculatePermutations(2));

This code prints:

13262000

Best Answer

Related Solutions

Wrong with the method of computing combinations for this GRE question

Combinatorics with ordering significance

Related Question