Griffiths D. Head First Statistics
Подождите немного. Документ загружается.
you are here 4 251
permutations and combinations
In the last race, you had a 1/6
probability of predicting the top
finishers correctly. But let’s see how
you fare in the novelty race; it’s a
Statsville tradition.
It’s time for the novelty race
The Statsville Derby is unusual in that not all of the animals
taking part in the races have to be horses. In the next race,
three of the contenders are zebras, and they’re racing
against three horses.
In this race, it’s the type of animal that matters rather
than the particular animal itself. In other words, all we’re
interested in is which sort of animal finishes the race in
which position. The question is, how many ways are there
of ordering all the animals by species?
The Derby’s offering a special bet: if you can predict
whether a horse or zebra will finish in each place, the payout
is 15:1. The question is, should you make this bet?
How would you go about solving this sort of problem? Write down your ideas
in the space below.
252 Chapter 6
So if there are three horses and three zebras in today’s
novelty race, how can we calculate how many different
orderings there are of horses and zebra.
This time we’re only interested in the type of animal,
and not the particular animal itself.
So far we’ve only looked at the number of ways in which we can order
unique objects such as horses, and calculating 6! would be the correct
result if this was what we needed on this occasion.
This time around it’s different. We no longer care about which particular
horse or zebra is in a particular position; we only care about what type
of animal it is.
As an example, if we looked at an arrangement where the three zebras
came first and the three horses came last, we wouldn’t want to count all
of the ways of arranging those three horses and three zebras. It doesn’t
matter which particular zebra comes first; it’s enough to know it’s a
zebra.
For this sort of problem, we
care about which type of
animal is in which position,
but we don’t care about the
name of the animal itself.
I’ll knock the stripes
off those zebras.
That’s easy. There are 6 animals, so
there are 6! ways of ordering them.
Arranging by individuals is different than arranging by type
arranging by type
you are here 4 253
permutations and combinations
We need to arrange animals by type
There are 6! ways of ordering the 6 animals, but the problem with this result is that it
assumes we want to know all possible arrangements of individual horses and zebras.
Let’s start by looking at the zebras. There are 3! ways of arranging the three
zebras, and the result 6! includes each of these 3! arrangements. But since we’re
not concerned about which individual zebra goes where, these arrangements are all
the same. So, to eliminate these repetitions, we can just divide the total number of
arrangements by 3!
We’re classing the 3 zebras as
being alike, so we divide the
number of arrangements by 3!
Next, let’s take the horses. There are 3! ways of arranging the three horses, and the number of
arrangements we have so far includes each of these 3! arrangements. As with the zebras, we
divide the end result by 3! to eliminate duplicate orderings.
This time we’re classing the 3
horses as being alike. There are
3! ways of arranging the horses,
so we divide the total number of
arrangements by 3!
This means that the number of ways of arranging the 6 animals according
to species is
In other words, the probability of betting correctly on the right order in
which the different species finish the race is 1/20.
Turn the page and we’ll look at this in more detail.
6! = 720
3!3! 6
×
6
= 720
36
= 20
There’s a 1/20 chance of
winning, but the payout’s
only 15: 1. I’d stay away
from this bet.
There are 6! animals
altogether...
...but the 3 zebras and 3
horses are alike, so we divide
by the number of ways we
can arrange these like animals
254 Chapter 6
n!
k!
n!
j!k!
We can take this further.
Imagine you want to arrange n objects, where k of one type are alike, and j of
another type are alike, too. You can find the number of possible arrangements by
calculating:
If you have n objects where k are alike the number of
arrangements is given by n!/k!
Imagine you need to count the number of ways in which n objects can be
arranged. Then imagine that k of the objects are alike.
To find the number of arrangements, start off by calculating the number of
arrangements for the n objects as if they were all unique. Then divide by
the number of ways in which the k objects (the ones that are alike) can be
arranged. This gives you:
There are n objects in total.
k of the objects are alike.
There are n objects in total.
j of one type of object are alike,
and so are k of another type.
The number of ways of arranging n objects where j of one
type are alike, and so are k of another type.
In general, when calculating arrangements
that include duplicate objects, divide the total
number of arrangements (n!) by the number of
arrangements of each set of alike objects (j!, k!,
and so on).
Generalize a formula for arranging duplicates
general formula for arranging by type
Arranging by type
If you want to arrange n objects where
j of one type are alike, k of another
type are alike, so are m of another type
and so on, the number of arrangements
is given by
n!
j!k!m!...
Vital StatisticsVital Statistics
you are here 4 255
permutations and combinations
The Statsville Derby have decided to experiment with their races. They’ve decided to hold a race
between 3 horses, 2 zebras and 5 camels, where all the animals are equally likely to finish the
race first.
1. How many ways are there of finishing the race if we’re interested in individual animals?
2. How many ways are there of finishing the race if we’re just interested in the species of animal in each position?
3. What’s the probability that all 5 camels finish the race consecutively if each animal has an equal chance of
winning? (Assume we’re interested in the species in each position, not the individual animals themselves.)
256 Chapter 6
The Statsville Derby have decided to experiment with their races. They’ve decided to hold a race
between 3 horses, 2 zebras and 5 camels, where all the animals are equally likely to finish the
race first.
1. How many ways are there of finishing the race if we’re interested in individual animals?
2. How many ways are there of finishing the race if we’re just interested in the species of animal in each position?
3. What’s the probability that all 5 camels finish the race consecutively if each animal has an equal chance of
winning? (Assume we’re interested in the species in each position, not the individual animals themselves.)
There are 10 animals so there are 10! = 3,628,800 different arrangements.
There are 3 horses, 2 zebras and 5 camels.
Number of arrangements = 10!
3!2!5!
= 3,628,800
6x2x120
= 3,628,800
1,440
= 252
First of all, let’s find the number of ways in which the 5 camels can finish the race together. To do
this, we class the 5 camels as one single object. That way, we’re guaranteed to keep them together.
This means that if we add our 1 group of camels to the 3 horses and 2 zebras, we actually need to
arrange 6 objects
Number of arrangements = 6!
3!2!
= 720
6x2
= 720
12
= 60
Then, to find the probability of this occurring, we just need to divide the number of ways the camels
finish together by all the possible ways the animal types can finish the race, which we calculated above.
The probability of all 5 camels finishing together is therefore 60/252 = 5/21
There are 10 animals.
We treat the 3 horses as being alike, and the 2
zebras, and also the 5 camels.
We treat the 3 horses as being alike, and the 2
zebras. We don’t need to divide by 5! for the 5
camels, as we’re counting them as 1 object.
1 group of camels + 3 horses + 2 zebras
exercise solution
you are here 4 257
permutations and combinations
Q:
Why did you treat the 5 camels as
one object in the last part of the exercise?
Surely they’re individual camels.
A: They’re individual camels, but in the
last part of that problem we need to make
sure we keep the camels together. To do this,
we bundle all the camels together and treat
them as one object.
Q:
It seems like the number of
arrangements for the different objects
has a lot to do with how you group them
into like groups.
A: That’s right. Mastering arrangements
is a skill, but a lot depends on how you think
things through.
The key thing is to think really carefully about
what sort of problem you’re actually trying to
solve and to get lots of practice.
Q:
Are there many races where horses,
zebras and camels all race together?
A: It’s unlikely. But hey, this is Statsville,
and the Statsville Derby runs its own events.
It’s time for the twenty-horse race
The novelty race is over, with the zebras taking the lead.
The next race is between 20 horses.
How would you go about finding the number of ways in which you can pick
three horses out of twenty?
Think you can predict
the top three horses?
If you can, the payout’s
a whopping 1,500 to 1.
258 Chapter 6
The main race is about to begin. There are twenty horses racing, and we need to find
the number of possible arrangements of the top three horses. This way, we can work
out the probability of guessing the exact order correctly.
We can work out the solution the same way we did earlier, by looking at how many
ways there are of filling the first three positions.
Let’s start with the first position. There are 20 horses in total, so this means there are
20 different ways of filling the first position. Once this position has been filled, that
leaves 19 ways of filling the second position and 18 ways of filling the third.
There are 20 horses, so this
means there are 20 ways of
filling the first position, 19 ways
of filling the second, and 18 ways
of filling the third.
20
×
19
×
18 = 6,840
We need a more concise way of solving this sort of
problem.
At the moment we only have three numbers to multiply together, but
what if there were more?
We need to generalize a formula that will allow us to find the total
number of arrangements of a certain number of horses, drawn from a
larger pool of horses.
So the probability of guessing the precise order in which the top three horses
finish the race is 1/6,840.
In this race, we’re not interested in how the rest of the positions are filled, it’s
only the first three positions that concern us. This means that the total number
of arrangements for the top three horses is
That gives us the right answer, but it could get complicated if
there were more horses, or if we wanted to fill more positions.
introducing permutations
How many ways can we fill the top three positions?
you are here 4 259
permutations and combinations
Examining permutations
So how can we rewrite the calculation in terms of factorials?
The number of arrangements is 20
×
19
×
18. Let’s rewrite it and see
where it gets us.
This is the total
number of objects
This is the number of
positions we want to fill
n
P
r
= n!
(n - r)!
20
×
19
×
18 = 20
×
19
×
18
×
(17
×
16
×
...
×
3
×
2
×
1)
(17
×
16
×
...
×
3
×
2
×
1)
= 20!
17!
If we multiply it by 17!/17!, this
will still give us the same answer.
This is the same expression
written in terms of factorials.
This is the same expression that we had before, but this time written in
terms of factorials.
The number of arrangements of 3 objects taken from 20 is called the
number of permutations. As you’ve seen, this is calculated using
In general, the number of permutations of r objects taken from n is the
number of possible way in which each set of r objects can be ordered.
It’s generally written
n
P
r
, where
I never said anything about the
horse order. Just guess which
horses are in the top three and
I’ll make it worth your while...
So if you want to know how many ways there are of ordering r objects
taken from a pool of n, permutations are the key.
Permutations give
the total number
of ways you can
order a certain
number of objects
(r), drawn from
a larger pool of
objects (n).
20!
(20 - 3)!
2,432,902,008,176,640,000
355,687,428,096,000
6,840
=
=
This is the same
answer we got
earlier
260 Chapter 6
What if horse order doesn’t matter
So far we’ve found the number of permutations of ordering three horses taken from a group of
twenty. This means that we know how many exact arrangements we can make.
This time around, we don’t want to know how many different permutations there are. We want
to know the number of combinations of the top three horses instead. We still want to know
how many ways there are of filling the top three positions, but this time the exact arrangement
doesn’t matter.
We don’t need to know the
precise order in which the
horses finish the race, it’s
enough to know which horses
are in the top three.
So how can we solve this sort of problem?
At the moment, the number of permutations includes the number of ways of
arranging the 3 horses that are in the top three. There are 3! ways of arranging each
set of 3 horses, so let’s divide the number of permutations by 3!. This will give us the
number of ways in which the top three positions can be filled but without the exact
order mattering.
The result is
20! 6,840
3!17! 3!
= 1,140
This means that there are 6,840 permutations for filling the first three places in the
race, but if you’re not concerned about the order, there are 1,140 combinations.
With a 1/1,140 chance of winning here,
the odds are way against you. But the
payout is also huge at 1,500:1, so you can
actually expect to come out ahead. It all
depends on how much of a risk taker you are.
introducing combinations
=
= = = = =