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 the first, second, and third place winners in a dog show are to be selected from amongst 15 canine finalists, then this may occur in any of 15!/(15 − 3)! = 2730 possible ways.

Note that if r = n (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

\frac{n!}{r!(n - r)!} = {n \choose r} = {n \choose {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 ten numbers and wish to choose 5 you would have 10!/5!(10 − 5)! = 252 ways to choose.

The number of five-card poker hands possible from a standard fifty-two card deck is ${{52 \choose 5} = 2598960}$ .

Combination with repetition

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

=  =

where n is the number of objects from which you can choose and r is the number to be chosen. This can be visualised in the following way: Imagine a string of n symbols, from which we choose r examples. e.g. pick eight symbols from the list {a,b,c,d,e}. We can rewrite this using the symbols 1 and /, meaning 'choose one' and 'next symbol' respectively. Therefore a choice of, say, {a,a,b,c,c,c,e,e} could be represented, starting at 'a', as {1,1,/,1,/,1,1,1,/,/,1,1}. ("Choose an 'a'; choose another 'a'; move on to the next symbol, 'b'; choose a 'b';" etc.) This is a equivalent to choosing n − 1 positions for the / symbol in a string of length (n − 1) + r, where n = 5 and r = 8 in this example. Thus this problem is equivalent to choosing n - 1 positions from amongst n + r − 1, without repetition, and hence falls under a previously described case. 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

Combinatorics | Permutations

Kombinasi dan permutasi | Размещение | การเรียงสับเปลี่ยน และ การจัดหมู่

Gourt Home::Gourt :: Permutations and combinations