@audrey Thanks a lot!

@RZ923 Cursed child is a play, and it isn't the Non-Existent Book, its another invisible book. Remember when Flourish and Blotts bought all those copies of The Invisible Book of Invisibility? Only for this book, almost all the bookstores in the world bought copies, and they all disappeared!

@The-Blade-Dancer Finding the number of subsets of a set is often affectionately, and perhaps even more clearly, explained, using the mnemonic of "counting the number of pizzas you can make with \(n\) toppings." 🍕 🍕 Does the pizza make this problem easier to understand? Definitely yes!! 🙂

So please don't be alarmed if you see pizza 🍕 , pepperoni, mushrooms 🍄, bell peppers 🌶, or sausage sprinkled throughout this post.

In addition to appearing in counting questions, this sort of problem pops up in number theory questions that ask things like, "How many factors does this number have?" So, it's a very useful and general concept that can be applied to a variety of problems.

I'm going to begin by starting at what seems to be the middle of the problem. Suppose I have a set of toppings: \( \{ \textcolor{red}{a, e, i, o, } \text{ and } \textcolor{red}{u} \}.\) (Maybe it's an exotic pizza restaurant, so its toppings are \(\textcolor{red}{a}\)nchovy 🐟 , \(\text{ } \text{ } \text{ } \textcolor{red}{e}\)ndive, \(\textcolor{red}{i}\)talian sausage, \(\textcolor{red}{o}\)lives, and \(\textcolor{red}{u}\)mami seasoning.)

Choosing a subset of \( \{ \textcolor{red}{a, e, i, o, } \text{ and } \textcolor{red}{u} \}\) is equivalent to composing a pizza using any of the possible toppings, with no toppings being a possible option.

All of the possible pizzas are shown below, with each pizza's toppings listed beneath it.

M3W3-aeiou-pizzas.png

Now let's add a new topping, \(\textcolor{red}{h},\) called "Prof. Loh's Favorite Hot Sauce."

How many new pizzas can we make that we couldn't make before? Well, all we have to do is take one of the previous pizzas (or topping combinations, whichever way you want to think of it), and add our new topping \(\textcolor{red}{h}.\)

Below I've illustrated all of the previous pizzas on the left, and all of the new pizzas on the right. Note that each of the new pizzas now includes "Prof. Loh's Favorite Hot Sauce" splattered indiscriminately all over it.

M3W3-aeiou-pizzas-new-topping.png

You can see that by adding our new topping, \(\textcolor{red}{h},\) we have doubled the number of pizzas that we can make.

Similarly, adding a new element to a set doubles the number of subsets that you can make with all those elements.

🍕 🍕 🍕 🍕 🍕

Okay, now let's go back to the beginning! Let's start with only one topping (only one element).

Our topping menu looks like this: \(\{ \textcolor{red}{a}\}.\) The only topping is \(\textcolor{red}{a}\)nchovy. We can make \(2\) different pizzas: 1.) a pizza with \(\textcolor{red}{a}\)nchovy or 2.) a pizza with nothing. \(\rightarrow \textcolor{red}{2} \text{ possible pizzas } \)

Our topping menu looks like this: \(\{ \textcolor{red}{a, e}\}.\) With our new topping, \(\textcolor{red}{e}\)ndive, we can make twice as many pizzas as we did when there was only one topping. \(\rightarrow \textcolor{red}{2^2} \text{ possible pizzas } \)

Our topping menu looks like this: \(\{ \textcolor{red}{a, e, i}\}.\) We can make twice as many pizzas as we did when there were only two toppings. \(\rightarrow \textcolor{red}{2^3} \text{ possible pizzas } \)

Our topping menu looks like this: \(\{ \textcolor{red}{a, e, i, o}\}.\) We can make twice as many pizzas as we did when there were only three toppings. \(\rightarrow \textcolor{red}{2^4} \text{ possible pizzas } \)

There's a neat pattern! It's that, for \(n\) toppings, we have \(2^n\) possible pizzas that we can make. To use general language, this means that for \(n\) elements in a set, there are \(2^n\) different subsets of those \(n\) elements that we can choose.

Another way to see that the number of subsets of \(n\) things equals \(2^n\) is to imagine that for each element in the set, there is a switch that turns it "on" or "off." There are two choices for each element. Thus the ways to arrange all the \(n\) switches equals \(2^n.\)

$$ \left( 2 \text{ choices for the } 1^{\text{st}} \right) \times \left( 2 \text{ choices for the } 2^{\text{nd}} \right) \times\left( 2 \text{ choices for the } 3^{\text{rd}} \right) \times\left( 2 \text{ choices for the } 4^{\text{th}} \right) \dots $$

You could also visualize the number of choices for each element by drawing a branching tree 🌲 that splits into a new branch level for every new element that there is. Each branch would split into two smaller branches, and thus the number of total ways (paths to an end-branch tip) would be equal to \(2^n.\)

🍕 I hope this helped! Please ask if you would like more diagrams or clarification about any of the ideas mentioned. You can also find more Daily Challenge lessons about subsets of \(n\) things by following the links below.

Module 0 Week 2 Day 8 Challenge Part 1
Module 3 Week 1 Day 2 Challenge Part 2