Permutations and combinations

This article is an elementary introduction to permutations and combinations in combinatorial mathematics.

Combinations

In familiar terms, a combination is an un-ordered selection made from a group of objects. For example, suppose you have fifty-two playing cards, and select five cards for a poker hand. It would not matter in which order the cards were drawn, because you could rearrange them in your hand.

In more formal terms, in combinatorics, a combination is a subset. In a set, the order does not matter. These are represented usually with curly braces: {2, 4, 6}. With sets, since order does not matter, you are only interested in what is present, not in what order. Thus,

{2, 4, 6} = {6, 4, 2}.

Also, {1, 1, 1} is the same as {1} because a set is defined by its elements; they don't usually appear more than once. See the article on combinations for more on this.

Permutations

A permutation, on the other hand, is an ordered selection made from a group of objects. For example, if you look at credit card codes you must also look at the order. The order 5-3-7-5 is different from 3-7-5-5: the order in which you pick your numbers is significant.

Now suppose you have these objects:

1, 2, 3

Here is a list of all permutations of those, using three numbers per line:

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

The article on permutations contains greater detail.

Repetitions

Both combinations and permutations have variants where some objects appear more than once (that is, they have some repetition). For example, if you wanted a combination of twelve fruits and you had 20 to choose from, you should be able to pick more than one fruit type.

Summary of formulae

Permutation with repetition

When order matters and an object can be chosen more than once then the number of permutations is:

$n^{r}\,$

Where n is the number of objects from which you can choose and r is the number to be chosen.

For example, if you have the letters A, B, C, and D and you wish to discover the number of ways to arrange them in three letter patterns (trigrams) you find that there are 4³ or 64 ways. This is because for the first slot you can choose any of the four values, for the second slot you can choose any of the four, and for the final slot you can choose any of the four letters. Multiplying them together gives the total.

Permutation without repetition

When the order matters and each object can be chosen only once, then the number of permutations is:

${\frac {n!}{(n-r)!}}$

Where n is the number of objects from which you can choose, r is the number to be chosen and ! is the standard symbol meaning factorial.

For example, if you have five people and are going to choose three out of these, you will have 5!/(5-3)! = 60 permutations.

Note that if n = r (meaning number of chosen elements is equal to number of elements to choose from) then the formula becomes

${\frac {n!}{(n-n)!}}={\frac {n!}{0!}}=n!$ when 0! = 1! = 1

For example, if you have three people and you want to find out how many ways you may arrange them it would be 3! or 3 × 2 × 1 = 6 ways. The reason for this is because you can choose from 3 for the initial slot, then you are left with only two to choose from for the second slot, and that leaves only one for the final slot. Multiplying them together gives the total.

Combination without repetition

When the order does not matter, but each object can be chosen only once, the number of combinations is:

${{n!} \over {r!(n-r)!}}={n \choose r}$

Where n is the number of objects from which you can choose and r is the number to be chosen.

For example, if you have ten numbers and wish to choose 5 you would have 10!/5!(10 − 5)! = 252 ways to choose.

Combination with repetition

When the order does not matter and an object can be chosen more than once, then the number of combinations is:

${{(n+r-1)!} \over {r!(n-1)!}}={{n+r-1} \choose {r}}={{n+r-1} \choose {n-1}}$

Where n is the number of objects from which you can choose and r is the number to be chosen.

For example, if you have ten types of donuts to choose from and you want three donuts there are (10 + 3 − 1)! / 3!(10 − 1)! = 220 ways to choose (see also multiset).

External links