Transcript Basic counting principles, day 1

Basic counting principles,
day 1
To decide how many ways something can
occur, you can draw a tree diagram.
Note that this only
shows half of the
tree – the automatic
transmission



Possible choices =
choices
2
* 3 * 4 = 24
transmission * music * color
Basic counting principle: If an event can
occur in p ways, and another event in q
ways, then there are p * q ways both
events can occur.
From now on we will use multiplication
and “fill the slots” as follows.
How many different batting orders are there in a 9person softball team? Fill the slots for each
position
1st
batter
2nd
batter
3rd
batter
4th
batter
5th
batter
6th
batter
7th
batter
8th
batter
9th
batter
9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1= 9!
1st
batter
2nd
batter
3rd
batter
4th
batter
9 ways
to
choose
first
batter
8 ways
left,
once
1st
batter
chosen
7 ways
now to
chose
3rd
Etc.
5
batter
6th
batter
7th
batter
8th
batter
9th
batter
batter
9! = 362,880 ways to write the batting order.
How many 7 digit phone numbers are there if
the first digit cannot be 0 or 1?
____*____*___* ____*____*____*____
8
#
choices
for first
digit
*
10
*
# choices
for
second
digit
10
* 10 * 10 * 10 * 10
# choices for all other digits will be the same
8,000,000 ways
How many 7-digit phone numbers begin with
867?
____*____ *____*____*____*____*____
1
one
choice
* 1 * 1
one
choice
one
choice
* 10 * 10 * 10 * 10
these four digits can
be 0-9 (10 choices)
10,000 different phone numbers
Using letters from the word “MATRIX”
How many 4-letter patterns can be formed?
# ways to fill slots:
_____ * _____ * _____ * _____
# ways to fill slots:
6 * 5 * 4 * 3 = 360
6 letters
to
choose
from
5
letters
left . .
etc.
Still using letters from the word
“MATRIX”, what if the first letter
must be a vowel?
_____ * _____ * _____ * _____
# ways to fill slots:
2 * 5 * 4 * 3 = 120
2
vowels
to
choose
from
5
letters
left . .
etc.
What if we fill only 4 slots and
the first and last letters must
be consonants?
______ * ______ * ______ * ______
# ways to fill slots:
fill these two first
4 * 4 * 3 * 3 = 144
4 consonents to
choose
from
4
letters
left . .
fill less important
slots last
3
letters
left . .
3
consonents
left to
choose
from
How many 3-digit palindromes
are possible? Note that a number
does not usually begin with a zero . . .
______ * ______ * ______
9 * 10 * 1 = 90
Can’t
begin
with a
zero
and
be 3digit
fill first
can
be
any
digit
must
be the
same
as the
first
digit
(one
way to
fill)
then fill the last one
fill second
In a 5-card poker hand, the 1st 3 cards were
red face cards, the last 2 were black nonface cards. How many ways can this
happen?
5 slots to fill:
_____ * ____ * _____ * _____* _____
6 * 5 * 4 * 20 * 19 = 45,600 ways
first 3 cards
choices:
K, Q, J hearts
or diamonds;
1st slot, 2nd slot,
3rd slot
A – 10 and
black: 20
cards; 1st
slot, 2nd slot
(of that type)
Mutually Exclusive events




To get to school, Rita can either walk or ride the
bus. If she walks, she can take 3 routes, if she
rides the bus, there are 2 routes. Rita’s choices
are mutually exclusive - she can’t do both,
therefore, the possibilities are added to each
other.
3 ways to walk
2 ways to take a bus
total possible routes: 3 + 2 = 5
How many odd numbers between 10 and 1000
start and end with the same digit?
We have two mutually exclusive events:
___ * ___ two digit choices
+
___ * ___ * ___ three digit choices
two digit choices: just count multiples of 11
that are odd: (11, 33, 55, 77, 99) 5 choices
three digit choices: calculate like our
palindrome problem (3 slots to fill)
1 * 10 * 5 50 choices
total = 50 + 5 = 55 odd numbers between
10 and 1000 that have the same first and
last digit.
An example that is not mutually exclusive…
(each time you have the same number of
choices)
An ID label has 4 letters. How many
different labels are possible?
____ * _____ * _____ * _____


From before, we know it is
26* 26 * 26 *26
= 264 = 456,976
You can also look at it like:
264 where
26 (base) = number of different choices
4 (exponent) = number of times you make
that choice
On a multiple choice test with 15
questions and 4 answer choices per
question, how many answer
combinations are there?
415=1,073,741,824!!!!
4 = number of different choices
15 = number of times you make that choice






How many license plates of 2 symbols
(letters and digits) can be made using at
least one letter in each?
cases:
one letter:
L D or D L
2(26*10)
two letters:
LL
262
total: 2(26*10) + 262 = 1196 license
plates
How many ways can you make a 3 symbol
license plate using at least one letter?
What are the cases?







Cases if the license plate has at least one
letter:
one letter:
LDD or DLD or DDL
two letters:
L L D or L D L or D L L
three letters:
LLL
3(26*102)
+
3(262*10)
+
263
Permutations

A permutation is an ordered arrangement:
ORDER MATTERS (KAT is different than
TAK). Our batting order problem and use
of the letters of matrix have been
permutations.
How many ways can letters in SPRING be
arranged?
6 * 5 * 4 * 3 * 2 * 1 = 6! =
720 ways to arrange the 6 letters when
order matters.
In general, there are n! permutations of n
objects.
What if we want to use the letters in
SPRING, but only want to know how many
2 letter arrangements can be made?
Using the “filling the slots” idea, we have
6 * 5 = 30 ways to fill two slots with
6 letter choices.
Another way to look at it is similar to
what we did for Pascal’s triangle:
6 * 5 * 4 * 3 * 2 *1
4 * 3 * 2 *1
6!

 6 P2
(6  2)!
In general, the number of permutations of
n objects taken r at a time is:
n!
 n Pr
(n  r )!
From 1000 contest entries, how many ways
can 1st, 2nd, and 3rd place prizes be
awarded? Does order matter?
We can fill in the slots:
_____ * _____ * _____
Or use our formula:
1000!
 997,002,000 ways
1000 P3 
(1000 3)!
How does it change if the values
are not all unique?
How many 6-letter permutations of ACOSTA
are there?
note: there are two A’s that will not be
distinguishable from each other in a word.
A1A2COST = A2A1COST
the number of permutations will be cut in
half.
P
6
!
720
6 6


 360
2
(6  6)! 2
2
Is the bottom just “2” because there
are 2 A’s? What if there were more?
Consider using the letters of
PARABOLA:
Consider PARABOLA
the number of arrangements of the 3 A’s that will be
equivalent are:
A1A2A3PRBOL
A1A3A2PRBOL
A2A1A3PRBOL
A2A3A1PRBOL
A3A1A2PRBOL
A3A2A1PRBOL
This shows that 3! arrangements would be identical (the
number of ways you can arrange 3 objects in different
order). Thus, we need to divide by 3!, not just 3.
This generalizes to objects that have
more than one duplicate. If all objects
are used, the number of permutations
of n objects of which p and q represent
the number of items that are alike is:
n!
p!q!
How many permutations of the letters
in the word POSSIBILITY using only
5 letters are there?
n!
11!

 4620
(n  r )! p!q! (11 5)!2! 3!
where the denominator represents
the 2 S’s and the 3 I’s.
That’s all folks
Have a counting, permutable kind of day
