Transcript Pascal`s triangle

SECTION 10-4
• Using Pascal’s Triangle
Slide 10-4-1
USING PASCAL’S TRIANGLE
• Pascal’s Triangle
• Applications
Slide 10-4-2
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.
Slide 10-4-3
PASCAL’S TRIANGLE
START
1
1
1
1
1
1
2
3
4
1
1
3
6
4
1
Slide 10-4-4
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.
Slide 10-4-5
PASCAL’S TRIANGLE
row
1
0
1
1
1
2
1
3
1
4
1
5
1
6
7
1
7
2
3
4
5
6
1
3
6
10
15
21
1
4
10
20
35
1
1
5
15
35
1
6
21
1
7
1
and so on
Slide 10-4-6
COMBINATION VALUES IN PASCAL’S
TRIANGLE
The “triangle” possesses many 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.
Slide 10-4-7
COMBINATION VALUES IN PASCAL’S
TRIANGLE
row
0
0C0
1
1C0
1C 1
2
2C0
2C1
2C2
3
3C 0
3C1
3C 2
3C3
4
4C0
4C1
4C2
4C3
4C 4
5 5C0
5C 1
5C2
5C 3
5C4
5C5
and so on
Slide 10-4-8
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
Slide 10-4-9
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.
Slide 10-4-10
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.
Slide 10-4-11
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
Slide 10-4-12