Transcript Introduction to Counting

Introduction to Counting
Introduction to Counting
Why a lesson on counting?
I’ve been doing that since
I was a young child!
Introduction to Counting
Good question!
Actually we’ll be looking at
situations more complex than
simply counting 1, 2, 3, …
Introduction to Counting
Counting in our context refers to
figuring out in how many ways
we can group or arrange things.
Click here to see a scenario
where we could apply counting.
(You might wish to right-click on the
link and open the file in a new window.)
Counting Example
A school club is putting on a festival to
raise money. The club is considering
several games which would involve
wagering money, and the treasurer needs
to determine which games would be likely
to generate revenue for the club.
Counting Example
Game 1
A player pays $1 and flips three coins.
If the coins all match (either all heads
or all tails), the player wins $3.
Counting Example
Game 2
A player pays $1 and rolls a pair of dice.
The player wins $5 if the dice come up
doubles (both dice are the same number).
Counting Example
Game 3
A player places $1 on each of two
numbers on a board that has the numbers
1-9. The player then picks two tokens out
of a bag which contains nine tokens, also
numbered 1-9. The player wins $1 for
matching one number, and $10 for
matching both numbers.
Counting Example
Which game do you think
would be best for the club?
Which game would you prefer to play?
Counting Example
In order to select which game to
offer, the treasurer might want
to consider the probability of a
customer winning each game.
Counting Example
Calculating the probability of winning
requires determining the possible
number of outcomes for each game.
We need to know the ratio
Number of Winning Outcomes
Number of Possible Outcomes
Counting Example
One way to calculate the possible
number of outcomes is by
constructing a tree diagram.
Counting Example
Game 1: Flipping Three Coins
Each coin has two possible outcomes: Heads or Tails
Counting Example
Game 1: Flipping Three Coins
Each coin has two possible outcomes: Heads or Tails
1st Coin:
H
T
Counting Example
Game 1: Flipping Three Coins
Each coin has two possible outcomes: Heads or Tails
1st Coin:
2nd Coin:
H
H
T
T
H
T
Counting Example
Game 1: Flipping Three Coins
Each coin has two possible outcomes: Heads or Tails
1st Coin:
H
2nd Coin:
3rd Coin:
H
H
T
T
T
H
H
T
H
T
T
H
T
Counting Example
Game 1: Flipping Three Coins
Follow the branches downward to see the possible outcomes.
1st Coin:
H
2nd Coin:
3rd Coin:
H
H
T
T
T
H
H
T
H
T
T
H
T
Counting Example
Game 1: Flipping Three Coins
For instance, a player could flip Heads and two Tails.
1st Coin:
H
2nd Coin:
3rd Coin:
H
H
T
T
T
H
H
T
H
T
T
H
T
Counting Example
Game 1: Flipping Three Coins
To determine the total possible number of outcomes, look at the
bottom row of the tree. There are 8 possible outcomes.
1st Coin:
H
2nd Coin:
3rd Coin:
H
H
T
T
T
H
H
T
H
T
T
H
T
Counting Example
Game 1: Flipping Three Coins
Only 2 outcomes give us matching coins: all Heads, or all Tails.
1st Coin:
H
2nd Coin:
3rd Coin:
H
H
T
T
T
H
H
T
H
T
T
H
T
Counting Example
Game 1: Flipping Three Coins
The ratio of winning outcomes to total outcomes is then 2/8, or 1/4.
1st Coin:
H
2nd Coin:
3rd Coin:
H
H
T
T
T
H
H
T
H
T
T
H
T
Counting Example
Game 1: Flipping Three Coins
In other words, we would expect a player to win ¼ of the time.
1st Coin:
H
2nd Coin:
3rd Coin:
H
H
T
T
T
H
H
T
H
T
T
H
T
Counting Example
Game 2: Rolling Two Dice
Making a tree diagram was relatively simple
for the first game, because it only involved a
total of eight possible outcomes.
Counting Example
Game 2: Rolling Two Dice
Rolling dice, however, involves six possible
outcomes per die, meaning six branches per die.
Counting Example
Game 2: Rolling Two Dice
Rolling dice, however, involves six possible
outcomes per die, meaning six branches per die.
1
2
3
4
5
6
This only represents the first die. To represent
the second die, we would need to connect six
branches to each of the current six branches.
Counting Example
Game 2: Rolling Two Dice
Rolling dice, however, involves six possible
outcomes per die, meaning six branches per die.
1
2
3
4
5
This quickly becomes impractical,
on paper or on a computer.
6
Counting Example
Game 2: Rolling Two Dice
Another approach is to use a table, with the
columns representing one die, and the rows
representing the other die. (To distinguish the two
dice, we’ll have one red die and one green die.)
Counting Example
Game 2: Rolling Two Dice
This table shows the possible outcomes.
Green Die
R
e
d
1
2
3
4
5
6
1
1,1
2,1
3,1
4,1
5,1
6,1
2
1,2
2,2
3,2
4,2
5,2
6,2
3
1,3
2,3
3,3
4,3
5,3
6,3
4
1,4
2,4
3,4
4,4
5,4
6,4
5
1,5
2,5
3,5
4,5
5,5
6,5
6
1,6
2,6
3,6
4,6
5,6
6,6
Counting Example
Game 2: Rolling Two Dice
There are 36 possible outcomes.
Green Die
R
e
d
1
2
3
4
5
6
1
1,1
2,1
3,1
4,1
5,1
6,1
2
1,2
2,2
3,2
4,2
5,2
6,2
3
1,3
2,3
3,3
4,3
5,3
6,3
4
1,4
2,4
3,4
4,4
5,4
6,4
5
1,5
2,5
3,5
4,5
5,5
6,5
6
1,6
2,6
3,6
4,6
5,6
6,6
Counting Example
Game 2: Rolling Two Dice
There are 6 winning outcomes.
Green Die
R
e
d
1
2
3
4
5
6
1
1,1
2,1
3,1
4,1
5,1
6,1
2
1,2
2,2
3,2
4,2
5,2
6,2
3
1,3
2,3
3,3
4,3
5,3
6,3
4
1,4
2,4
3,4
4,4
5,4
6,4
5
1,5
2,5
3,5
4,5
5,5
6,5
6
1,6
2,6
3,6
4,6
5,6
6,6
Counting Example
Game 2: Rolling Two Dice
The ratio of winning outcomes to possible outcomes is 6/36,
or 1/6. We expect a player to win 1/6 of the time.
Green Die
R
e
d
1
2
3
4
5
6
1
1,1
2,1
3,1
4,1
5,1
6,1
2
1,2
2,2
3,2
4,2
5,2
6,2
3
1,3
2,3
3,3
4,3
5,3
6,3
4
1,4
2,4
3,4
4,4
5,4
6,4
5
1,5
2,5
3,5
4,5
5,5
6,5
6
1,6
2,6
3,6
4,6
5,6
6,6
Counting Example
Game 3: Picking Two Numbers, 1-9
We could also use a table for this example.
1
2
3
4
5
6
7
8
9
1
1,1
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2
2,1
2,2
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3
3,1
3,2
3,3
3,4
3,5
3,6
3,7
3,8
3,9
4
4,1
4,2
4,3
4,4
4,5
4,6
4,7
4,8
4,9
5
5,1
5,2
5,3
5,4
5,5
5,6
5,7
5,8
5,9
6
6,1
6,2
6,3
6,4
6,5
6,6
6,7
6,8
6,9
7
7,1
7,2
7,3
7,4
7,5
7,6
7,7
7,8
7,9
8
8,1
8,2
8,3
8,4
8,5
8,6
8,7
8,8
8,9
9
9,1
9,2
9,3
9,4
9,5
9,6
9,7
9,8
9,9
Counting Example
Game 3: Picking Two Numbers, 1-9
At first, it may appear there are 81 possible outcomes.
But notice that this includes some impossible outcomes.
I.e., we cannot end up with two of the same number.
1
2
3
4
5
6
7
8
9
1
1,1
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2
2,1
2,2
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3
3,1
3,2
3,3
3,4
3,5
3,6
3,7
3,8
3,9
4
4,1
4,2
4,3
4,4
4,5
4,6
4,7
4,8
4,9
5
5,1
5,2
5,3
5,4
5,5
5,6
5,7
5,8
5,9
6
6,1
6,2
6,3
6,4
6,5
6,6
6,7
6,8
6,9
7
7,1
7,2
7,3
7,4
7,5
7,6
7,7
7,8
7,9
8
8,1
8,2
8,3
8,4
8,5
8,6
8,7
8,8
8,9
9
9,1
9,2
9,3
9,4
9,5
9,6
9,7
9,8
9,9
Counting Example
Game 3: Picking Two Numbers, 1-9
We have also included some duplications. For example,
drawing 2 and then 3 is the same as drawing 3 and then
2; we’re only interested in the pairing, not the order.
1
2
3
4
5
6
7
8
9
1
-
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2
2,1
-
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3
3,1
3,2
-
3,4
3,5
3,6
3,7
3,8
3,9
4
4,1
4,2
4,3
-
4,5
4,6
4,7
4,8
4,9
5
5,1
5,2
5,3
5,4
-
5,6
5,7
5,8
5,9
6
6,1
6,2
6,3
6,4
6,5
-
6,7
6,8
6,9
7
7,1
7,2
7,3
7,4
7,5
7,6
-
7,8
7,9
8
8,1
8,2
8,3
8,4
8,5
8,6
8,7
-
8,9
9
9,1
9,2
9,3
9,4
9,5
9,6
9,7
9,8
-
Counting Example
Game 3: Picking Two Numbers, 1-9
In reality, then, we have 36 possible outcomes.
1
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3,4
3,5
3,6
3,7
3,8
3,9
4,5
4,6
4,7
4,8
4,9
5,6
5,7
5,8
5,9
6,7
6,8
6,9
7,8
7,9
8,9
Counting Example
Game 3: Picking Two Numbers, 1-9
Say a player chooses 1 and 2. We need to know the
number of pairs that contain either 1 or 2, but not both.
1
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3,4
3,5
3,6
3,7
3,8
3,9
4,5
4,6
4,7
4,8
4,9
5,6
5,7
5,8
5,9
6,7
6,8
6,9
7,8
7,9
8,9
Counting Example
Game 3: Picking Two Numbers, 1-9
There are 14 winning combinations for matching 1
number. We expect that 14/36, or 7/18 of the time, a
player will win $1.
1
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3,4
3,5
3,6
3,7
3,8
3,9
4,5
4,6
4,7
4,8
4,9
5,6
5,7
5,8
5,9
6,7
6,8
6,9
7,8
7,9
8,9
Counting Example
Game 3: Picking Two Numbers, 1-9
There is only 1 pairing that will match the player’s
pairing, so we expect that 1/36 of the time the player will
win $10.
1
1
2
3
4
5
6
7
8
9
2
3
4
5
6
7
8
9
1,2
1,3
1,4
1,5
1,6
1,7
1,8
1,9
2,3
2,4
2,5
2,6
2,7
2,8
2,9
3,4
3,5
3,6
3,7
3,8
3,9
4,5
4,6
4,7
4,8
4,9
5,6
5,7
5,8
5,9
6,7
6,8
6,9
7,8
7,9
8,9
Counting Techniques
So far, we have looked at two different
techniques for counting possibilities:
tree diagrams and tables.
For more complicated problems, however, we
have another powerful tool:
The Multiplication Principle
The Multiplication Principle
People have stated the Multiplication Principle
in a number of ways. Here’s one way to say it:
Consider the number of options available every
time you make a choice or conduct a trial.
Multiply those numbers together to determine
the total possible number of outcomes.
The Multiplication Principle
Game 1: Flipping Three Coins
Each coin has a possibility of two outcomes:
Heads or Tails. Because we are flipping three
coins, multiply three 2s together.
2*2*2 = 8 possible outcomes
The Multiplication Principle
Game 3: Picking Two Numbers
This is a more common application of the
multiplication principle, where we have no
repetition—we cannot have the same number
twice.
The Multiplication Principle
Game 3: Picking Two Numbers
For picking the first number, we have 9 options:
the numbers 1-9.
For picking the second number, we have 8
options: the numbers 1-9, except the number
we picked first.
The Multiplication Principle
Game 3: Picking Two Numbers
9*8 = 72 possible outcomes
Recall, though, that we have duplications.
Every pair of numbers has been counted twice.
For example, 1,3 is the same as 3,1.
As a result, we need to divide by 2 to get the
true number of possible outcomes.
The Multiplication Principle
Game 3: Picking Two Numbers
(9*8) / 2 = 36 possible outcomes
The Multiplication Principle
When using the multiplication principle, and
when doing counting problems in general, it is
vital to determine whether order matters.
If order does not matter, then the multiplication
principle will usually give an answer that
overcounts, and you will need to modify it.
We’ll see more examples of
that later in the unit.
Sample Problems
1. One club member has suggested changing
the first game by having players flip 4 coins.
How many outcomes are possible for this
version of the game? (The coins are
unique, or we are keeping track of the order
in which they are flipped.)
Sample Problems
1. One club member has suggested changing
the first game by having players flip 4 coins.
How many outcomes are possible for this
version of the game? (The coins are
unique, or we are keeping track of the order
in which they are flipped.)
Each coin has 2 possible outcomes (Heads
or Tails) so the total possible number of
outcomes is
2*2*2*2 = 16 possible outcomes
Sample Problems
2. One club member wants to make the third
game more challenging by using 12 numbers
instead of only 9. How many outcomes are
possible when selecting 2 numbers out of 12?
Sample Problems
2. One club member wants to make the third
game more challenging by using 12 numbers
instead of only 9. How many outcomes are
possible when selecting 2 numbers out of 12?
There are 12 options for the first number, and
then 11 options for the second number. The
order does not matter, though, so we are
counting each pair twice and must divide by
2:
(12*11) / 2 = 66 possible outcomes
Sample Problems
3. Click here to look again at the Whopper
problem. How many different ways can one
order a Whopper?
(You might wish to right-click on the link and
open the file in a new window.)
Credits
Background designs are the property of
Geetesh Bajaj. Used with permission. ©
Copyright, Geetesh Bajaj. All Rights
Reserved.