Transcript Day 6 16.1 and 16.2 Fundamental Counting Principle and

16.1 Fundamental Counting
Principle
OBJ:  To find the number of
possible arrangements of objects by
using the Fundamental Counting
Principle
DEF:  Fundamental Counting
Principle
If one choice can be made in a ways and a
second choice can be made in b ways,
then the choices in order can be made in a
x b different ways.
EX:  A truck driver must drive from Miami to
Orlando and then continue on to Lake City.
There are 4 different routes that he can take
from Miami to Orlando and 3 different routes
from Orlando to Lake City.
Miami
A
C
G
T
1
Orlando 7
9
Lake City
Strategy for Problem Solving:
1) Determine the
number of
decisions.
2) Draw a blank (____)
for each.
3) Determine # of
choices for each.
4) Write the number in
the blank.
5) Use the
Fundamental
Counting Principle
1) 2 : Choosing a letter
and a number
2) _____ _____
3) 4 letters, 3_numbers
4)
4__
3__
5) 4 x 3 =
12_ possible routes
A1,A7,A9;C1,C7,C9;
G1,G7,G9;T1,T7,T9
EX:  A park has nine gates—three
on the west side, four on the north
side, and two on the east side.
In how many different
ways can you :
1) enter the park from the
west side and later
leave from the east
side?
2) enter from the north
and later exit from the
north?
3)enter the park and later
leave the park?
2 : Choosing an entrance
and an exit gate
1) 3 x 2 =
west
east
6
2) 4 x 4 =
north north
16
3) 9
x 9 =
enter leave
81
EX:  How many three-digit numbers can
be formed from the 6 digits: 1, 2, 6, 7, 8,
9 if no digit may be repeated in a number
•
3 : Choosing a 100’s, 10’s, and1’s digit
•
4
=
1’s
6 x 5 x
100’s 10’s
120
EX:  How many four-digit numbers can
be formed from the digits 1, 2, 4, 5, 7, 8, 9
if no digit may be
repeated in a number?
4 : Choosing a
1000’s,100’s,10’s,1’s
digit
7 x 6 x 5 x 4 =
1000’s 100’s 10’s 1’s
840
If a digit may be repeated
in a number?
4 : Choosing a
1000’s,100’s,10’s,1’s
digit
7 x 7 x 7 x 7 =
1000’s 100’s 10’s 1’s
2401
EX:  How many three-digit numbers
can be formed from the digits 2, 4, 6, 8, 9
if a digit may be repeated in a number?
• 3 : Choosing a 100’s, 10’s, and1’s digit
•
5 x 5 x 5 =
100’s
10’s
1’s
125
EX:  A manufacturer makes sweaters in 6
different colors. Each sweater is available with
choices of 3 fabrics, 4 kinds of collars, and
with or without buttons.
How many different sweaters does the
manufacturer make?
4:
,
,
,
_
color
fabric
collors with/without
6
x
3 x
4 x
2
=
144
EX:  Find the number of possible
batting orders for the nine starting
players on a baseball team?
• 9 decisions
• 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1_ =
362,880
(Also 9! Called 9 Factorial)
16.2 Conditional Permutations
OBJ:  To find the number of
permutations of objects when
conditions are attached to the
arrangement.
DEF:  Permutation
An arrangement of objects in a definite
order
EX:  How many permutations of all
the letters in the word MONEY end
with either the letter E or the letter y?
Choose the 5th letter, either a E or Y
x ___ x ___ x ___ x 2 =
1st
2nd 3rd 4th
5th
4 x ___ x ___ x ___ x 2 =
1st
2nd 3rd 4th
5th
4 x 3 x 2 x 1 x 2 =
1st
2nd 3rd 4th
5th
48
EX:  How many permutations of all
the letters in PATRON begin with NO?
Choose the 1st two letters as NO
1 x 1 x __ x __ x __ x __ =
1st 2nd 3rd 4th 5th 6th
1 x 1 x 4 x __ x __ x __ =
1st 2nd 3rd 4th 5th 6th
1 x 1 x 4 x 3 x 2 x 1=
1st 2nd 3rd 4th 5th 6th
24
EX:  How many permutations of all the
letters in PATRON begin with either N or O?
Choose the 1st letter, either N or O
2 x
x __ x __ x __ x __ =
1st 2nd 3rd 4th 5th 6th
2 x 5 x
x __ x __ x __ =
1st 2nd 3rd 4th 5th 6th
2 x 5 x 4 x 3 x 2 x 1 =
1st 2nd 3rd 4th 5th 6th
240
NOTE: From the digits
7, 8, 9, you can form 10
odd numbers containing
one or more digits if no
digit may be repeated in
a number.
1digit 7
9
2digit 79 87 89
97
3digit 789 879 897 987
Since the numbers are
odd, there are two
choices for the units
digit, 7 or 9.
In this case, the numbers
may contain one, two, or
three digits.
Since 2+ 4 + 4 =10,
this suggests that an “or”
decision like one or more
digits, involves addition.
There are 2 one-digit numbers,
4 two-digit numbers,
and 4 “3 digit” numbers.
EX:  How many even numbers containing
one or more digits can be formed from 2, 3, 4,
5, 6 if no digit may be repeated in a number?
Note : there are three choices for a units
digit: 2, 4, or 6.
=
X
=
X
X
=
X
X
X
=
X
X
X
X
=
+
+
+
+
=
EX:  How many odd numbers containing one
or more digits can be formed from 1, 2, 3, 4 if
no digit can be repeated in a number?
=
+
X
=
X
X
=
X
X
X
=
+
+
+
=
NOTE: In some situations, the total number
of permutations is the product of two or more
numbers of permutations.
For example, there are 12 permutations of A,
B, X, Y, Z with A, B to the left “and” X, Y, Z to
the right.
ABXYZ
ABXZY
ABYXZ
ABYZX
ABZXY
ABZYX
BAXYZ
BAXZY
BAYXZ
BAYZX
BAZXY
BAZYX
Notice that
(1) A, B can be arranged in 2!, or 2 ways;
(2) X, Y, Z can be arranged in 3!, or 6 ways; and
(3) A, B, X, Y, Z can be arranged in 2! x 3!, or 12 ways.
An “and” decision involves multiplication.
EX:  Four different algebra books and three different
geometry books are to be displayed on a shelf with the
algebra books together and to the left of the geometry
books. How many such arrangements are possible?
___X___ X___X____X____X ____X___
ALG I ALG 2 ALG 3 ALG 4 GEOM I GEOM 2 GEOM 3
4 X___ X___X____X
3 X ____X___
ALG I ALG 2 ALG 3 ALG 4 GEOM I GEOM 2 GEOM 3
4 X 3
X 2X 1 X 3 X 2
X
1 __
ALG I ALG 2 ALG 3 ALG 4 GEOM I GEOM 2 GEOM 3
= 144
EX:  How many permutations of 1, A,
2, B, 3, C, 4 have all the letters together
and to the right of the digits?
___X___ X___X____X____X ____X___
N1 N2 N3 N4 L1 L2 L3
4 X___ X___X____X 3 X ____X___
N1 N2 N3 N4 L1 L2 L3
4 X 3 X 2X 1 X 3 X 2 X 1_
N1 N2 N3 N4 L1 L2 L3
= 144