Transcript Counting

MAT 1000
Mathematics in Today's World
Last Time
We talked about computing probabilities when all of the
outcomes of a random phenomenon are “equally likely”
We also looked at a way to experimentally determine
probabilities using “simulations”
Today
When all outcomes are equally likely, finding probabilities
only requires counting.
We will learn methods to count even when there are more
outcomes then we could write down in a list.
Counting
When the outcomes of a random phenomenon are equally
likely (all have the same probability), then we have the
following formulas:
1
probability of any one outcome =
total number of outcomes
number of outcomes in the event
probability of an event=
total number of outcomes
(Remember that an event is some collection of outcomes.)
Equally likely outcomes
All that these formulas require is counting.
For example, if I want to know the probability of any of the
outcomes from rolling two dice, it’s enough to know that
there are 36. I don’t need to list them all.
This is especially useful when there are too many
outcomes to list.
Formulas for counting
What is the probability of someone guessing a four-digit
PIN (for example for a bank or debit card)?
If we assume that every four-digit PIN is equally likely, then
we can use the formula
1
probability of any one outcome =
total number of outcomes
Here the total number of outcomes is the number of fourdigit PINs. How many are there?
Formulas for counting
Listing them all would be tedious and difficult. Can we still
count them?
Let’s compare this with an easier example.
There are 36 possible outcomes for rolling two dice. We
originally found them by making a list. Can we count them
without the list?
Yes: there are six possible numbers for the first die, and six
for the second, and 6 ⋅ 6 = 36
Formulas for counting
This is an example of what the book calls the “fundamental
principle of counting.”
If there are 𝑎 ways of choosing one thing, 𝑏 ways of
choosing the next, and so on up to 𝑧 ways of choosing the
last, then altogether the number of choices is
𝑎 ⋅ 𝑏 ⋅…⋅𝑧
We have 6 possible outcomes for rolling the first die, and 6
for the second, so there are a total of 6 ⋅ 6 = 36 outcomes.
Formulas for counting
What about a four-digit PIN?
There are 10 choices for the first digit:
0 1 2 3 4 5 6 7 8 9
Likewise we have 10 choices for the second, 10 for the
third, and 10 for the fourth. So the number of four-digit PINs
is
10 ⋅ 10 ⋅ 10 ⋅ 10 = 10,000
Formulas for counting
Then the probability that someone can randomly guess
your PIN is
1
1
=
total number of outcomes 10,000
Formulas for counting
If four-digit PINs are randomly assigned, what is the
probability that you get a PIN with four identical digits?
Since each PIN is equally likely, we can use the formula:
number of outcomes in the event
probability of an event=
total number of outcomes
We already know that there are 10,000 different four-digit
PINs.
We need to know the number of outcomes in our event.
Formulas for counting
In this case the number turns out to be small enough to
count without a formula.
Our “event” is getting a PIN all of whose digits are the
same. For example 1111, or 7777. How many such fourdigit PINs are there?
There are ten.
The digits could all be any one of the ten digits 0, 1, … , 9.
Formulas for counting
Alternately, we can just list all four-digit PINs with all four
digits identical:
0000
1111
2222
3333
4444
5555
6666
7777
8888
9999
So the probability of getting a PIN with four identical digits
is:
number of outcomes in the event
10
1
=
=
total number of outcomes
10,000 1000
Formulas for counting
Here’s a different counting problem: how many four-digit
PINs are there if we are not allowed to repeat digits?
In other words a PIN like 1234 is allowed, but not a PIN like
2452 or 7674, where a digit is repeated.
We already know that the number of such PINs must be
less than 10,000, but how many are there?
We can use the fundamental principle of counting.
Formulas for counting
We are “choosing” four digits. How many choices are there
for the first?
There are 10 choices.
What about the second?
Now, we don’t have 10 choices—we can’t repeat the first
digit.
Suppose the first digit was 7. If we pick 7 for the second
digit, we’ve repeated ourselves. So the second digit can be
any number except 7.
Then how many choice are there?
There are 9 choices—anything except our first digit.
Formulas for counting
So we have 10 choices for the first digit and 9 for the
second. How many choices are there for the third?
We have already picked two digits, and we can’t reuse
either of those. So we only have 8 choices.
We want a four-digit PIN, so we need to pick one more
number. Since it can’t be the same as the first, second, or
third choice we’ve made, we’ve only got 7 options.
Formulas for counting
The fundamental principle tells us that there are
10 ⋅ 9 ⋅ 8 ⋅ 7
ways to pick a four-digit PIN with no repeated digits.
Multiplying out, we see there are 5040 such PINs.
One way of looking at what we’ve done:
We have four “spaces”
___ ___ ___ ___
which we want to “fill,” each with a different number.
Formulas for counting
What’s the probability that if we randomly choose a fourdigit PIN with no repeated digits, then we get the PIN
1234?
Since any PIN is equally likely, the probability of the one
outcome 1234 is
1
probability of any one outcome =
total number of outcomes
This is
1
= 0.002
5040
Counting
What’s the probability that if we randomly choose a fourdigit PIN with no repeated digits, the first digit of our PIN is
1?
What does this mean? We want the first digit to be 1, so
we want a number like 1234 or 1573, but we don’t want
numbers like 3612, where the 1 is not the first digit.
This is an event. So we can use the formula
number of outcomes in the event
probability of an event=
total number of outcomes
Counting
How many outcomes are in the event? In other words, how
many PINs are there where no digits are repeated and the
first digit is 1?
We have to count.
Unlike earlier, we don’t have four spaces to fill.
___ ___ ___ ___
because we know what goes in the first space…
Counting
How many outcomes are in the event? In other words, how
many PINs are there where no digits are repeated and the
first digit is 1?
We have to count.
Unlike earlier, we don’t have four spaces to fill.
_1_ ___ ___ ___
because we know what goes in the first space…
… a 1.
Counting
So we only have three spaces to fill.
How many choices do we have for the first space?
Even though there are 10 digits, remember that the first
digit must be a 1, and we aren’t allowed to repeat. So we
only have 9 choices.
How about for the second digit?
There are 8 choices.
Counting
For the third digit we have 7 choices.
So the number of four-digit PINs with no repeated digits
that start with a 1 is:
9 ⋅ 8 ⋅ 7 = 504
Then the probability that we pick a four-digit PIN with no
repeated digits, and we get a PIN that starts with a 1 is:
504
1
=
5040 10
Counting
The difference between the number of four-digit PINs
10 ⋅ 10 ⋅ 10 ⋅ 10 = 10,000
and four-digit PINs with no repetitions
10 ⋅ 9 ⋅ 8 ⋅ 7 = 5040
is an important difference.
In both cases we are picking four digits out of the 10
possible, but if we aren’t allowed to repeat, we will have
fewer possible four-digit PINs.
Counting
If we are choosing 𝑘 things from of a list 𝑛 possibilities, and
we are allowed to repeat, then there are
𝑛 ⋅ 𝑛 ⋅ … ⋅ 𝑛 = 𝑛𝑘
possible choices.
If we are not allowed to repeat, we have 𝑛 choices for the
first thing, 𝑛 − 1 for the second, 𝑛 − 2 for the third…
and it turns out we will have 𝑛 − 𝑘 + 1 for the last.
As a formula, this is:
𝑛 ⋅ 𝑛 − 1 ⋅ 𝑛 − 2 ⋅ … ⋅ (𝑛 − 𝑘 + 1)
Counting
It’s probably easier not to try and memorize a formula.
Instead, remember it this way: we are picking 𝑘 things, so
we have 𝑘 spaces to fill. There are 𝑛 choices for the first
thing, and then for each subsequent thing, we have one
fewer choice.
An arrangement of 𝑘 things out of 𝑛 possibilities with no
repetitions is called a permutation, which is sometimes
abbreviated:
𝑛𝑃𝑘
Counting
Suppose 10 runners are competing in a race. The winner
gets a gold medal, second place gets a silver medal, and
third place gets a bronze medal. How many different
arrangements of gold, silver, bronze are possible?
Here we are “filling” three “spaces”
______
______
_______
gold
silver
bronze
How many possible gold medal winners are there? 10.
Once we know who wins the gold, we’ve only got 9 choices
for silver, and then 8 for the bronze.
Counting
Notice, this is all we care about. We aren’t interested in
fourth place, fifth place, and so on.
So we have
10 ⋅ 9 ⋅ 8 = 720
possible lists of gold, silver, bronze.
By the way, this is exactly
10𝑃3
Counting
What if we do want to know the rest of the places: who
came in fourth, and fifth, and so on?
Now we are filling all 10 spots. We get 10 choices for first
place, 9 for second, 8 for third, 7 for fourth, and so on.
Once we have picked first place through ninth place, we
only have one runner left for last place. So there are
10 ⋅ 9 ⋅ 8 ⋅ … ⋅ 2 ⋅ 1 = 3,628,800
orderings of all 10 runners
Counting
You may know another name for the number
10 ⋅ 9 ⋅ 8 ⋅ … ⋅ 2 ⋅ 1
This is called “10 factorial,” which is usually abbreviated
with an exclamation mark:
10! = 10 ⋅ 9 ⋅ 8 ⋅ … ⋅ 2 ⋅ 1
It turns out that if we pick 𝑛 things from a list of 𝑛 and don’t
repeat, the number of choices is exactly 𝑛!
In other words: 𝑛𝑃𝑛 = 𝑛!
(This is 𝑛𝑃𝑘 when 𝑘 and 𝑛 are the same. When they are
different the formula for 𝑛𝑃𝑘 is more complicated).
Counting
If I was one of the runners, I might like to try and find the
probability of getting a medal.
This is really three “events”
1. I get the gold medal
2. I get the silver medal
3. I get the bronze medal
These events are disjoint (I can’t win more than one
medal), so to find the probability of any one of these three
events occurring, I can add the probabilities of each.
Counting
Let’s count the number of possible arrangements in which I
am the gold medal winner.
__Me___
gold
______
silver
_______
bronze
There are 9 runners other than me, and we can put any
one of them in the silver medal spot. That leaves 8 choices
for the bronze medal spot.
So there are 72 arrangements in which I am the gold
medal winner
Counting
Likewise there are 72 arrangements in which I win the
silver medal, and 72 in which I win the bronze medal.
So I might like to conclude that the probability of my
winning a medal is:
72
72
72
216
3
+
+
=
=
720 720 720 720 10
But I would be wrong.
Counting
In determining the probabilities of winning a gold, silver, or
bronze medal, I was using the following formula
number of outcomes in the event
probability of an event=
total number of outcomes
This formula only works when all outcomes have the same
probability.
In a race, that’s not the case. If I’m racing against Usain
Bolt, he has a much higher probability of winning than I do.
Summary
We have two formulas, both derived from the fundamental
principle of counting.
For both formulas, we are choosing 𝑘 things out of a list of
𝑛
1. If we are allowed to repeat, then we have 𝑛𝑘 ways to
choose our 𝑘 things.
Note that because we can repeat, we can have 𝑘 as large
as we like.
Summary
Example
Computers represent data with 1s and 0s. A single digit (1
or 0) is called a bit. A byte is 8 bits. How many possible
different bytes are there?
We are choosing 8 things from a list of 2, and repetitions
are allowed. So there are
28 = 256
different possible bytes.
Summary
Example
Computers represent data with 1s and 0s. A single digit (1
or 0) is called a bit. A byte is 8 bits. How many possible
different bytes are there?
We are choosing 8 things from a list of 2, and repetitions
are allowed. So there are
28 = 256
different possible bytes.
Summary
If we are choosing 𝑘 things out of a list of 𝑛, we are not
allowed to repeat, and the order in which we choose
matters, then there are 𝑛𝑃𝑘 ways of choosing.
Note that because we can’t repeat, the number of things
we choose (𝑘) can’t be larger than the number of things to
choose from (𝑛).