# Why is the dish combinations in this problem 45 and not 12?

At a restaurant, customers can choose up to four side dishes and up to two main courses. If a customer must have at least 1 side dish and 1 main course, how many distinct dinner plate combinations are possible?

The answer is 45. I can only calculate 12.

Call the four side dishes A,B,C,D. Call the Main courses E and F.

E goes with A,B,C,D. F goes with A,B,C,D.

8 current.

Now EF goes with A,B,C,D.

12 total.

• It seems that any number of side dishes are also allowed. Sep 30, 2022 at 17:41

If any number of side dishes are allowed, then you may note that there are in total $$2^4 - 1 = 15$$ combinations of side dishes and $$2^2 - 1 = 3$$ combinations of main dishes, so a total of $$15 \cdot 3 = 45$$ total combinations.

You calculated:

1. How many ways you can have one main dish and one side dish. (4 each, 8 total).
2. How many ways you can have two main dishes and one side dish (4 total).

But the problem says up to four side dishes. You did not count how many ways you can pick one main dish and two side dishes, two main dishes and two sides dishes, etc.

If you have 4 side dishes, there are $$15$$ possible choices you can make, $$4=\binom{4}{1}$$ ways to choose one side dish, $$6=\binom{4}{2}$$ ways to pick two-side-dishes options, $$4=\binom{4}{3}$$ ways to pick three side dishes, and $$1=\binom{4}{4}$$ ways to pick all four side dishes (or just the number of subsets of a 4-element set without the empty set, $$2^4-1$$). And you have three ways to pick the main dish (one dish in $$2$$ ways, both dishes in one way).

So you have $$15\times 3 = 45$$ ways to make both choices.

Possible combinations of side dishes: $${4 \choose 1}+{4 \choose 2}+{4 \choose 3}+{4 \choose 4}=4+6+4+1=15$$.

Possible combinations of main courses: $${2 \choose 1}+{2 \choose 2}=2+1=3$$.

Thus the total number is $$15\times3=45$$.

For variety, here's an inclusion-exclusion approach. Count all subsets of $$4+2$$ dishes, subtract the "no side" and "no main" cases, and add back in the "no dish" case that was subtracted twice: $$2^{4+2} - \binom{4}{0}2^2 - \binom{2}{0}2^4 + \binom{4}{0}\binom{2}{0} = 64 - 4 - 16 + 1 = 45$$