Transcript election problem

12
THE NATURE OF COUNTING
Copyright © Cengage Learning. All rights reserved.
12.1
Permutations
Copyright © Cengage Learning. All rights reserved.
Election Problem
3
Election Problem
Consider a club with five members:
A = {Alfie, Bogie, Calvin, Doug, Ernie}
In how many ways could they elect a president and
secretary? We call this the election problem.
There are several ways to solve this problem.
4
Election Problem
The first, and perhaps the easiest, is to make a picture,
known as a tree diagram, listing all possibilities
(see Figure 12.1).
Tree diagram for five choices
Figure 12.1
5
Election Problem
We see there are 20 possibilities for choosing a president
and a secretary from five club members. This method is
effective for “small” tree diagrams, but the technique quickly
gets out of hand.
For example, if we wished to see how many ways the club
could elect a president, secretary, and treasurer, this
technique would be very lengthy.
A second method of solution is to use boxes or
“pigeonholes” representing each choice separately.
6
Election Problem
Here we determine the number of ways of choosing a
president, and then the number of ways of choosing a
secretary.
We multiply the numbers in the pigeonholes,
5  4 = 20
and we see that the result is the same as from the tree
diagram.
7
Election Problem
A third method is to use the fundamental counting principle.
8
Example 1 – Determine the number of ways of choosing three
In how many ways could the given club choose a president,
secretary, and treasurer?
Solution:
The answer is 5  4  3 = 60.
9
Election Problem
When set symbols { } are used, the order in which the
elements are listed is not important. Suppose now that you
wish to select elements from A = {a, b, c, d, e} by picking
them in a certain order.
The selected elements are enclosed in parentheses to
signify order and are called an arrangement of elements
of A.
For example, if the elements a and b are selected from A,
then there are two pairs, or arrangements:
(a, b) and (b, a)
10
Election Problem
These arrangements are called ordered pairs. Remember,
when parentheses are used, the order in which the
elements are listed is important.
This example shows ordered pairs, but you could also
select an ordered triple such as (d, c, a). These
arrangements are said to be selected without repetition,
since a symbol cannot be used twice in the same
arrangement.
11
Election Problem
If we are given some set of elements and we are to choose
without repetition a certain number of elements from the
set, we can choose them so that the order in which the
choices are made is important, or so that it is not.
If the order is important, we call our result a permutation,
and if the order is not important, it is called a combination.
We now consider permutations.
Suppose we consider the election problem for a larger set
than A; we wish to elect a president, secretary, and
treasurer from among {Frank, George, Hans, Iris, Jane,
Karl}.
12
Election Problem
We could use one of the previously mentioned three
methods, but we wish to generalize, so we ask, “Is it
possible to count the number of arrangements without
actually counting them?”
In answering this question, we note that we are selecting 3
persons in order from a group of 6 people. If an arbitrary
finite set S has n elements and r elements are selected
without repetition from S (where r  n ), then an
arrangement of the r selected elements is called a
permutation.
13
Election Problem
14
Example 3 – Number of permutations of two chosen from six
How many permutations of two elements can be selected
from a set of six elements?
Solution:
Let B = {a, b, c, d, e, f} and select two elements:
(a, b), (a, c), (a, d), (a, e), (a, f), (b, a), (b, c), (b, d), (b, e),
(b, f), (c, a), (c, b), (c, d), (c, e), (c, f), (d, a), (d, b), (d, c),
(d, e), (d, f), (e, a), (e, b), (e, c), (e, d), (e, f), (f, a), (f, b),
(f, c), (f, d), (f, e)
There are 30 permutations of two elements selected from a
set of six elements.
15
Election Problem
16
Example 4 – Evaluate permutations
Evaluate:
a. 52P2
b. 7P3
c. 10P4
d. 10P1
e. nPr
17
Example 4 – Solution
We use the fundamental counting principle:
a. 52P2 = 52  51 = 2,652
b. 7P3 = 7  6  5 = 210
c. 10P4 = 10  9  8  7 = 5,040
d. 10P1 = 10
18
Example 4 – Solution
cont’d
e. nPr = n(n – 1)(n – 2)………(n – r + 1)
19
Factorial
20
Factorial
In our work with permutations, we will frequently encounter
products such as
6  5  4  3  2  1 or 10  9  8  7  6  5  4  3  2  1 or
52  51  50  49  . . .  4  3  2  1
Since these are rather lengthy, we use factorial notation.
21
Example 6 – Evaluate factorials
Evaluate factorials for the numbers 0, 1, …….,10.
Solution:
0! = 1
1! = 1
2! = 2  1 = 2
3! = 3  2  1 = 6
4! = 4  3  2  1 = 24
5! = 5  4  3  2  1 = 120
6! = 6  5  4  3  2  1 = 720
22
Example 6 – Solution
cont’d
7! = 7  6  5  4  3  2  1 = 5,040
8! = 8  7  6  5  4  3  2  1 = 40,320
9! = 9  8  7  6  5  4  3  2  1 = 362,880
10! = 10  9  8  7  6  5  4  3  2  1 = 3,628,800
23
Factorial
Notice (from Example 6) that these numbers get big pretty
fast. We need not wonder why the notation “!” was chosen!
For example,
52!  8.065817517  1067
If you actually carry out the calculations in Example 6, you
will discover a useful property of factorials:
3! = 3  2!, 4! = 4  3!, 5! = 5  4!;
that is, to calculate 11! you would not need to “start over”
but simply multiply 11 by the answer found for 10!.
24
Factorial
This property is called the multiplication property of
factorials or the count-down property.
25
Example 7 – Evaluate factorial expressions
Evaluate:
a. 6! – 4!
b. (6 – 4)!
Solution:
a. 6! – 4! = 720 – 24 = 696
b. (6 – 4)! = 2! = 2
Compare order of operations in parts a and b.
c.
Count-down property
26
Example 7 –Solution
cont’d
d.
= 12  11  10 = 1,320
e.
= 9,900
Repeated use of
the count-down
property
This example shows that you
need the count-down property
even if you are using a
calculator.
27
Factorial
Using factorials, we can find a formula for nPr.
nPr
= n(n – 1)(n – 2)………(n – r + 1)
= n(n – 1)(n – 2)………(n – r + 1) 
=
=
This is the general formula for nPr.
28
Factorial
29
Distinguishable Permutations
31
Distinguishable Permutations
We now consider a generalization of permutations in which
one or more of the selected items is indistinguishable from
the others.
32
Example 12 – Find the number of distinguishable permutations
Find the number of arrangements of letters in the given
word:
a. MATH
b. HATH
Solution:
a. This is a permutation of four objects taken four at a time:
4P4
= 4! = 24
b. This is different from part a because not all the letters in
the word HATH are distinguishable; that is, the first and
last letters are both H’s, so they are indistinguishable.
33
Example 12 – Solution
cont’d
If we make the letters distinguishable by labeling them as
HATH, we see that now the list is the same as in part a. Let
us list the possibilities as shown below.
34
Example 12 – Solution
cont’d
We see that there are 24 possibilities, but notice how we
have arranged this listing. If we consider H = H (that is, the
H’s are indistinguishable), we see that the first and the
second columns are the same.
Since there are two indistinguishable letters, we divide the
total by 2:
35
Distinguishable Permutations
36