Transcript Chapter 9: Discrete Mathematics

Some lovely and slightly random facts…
Give the number of objects described.
1. The number of cards in a standard deck
52
2. The number of cards of each suit in a standard deck
3. The number of faces on a cubical die
13
6
4. The number of possible totals when two dice are rolled
5. The number of vertices of a decagon
10
6. The number of musicians in a string quartet
4
11
More lovely and slightly random facts…
Give the number of objects described.
7. The number of players on a soccer team
11
8. The number of prime numbers between 1 and 10, inclusive 4
9. The number of squares on a chessboard
64
10. The number of cards in a contract bridge hand
11. The number of players on a rugby team
15
13
Chapter 9:1a
Discrete
Mathematics
What is Discrete Mathematics???
Any interval (a, b) contains a continuum of real
numbers  you can “zoom in” forever and there will
still be an interval there…
The mathematics of the continuum is used a great
deal in algebra, analysis, and geometry, which all
lead to important concepts in calculus…
In contrast, discrete mathematics involves separate
(or “discrete”) numbers that do not lie on a continuum.
The simplest type of discrete mathematics is…
COUNTING!!!
The Importance of Counting
In how many ways can three distinguishable objects be
arranged in order? (let’s call them A, B, and C)
We can “see” the solution to this problem with a
tree diagram:
B
C
The six different
A
C
orderings:
B
A
ABC, ACB,
Starting
B
C
Point
C
BAC, BCA,
A
CAB, CBA
A
B
B
C
A
Multiplication Principle of Counting
If a procedure P has a sequence of stages S 1,
S 2 , … , Sn and if
S 1 can occur in r 1 ways,
S 2 can occur in r 2 ways,
S n can occur in r n ways,
then the number of ways that the procedure P can
occur is the product: r 1 r 2
rn .
(our tree diagram gives a visualization of this principle…)
Multiplication Principle of Counting
Important note about this principle!!!
Be mindful of how the choices at
each stage are affected by the
choices at preceding stages…
(think about how this applies
In our very first example)
Using the Multiplication Principle
A certain state’s license plates consist of three letters
followed by three numerical digits (0 through 9). Find the
number of different license plates that could be formed
(a) if there is no restriction on the letters or digits;
(b) if no letter or digit can be repeated.
With no restrictions, we have 26 ways to fill each of the
first three blanks, and 10 ways to fill each of the final
three blanks.
Multiplication Principle: 26 x 26 x 26 x 10 x 10 x 10
= 17,576,000 ways
Using the Multiplication Principle
A certain state’s license plates consist of three letters
followed by three numerical digits (0 through 9). Find the
number of different license plates that could be formed
(a) if there is no restriction on the letters or digits;
(b) if no letter or digit can be repeated.
If no repeats are allowed, there are 26 choices for the first
blank, 25 for the second, 24 for the third, 10 for the fourth,
9 for the fifth, and 8 for the sixth.
Multiplication Principle: 26 x 25 x 24 x 10 x 9 x 8
= 11,232,000 ways
Are these realistic estimates for #’s of ways???
Permutations
What are they???
Permutations – possible orderings of a set of objects
Consider the  There are 24 possible
orderings………………………can we generalize for a rule ?
RULE: If there are n objects in a set, then there
are n ! permutations of the set
Note: the symbol n! (read “n factorial”) represents the
product n(n – 1)(n – 2)(n – 3)…(2)(1). In addition, we
define 0! = 1.
What are they???
Permutations – possible orderings of a set of objects
RULE: If there are n objects in a set, then there
are n ! permutations of the set
This rule only works if all elements of a set are
distinguishable from each other…
Distinguishable Permutations
There are n! distinguishable permutations of an n-set containing
n distinguishable objects.
If an n-set contains n1 objects of a first kind, n 2 objects of a
second kind, and so on, with n 1 + n2 + … + n k = n, then the
number of distinguishable permutations of the n-set is
n!
n1 !n2 !n3 !
nk !
Some Practice Problems
Count the number of different 9-letter “words” (don’t worry
about whether they’re in the dictionary) that can be formed
using the letters in each of the given words.
1. DRAGONFLY
Each permutation of the 9 letters forms a different word.
There are 9! = 362,880 such permutations.
2. BUTTERFLY
There are also 9! permutations, but simply switching the
two T’s does not result in a new word.
9!
There are
= 181,440 distinguishable permutations.
2!
Some Practice Problems
Count the number of different 9-letter “words” (don’t worry
about whether they’re in the dictionary) that can be formed
using the letters in each of the given words.
3. BUMBLEBEE
The three B’s and three E’s are indistinguishable, so we
divide by 3! twice to correct for the overcount…
9!
There are
= 10,080 distinguishable permutations.
3!3!
Permutation Counting Formula
In some counting problems, we are interested in using n
objects to fill r blanks in order, where r < n. These are called
permutations of n objects taken r at a time.
The number of permutations of n objects taken r at a time is
denoted n P r and is given by
n!
n Pr 
 n  r !
If r > n, then n Pr
0
for
0r n
What is
?
P
n n
More Practice Problems
Evaluate the given expressions, first without a calculator.
Then, check your answer with a calculator.
1.
6! 6  5  4  3  2 1
6!



360

P
6 4
2 1
 6  4 ! 2!
11!
11!


990
2. P 

11

10

9
11 3
11  3! 8!
More Practice Problems
Evaluate the given expression.
3.
n!

P
n 3
 n  3 !
n  n  1 n  2  n  3  2 1

 n  3  2 1
 n  n  1 n  2
More Practice Problems
Sixteen actors answer a casting call to try out for roles as
dwarfs in a production of Snow White and the Seven Dwarfs.
In how many ways can the director cast the seven roles?
There are 7 blanks to be filled, and 16 actors with which
to fill them:
16
P7  57, 657, 600
ways
More Practice Problems
Proctor has 22 players train for his rugby team, and he must
fill 15 playing spots for a weekend match. Assuming that all
players are equally qualified for each playing position, in how
many ways can Proctor fill the spots?
P

2.23016

10
22 15
17
ways