Transcript Unit #6 Slide Show

Unit #6 Permutations and Combinations
6.1 Fundamental Counting Principle
The fundamental counting principal is a mathematical method of finding the
number of ways an outcome can be performed.
Bert Church High School has 7 doors to enter/exit the building. How many
ways can a student enter, then exit the building if they do not use the same
door twice?
Enter
Exit
Total Results
1
2, 3, 4, 5, 6, or 7
6
2
1, 3, 4, 5, 6, or 7
6
3
1, 2, 4, 5, 6 or 7
6
4
1, 2, 3, 5, 6 or 7
6
etc
Ways to enter
7  6  42
Ways to exit
6.1 Fundamental Counting Principle cont.
An outcome is made up of events a, b, c, d, etc. The number of ways this outcome
can be performed is given by;
a  b  c  d ...
EXAMPLE #1
Class example #1, pg. 373
A toy manufacturer makes wooden toys in three parts. The top part is either red,
white or blue. The middle part is orange or black. The bottom part is
yellow, green, pink or purple.
a. How many different coloured toys are possible using a tree diagram?
b. How many different coloured toys are possible using the fundamental
counting principle?
6.1 Fundamental Counting Principle cont.
EXAMPLE #2
Class example #3, pg. 374
A Math 30 quiz consists of eight multiple choice questions. Each question has
four choices, A, B, C, and D. How many different sets of answers are possible?
EXAMPLE #3
Class example #5, pg. 374
Car number plates in an African country consist of a letter other than I or O,
followed by three digits, the first of which cannot be zero, followed by any two
letters which are not repeated. How many different car number plates can be
produced?
6.1 Fundamental Counting Principle cont.
EXAMPLE #4
Class example #6, pg 375
Consider the digits 2, 3, 5, 6, 7 and 9.
a) If repetitions are not permitted, how many 3-digit numbers can be formed?
b) How many of these are less than 400? Even? Odd? Multiples of 5?
6.2 Permutations
Permutations are an arrangement where order is important.
Subset Permutations
A subset permutation consists of n possible events where only r are chosen.
8 people enter a relay race. How many ways can they finish 1st, 2nd and 3rd?
8  7  6  336
This example illustrates that if there are n items, and we choose r of them, we
can arrange those items;
n(n  1)(n  2)...(n  r  1) ways
6.2 Permutations cont.
Full set Permutations
A full set permutation consists of n possible events where all n are chosen.
8 people enter a relay race. How many ways can they finish?
8  7  6  ... 1  40320
This is more commonly calculated as 8!
MATH - PRB
This example illustrates that if
there are n items, and we choose
n of them, we can arrange those
items;
n(n  1)(n  2)...3  2 1  n!
6.2 Permutations cont.
Calculating a permutation using a formula
8 people enter a relay race. How many ways can they finish 1st, 2nd and 3rd?
P  8 7  6
8 3
P (5!)  8  7  6(5!)
8 3
8 P3 
n Pr 
8!
5!
n!
(n  r )!
6.2 Permutations cont.
EXAMPLE #1
Class example #1, pg 377.
Find the value of
43!
40!
37!
33!4!
EXAMPLE #2
Class example #2, pg 377
Simplify
n!
( n  2)!
( n  3)!
n!
n!
n( n  1)
6.2 Permutations cont.
EXAMPLE #3
Class example #5, pg. 381
In a South American country, vehicle license plates consist of any 2 different
letters followed by 4 different digits. Find how many different license plates
are possible by;
a) Fundamental counting principle
b) permutations
EXAMPLE #4
Class example #6, pg. 382
Solve
n
P4  28  n1 P2
6.3 Permutations with Restrictions/Repetition
How many different arrangements of the word CANADA are possible?
6!  720
This would only be true if all the letters in the word CANADA were unique (i.e.
no repetition of the letter A). Examine the following arrangements;
AAACND
AAACND
AAACND
AAACND
AAACND
AAACND
The calculation 6!  720 considers each of these to be
different, based on the assumption that the A’s are unique.
The reality is that these 6 arrangements are not different,
and should only be counted once.
Arrangements of the word CANADA …
P6 6!
  120
3! 3!
6
6.3 Permutations with Restrictions/Repetition cont.
General Rule for Repetition
The number of arrangements of n items, where p are of one kind, q are of a
second kind, r are of a third kind, etc, is given by;
n!
p !q !r !...
EXAMPLE #1
Class example #1, pg. 385
How many ways can all the letters of the word ORANGES be arranged if;
a) There are no restrictions.
b) The first letter must be an N.
c) The vowels must be together.
6.3 Permutations with Restrictions/Repetition cont.
EXAMPLE #2
Class example #3, pg. 385
Find the number of permutations of the letters in the word KITCHEN if;
a) The letters K, C and N must be together but not necessarily in that order.
b) The vowels must not be together.
EXAMPLE #3
Class example #4, pg. 385
In how many ways can 3 girls and 4 boys be arranged in a row if no two people
of the same gender can sit together?
6.3 Permutations with Restrictions/Repetition cont.
EXAMPLE #4
Class example #7, pg. 387
Find the number of permutations of the letters of the word;
a) VANCOUVER
b) MATHEMATICAL
EXAMPLE #5
Class example #8, pg. 387
How many arrangements of the word POPPIES can be made under each condition;
a)
b)
c)
d)
e)
Without restrictions.
Each arrangement begins with a P.
The first two letters are P.
All the P’s are together.
The arrangement begins with exactly one P.
6.4 Combinations
Combinations are arrangements where order is not important.
In a class of 15 students, 3 will be selected to win one of 3 prizes, each $50.00.
How many groups of 3 students can be selected?
15 P3 
15!
 2730
12!
Examine the following groups of three students, D, F and I.
DFI
DIF
FDI
FID
IDF
IFD
15 P3 
15!
 2730 will count these 6 times.
12!
However, this is the same group of three students, and should only be
counted once (they don’t care about the order because all prizes are
the same).
P
 15 C3  455
3!
15 3
6.4 Combinations cont.
Calculating a combination using a formula
15 items choose 3, order not important.
P
15!
1
15!

 
3! (15  3)! 3! 12!3!
15 3
n Cr 
n!
(n  r )!r !
MATH - PRB
6.4 Combinations cont.
EXAMPLE #1
Class example #2, pg. 395
To win LOTTO 649, a person must correctly choose six numbers from 1-49.
Jasper , wanting to play LOTTO 649, began to wonder how many numbers he
could make up. How many choices would Jasper have to make to ensure he had
the six winning numbers?
EXAMPLE #2
Class example #3, pg. 395
The Athletic Council decides to form a sub-committee of seven council
members to look at how funds raised should be spent on sports activities in
the school. There are a total of 15 athletic council members, 9 makes and 6
females. The subcommittee must consist of exactly 3 females;
a)
b)
c)
d)
How many ways can the females be chosen?
How many ways can the males be chosen?
In how many ways can the subcommittee be chosen?
In how many ways can the subcommittee be chosen if Bruce, the football
coach, must be included?
6.4 Combinations cont.
EXAMPLE #3
Class example #1, pg. 399
The Student Council decides to form a subcommittee of five council members to
look at how funds raised should be spent on the students of the school. There
are a total of 11 student council members, 5 males and 6 females. How many
different ways can the subcommittee consist of;
a) Exactly 3 females?
b) At least 3 females?
c) At least one male?
EXAMPLE #4
Class example #5, pg. 401
During a Pee Wee hockey tryout, all the players met on the ice after the last
practice and shook hands with each other. How many players attended the trout
if there were 300 handshakes in all?
6.4 Combinations cont.
EXAMPLE #5
Class example #6, pg. 402
A polygon has 65 diagonals. How many sides does it have?
6.5 Probability using Permutations and Combinations
Probability is based on the calculation of a ratio. The probability of event E is;
P( E ) 
favourable outcomes
possible outcomes
Counting methods (fundamental counting principle, permutations and
combinations) allow us to determine both the favourable and possible
outcomes.
EXAMPLE #1
Class example #1, pg 419.
The word COUNTED has been spelled using Scrabble tiles. Two tiles are
randomly chosen at a tie and placed in the order which they were chosen.
Determine the probability that the tiles are:
a) CO
b) Both vowels
6.5 Probability using Permutations and Combinations cont.
EXAMPLE #2
Class example #2, pg. 419
The Athletic Council decides to form a subcommittee of seven council members
to look at how funds raised should be spent on sports activities at the school.
There are a total of 15 athletic council members, 9 males and 6 females. What is
the probability that the subcommittee will consist of exactly 3 females?
EXAMPLE #3
Class example #5, pg. 420
In a card game, you are dealt 5 cards from a pack of 52 shuffled cards. When you
look at your 5 cards, what is the probability, expressed in combination
notation, you have;
a)
b)
c)
d)
Four aces?
Four tens and an ace?
10, J, Q, K and ace?
At least one Jack?
6.6 Pascal’s Triangle and Pathways
Mathematician Blaise Pascal discovered a number pattern in the seventeen
century that has many applications to mathematical problems today.
The pattern is;
1
1
1
1
1
1
2
3
4
5
1
1
3
6
10
1
4
10
1
5
Can you find the next two rows?
1
Add adjacent numbers in the previous
row to find the numbers making up
the next row.
6.6 Pascal’s Triangle and Pathways cont.
Pascal Triangle Properties
Many interesting phenomena can be observed from the number pattern;
1
1
+
1
1 + 2 + 1
1 + 3 + 3 + 1
1
4
6
4
1
1
5
10
10
5
1
Add these numbers …
And, you get this one.
This works on any
diagonal.
20
21
22
23
The nth row has a sum
of 2n1
6.6 Pascal’s Triangle and Pathways cont.
Pascal Triangle Properties and Combinations
1
1
1
2
1
1
3
6
5
10
2
3
4
5
C0
C0
C0
4
5
C1
1
2
3
5
C2
n
1
C1
2
3
4
1
5
C1
C1
C1
4
C0
C0
C0
1
10
0
1
1
3
4
1
Each row of the
triangle is
formed by the
combinations;
1
C2
C2
3
4
5
C2
C3
C3
C3
4
5
C4
C4
5
C5
C{0,1,2,3...n}
6.6 Pascal’s Triangle and Pathways cont.
EXAMPLE #1
Class example #1, pg 407
a) What is the sum of the numbers in the tenth row of Pascal’s Triangle?
b) Omit for now.
c) What is the sum of;
15
6
C0  15 C1  ...  15 C15
C0  6 C1  ...  6 C5
EXAMPLE #2
Class example #1, pg. 413
A city centre has a rectangular road system with 5 streets running north to south
and 6 avenues running west to east.
a) Draw a grid to represent this situation.
b) Sean is driving a car situated at the extreme northwest corner of the city
centre. How many ways can he drive to the extreme southeast corner?
6.6 Pascal’s Triangle and Pathways cont.
EXAMPLE #3
Class example #2, pg 414
Find the number of pathways from A to B if paths must move closer to B.
A
A
B
B
6.6 Pascal’s Triangle and Pathways cont.
EXAMPLE #4
Class example #3, pg. 414
How many routes must be considered if, at each intersection the taxi must always
move closer to the stadium?
Tr ain Station
City Park
Football Stadium
6.7 Binomial Theorem
Expand each of the following;
( x  y )0
1
( x  y )1
x y
( x  y)2
x 2  2 xy  y 2
( x  y )3
x3  3x 2 y  3xy 2  y 3
Notice;
1.
2.
3.
4.
The x value in the first term is to the power of n.
The x value in successive terms is reduced by 1.
The y value in the first term is to the power of 0.
The y value in successive terms is increased by 1 until the last term where it’s
n.
6.7 Binomial Theorem cont.
The derivation of coefficients
Examine x3  3x 2 y  3xy 2  y 3
The coefficients of 1, 3, 3, 1 are found in Pascal’s Triangle.
1
1
1
1
1
1
2
3
4
5
( x  y )0
( x  y )1
1
1
3
6
10
( x  y)2
3
1 ( x  y)
4
10
1
5
1
Here …
6.7 Binomial Theorem cont.
Putting it all together
Expand ( x  y )5
With n = 5, the final expression will contain 6 terms, so you must use the 6th row
of Pascal’s Triangle.
5
P0 x 5
4
P
x
y
5 1
5
P2 x 3 y 2
5
P3 x 2 y 3
4
P
xy
5 4
5
P
y
5 5
x5  5 x 4 y  10 x3 y 2  10 x 2 y 3  5 xy 4  y 5
6.7 Binomial Theorem cont.
EXAMPLE #1
Class example #2, pg. 409
Find the fifth term of ( x  y )8
Find the middle term of (2 x  5)6
EXAMPLE #2
Class example #4, pg. 409
One term in the expansion of ( x  a)10 is 3,281,250x 4 . Find a.
EXAMPLE #3
Class example #5, pg. 409
15
Find the constant term of
1 

2x



x2 

6.8 Binomial Probability
Over the next few weeks, the Flames will play the Oilers 4 times. In the last 10
games they’ve played, the Flames have won 7 times.
What is the probability the Flames will beat the Oilers in 3 of their next 4
games?
Based on what we know, each time they play, the probability of a Flames win is;
7
 0.7
10
So, a four game stretch might look like; WWWL (W is a win, L is a loss).
0.7  0.7  0.7  0.3  0.73  0.3
Win
Loss
6.8 Binomial Probability cont.
What is incorrect about 0.7  0.7  0.7  0.3
Why should we be
restricted to the
first 3 games being
wins? Is this the
only arrangement?
Arrangements of 3 W’s and 1 L
4!
3!
or
4
C3
6.8 Binomial Probability cont.
Probability of the Flames beating the Oilers in 3 of the next 4 games?
4
C3 (0.7)3 (0.3)
Arrangements
possible for
wins/losses.
Wins Losses
Total possible outcome for the Flames and Oilers playing 4 games?
(0.7  0.3) 4  4 C0 (0.7) 4  4 C1 (0.7)3 (0.3)  4 C2 (0.7) 2 (0.3) 2  4 C3 (0.7)(0.3)3  4 C4 (0.3) 4
Flames
win all
Flames
win 3
Flames
win 2
Flames
win 1
Flames
don’t win
6.8 Binomial Probability cont.
EXAMPLE #1
Class example #2, pg 435
Five dice are rolled. What is the probability of rolling
a) Exactly three twos?
b) At least three twos?