|
This article is an elementary introduction to permutations and combinations in combinatorial mathematics.
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 (a standard deck), and select five cards for a poker hand. It would not matter which order the cards were drawn in, because you could rearrange them in your hand.
A permutation, on the other hand, is an ordered selection made from a group of objects. For example, if you play the Play 3 Lotto you must choose three numbers. Choosing 5, 3, and 7 is different from choosing 3, 7, and 5: the order in which you pick your numbers matters.
Both combinations and permutations have variants when some objects appear twice (that is, when either has some repetition). For example, if you wanted a combination of twelve donuts and you had 20 to choose from, you should be able to choose the same donut type more than once.
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, one is 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.
Now suppose you have these:
- 1, 2, 3
Here's a list of all permutations of those: - 1 2 3
- 1 3 2
- 2 1 3
- 2 3 1
- 3 1 2
- 3 2 1
Given three symbols and three numbers per line, there are 6 possible permutations.
In the article on permutations you will find this sentence: "Suppose you have a total of n distinct objects at your disposal and you want to create permutations of r elements selected from those n, where r≤n."
In the above example, we have n = 3 (since we have 3 distinct objects, 1, 2, and 3). Also here we have r = 3 because each line has 3 elements. Now each line can have no more than 3 elements, because r must be no more than n (3 in this case). But we could have had only 2 elements per line!
The article on permutations tells you how to calculate the number of permutations possible -- P(n, r).
Most likely, you will want to use r = n, so above we have P(n, n) = 6.
Also see the article on combinations to find C(n, k) which is "the number of k-combinations of set with n elements." That we have a set of n elements means we are working with n symbols -- here, 0 and 1, so we have n = 2 above. The first line listed above has k = 1 ("Length of 1"), the second k = 2 ("Length of 2"), etc.
Summary of formulae
Combination with repetition
When the order does not matter, but an object can be chosen more than once use the formula:
Here 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)! or 220 ways to choose.
| Combination without repetition
When the order does not matter, but an object can be chosen only once use the formula:
Here 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)! or 252 ways to choose.
| Permutation (without repetition)
When the order matters but each object is only chosen once you can use the formula:
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. | Permutation with repetition allowed
When order matters and an object can be chosen more than once you use the formula:
Here n is the number of objects from which you can choose and r is the number of slots you need to fill.
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 43 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.
|
External link - Permutations and combinations (http://www.mathagonyaunt.co.uk/STATISTICS/ESP/Perms_combs.html)
|
Feeds |
Contact