Discrete Math- How many pizzas can be ordered with at least one meat and one veggie

Question

A pizza parlor has six meat toppings and four vegetable toppings that can be added to a pizza. Pizzas also come in three different sizes. a) If any nonempty subset of the ten toppings can be added to each size of pizza, how many different pizzas can be ordered? b) How many pizzas can be ordered that have at least one meat topping and at least one vegetable topping?

I figured out a). Since there are 10 different toppings, and 3 different pizza sizes, there are 2^10 different combinations for each pizza. We multiply that by 3 therefore we get 3072 different pizzas. Though b) is what I can figure out.

How do you find out how many pizzas have at least on meat topping and at least one vegetable topping? help would be appreciated, thanks

Answer 1

First of all your answer to a is incorrect. It should be 3069 because you do not include the empty sets.

For b, you subtract all the possible toppings that do not fit the requirement from the total combinations. So:

# of ways with no meat but no empty sets= $3(2^4 - 1)$

# of ways with no vegetables but no empty sets= $3(2^6 - 1)$ //notice that they don't double count with the previous #

What you want: $3069 - 3(2^4+2^6-2)=2835$

Answer 2

You can count the number of pizzas that do not fit the requirement, and then subtract that from the total.

The number of pizzas with $0-6$ meat toppings is equal to $3(2^6)$ -- $3$ from the different sizes, and then in each case we are picking $0-6$ toppings from a total of $6$ toppings, and $\displaystyle \sum_{k=0}^n {n \choose k} = 2^n$

The number of pizzas with $1-4$ vegetable toppings, similarly, is $3(2^4 - 1)$

Thus, the number of pizzas with at least one vegetable and meat topping is $3(2^{10} - 2^6 - 2^4 + 1) = 2835$