Transcript Section 10.2

Chapter 10
Counting
Methods
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
1
Chapter 10: Counting Methods
10.1 Counting by Systematic Listing
10.2 Using the Fundamental Counting Principle
10.3 Using Permutations and Combinations
10.4 Using Pascal’s Triangle
10.5 Counting Problems Involving “Not” and “Or”
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
2
Section 10-2
Using the Fundamental Counting
Principle
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
3
Using the Fundamental Counting
Principle
• Know the meaning of the uniformity in counting
and understanding the fundamental counting
principle.
• Use the fundamental counting principle to solve
counting problems.
• Determine the factorial of a whole number.
• Use factorials to determine the number of
arrangements, including distinguishable
arrangements, of a given number of objects.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
4
Uniformity Criterion for Multiple-Part
Tasks
A multiple-part task is said to satisfy the
uniformity criterion if the number of choices for
any particular part is the same no matter which
choices were selected for the previous parts.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
5
Fundamental Counting Principle
When a task consists of k separate parts and satisfies
the uniformity criterion, if the first part can be done
in n1 ways, the second part can be done in n2 ways,
and so on through the k th part, which can be done in
nk ways, then the total number of ways to complete
the task is given by the product
n1  n2  n3 
 nk .
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
6
Example: Counting Two-Digit Numbers
How many two-digit numbers can be made from the
set {0, 1, 2, 3, 4, 5}? (numbers can’t start with 0.)
Solution
Part of Task
Select first digit
Number of ways
5
(0 can’t be used)
Select second
digit
6
There are 5(6) = 30 two-digit numbers.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
7
Example: Building Two-Digit Numbers
with Restrictions
How many two-digit numbers that do not contain
repeated digits can be made from the set
{0, 1, 2, 3, 4, 5}?
Solution
Part of
Task
Number of
ways
Select first Select second digit
digit
5
5
(repeated digits not allowed)
There are 5(5) = 25 two-digit numbers.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
8
Example: Counting the Number of IDs
How many ways can you select two letters followed
by three digits for an ID?
Solution
Part of
Task
Number
of ways
First
letter
26
Second Digit
letter
26
10
Digit
Digit
10
10
There are 26(26)(10)(10)(10) = 676,000 IDs possible.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
9
Factorials
For any counting number n, the product of all
counting numbers from n down through 1 is
called n factorial, and is denoted n!.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
10
Factorial Formula
For any counting number n, the quantity
n factorial is given by
n !  n(n  1)(n  2)
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
2 1.
11
Example:
Evaluate each expression.
a) 4!
b) (4 – 1)!
5!
c)
3!
Solution
a) 4!  4  3  2 1  24
b) (4  1)!  3  2 1  6
5! 5  4  3!
c)

 5  4  20
3!
3!
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
12
Definition of Zero Factorial
0!  1
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
13
Arrangements of Objects
When finding the total number of ways to
arrange a given number of distinct objects,
we can use a factorial.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
14
Arrangements of n Distinct Objects
The total number of different ways to arrange
n distinct objects is n!.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
15
Example: Arranging Books
How many ways can you line up 6 different
books on a shelf?
Solution
The number of ways to arrange 6 distinct objects
is 6! = 720.
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
16
Arrangements of n Objects Containing
Look-Alikes
The number of distinguishable arrangements of n
objects, where one or more subsets consist of lookalikes (say n1 are of one kind, n2 are of another kind,
…, and nk are of yet another kind), is given by
n!
.
n1 !n2 ! nk !
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
17
Example: Counting Distinguishable
Arrangements
Determine the number of distinguishable
arrangements of the letters of the word INITIALLY.
Solution
9 letters total
3 I’s and 2 L’s
9!
 30240.
3!2!
Copyright © 2016, 2012, and 2008 Pearson Education, Inc.
18