Subsets

How many ways can you pick from {a, b, c, d}? Powers of two.

From a set of 4 items {a, b, c, d}, how many ways can you pick a subset (any size, including the empty set and the whole set)?

Try this

number of items in the set, n

number of subsets = 2ⁿ (counting the empty set and the whole set) = 16

Why 2ⁿ?

Build a subset by walking down the list and, for each item, deciding in or out — that's 2 choices per item, n times: 2 × 2 × ... × 2 = 2ⁿ. The all-out choice is the empty set; the all-in choice is the whole set. Every subset is exactly one of those in/out patterns.

Same maths as binary digits: n switches, each on or off, gives 2ⁿ combinations. Subsets, binary numbers, and 'pick which toppings' are all the same counting problem.

Your turn

A pizza shop offers 5 toppings. How many different topping combinations are possible, including 'plain'?

Subsets of an n-element set

2^{n}

Each item is either in or out. Two choices, n times.

Try it

n = 4

2⁴ = 16 subsets. n = 10 gives 1,024. n = 20 gives over a million.

This is the same maths as binary digits. n switches with two states each = 2ⁿ outcomes.