Permutations & Combinations
The origin of permutation
is the Latin word mutare which related to change. The per
prefix is an emphsis of complete or extreme change. Here we reprint the earlist use of the word, as found on Jeff Miller's wonderful web site :PERMUTATION first appears in print with its present meaning in Ars Conjectandi by Jacques Bernoulli: "De Permutationibus. Permutationes rerum voco variationes..." (Smith vol. 2, page 528).
Earlier, Leibniz had used the term variationes and Wallis had adopted alternationes (Smith vol. 2, page 528).
In math we use the word
to apply to changes in sets of objects, and most usually to their order.
For example the set {x,y,z} can have its order changed by switching the
positions of any two of the elements. Here are the six permutations
of this set:
{a,b,c}; {a,c,b};{b,a,c};{b,c,a};{c,a,b};{c,b,a}
. For any set of n objects, there are n! permutations of the complete
set.
A permutation which only
exchanges two elements is often called a transposition. It is known
that every permutation can be found from any other by a string of transpositions.
The notation to switch the first and third element in a set is (1,3).
We might write {a,b,c} (1,3)
= {c,b,a} . Here is the list of permutations again with the order adjusted
with the transpositions to generate each from the one before it.
{a,b,c} (2,3)
{a,c,b} (1,3)
{b,a,c} (2,3)
{b,c,a} (1,2)
{c,b,a} (2,3)
{c,a,b}. There are more complicated symbol systems to produce permutations
of more than two elements at a time.
Sometimes we
wish to work with only a part of the set. For example we may want
to know how many two letter "words" can be made with the letters from the
set {a,b,c,d,e}. The symbol for this number is frequently written
as nPr, or in this case, 5P2. It is read "the number of permutations
of five things taken two at a time." You have to appreciate the beauty
of a system that allows three letters to say so much. The formula
to calculate the numerical value of nPr is 
for 5P2 we get 5!/(5-2)! = 20, so there should be 20 two letter "words"
possible from the five letters above, and here they are: ab, ac, ad, ae,
bc, bd, be, cd, ce, de. "Hey", you scream, that is only ten, but
they can each be written backward to get the other ten.
The difference between permutations
and combinations is that in combinations, the order is not significant.
With the same combination of three letters, we can find six permutations
of the letters. The word combine, from which combination derives,
is built of the Latin prefix com, for together, and bini
a special form of the Latin root for two, bi. Bini
would be similar to our word pair, and the idea of combining was to put
together two at a time.
The number of combinations
of n things taken r at a time is written as nCr, similar to the symbol
for permutations. It is also frequently written as 
.
The numeric calculation of nCr
is found by dividing nPr by r! This leads to the equation 
.
So for 5C2 we get only ten possible selections.
If you want to pursue the
idea of combinations and permutations in greater depth, find out how they
relate to Pascal's Triangle, and find links to many
more ideas related to this topic, follow this link to the
Dr. Math archives .