Finding the Number of Subsets of a Set
We have looked only at combination problems in which we chose exactly objects. In some problems, we want to consider choosing every possible number of objects.
A pizza restaurant that offers [latex]5[/latex] 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 [latex]C\left(5,0\right)=1[/latex] way to order a pizza with no toppings.
- There are [latex]C\left(5,1\right)=5[/latex] ways to order a pizza with exactly one topping.
- If we continue this process, we get:
[latex]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[/latex]
There are [latex]32[/latex] possible pizzas.
This result [latex]32[/latex] is equal to [latex]{2}^{5}[/latex] possible pizzas, which offers [latex]5[/latex] toppings. Coincidence? Definitely not!
formula for the number of subsets of a set
A set containing [latex]n[/latex] distinct objects has [latex]{2}^{n}[/latex] subsets.