Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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:
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$$
