Transcript Mathematical Ideas - Millersville University of Pennsylvania

Chapter 11
Counting
Methods
© 2008 Pearson Addison-Wesley.
All rights reserved
Chapter 11: Counting Methods
11.1
11.2
11.3
11.4
11.5
Counting by Systematic Listing
Using the Fundamental Counting Principle
Using Permutations and Combinations
Using Pascal’s Triangle
Counting Problems Involving “Not” and
“Or”
11-4-2
© 2008 Pearson Addison-Wesley. All rights reserved
Chapter 1
Section 11-4
Using Pascal’s Triangle
11-4-3
© 2008 Pearson Addison-Wesley. All rights reserved
Using Pascal’s Triangle
• Pascal’s Triangle
• Applications
11-4-4
© 2008 Pearson Addison-Wesley. All rights reserved
Pascal’s Triangle
The triangular array on the next slide represents
“random walks” that begin at START and proceed
downward according to the following rule. At each
circle (branch point), a coin is tossed. If it lands
heads, we go downward to the left. If it lands tails,
we go downward to the right. At each point, left an
right are equally likely. In each circle the number of
different routes that could bring us to that point are
recorded.
11-4-5
© 2008 Pearson Addison-Wesley. All rights reserved
Pascal’s Triangle
START
1
1
1
1
1
1
2
3
4
1
1
3
6
4
1
11-4-6
© 2008 Pearson Addison-Wesley. All rights reserved
Pascal’s Triangle
Another way to generate the same pattern of numbers
is to begin with 1s down both diagonals and then fill
in the interior entries by adding the two numbers just
above the given position. The pattern is shown on the
next slide. This unending “triangular array of
numbers is called Pascal’s triangle.
11-4-7
© 2008 Pearson Addison-Wesley. All rights reserved
Pascal’s Triangle
row
1
0
1
1
1
2
1
3
1
4
5
1
6
7
1
1
7
2
3
4
5
6
1
3
6
10
15
21
1
1
4
10
20
1
5
15
35
35
and so on
1
6
21
1
7
1
11-4-8
© 2008 Pearson Addison-Wesley. All rights reserved
Combination Values in Pascal’s Triangle
The “triangle” possesses may properties. In
counting applications, entry number r in row
number n is equal to nCr – the number of
combinations of n things taken r at a time.
The next slide shows part of this
correspondence.
11-4-9
© 2008 Pearson Addison-Wesley. All rights reserved
Combination Values in Pascal’s Triangle
row
0
1
2
3
4
5
0C0
1C0
2C0
3C0
4C0
5C0
2C1
3C1
4C1
5C1
1C1
2C2
3C2
4C2
5C2
3C3
4C3
5C3
4C4
5C4
5C5
and so on
11-4-10
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Applying Pascal’s Triangle to
Counting People
A group of seven people includes 3 women and 4 men.
If five of these people are chosen at random, how
many different samples of five people are possible?
Solution
Since this is really selecting 5 from a set of 7. We
can read 7C5 from row 7 of Pascal’s triangle. The
answer is 21
11-4-11
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Applying Pascal’s Triangle to
Counting People
Among the 21 possible samples of five people in the
last example, how many of them would consist of
exactly 2 women?
Solution
To select the women (2), we have 3C2 ways. To
select the men (3), we have 4C3 ways. This gives a
total of
3 C2  4C3
 3  4  12 samples.
11-4-12
© 2008 Pearson Addison-Wesley. All rights reserved
Example: Applying Pascal’s Triangle to
Coin Tossing
If six fair coins are tossed, in how many different
ways could exactly four heads be obtained?
Solution
There are various “ways” of obtaining exactly four
heads because the four heads can occur on different
subsets of coins. The answer is the number of sizefour subsets of a size-six subset. This answer is from
row 6 of Pascal’s triangle:
6 C4
 15.
11-4-13
© 2008 Pearson Addison-Wesley. All rights reserved
Summary of Tossing Six Fair Coins
Number of
Heads n
0
1
2
3
4
5
6
Ways to Have Exactly
n Heads
1
6 C1  6
6 C2  15
6 C3  20
6 C4  15
6 C5  6
6 C6  1
6 C0
© 2008 Pearson Addison-Wesley. All rights reserved
11-4-14