In this segment we introduce a simple but powerful tool, the
basic counting principle, which we will be using over
and over to deal with counting problems.
Let me describe the idea through a simple example.
You wake up in the morning and you find that you have in your
closet 4 shirts, 3 ties, and 2 jackets.
In how many different ways can you get dressed today?
To answer this question, let us think of the process of
getting dressed as consisting of three steps, three stages.
You first choose a shirt, let's say this one, and you
have 4 choices of shirts.
But each shirt can be used together with 1 of the 3
available ties to make 3 different shirt-tie
combinations.
But since we had 4 choices for the shirt, this means that we
have 4 times 3, equals 12, shirt-tie combinations.
Finally, you choose a jacket.
Each shirt-tie combination can go together with either
jacket, and so the fact that you have 2 jackets available
doubles the number of options that you have, leading to 24
different options overall.
So 24 is the answer to this simple problem.
And how did the number 24 come about?
Well, 24 is the same as the number of options you had in
the first stage times the number of options you had in
the second stage times the number of options you had in
the third stage.
Let us generalize.
Suppose we want to construct some kind of object, and we're
going to construct it through a sequential process, through
a sequence of r different stages.
In the example that we just considered, the number of
stages was equal to 3.
At each one of the stages, you have a number of options that
are available.
So in our example, at the first stage we had 4 options,
at the second stage we had 3 options, and at the last stage
we had 2 options.
What is important is that when you reach stage i, no matter
what you chose, no matter what you did at the previous
stages, the number of options that you will have available
at stage i is going to be that fixed number, n-sub-i.
So what is the answer?
How many different objects can you construct this way?
Well, just generalizing from what we did in our specific
example, the answer is the product of the number of
choices or options that you had at each stage.
This is the counting principle.
It's a very simple idea, but it is powerful.
It will allow us to solve fairly
complicated counting problems.
However, before we go into more complicated problems, let
us first deal with a few relatively easy examples.
In our first example, let us consider license plates that
consist of 2 letters followed by 3 digits.
The question is, how many different
license plates are there?
We think of the process of constructing a license plate
as a sequential process.
At the first stage we choose a letter, and we have 26 choices
for the first letter.
Then we need to choose the second letter, and we have 26
choices for that one.
Then we choose the first digit.
We have 10 choices for it.
We choose the second digit, for which we have 10 choices.
And finally, we choose the last digit, for which we also
have 10 choices.
So if you multiply these numbers, you can find the
number of different license plates that you can make with
2 letters followed by 3 digits.
Now let us change the problem a little bit and require that
no letter and no digit can be used more than once.
So, let us think of a process by which we could construct
license plates of this kind.
In the first stage, we choose the first letter that goes to
the license plate, and we have 26 choices.
Now, let us go into a second stage where we choose the
second letter.
Because we used 1 letter in the first stage, this means
that there's only 25 available letters that can be used.
We only have 25 choices at the second stage.
Now, let us start dealing with the digits.
We choose the first digit, and we have 10 choices for it.
However, when we go and choose the next digit we will only
have 9 choices, because 1 of the digits has
already been used.
At this point, 2 digits have been used, which means that at
the last stage we have only 8 digits to choose from.
So by multiplying these numbers, we can find out the
answer to this question, the number of license plates if
repetition is prohibited.
Let us now consider a different example.
Suppose that we start with a set that
consists of n elements.
What we want to do is to take these n
elements and order them.
A terminology that's often used here is that we want to
form a permutation of these n elements.
One way of visualizing permutations is to say that
we're going to take these elements of the set, which are
unordered, and we're going to place them
in a sequence slots.
So we create n slots.
And we want to put each one of these elements into one of
these slots.
How do we go about it?
We think of putting the elements into slots,
one slot at a time.
We first consider the first slot.
We pick one of the elements and put it there.
How many choices do we have at this stage?
We have n choices, because we can pick any of the available
elements and place it in that slot.
Next, we pick another element and put it
inside the second slot.
How many choices do we have at this step?
Well, we have already used one of the available elements,
which means that there's n minus 1 elements to choose
from at the next stage.
At this point, we have used 2 of the elements.
There is n minus 2 that are left.
We pick one of them and put it in the third slot, and we have
n minus 2 choices at this point.
We continue this way.
We keep going on.
At some point we have placed n minus 1 of the
elements into slots.
There's only one element left, and that element, necessarily,
will get into the last slot.
There are no choices to be made at this point.
So the overall number of ways that we can carry out this
process, put the elements into the n slots, by the counting
principle is going to be the product of the number of
choices that we had at each one of the stages.
So it's the product of the numbers n, n minus 1, n minus
2, all the way down to 1.
And this product we denote as a shorthand this way, which we
read as n factorial.
n factorial is the product of all integers from 1 all the
way up to n.
And in particular, the number of permutations of n elements
is equal to n factorial.
Let us now consider another example.
We start again with a general set, which
consists of n elements.
And we're interested in constructing a
subset of that set.
In how many different ways can we do that?
How many different subsets are there?
Let us think of a sequential process through which we can
choose the subset.
The sequential process proceeds by considering each
one of the elements of our set, one at a time.
We first consider the first element, and
here we have 2 choices.
Do we put it inside the set or not?
So 2 choices for the first element.
Then we consider the second element.
Again, we have 2 choices.
Do we put it in the subset or not?
We continue this way until we consider all the elements.
There's n of them.
And the overall number of choices that we have is the
product of 2 times 2 times 2, n times, which is 2
to the power n.
At this point, we can also do a sanity check to make sure
that our answer is correct.
Let us consider the simple and special case where n is equal
to 1, which means we're starting with this set with 1
element, and we want to find the number of
subsets that it has.
According to the answer that we derived, this should have 2
to the first, that is 2 subsets.
Which ones are they?
One subset of this set is the set itself and the other
subset is the empty set.
So we do have, indeed, 2 subsets out of that set, which
agrees with the answer that we found.
Notice that when we count subsets of a given set, we
count both the set itself, the whole set, and we also count
the empty set.
All of these are subsets of our set.
At this point, we can now pause and you can try to
answer some simple questions of the same kind as the ones
that we just practiced.