## Finding the Number of Subsets of a Set

We have looked only at combination problems in which we chose exactly $r$ objects. In some problems, we want to consider choosing every possible number of objects. Consider, for example, a pizza restaurant that offers 5 toppings. Any number of toppings can be ordered. How many different pizzas are possible?

To answer this question, we need to consider pizzas with any number of toppings. There is $C\left(5,0\right)=1$ way to order a pizza with no toppings. There are $C\left(5,1\right)=5$ ways to order a pizza with exactly one topping. If we continue this process, we get

$C\left(5,0\right)+C\left(5,1\right)+C\left(5,2\right)+C\left(5,3\right)+C\left(5,4\right)+C\left(5,5\right)=32$

There are 32 possible pizzas. This result is equal to ${2}^{5}$.

We are presented with a sequence of choices. For each of the $n$ objects we have two choices: include it in the subset or not. So for the whole subset we have made $n$ choices, each with two options. So there are a total of $2\cdot 2\cdot 2\cdot \dots \cdot 2$ possible resulting subsets, all the way from the empty subset, which we obtain when we say “no” each time, to the original set itself, which we obtain when we say “yes” each time.

### A General Note: Formula for the Number of Subsets of a Set

A set containing n distinct objects has ${2}^{n}$ subsets.

### Example 5: Finding the Number of Subsets of a Set

A restaurant offers butter, cheese, chives, and sour cream as toppings for a baked potato. How many different ways are there to order a potato?

### Solution

We are looking for the number of subsets of a set with 4 objects. Substitute $n=4$ into the formula.

$\begin{array}{l}{2}^{n}={2}^{4}\hfill \\ \text{ }=16\hfill \end{array}$

There are 16 possible ways to order a potato.

### Try It 9

A sundae bar at a wedding has 6 toppings to choose from. Any number of toppings can be chosen. How many different sundaes are possible?

Solution