# 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, biBini 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 .