Wrong with the method of computing combinations for this GRE question

combinationscombinatorics

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

Correct answer: 80

I calculated this question incorrectly using the following logic:
Jane must always have at least one vegetable dish, so let's select that first, 5C1, now she can select any combination of 2 items from the remaining 8 items, 8C2, therefore the answer should be (5C1)*(8C2) = 140.

I see that I am counting some combinations twice because the two sets intersect in the veggies. However I am looking for a general unified formula to compute problems of this nature rather than the suggested solution of computing "how many all veggie dishes, 2 veggie, 1 veggie dishes" and summing. That method isn't scalable as the number of ingredients goes up.

Best Answer

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

Related Solutions

[Math] combination of choosing dinner menu

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.

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

[Math] combination of choosing dinner menu

Combinatorics with ordering significance

Related Question