Permutations and combinations
When we talk of permutations and combinations in everyday talk we often use the two terms interchangeably. In mathematics, however, the two each have very specific meanings, and this distinction often causes problems.
In brief, the permutation of a number of objects is the number of different ways they can be ordered; i.e. which is first, second, third, etc. If you wish to choose some objects from a larger number of objects, the way you position the chosen objects is also important. With combinations, on the other hand, one does not consider the order in which objects were chosen or placed, just which objects were chosen. We could summarise permutations and combinations (very simplistically) as
Permutations - position important (although choice may also be important)
Combinations - chosen important,
which may help you to remember which is which.
Pictures on a wall
Suppose you have to put some pictures on the wall, and suppose you only have two pictures: A and B.
You could hang them
Order 1 
or Order 2 Not much of a choice, but it leads on to the difference between permutations and combinations.
THE IMPORTANT DIFFERENCE
As mentioned above, there is an important difference between permutations and combinations. In this case, for permutations the order of events is important: order 1 is different from order 2. For combinations, however, it does not matter which picture was hung first. In this example there are two permutations (A, B ? B, A), but only one combination (A, B = B, A).
Another way that you may find useful to help you remember is to consider a combination lock. On combination locks you have to turn dials with numbers on so a particular number is given, e.g. '1, 2, 3, 4'. But they do not unlock when if the order is changed (e.g. 2, 1, 3, 4). In this case the order is important. So combination locks should not be called combination locks but 'permutation' locks.
A permutation lock! Now we know the difference between combinations and permutations let us consider a more complicated picture-hanging problem. First we will look at permutations.
Two company, three's a crowd!
This time you have three pictures, called, not surprisingly, A, B and C. How many different permutations are there for you to hang your works of art? A worrying problem indeed! Let's hang them up.
When we hang the first picture we can choose from all three.
When we get to the next picture we have only two to choose from
Finally, for the last picture there isn't a choice ? it's the one that remains. So we get the six permutations
Now this can be worked through, but what if we had 10 pictures. How many permutations would that be? Time for some maths to make it easier.
For the first picture you had a choice of three. For the second picture you had a choice of two and then you had the last picture, with Hobson's choice (no choice!). Written algebraically this is 3 × 2 × 1. For large numbers this is very time consuming to write out, which is why mathematicians use factorial notation.
A bit harder
What happens if we did have 10 pictures and wanted to choose our three most favourite to hang up? How many permutations would we have then?
For the first picture on the wall we could choose from all ten. For the next we could choose from the remaining nine, and for the third choice we could pick one from eight. 10 × 9 × 8 = 720.
For this choice of pictures we have 720 permutations, but this isn't 10!.
10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3628800
We used the first three terms (10 × 9 × 8) but not the rest (7 × 6 × 5 × 4 × 3 × 2 × 1). But what we can do is work out 10! and then divide by the other bits:
The final term is much easier than it it looks at first. It relates the number of items to choose from to the number of choices we made (hanging 3 pictures out of 10).
Not surprisingly mathematicians have some shorthand for this too:
where n is the number of different objects and r of them are to be arranged.
Combinations
So far, we have considered hanging pictures on a wall where the order they are hung is important. But what if the order is not important? Consider the hanging of the three pictures above, we had six permutations. But the three pictures were the same in the each permutation, they were all pictures A, B and C, however they were placed. They were only one combination. We had 3! permutations from three pictures and one combination. If you like, these three pictures made one set, and the same is true for each group of three pictures.
Consider the problem of choosing three pictures from a set of ten. If we took the first three pictures (1, 2 and 3) we could arrange these in six different ways (permutations), as we did with the three pictures A, B and C. Now, if we take the next possible set of three: 2, 3 and 4, we can arrange these in six different permutations. Likewise for all the other sets of three pictures; each set of three can be arranged in six different ways, i.e. each set of three pictures will have six permutations. We know from the example above that there are 720 permutations when choosing three pictures from ten. And each set of three chosen can be arranged in 3! different ways. So the number of sets of three (i.e. the number of combinations) is 720 ÷ 3! = 120.
. In the same way that permutations have shorthand, combinations have similar shorthand. All we have to do is divide the number of permutations by the number of permutation in each set. So, the right-hand side of the following equation is the same as the equation for the number of permutations except for an additional r! term in the divisor (which corrects for the number of permutations of each set). Note, also, that the P (for permutation) is replaced by C (for combination).
. If you have a scientific calculator you should see these labelled (on some calculators they are separate keys, on others they are second-function keys). In general, you enter the number of items to choose from (n) then the nCr or nPr button and then the number of items to choose (r).
Circular permutations
They are ordered arrangements of objects in a circle. While order is still considered, a circular permutation is not considered to be distinct from another unless at least one object is preceded or succeeded by a different object in both permutations. In the set of objects, one object can be fixed, and the other objects can be arranged in different permutations. Thus, the number of permutations of n distinct objects that are arranged in a circle is (n-1) !.
EX. There are (6 - 1)! = 5! = 120 ways to seat 6 persons at a circular dinner table.
Back to Community Shelf
8 Nickels awarded!![[Post New]](/templates/default/images/icon_minipost_new.gif){kind=icon}
132
