Permutations and Combinations
Prerequisites
prerequisites
This section shows how to
count the number of different ways that things can be put together.
You will learn how to answer the following types of questions:
- How many different seating arrangements are
possible in a class of students?
- How many different dinners of main dish plus
side dish plus dessert can we build at the diner?
- How many ways can we divide a class into two
teams?
- If we are running an experiment using
five different dosages of a sample drug, how many different
comparisons can we make between different dosages?
Permutations
Suppose that there are three children: Amy, Ben,
and Claude, and you are going to play a game with each of them.
You can only play one game at a time, so you are going to have
to play with the children in a partiular order. There are various
possible orders. You could play with first with Amy, second with
Ben, and third with Claude. Or you could play the children in
a different order. Each particular order is called a permutation.
More generally, a permutation is defined as the arrangement of
the elements of a set of elements in a particular order.
In how many different ways can we arrange Amy,
Ben, and Claude into first, second, and third?
One method of figuring this out is list all possible sqquences,
as shown in Figure 1.
[Figure 1.
Amy, Ben, Claude
Amy, Claude, Ben
Ben, Amy, Claude
Ben, Claude, Amy
Claude, Amy, Ben
Claude, Ben, Amy
]
[Caption 1: Exhaustive list of all six possible permutations]
This method works well if we have a small number
of elements such as the three in this example. It would be quite
time consuming if we had thirty or three hundred instead of just
three. Therefore it is worth developing a mathematical formula
that can determine the number of arrangements. Since we have three
children, there are three possible choices for who can come first.
Suppose that Claude comes first. How many choices are there now
for who can come in second? Since Claude has already been placed,
only two choices remain for who can come in second: in this case,
either Amy or Ben. Suppose that Amy comes in second. How many
choices remain for third place? Since Claude is first and Amy
is second, there is only one outcome remaining: Ben must be in
third. This is illustrated in Figure 2.
[Figure 2.
First Second Third
Ben - Claude
Amy < Claude - Ben
/
/ Amy - Claude
-- Ben < Claude - Amy
\
\
Claude < Amy - Ben
Ben - Amy
]
[Caption 2: 3 choices x 2 choices x 1 choice = 6 possible permutations]
We can choose any student (in our case, among 3) to put in the
first rank. Once the first one is chosen, we can choose from all
the other students (2 remain) for the second rank. Once the second
is chosen, we can choose from all the remaining students (only
1 remains) for the third rank. We still see the same 6 possible
arrangements of three students ranked into first, second, and
third. But using this method, we see that the count of the total
number of arrangements can be determined by multiplying: there
are 3x2x1 = 6 possible arrangements.
When arranging thirty students in order from 1 to 30, we can use
the same method. When placing a student into the first seat, there
are 30 possible choices. Once that student has been placed, we
can choose from any of the remaining 29 students for the second
seat. After those two have been placed, any of the remaining 28
could go into the third seat, and so on. In the end, there are
30x29x28x27x26x25x24x23x22x21x20x19x18x17x16x15x14x13x12x11x10x9x8x7x6x5x4x3x2x1
possible arrangements. (When we are multiplying together all the
numbers from 1 up to 30, the shorthand for this is written ?30!?
and is pronounced ?30 factorial.? To compute 30 factorial quickly
on your calculator, you can use the factorial button, which might
be marked as ?N!?.)
As another example, suppose that we are the scheduler in charge
of arranging the prime-time television lineup for our television
station. The bosses have given us six different half-hour sitcoms,
and we need to arrange them into the six slots from 6pm-9pm. How
many different television lineups are possible?
Similar to the above examples, there are 6! = 6x5x4x3x2x1 = 720
possible television lineups.
But now let?s try a more complicated example. Suppose that the
writers have given us 30 different sitcoms to consider for the
prime-time lineup. There are only 6 available slots, so 24 of
the sitcoms will be left unused. How many different prime-time
lineup arrangements are possible when drawing from 30 different
choices to fill 6 slots?
Let?s break down the lineup into one slot at a time.
If we are filling only the first time slot, 6-6:30, there are
30 different possibilities that we can choose.
If we are filling two slots in order, 6-6:30 and 6:30-7, we now
have 30x29 = 870 different arrangements (permutations) that we
can choose. This is because for each of our 30 different opening
choices, we can choose 29 different follow-up shows, yielding
30x29 different two-sitcom lineups.
If we are filling the first, second, and third positions from
our 30 sitcoms, we have 30x29x28 = 24,360 different permutations.
For six slots, we continue in the same fashion, computing 30x29x28x27x26x25
= 427,418,000 different permutations.
(Notice that this is the same problem as if we are responsible
for selecting the first through sixth seats from among our classroom
of thirty students.)
As shown in Figure 3, when we are multiplying together a decreasing
sequence of numbers, we can compute the answer to our problem
by dividing two different factorials: on the top, we have the
factorial of the total number of sitcoms (30!); on the bottom,
we have the factorial of the total remaining unused sitcoms (24!
= (30-6)!). This is equivalent to multiplying 30x29x?x26x25.
[Figure 3.
30x29x28x27x26x25x 24x23x22x21x20x19x?x3x2x1 30!
427,418,000 = 30x29x28x27x26x25 = ---------------------------------------------------------
= -----
24x23x22x21x20x19x?x3x2x1 24!
]
[Caption 3: Number of permutations of 6 sitcoms chosen in order
from a pool of 30.]
Hence the formula for computing the Total Number of Permutations
ranking M individuals out of a pool of N choices is given by:
P(M,N) = N! / (N-M)!.
In our example of Figure 3, P(6,30) = 30!/(30-6)! = 30!/24! =
427,418,000.
Sample Exercise:
Suppose that in a horse-race that has 8 different horses, we would
like to count the total number of different possible ?trifectas.?
The trifecta is the exact arrangement of the first, second, and
third place finishers in the horserace. For example, ?8-3-2? would
be the trifecta where horse #8 comes in first place, horse #3
takes second, and horse #2 takes third. How many different trifectas
are possible?
Solution to Sample Exercise:
The number of ways to choose 3 horses in order from a pool of
8 horses is given by 8x7x6, or P(3,8) = 8!/5!. So 336 different
trifectas are possible.
Notice that in this case, we are simply counting the total number
of different trifectas. Perhaps we own the trifecta-ticket printing
machine at this racetrack. The races always run 8 horses, and
we are in charge of printing trifecta tickets. We?d like to know
how many distinct kinds of trifecta tickets that we might be required
to print for this racetrack. However, in any particular race,
not all of the first-second-third place arrangements are equally
likely ? in fact many of these combinations would be outlandishly
unlikely! Counting permutations is simply about counting the different
arrangements, without any regard to their likelihood (or unlikelihood).
With permutations, we are very concerned about the rank order
of our selection. In the horse racing sample exercise, if the
horses in the race above finish in the order: #8, #3, #2, then
your trifecta ticket 8-2-3 is completely worthless. Only the 8-3-2
trifecta ticket wins.
Sometimes, however, we don?t care about the rank order of our
chosen items. In the sitcom example, perhaps we are not choosing
the exact lineup, but rather we are simply choosing the 6 sitcoms
out of 30 that will be aired, leaving 24 unused. (Someone else
will be in charge of devising the exact lineup.) Instead of giving
a rank ordering, we are simply responsible for deciding whether
each sitcom is ?in? or ?out.? How many different seasons are possible
? in other words, how many different ways can we identify six
winners from a pool of thirty candidates?
Combinations
----
--scott
_________________________________________________________________
Get rid of annoying pop-up ads with the new MSN Toolbar ? FREE!
http://toolbar.msn.com/go/onm00200414ave/direct/01/
|