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 in which order the cards were drawn, 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 is significant.
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 donuts and you had 20 to choose from, you should be able to pick more than one donut type.
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.
Now suppose you have these:
- 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 above is an example of the permutations of 3 items (there are 3 numbers to choose from), taken 3 at a time (there are 3 numbers per line). If P(n,r) is the number of permutations of n items, taken r at a time, we have n = 3 and r = 3, or P(3,3). If there were only 2 elements per line, we would have n = 2, and thus P(3,2).
In many situations dealing with the arrangement of objects, you will want to use r = n (that is, you are considering arrangements of all the items you are choosing from), so above we have P(n, n) = 6.
The article on permutations contains greater detail.
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 -- for example, if we're dealing with 0 and 1 (that is, the set {0, 1}), then n = 2. If we take 2 numbers at a time, then k = 2. Thus, you have C(2,2). There is only one such combination, so C(2,2) = 1. (In fact, C(n, k) = 1 whenever n = k.)
Summary of formulas
Combination with repetition
When the order does not matter and 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 each 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 with repetition
When order matters and 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 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.
|
Permutation without repetition
When the order matters, but each object can be chosen only once, 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.
|
External link
See also
