Transcript Section 3

Permutations and Combinations
Section 3
Objectives:
• Use factorial notation to represent the
number of permutations of a set of
objects.
• Calculate the number of permutations of n
objects taken r at a time.
• Calculate the number of combinations of n
objects taken r at a time.
• Apply the theory of permutations and
combinations to solve counting problems.
Permutations
• Notation:
P(n , r) =
nP r
• For permutations, order is important!
So abc and acb are different permutations.
Permutations cont. (2)
How many permutations are there of the letters a, b, c, and d?
Write the answer using P(n, r) notation.
We write the letters a, b, c, and d in a line without repetition, so
abcd and bcad are two such permutations.
The slot diagram indicates there are 4 × 3 × 2 × 1 = 24
possibilities.
This can be written as
=
4P4
Permutations cont. (3)
How many permutations are there of the letters a, b, c,
d, e, f, and g if we take the letters three at a time?
Write the answer using P(n, r) notation.
The slot diagram indicates there are 7 × 6 × 5 = 210
possibilities.
This can be written in permutation notation as
Factorial Notation
So
And
P(4, 4) =
4 P4
= 4!
• Compute (8 – 3)!.
= 120
• Compute
.
Factorial Notation cont. (2)
So
P(n, r) is the product of r factors beginning with n and each
then decreasing by 1 .
• Example:
A 12-person theater group wishes to select one person
to direct a play, a second to supervise the music, and a third to
handle publicity, tickets, and other administrative details. In how
many ways can the group fill these positions?
• Solution:
Order does matter so this is a permutation of selecting 3
people from 12.
Using a slot diagram, we see 3 factors beginning with 12:
(12)(11)(10) = 1,320
___ ___ ___
Combinations
• How many three-element subsets can be chosen from a set of five
objects?
• Order is not important, so this is a combination problem.
• How many four-person committees can be formed from a set of 10
people?
• Solution:
Order is not important, so this is a combination
problem.
C(10, 4) = P(10, 4) / 4!
Combinations cont. (2)
•
•
A syndicate has $15 million to spend on tickets for a lottery. Tickets cost $1 and
contain a combination of six numbers from 1 to 44. Does the syndicate have
enough money to buy enough tickets to be guaranteed a winner?
Solution:
The combination of 6 numbers from the 44 possible gives the
number of different tickets. That is, C(44, 6) = 7,059,052. Thus, the syndicate has
more than enough money to buy enough tickets to be guaranteed a winner.
• In the game of poker, five cards are drawn from a standard 52-card deck.
How many different poker hands are possible?
• In the game of bridge, a hand consists of 13 cards drawn from a standard 52card deck. How many different bridge hands are there?
Combining Counting Methods
Two men and two women from a firm will attend a conference. If the firm has
ten men and nine women, in how many different ways can the conference
attendees be selected?
Solution:
The answer is not C(19, 4) since this includes options like
four men and no woman being sent to the conference.
Stage 1:
Select the two women from the nine available.
Stage 2:
Select the two men from the ten available.
Thus, choosing the women and then choosing the men can be done in
ways.
Combining Counting Methods cont. (2)
A 16-member consortium wishes to choose a committee consisting of a
president, a vice president, and a three-member executive board. In how
many different ways can this committee be formed?
Solution: We will count this in two stages:
(a) choosing the president and vice president from the consortium,
(b) choosing an executive board from the remaining members.
Stage 1: Choose the president and vice president. This can be done in
P(16, 2) ways.
Stage 2: Select the executive board. This can be done in
C(14, 3) ways.
Total:
Pascal’s Triangle
For example, consider the set {1, 2, 3, 4} and the 4th row of Pascal’s triangle: 1 4 6 4 1.
Pascal’s Triangle cont. (2)
For example, again consider the 4th row of Pascal’s triangle: 1 4 6 4 1 .
C(4, 0) = 1
C(4, 1) = 4
C(4, 2) = 6
C(4, 3) = 4
C(4, 4) = 1
Pascal’s Triangle cont. (3)
Assume that a pharmaceutical company has developed five antibiotics and four immune system
stimulators. In how many ways can we choose a treatment program consisting of three
antibiotics and two immune system stimulators to treat a disease? Use Pascal’s triangle to
speed your computations.
Solution: We will count this in two stages:
(a) choosing the antibiotics,
(b) choosing the immune system simulators.
Stage 1: Choosing 3 antibiotics from 5 can be done in C(5, 3) ways.
Stage 2: Choosing 2 immune system simulators from 4 can be done in C(4, 2) ways.
Total:
C(5, 3) × C(4, 2) = 10 × 6 = 60 ways.