Transcript 6.4 Permutations and combinations

Logic and Introduction to Sets
Chapter 6
6.4 Permutations and Combinations
For more complicated problems, we will need to
develop
two important concepts: permutations and
.
combinations. Both of these concepts involve what
is called the factorial of a number.
Dr .Hayk Melikyan/ Department of Mathematics and CS/
[email protected]
FACTORIAL
For n a natural number,
n! = n(n - 1)(n - 2)·...·3·2·1
0! = 1
n! = n(n - 1)!
1! = 1
2! = 2
3! = 6
4!= 3!*4 = 24
What about 10! =
[NOTE:
Many calculators have an key or its equivalent.]
FM/2004/Melikyan
Definition of n factorial (!)
 n! = n(n-1)(n-2)(n-3)…1
 How it is used in counting:
Example.
 The simplest protein molecule in biology is called vasopressin
and is composed of 8 amino acids that are chemically bound
together in a particular order. The order in which these amino
acids occur is of vital importance to the proper functioning of
vasopressin. If these 8 amino acids were placed in a hat and
drawn out randomly one by one, how many different
arrangements of these 8 amino acids are possible?
 Solution: Let A,B,C,D,E,F,G,H symbolize the 8 amino acids.
They must fill 8 slots ___ ___ ___ ___ ___ ___ ___ ___ .
 There are 8 choices for the first position, leaving 7 choices for
the second slot, 6 choices for the third slot and so on. The
number of different orderings is
 8(7)(6)(5)(4)(3)(2)(1)=8! =40,320.
FM/2004/Melikyan
Example continued:



Of the 40,320 possible orderings of the 8 amino acids, the human
body can use just one. What is the probability that, by random
chance alone with no outside interference, the correct order
occurs. We will discuss probability in the next chapter, but here is the
answer:
1
Probability of correct order is
, an extremely unlikely event.
40,320
For more complicated biological molecules, such as hemoglobin, with
many more amino acids, the probability that the correct order occurs
by random chance alone is extremely small (close to zero!) which
raises questions in some scientists’ minds of just how such molecules
came to be formed by random chance. Some have concluded that
their creation was not due to random chance but by intelligent
design which raises still more questions that cannot be completely
answered.
FM/2004/Melikyan
Two problems illustrating combinations and
permutations.
Consider the following two problems:
1)
Consider the set { p , e , n} How many two-letter “words” (including
nonsense words) can be formed from the members of this set?
We will list all possibilities: pe, pn, en, ep, np, ne , a total of 6.
2)
Now consider the set consisting of three males: {Paul, Ed, Nick} For
simplicity, we will denote the set { p, e, n} How many two-man
crews can be selected from this set?
2)
Answer: pe (Paul, Ed), pn (Paul, Nick) and en (Ed, Nick) and that is
all!
FM/2004/Melikyan
Difference between permutations and
combinations
 The difference between the two problems is this:
 Both problems involved counting the numbers of arrangements
of the same set {p , e , n}, taken 2 elements at a time,
without allowing repetition. However, in the first problem, the
order of the arrangements mattered since pe and ep are
two different “words”. In the second problem, the order did
not matter since pe and ep represented the same two-man
crew. So we counted this only once.
 The first example was concerned with counting the number of
permutations of 3 objects taken 2 at a time.
 The second example was concerned with the number of
combinations of 3 objects taken 2 at a time
FM/2004/Melikyan
PERMUTATIONS
A PERMUTATION of a set of distinct objects is an
Arrangement of the objects in a specific order,
without repetitions.
The number of permutations of n distinct objects
without repetition, denoted by Pn,n , is:
Pn,n = n(n - 1)·...·3·2·1 = n! (n factors)
FM/2004/Melikyan
PERMUTATIONS OF n OBJECTS TAKEN r AT A TIME
A permutation of a set of n distinct objects taken r at a
time without repetition is an arrangement of the r objects
in a specific order. The number of permutations of n
objects taken r at a time, denoted by Pn,r, is given by:
Pn,r = n(n - 1)(n - 2)·...·(n - r + 1)
(r factors)
or
[Notethe number of permutations of n objects
FM/2004/Melikyan
taken n at a time.
Permutations
The notation P(n,r) represents the number of permutations
(arrangements) of n objects taken r at a time when r is less than
or equal to n. In a permutation, the order is important.
In our example, we have P(3,2) which represents the number of
permutations of 3 objects taken 2 at a time.
In our case, P(3,2) = 6 = (3)(2)
In general, P(n,r) = n(n-1)(n-2)(n-3)…(n-r+1)
FM/2004/Melikyan
More examples
Use the definition P(n,r) = n(n-1)(n-2)(n-3)…(n-r+1)






Find P(5,3)
Here, n = 5 and r = 3 so we have P(5,3) = (5)(5-1)5-3+1) =
5(4)3 = 60. This means there are 60 arrangements of 5 items taken 3
at a time.
Application: How many ways can 5 people sit on a park bench if the
bench can only seat 3 people?
Solution: Think of the bench as three slots ___ ___ ___ .
There are five people that can sit in the first slot, leaving four
remaining people to sit in the second position and finally 3 people
eligible for the third slot. Thus, there are 5(4)(3)=60 ways the people
can sit. The answer could have been found using the permutations
formula: P(5,3) = 60, since we are finding the number of ways of
arranging 5 objects taken 3 at a time.
FM/2004/Melikyan
P(n,n)= n(n-1)(n-2)…1
 Find P(5,5) , the number of arrangements of 5 objects taken
5 at a time.
 Answer: P(5,5) = 5(5-1)…(5-5+1) = 5(4)(3)(2)(1)=120.
 Application: A bookshelf has space for exactly 5 books. How
many different ways can 5 books be arranged on this
bookshelf?
 ___ ___ ___ ___ ___ Think of 5 slots, again. There are five
choices for the first slot, 4 for the second and so on until
there is only 1 choice for the final slot. The answer is
5(4)(3)(2)(1)
which is the same as P(5,5) = 120.
FM/2004/Melikyan
Combinations
 In the second problem, the number of 2 man crews that can
be selected from {p,e ,n} was found to be 6. This corresponds
to the number of combinations of 3 objects taken 2 at a time
or
 C(3,2). We will use a variation of the formula for permutations
to derive a formula for combinations.
 Consider the six permutations of { p, e, n} which are grouped
in three pairs of 2. Each pair corresponds to one combination
of 2.
pe, ep,
np, pn,
en, ne,
 so if we want to find the number of combinations of 3 objects
taken 2 at a time, we simply divide the number of
permutations of 3 objects taken 2 at a time by 2 (or 2!)
 We have the following result: C(3,2) =
FM/2004/Melikyan
P(3, 2)
2!
Generalization

General result: This formula gives the number of subsets of size r
that can be taken from a set of n objects. The order of the items in
each subset does not matter.
P(n, r ) n(n  1)(n  2)...(n  r  1)
C (n, r ) 

r!
r (r  1)(r  2)...1
FM/2004/Melikyan
COMBINATIONS OF n OBJECTS TAKEN r AT A TIME
A combination of a set of n distinct objects taken r at a time
Without repetition is an r-element subset of the set of n objects.
(The arrangement of the elements in the subset does not
matter.) The number of combinations of n objects taken r at a
time, denoted by Cn,r or
by is given by:
NOTE:
In a permutation, the ORDER of the objects counts.
In a combination, order does not count.
FM/2004/Melikyan
Examples

Find C(8,5)

Solution: C(8,5) =

2. Find C(8,8)

Solution: C(8,8) =
P(8,5) 8(7)(6)(5)(4) 8(7)(6)


 8(7)  56
5!
5(4)(3)(2)(1) 3(2)(1)
P(8,8) 8(7)(6)(5)(4)(3)(2)(1)

1
8!
8(7)(6)(5)(4)(3)(2)(1)
FM/2004/Melikyan
Combinations or Permutations?
 1. In how many ways can you choose 5 out of
10 friends to invite to a dinner party?
 Solution: Does the order of selection matter?
If you choose friends in the order A,B,C,D,E or
A,C,B,D,E the same set of 5 was chosen, so
we conclude that the order of selection does
not matter. We will use the formula for
combinations since we are concerned with
how many subsets of size 5 we can select
from a set of 10.
C(10,5) =
P(10,5) 10(9)(8)(7)(6) 10(9)(8)(7)


 2(9)(2)(7)  252
5!
5(4)(3)(2)(1)
(5)(4)
FM/2004/Melikyan
Permutations or Combinations?
 How many ways can you arrange 10 books on a bookshelf that
has space for only 5 books?
 Does order matter? The answer is yes since the arrangement
ABCDE is a different arrangement of books than BACDE. We
will use the formula for permutations. We need to determine
the number of arrangements of 10 objects taken 5 at a time so
we have P(10,5) = 10(9)(8)(7)(6)=30,240
FM/2004/Melikyan
Lottery problem
 A certain state lottery consists of selecting a set of
6 numbers randomly from a set of 49 numbers. To
win the lottery, you must select the correct set of
six numbers. How many possible lottery tickets are
there?
 Solution. The order of the numbers is not
important here as long as you have the correct set
of six numbers. To determine the total number of
lottery tickets, we will use the formula for
combinations and find C(49, 6), the number of
combinations of 49 items taken 6 at a time. Using
our calculator, we find that
 C(49,6) = 13,983,816
FM/2004/Melikyan
Examples (Problem #33)
a) How many ways can a 3-person subcommittee be selected
from a committee of a seven people?
b) How many ways con a president vice-president, and secretary
be selected from t a committee of 7 people?
(A ) The number of ways that a three-person subcommittee can
be selected from a seven member committee is the number of
combinations (since order is not important in selecting a
subcommittee) of 7 objects 3 at a time. This is:
FM/2004/Melikyan
Example (cont)
(B) The number of ways a president, vice-president, and
secretary can be chosen from a committee of 7 people is the
number of permutations (since order is important in
choosing 3 people for the positions) of 7 objects 3 at a time.
This is:
FM/2004/Melikyan
Problem #39
From a standard 52-card deck, how many 7-card hands
have exactly 5 spades and 3 hearts?
The five spades can be selected in C13,5 ways and the two
hearts can be selected in C13,2 ways. Applying the
Multiplication Principle, we have: Total number of hands
FM/2004/Melikyan