Permutations

A permutation of a set of objects is an arrangement of those objects into a particular order. For example, there are six permutations of the set ${1,2,3}$: $(1,2,3)$, $(1,3,2)$, $(2,1,3)$, $(2,3,1)$, $(3,1,2)$, and $(3,2,1)$. One might define an anagram of a word as a permutation of its letters. 

The 6 permutations of 3 balls

If one has three different colored balls, there are six distinct ways to order them, as shown. These six distinct orderings are as follows: red-green-blue, red-blue-green, green-red-blue, green-blue-red, blue-red-green, and blue-green-red.

The number of permutations of $n$ distinct objects is given by:

 $\displaystyle n \cdot (n − 1) \cdot (n − 2) \cdots 2 \cdot 1$

This is called $n$ factorial and is written $n!$.

In other words, a factorial is to multiply all the numbers from $1$ up to this number. So $5!$ means $1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120$. Thus, $120$ is the number of permutations possible for a set of five distinct objects.

Example

In the game of Solitaire, seven cards are dealt out at the beginning: one face-up, and the other six face-down. A complete card deck has $52$ cards. Assuming that the only card that is seen is the $7$ of spades, how many possible "hands" (the other six cards) can be underneath? What makes this a permutation problem is that the order matters: if an ace is hiding somewhere in those six cards, it makes a difference whether the ace is on the first position, the second, etc. Permutation problems can always be addressed as an example of the multiplication rule, with one small twist.

One stack of cards in a game of solitaire

To find out how many possible combinations of cards there are below the seven of spades, we use the concept of permutations to calculate the possible arrangements of cards.

How many cards might be in the first position, directly under the showing $7$? The answer is 51. That card can be anything except the $7$ of spades.

If any given card is in the first position, how many cards might be in second position? The answer is $50$. The seven of spades and the next card have both been dealt. So there are possible cards left for the second position.

So how many possibilities are there for the first two positions combined? The answer is $51 \cdot 50$.

How many possibilities are there for all six positions? The answer is $51 \cdot 50 \cdot 49 \cdot 48 \cdot 47 \cdot 46$, or approximately $1.3 \cdot 10^{10}$; about $13$ billion possibilities!

This result can be expressed more concisely by using factorials. 

Note that $\frac {7!}{5! }$ can also be written as $\frac {1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6\cdot 7}{1\cdot 2\cdot 3\cdot 4\cdot 5}$. Most of the terms cancel, leaving only $6×7=42$.

Consider another example, $\frac {51!}{45! }$. If all of the terms are written out, the first $45$ terms cancel, leaving $46 \cdot 47 \cdot 48 \cdot 49 \cdot 50 \cdot 51$ in the numerator. Instead of typing into a calculator six numbers to multiply, or sixty numbers or six hundred depending on the problem, the answer to a permutation problem can be found by dividing two factorials. In many calculators, the factorial option is located under the "probability" menu for this reason.

General Considerations

In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order. The study of permutations generally belongs to the field of combinatorics.

Permutations occur, in more or less prominent ways, in almost every domain of mathematics. They often arise when different orderings on certain finite sets are considered, possibly only because one wants to ignore such orderings and needs to know how many configurations are thus identified. For similar reasons, permutations arise in the study of sorting algorithms in computer science.