What's a set? A set is just a collection of items... in the case above it's a mini steam engine, a mango and a padlock...
And what's a subset? It's just a collection of some or even all or none of those items... here the mini steam engine is missing...
How many subsets can you make from a given set? For example, how many subsets can you make if your set has 3 items? To get a feeling for this, let's start with simpler cases...
case 1: how many subsets if your set has 1 item? Let's start with just the rightmost item.. we see we have 1 subset with the item and 1 subset without it... so 2 subsets total
case 2: how many subsets if your set has 2 items? Well, we have our original 2 subsets with the rightmost item, with our new item present, and then those same 2 subsets with the new item missing... so 4 subsets total:
case 3: how many subsets if your set has 3 items... the same pattern holds... all the previous subsets with the new item and also without the new item, so 8 subsets total
This is the same pattern we saw with bits in a binary number when we were discussing r, g, b pixel values. Since every new item doubles the number of subsets, the total number of subsets of a set of n items is 2^n. The set of all subsets is called the "Power Set", so the size of the Power Set is 2^n... and as we saw with the grains of rice on the chess board, as n grows, 2^n becomes a very large number indeed.
Kommentare