Transcript Counting and Probability

AoPS:
Introduction to
Counting &
Probability
Chapter 5
More with Combinations
Intro
We’ll see how to do some more complicated
problems using combinations and how to use
combinations together with some of our other
counting methods, such as casework and
complementary counting. After that, we’ll move
on to the concept of distinguishablilty.
Paths on a Grid
Problem 5.1:
Each block on the grid shown on the next page is
1 unit by 1 unit. Suppose we wish to walk from
A to B via a 7 unit path, but we have to stay on
the grid – no cutting across blocks.
(a)How many steps to the right do we have to
take?
(b)How many steps up do we have to take?
(c)How many different paths can we take?
Paths on a Grid
We know that we must take a 7 unit path.
B
A
7! = 7 = 35
4!3!
3
Path consists of 4 steps right and 3 steps up and
those steps can be taken in any order.
Paths on a Grid
We know that we must take a 7 unit path.
B
A
So the # of paths is 7C3 = 7 x 6 x 5 = 35.
3x2x1
Exercises
5.2.1 How many paths are there from A to B on
the grid shown, if every step must be up or to the
right?
B
A
Exercises
5.2.1 How many paths are there from A to B on
the grid shown, if every step must be up or to the
right?
B
A
There are 5 steps to the right and 2 steps up. These 7
steps can be made in any order, so the answer is
7
7x6
=
= 21
2
2x1
Exercise 5.2.2
How many paths are there from C to D on
the grid shown, if every step must be down or to
the right?
C
D
Exercise 5.2.2
There are 4 steps to the right and 6 steps down.
These 10 steps can be made in any order, so
C
10 = 10 x 9 x 8 x 7 = 210
4
4x3x2x1
D
Exercise 5.2.3
(a) How many 9-step paths are there from E to G?
E
G
Exercise 5.2.3
(a) How many 9-step paths are there from E to G?
E
G
There are 5 steps right and 4 steps down. These 9
steps can be in any order, so
9 = 9 x 8 x 7 x 6 = 126
4
4x3x2x1
Exercise 5.2.3
(b) How many of those paths pass through F?
E
F
G
From E to F, it is 3 steps to the right and 1 step
down, for a total of 4 4
=
= 4 different paths
1 1
E
F
G
From F to G, it is 2 steps to the right and 3 steps
down, for a total of 5 5 x 4
=
= 10 different paths
2 2x1
E
F
G
From F to G, it is 2 steps to the right and 3 steps
down, for a total of 5 5 x 4
=
= 10 different paths
2 2x1
E
F
So there are 4 x 10 = 40 paths
from E to G through F.
G
More Committee-type Problems
Problem 5.2 Coach Grunt is preparing the 5person starting lineup for his basketball team, the
Grunters. There are 12 players on the team. Two
of them, Ace & Zeppo, are league All-Stars, so
they’ll definitely be in the starting lineup. How
many different starting lineups are possible?
Coach Grunt has to choose 3 players from the
10 players that are remaining after Ace & Zeppo
have been placed in the lineup. The order does
not matter, so the answer is
10 = 10 x 9 x 8 = 120
3
3x2x1
This is a basic combination problem that
you should already know!
Problem 5.3
There are 30 men and 40 women in the Town
Library Club. They wish to form a 7-person
steering committee with 3 men & 4 women. In
how many ways can they form the committee?
There are 30 men and 40 women in the Town
Library Club. They wish to form a 7-person
steering committee with 3 men & 4 women. In
how many ways can they form the committee?
We are selecting 2 separate committees: 3 men
from 30 men total in
30 = 30 x 29 x 28 = 4,060 ways, and
3
3x2x1
There are 30 men and 40 women in the Town
Library Club. They wish to form a 7-person
steering committee with 3 men & 4 women. In
how many ways can they form the committee?
4 women from 40 women total in
40 = 40 x 39 x 38 x 37 = 91,390 ways
4
4x3x2x1
4 women from 40 women total in
40 = 40 x 39 x 38 x 37 = 91,390 ways
4
4x3x2x1
The 2 committees are independent so we can
multiply them together to get the # of ways that
we can form the 7-member committee:
(4,069) (91,390) = 371,043,400.
Problem 5.4
Coach Grunt’s rival team is the Screamers,
coached by Coach Yellsalot. The Screamers also
have 12 players, but two of them, Bob and Yogi,
refuse to play together. How many starting lineups (of 5 players) can Coach Yellsalot make if
the starting lineup can’t contain both Bob and
Yogi?
Solution 5.4
There are at least 2 ways to solve this: casework
or using complementary counting.
3 different cases:
Case 1: Bob starts (and Yogi doesn’t)
Then the coach must choose 4 more players from
the remaining 10 players. So there are 10 lineups
4
that the coach can choose
Solution 5.4
There are at least 2 ways to solve this: casework
or using complementary counting.
3 different cases:
Case 2: Yogi starts (and Bob doesn’t)
Then the coach must choose 4 more players from
the remaining 10 players. So there are 10 lineups
4
that the coach can choose
Case 3: Neither Bob nor Yogi Starts
Then the coach must choose all 5 players from
the remaining 10 players. So there are 10 lineups
5
in this case.
To get the total # of starting lineups, add each case:
10
4
10
+
4
10
+
5
= 210 + 210 + 252 = 672
Complementary Counting
If there are no restrictions then the coach must
choose all 5 players from the entire roster of 12
players which he can do in 12 ways.
5
But then we have to subtract the lineups that are not
allowed, which are the lineups in which both Bob &
Yogi start. This was counted in problem 5.2: the
coach must choose 3 more players from the
remaining 10 players to complete the lineup, and he
can in 10C3 ways.
So the answer to the problem is the total # of
lineups (without restrictions) minus the # of lineups
that are not allowed:
12
5
10
-
3
= 792 – 120 = 672
Problem 5.5
In how many ways can a dog breeder separate his
10 puppies into a group of 4 and a group of 6 if he
has to keep Biter and Nipper, two of the puppies,
in separate groups?
Since Biter and Nipper cannot be in the same group,
subtract the # of ways to form 2 groups with Biter
and Nipper in the same group. This means
Casework.
Case 1: Biter & Nipper in the same group
If they are both in the smaller group, we have to
choose 2 more dogs from the 8 remaining to
complete the smaller group, 8C2 ways or 8 .
2
Warning!
Don’t mistakenly count the possibilities in Case 1 as
8
8 by reasoning that we must choose 2 of 8 for
2 6 the smaller group, and 6 from 8 for the
larger group. These choices are not independent!
Once we pick the 2 dogs for the smaller group, there
is no choice but to put the remaining 6 dogs into the
larger group.
Case 2: Biter & Nipper are in the larger group
If both are in larger group, then choose 4 dogs from
the remaining 8 to compose the smaller group which
can be done 8C4 ways.
To get the # of ways to form groups such that Biter
& Nipper are both in the same group, add the counts
from our 2 cases,
8 + 8
2
4
Case 2: Biter & Nipper are in the larger group
Since these are the cases we don’t want, subtract this
count from the # of ways to form the 2 groups w/o
restrictions.
10
4
-
8
2
+
8
4
=210 – (28 + 70) =112
The other way is to solve this by direct casework.
Case 1: Biter is in smaller group, Nipper is in larger.
To complete smaller, choose 3 more dogs from the
remaining 8, 8C3.
Case 2: Nipper is in larger group, Bitter is in
smaller.
Again to complete the smaller, choose 3 more dogs
from the remaining 8, 8
3
So to get the total count, add 56 + 56 = 112.
Exercises
5.3.1 A Senate committee has 8 Republicans & 6
Democrats. In how many ways can we form a subcommittee with 3 Republicans & 2 Democrats?
Solution
5.3.1 A Senate committee has 8 Republicans & 6
Democrats. In how many ways can we form a subcommittee with 3 Republicans & 2 Democrats?
There are 8 Rep’s and 3 spots for them, so there are
8 = 56 ways to choose Rep’s.
3
There are 6 Dem’s and 2 spot for them, so there are
6 = 15 ways to choose Dem’s. 56 x 15 = 840 ways
2
Exercises
5.3.2 Our school’s girls volleyball team has 14
players, including a set of 3 triplets: Alicia, Amanda,
& Anna. In how many ways can we choose 6 starters
(a)with no restrictions?
(b) if all 3 triplets are in the starting lineup?
(c) if exactly one of the triplets is in the starting
lineup?
(d) if at most one of the triplets is in the starting
lineup?
Solution
5.3.2 Our school’s girls volleyball team has 14
players, including a set of 3 triplets: Alicia, Amanda,
& Anna. In how many ways can we choose 6 starters
(a)with no restrictions?
Choosing 6 starters from 14 players,
14 = 3003 ways.
6
5.3.2 Our school’s girls volleyball team has 14
players, including a set of 3 triplets: Alicia, Amanda,
& Anna. In how many ways can we choose 6 starters
(b) if all 3 triplets are in the starting lineup?
If all triplets are in the starting lineup, choose the 3
remaining starters from the 11 players,
11 = 165 ways.
3
5.3.2 Our school’s girls volleyball team has 14
players, including a set of 3 triplets: Alicia, Amanda,
& Anna. In how many ways can we choose 6 starters
(c) if exactly one of the triplets is in the starting
lineup?
If exactly 1 is in the lineup, we have 3 choices for
which triplet to put in the starting lineup, and then
11 people to choose for the remaining spots. So
3 x 11 = 3 x 462 = 1386.
5
In how many ways can we choose 6 starters
(d) if at most one of the triplets is in the starting
lineup?
Add together the # of lineups with one triplet & with
no triplets. The # of lineups with no triplets is 11
6
= 462, since we must choose 6 starters from the 11
remaining players. When one triplet is in the lineup,
there are 1386 options (part c). So the total is
1386 + 462 = 1848.
Exercises
5.3.3 Suppose we want to divide the 10 dogs from
Problem 5.5 into 3 groups, one with 3 dogs, one
with 5 dogs, and one with 2 dogs. How many ways
can we form the groups such that Biter is in the
3-dog group and Nipper is in the 5-dog group?
Solution
5.3.3 Suppose we want to divide the 10 dogs from
Problem 5.5 into 3 groups, one with 3 dogs, one
with 5 dogs, and one with 2 dogs. How many ways
can we form the groups such that Biter is in the
3-dog group and Nipper is in the 5-dog group?
Place Biter in the 3-dog group & Nipper in the 5-dog
group. This leaves 8 dogs remaining to put in the last
2 spots of Biter’s group, which is
8 ways.
2
Solution
Place Biter in the 3-dog group & Nipper in the 5-dog
group. This leaves 8 dogs remaining to put in the last
2 spots of Biter’s group, which is
8 ways.
2
Then there are 6 dogs remaining for the last 4 spots
in Nipper’s group, which is
6 ways.
2
Solution
The remaining 2-dog group takes the last 2 dogs. So
the total # of possibilities is
8 x 6 = 420.
2
4
Exercises
5.3.4 We call a number a descending number if each
digit is strictly smaller than the digit that comes
before it. For example, 863 is a descending #. How
many 3-digit descending numbers are there?
Solution
5.3.4 We call a number a descending number if each
digit is strictly smaller than the digit that comes
before it. For example, 863 is a descending #. How
many 3-digit descending numbers are there?
For every 3 different digits, there is one corresponding
descending #, which is just the digits in descending
order. So the answer is the # of combinations of 3
different digits, which is
10 = 120.
3
Exercises
5.3.5 We call a number a mountain number if its
middle digit is strictly larger than any other digit.
before it. For example, 284 is a mountain #. How
many 3-digit mountain numbers are there?
Solution
5.3.5 We call a number a mountain number if its
middle digit is strictly larger than any other digit.
before it. For example, 284 is a mountain #. How
many 3-digit mountain numbers are there?
Case 1: numbers of the form xyz (x ≠ 0)
Any pair of nonzero digits has a corresponding
palindrome (xyz) mountain #, so the # of these is
9
2
= 36.
Solution
5.3.5 We call a number a mountain number if its
middle digit is strictly larger than any other digit.
before it. For example, 284 is a mountain #. How
many 3-digit mountain numbers are there?
Case 2: numbers of the form xyz (z ≠ 0, x ≠ z)
Any group of 3 nonzero digits (y > x > z > 0)
has 2 corresponding mountain #’s (xyz and zyx),
so the # of these is
2x
9
3
= 168.
Solution
5.3.5 We call a number a mountain number if its
middle digit is strictly larger than any other digit.
before it. For example, 284 is a mountain #. How
many 3-digit mountain numbers are there?
Case 3: numbers of the form xy0 (x ≠ 0, y ≠ 0)
Any pair of nonzero digits has a corresponding
mountain # in the form xy0,
so there are
9
2
= 36.
Solution
5.3.5 We call a number a mountain number if its
middle digit is strictly larger than any other digit.
before it. For example, 284 is a mountain #. How
many 3-digit mountain numbers are there?
So the total # of mountain numbers is
36 + 168 + 36 = 240.
Distinguishability
Distinguishable means to tell items apart and
indistinguishable means items cannot be told
apart.
A B
C
D
Box 1
4 distinguishable balls and
Box 2
2 distinguishable boxes
Distinguishability
Distinguishable means to tell items apart and
indistinguishable means items cannot be told
apart.
A B
C
D
4 distinguishable balls and
2 indistinguishable boxes
Distinguishability
Distinguishable means to tell items apart and
indistinguishable means items cannot be told
apart.
Box 1
4 indistinguishable balls and
Box 2
2 distinguishable boxes
Distinguishability
Distinguishable means to tell items apart and
indistinguishable means items cannot be told
apart.
4 indistinguishable balls and 2 indistinguishable boxes
Problem 5.6
How many ways are there to put 4 distinguishable
balls into 2 distinguishable boxes?
Solution
For each ball, there are 2 choices of which box to
place it in. Since this choice is independent for
each of the 4 balls, multiply the # of choices
together.
A B
C
D
Box 1
Box 2
So there are 24 = 16 ways to place 4
distinguishable balls into 2 distinguishable boxes.
Problem 5.7
How many ways are there to put 4 distinguishable
balls into 2 indistinguishable boxes?
Problem 5.7
How many ways are there to put 4 distinguishable
balls into 2 indistinguishable boxes?
A B
C
D
Problem 5.7
We don’t care which box is which, we only care
about which balls are together and which ones
aren’t. There are 2 ways we can do this count.
1st: take the count from Prob 5.6 & divide by the #
of ways to arrange the boxes – 2! = 2 ways so
A B
C
D
there are 16/2 = 8 ways to arrange 4
distinguishable balls into 2 indistinguishable
boxes.
Problem 5.7
WARNING:
This method does not generalize to more
than 2 boxes, as you will see in Exercise 5.4.2.
A B
C
D
Problem 5.7
Alternatively, this could have been solved by
casework.
Case 1: One box has 4 balls, the other has 0 balls
There is only 1 way to do this – put all the balls into
A B
C
D
one box (it doesn’t matter which box, since they
are indistinguishable).
Problem 5.7
Alternatively, this could have been solved by
casework.
Case 2: One box has 3 balls, the other has 1 ball
The choice here is which ball is by itself in a box &
A B
C
D
there are 4 choices.
Problem 5.7
Case 3: Each box has 2 balls
At 1st glance it looks like we have to choose 2 balls
from the total of 4 balls to go into the 1st box, &
then the remaining 2 balls will go into the 2nd box.
A B
C
D
So there are 4C2 = 6 choices.
However, this overcounts the choices by a factor
of 2.
Problem 5.7
Case 3: Each box has 2 balls
For Example: Look at balls A, B, C, & D. If we
1st choose A & B, then one box has A, B, and the
other has C, D.
A B
C
D
Problem 5.7
Case 3: Each box has 2 balls
But this is exactly the same situation as if we had
originally put C, D in the 1st box and A, B in the
2nd box,
A B
C
D
so divide by
2,
giving 6/2 = 3 possibilities
Problem 5.7
To get the total number of possibilities, add the
counts from the 3 cases: 1 + 4 + 3 = 8
ways to arrange 4 distinguishable balls into
2 indistinguishable boxes.
A B
C
D
Problem 5.7
WARNING:
This casework approach is not quite as simple
if there are 3 or more boxes, as will be
demonstrated in Exercise 5.4.2.
A B
C
D
Problem 5.8
How many ways are there to put 4 indistinguishable
balls into 2 distinguishable boxes?
Box 1
Box 2
Problem 5.8
How many ways are there to put 4 indistinguishable
balls into 2 distinguishable boxes?
Since the balls are indistinguishable, the only thing
to keep track of is how many balls are in each box.
In this case, the cases can be listed:
Box 1
Box 2
Problem 5.8
How many ways are there to put 4 indistinguishable
balls into 2 distinguishable boxes?
Since the balls are indistinguishable, the only thing
to keep track of is how many balls are in each box.
In this case, the cases can be listed:
Box 1
Box 2
put either 0, 1, 2, 3, 4 balls into the 1st box, & the
rest into the 2nd box.
Problem 5.8
Since the balls are indistinguishable, the only thing
to keep track of is how many balls are in each box.
In this case, the cases can be listed:
put either 0, 1, 2, 3, 4 balls into the 1st box, & the
rest into the 2nd box.
Box 1
Box 2
So there are 5 ways to arrange 4 indistinguishable
balls into 2 distinguishable boxes.
Problem 5.9
How many ways are there to put 4 indistinguishable
balls into 2 indistinguishable boxes?
In this problem, it is only necessary to count the # of
ways to split 4 items into 2 groups. There are only
3 ways:
{4, 0}, {3, 1} & {2, 2}
So there are only 3 ways to put 4 indistinguishable
balls into 2 indistinguishable boxes.
In these four problems, it is clear that
distinguishability matters. Nothing to memorize.
You should be able to use logic on any given
problem to figure out how to account for the
distinguishability and/or indistinguishability of
what you are counting. The purpose of problems
5.6-5.9 is to make it clear that there is a difference.
Exercises
5.4.1 How many ways are there to put 5 balls in
2 boxes if
(a) the balls are distinguishable and the boxes are
distinguishable?
(b) the balls are distinguishable but the boxes are
not?
(c) the balls are not distinguishable but the boxes
are
(d) the balls are not distinguishable and neither
are the boxes?
Solutions
5.4.1 How many ways are there to put 5 balls in
2 boxes if (a) the balls are distinguishable and the
boxes are distinguishable?
There are 2 different boxes, so each of the 5 balls
can be placed in 2 different locations. So the
answer is 25 = 32.
Exercises
5.4.1 How many ways are there to put 5 balls in
2 boxes if (b) the balls are distinguishable but th
boxes are not?
Since the boxes are indistinguishable, there are 3
possibilities for arrangements of the # of balls in
each box:
Case 1: 5 balls in one box, 0 in the other box. We
must choose 5 balls to go in one box, which can be
done in 5C5 ways = 1 way.
Exercises
5.4.1 How many ways are there to put 5 balls in
2 boxes if (b) the balls are distinguishable but th
boxes are not?
Since the boxes are indistinguishable, there are 3
possibilities for arrangements of the # of balls in
each box:
Case 2: 4 balls in one box, 1 in the other box. We
must choose 4 balls to go in one box, which can be
done in 5C4 ways = 5 ways.
Exercises
5.4.1 How many ways are there to put 5 balls in
2 boxes if (b) the balls are distinguishable but th
boxes are not?
Since the boxes are indistinguishable, there are 3
possibilities for arrangements of the # of balls in
each box:
Case 3: 3 balls in one box, 2 in the other box. We
must choose 3 balls to go in one box, which can be
done in 5C3 ways = 10 ways.
Exercises
5.4.1 How many ways are there to put 5 balls in
2 boxes if (b) the balls are distinguishable but th
boxes are not?
This gives a total of 1 + 5 + 10 = 16 arrangements.
Also note that every arrangement of balls when the
boxes are indistinguishable is counted twice in the
distinguishable case. So simply divide the answer
from part (a) by 2. However, this doesn’t work if
there’s more than 2 boxes (as we’ll see later).
Exercises
5.4.1 How many ways are there to put 5 balls in
2 boxes if (c) the balls are distinguishable but th
boxes are not?
Since the balls are indistinguishable, we need only
count the # of balls in the distinguishable boxes.
we can put 5, 4, 3, 2, 1, or 0 balls in Box #1 (and
the rest go in Box #2). So there are 6 different
arrangements.
Exercises
5.4.1 How many ways are there to put 5 balls in
2 boxes if (d) the balls are distinguishable but th
boxes are not?
Since both balls & boxes are indistinguishable, we
can arrange them with 5 in one and 0 in the other,
4 in one and 1 in the other, or 3 in one and 2 in the
other, for a total of 3 different arrangements.
Exercise 5.4.2
How many ways are there to put 5 balls in 3 boxes
(a) the balls are distinguishable and the boxes are
distinguishable?
(b) the balls are distinguishable but the boxes aren’t
(c) the balls are not distinguishable but the boxes
are
(d) the balls are not distinguishable and neither are
the boxes
Exercise 5.4.2
How many ways are there to put 5 balls in 3 boxes
(a) the balls are distinguishable and the boxes are
distinguishable?
There are 3 different boxes, so each of the 5 balls
can be placed in 3 different locations, so the answer
is 35 = 243.
Exercise 5.4.2
How many ways are there to put 5 balls in 3 boxes
(b) the balls are distinguishable but the boxes aren’t
Since the boxes are indistinguishable, there are 5
different cases for arrangements of the # of balls in
each box: (5,0,0), (4,1,0), (3,2,0), (3,1,1), or (2,1,1)
(b) the balls are distinguishable but the boxes aren’t
Since the boxes are indistinguishable, there are 5
different cases for arrangements of the # of balls in
each box: (5,0,0), (4,1,0), (3,2,0), (3,1,1), or (2,1,1)
(5,0,0): There is only 1 way to put all 5 balls in one
box
(b) the balls are distinguishable but the boxes aren’t
Since the boxes are indistinguishable, there are 5
different cases for arrangements of the # of balls in
each box: (5,0,0), (4,1,0), (3,2,0), (3,1,1), or (2,1,1)
(5,0,0): There is only 1 way to put all 5 balls in one
box
(4,1,0): There are 5C4 = 5 choices for 4 balls in one
box
(b) the balls are distinguishable but the boxes aren’t
Since the boxes are indistinguishable, there are 5
different cases for arrangements of the # of balls in
each box: (5,0,0), (4,1,0), (3,2,0), (3,1,1), or (2,1,1)
(5,0,0): There is only 1 way to put all 5 balls in one
box
(4,1,0): There are 5C4 = 5 choices for 4 balls in one
of the boxes
(3,2,0): There are 5C3 = 10 choices for 3 balls in one
of the boxes
(b) the balls are distinguishable but the boxes aren’t
(5,0,0), (4,1,0), (3,2,0), (3,1,1), or (2,1,1)
(5,0,0): There is only 1 way to put all 5 balls in one
box
(4,1,0): There are 5C4 = 5 choices for 4 balls in one
of the boxes
(3,2,0): There are 5C3 = 10 choices for 3 balls in one
of the boxes
(3,1,1): There are 5C3 = 10 choices for 3 balls in one
of the boxes
(2,2,1): There are 5C2 = 10 options for one of the
boxes with 2 balls, then 3C2 = 3 options for the 2nd
box with 2 balls, & one option remaining for the 3rd.
But, since the boxes with 2 balls are indistinguishable, we are counting each pair of balls twice, and
must divide by 2. So there are (10 X 3) ÷ 2 = 15
arrangements of balls as (2,2,1). Thus the total # of
arrangements for 3 indistinguishable boxes and 5
distinguishable balls is 1 + 5 + 10 + 10 + 15 = 41.
Exercise 5.4.2
How many ways are there to put 5 balls in 3 boxes
(c) the balls are not distinguishable but the boxes
are
Since the balls are indistinguishable, we must only
count the # of balls in the different boxes.
There are 3 ways to arrange the balls as (5, 0, 0):
box 1 can have 5, box 2 can have 5, box 3 can have
5.
There are 3! = 6 ways to arrange (4, 1, 0) and
3! = 6 ways to arrange (3, 2, 0); in each case we
must choose 1 of the 3 boxes to have the largest #
of balls, and also one of the remaining 2 boxes to
be left empty.
However, there are only 3 ways to arrange (3, 1, 1)
and 3 ways to arrange (2, 2, 1); in each case, we
must choose one box to have the “different” # of
balls (3 in the (3, 1, 1) case and 1 in the (2, 2, 1)
case). This gives a total of 3 + 6 + 6 + 3 + 3 = 21
arrangements.
Exercise 5.4.2
How many ways are there to put 5 balls in 3 boxes
(d) the balls are not distinguishable and neither are
the boxes
The ways to arrange indistinguishable balls into
indistinguishable boxes only depends on the # of
balls in the boxes. The ways to do this are (5, 0, 0),
(4, 1, 0), (3, 2, 0), (3, 1, 1), (2, 2, 1).
There are 5 ways.
Review Problems
5.10 In the diagram shown
(a) how many paths are there from A to B? (Assume
all paths only go up and to the right.)
(b) how many paths are there from A to C?
(c) how many paths are there from C to B?
(d) how many paths are there from A to B passing
through C?
B
C
A
Solutions
5.10 In the diagram shown
(a)how many paths are there from A to B? (Assume all
paths only go up and to the right.)
There are 5 steps to the right and 4 steps up. These 9
steps can be made in an order, so the answer is
9C4 = 126.
B
C
A
Solutions
5.10 In the diagram shown
(b) how many paths are there from A to C?
There is 1 step to the right and 2 steps up. These 3
steps can be made in any order, so the answer is
3C1 = 3.
B
C
A
Solutions
5.10 In the diagram shown
(c) how many paths are there from C to B?
There are 4 steps to the right and 2 steps up. These 6
steps can be made in any order, so the answer is
6C4 = 15.
B
C
A
Solutions
5.10 In the diagram shown
(d) how many paths are there from A to B passing
through C?
There are 3 paths from A to C and 15 paths from C to
B, so there are 3 X 15 = 45 paths from A to B through
C.
B
C
A
Review Problems
5.13 My school’s math club has 6 boys and 8
girls. I need to select a team to send to the state
math competition. We want 6 people on the team.
In how many ways can I select the team:
(a)without restrictions?
(b)to have 3 boys and 3 girls?
(c)to have more girls than boys?
Solutions
We want 6 people on the team.
In how many ways can I select the team:
(a)without restrictions?
With no restrictions, we are merely picking 6 out
of 14. This is 14C6 = 3003.
Solutions
We want 6 people on the team.
In how many ways can I select the team:
(b) to have 3 boys and 3 girls?
We are picking 3 boys out of 6, so there are
6C3 = 20 options for the boys on the team. We are
picking 3 girls out of 8, so there are 8C3 = 56
options for the girls on the team. This gives a total
of 20 X 56 = 1120 choices.
Solutions
(c) to have more girls than boys?
We do this problem similarly to part (b), except
with 3 cases.
Case 1: 4 girls, 2 boys on the team.
With 4 girls on the team, there are 8C4 = 70 ways
to pick the girls, & 6C2 = 15 ways to pick the boys
for a total of 70 X 15 = 1050.
Solutions
(c) to have more girls than boys?
We do this problem similarly to part (b), except
with 3 cases.
Case 2: 5 girls, 1 boy on the team.
With 5 girls on the team, there are 8C5 = 56 ways
to pick the girls, & 6C1 = 6 ways to pick the boy
for a total of 56 X 6 = 336.
Solutions
(c) to have more girls than boys?
We do this problem similarly to part (b), except
with 3 cases.
Case 3: 6 girls on the team.
With 6 girls on the team, there are 8C6 = 28 ways
to pick the girls on the team.
This gives us a sum of 1050 + 336 + 28 = 1414.
Review Problems
5.14 The Sagebrush student council has 6 boys
and 6 girls as class representatives. Two
committees, each consisting of 2 boys & 2 girls,
are to be created. If no student can serve on both
committees, how many different combinations of
committees are possible? (Source: MATHCOUNTS)
Solution
To make the 1st committee, we choose 2 boys in
6C2 = 15 ways and 2 girls in 6C2 = 15 ways, for a
total of 15 x 15 = 225 possible committees. Then
to make the 2nd committee, we choose 2 more
boys in 4C2 = 6 ways & 2 more girls in 4C2 = 6
ways for a total of 6 x 6 possibilities. So the # of
ways to form 2 committees like this is 225 x 36
=
8100.
Solution
But this counts each pair of committees twice
(in other words, there is no “first” committee or
“second” committee), so we must divide by 2 to
get the final answer of 8100 ÷ 2 = 4050 pairs of
committees.
Challenge Problem
5.22 Twenty married couples are at a party. Every
man shakes hands with everyone except himself and
his spouse. Half of the women refuse to shake hands
with any other women. The other 10 women all
shake hands with each other (but not with themselves). How many handshakes are there at the
party?
Solution
20 men shake 38 hands each (not themselves or
spouses), so combined they shake 760 hands. 10
women shake only 19 hands (all the men but their
husbands and the 9 other friendly women), so
women shake a total of 10 x 19 + 10 x 28 = 470
hands. This means a total of 1230 hands have been
shaken. However, each handshake has been counted
twice, so we divide by 2 and see that there are 615
handshakes.
Challenge
5.23 Five different circles are drawn in a plane.
What is the maximum number of different points
at which the circles can meet?
Solution
Each circle can meet each other circle in at most
2 points. Draw five circles such that each circle
intersects with every other circle twice, and so
that no 3 circles intersect at the same point. Since
there are 5C2 = 10 pairs of circles, and 2
intersections per pair of circles, there are
10 x 2 = 20 intersections.
This ends Chapter 5