Permutations and combinations

From Wikipedia, the free encyclopedia

It has been suggested that this article or section be merged into Combination. (Discuss)

In familiar terms, a combination is an un-ordered selection made from a group of objects. Any five playing cards from fifty-two card deck can form a valid combination. A permutation, on the other hand, is an ordered selection made from a group of objects. So for objects 1, 2, 3, there are six permutations: 123, 132, 213, 231, 312, and 321.

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 fruit salad consisting of apples, bananas and oranges, should you be able to pick apples more than once?

1 Formal
2 See also
3 External links

[edit] Formal

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.

[edit] 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.

[edit] 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.

[edit] 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}.$

[edit] 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. 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 an 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).