Welcome to a lesson,
how to determine the number of subsets of a given set
as well as how to determine the number of subsets of a set
with a certain cardinality or certain number of elements.
Let's begin by considering set A
with elements 1, 2, 3, 4, and 5.
The question is how many subsets of A are there?
For review, the power set of A
is equal to the set containing all of the subsets of set A,
and therefore the cardinality of the power set of A
is equal to the number of subsets of set A.
So, for example, if set A is the set with elements 1 and 2,
the cardinality of the power set of A is equal to 4
because the set has a total of four subsets,
which we should recall the four subsets are the empty set,
the set with the element of 1,
the set with the element of 2, and set A itself.
If set A has elements 1, 2, and 3,
then the cardinality of the power set of A is equal to 8
because set A has a total of eight subsets.
But, again, our question is how many subsets are there
when set A is the set with elements 1, 2, 3, 4, and 5,
and what is the cardinality of the power set of A?
Think about how we would build a subset.
For each of the elements in A,
decide whether or not to include the element in the subset.
We need to decide yes or no for the first element,
yes or no for the second element,
yes or no for the third element, and so on.
For each of the five elements, we have two choices,
and therefore the number of subsets
is two times two times two times two times two,
or two to the fifth, which is equal to 32.
This is due to the multiplicative principle
or counting principle.
So we can generalize and say,
"The cardinality of the power set of A
is equal to two to the power of n
where n is the number of elements in set A."
And now of the 32 subsets of set A,
how many have three elements?
We might be thinking
that the multiplicative principle indicates
that there are a total of five times four times three
or 60 ways to select three-element subsets,
but this isn't quite right
because, notice, 60 is greater than 32
and we know we have a total of 32 subsets.
This isn't correct
because five times four times three equals 60
indicates that the order of the elements matter,
but we know the order of the elements
does not change the set.
For example, notice these two sets
with the elements of 2, 4, and 5 are the same set,
but in the calculation of five times four times three,
which gives us 60,
this would be counted as different.
However, we can correct this by dividing.
For each set of three elements,
there are three times two times one or six ways
to arrange the three elements
which are counted as different in the 60 ways,
and therefore we can determine the number of unique subsets
by taking 60 and dividing by six
which gives us 10 subsets with exactly three elements.
Before we'd look at an easier way to determine
the number of subsets
with a certain number of elements or certain cardinality,
let's look at a table.
Let's complete the table below where on the first row,
we have the number of elements in the subset,
and then the second row, we have the number of subsets.
For example, how many subsets of set A have zero elements?
That would just be one set, the empty set.
And we can also easily determine
the number of subsets with five elements
which should be set A itself
and if there's only one subset with five elements.
And now let's go back to the number of subsets
with one element.
Well, because there are five elements,
there would be five subsets with one element.
If we think about this for a moment,
the number of subsets with four elements
is going to be the same
as the number of subsets with one element.
Every time we form a subset with one of the five elements,
we leave behind four elements
that would form a subset with four elements,
and therefore there's also five subsets with four elements.
This also indicates
that the number of subsets with two elements
and the number of subsets with three elements
is going to be the same,
and, again, that should make sense.
If we take two of the five elements
to form a subset with two elements,
the three elements left behind
would form a subset with three elements.
So notice so far we've counted six plus six or 12 subsets.
Because we know we have a total of 32 subsets,
32 minus 12 is 20,
20 divided by two is 10,
which leaves us 10 subsets with two elements
and 10 subsets with three elements.
But there is a much easier way to determine
the number of subsets with a certain number of elements
or certain cardinality using combinations.
A combination of objects is used when order doesn't matter.
The number of subsets of a set of size n
each with cardinality k is equal to n choose k,
indicated by any of these three notations here.
So, again, n is the number of elements in the original set,
and k is the cardinality or size of the subset.
And we define n choose k, or n-items chosen k to time,
as n factorial,
divided by the product of n minus k factorial
and k factorial.
Let's verify the formula by verifying
that for set A, there are 10 subsets with two elements.
Because set A has five elements
and we're trying to determine
the number of subsets with two elements,
we need to calculate five choose two,
which means n is equal to five and k is equal to two.
Applying the formula,
we have n factorial which is five factorial
divided by the product of n
minus k factorial and k factorial
which is five minus two factorial and two factorial.
Simplifying, we have five factorial
divided by the product of three factorial and two factorial.
Now we'll go and expand the factorials.
Five factorial is five times four
times three times two times one,
three factorial is three times two times one,
and two factorial is two times one.
Now we'll go and simplify.
Three divided by three simplifies to one.
Notice in the denominator,
we have two times two which is four.
Two times two simplifies to one in the denominator,
and four in the numerator simplifies to one.
Notice how this does leave us with five times two, or 10,
which is what we expected from the table.
Set A has 10 subsets with cardinality two
or 10 subsets with two elements.
Before we go, I do want to mention
most calculators do have a combination function.
For example, here is the Desmos Scientific Calculator.
If we click functions
and then nCr is the combination function,
and then we go back to the main keyboard
and simply enter five comma two for five choose two,
and the combination is calculated
which does verify the result as 10.
I hope you found this helpful.