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:

  1. How many different seating arrangements are possible in a class of students?

  2. How many different dinners of main dish plus side dish plus dessert can we build at the diner?

  3. How many ways can we divide a class into two teams?

  4. 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/