Permutation
Permutation |
---|
Permutation
- The image is a tree of permutations which shows all possible orderings for four colors.
Contents
Basic Description
A permutation of any set is an arrangement of the set’s elements where order matters. As you can see from the above tree, the number of distinct arrangements for the four colors is 24. Notice at that each branch, there is one less choice of color than the last. This is because there is one less color that has not already been put into the ordering. An ordering of a certain size subset (of size r) is called an r-permutation of the set.
A More Mathematical Explanation
- Note: understanding of this explanation requires: *factorials, combinations
Distinct Elements
When we are taking permutations of distinct elements, we are sampling withou [...]Distinct Elements
When we are taking permutations of distinct elements, we are sampling without replacement. Picture it this way, when we are lining students up, we do not put the students that we have already lined up back into the shuffle to be potentially chosen again to be the next students to be placed in line. No, to choose students to place farther back along the queue, we have to select among the pool of students remaining outside the queue.
The math behind finding the number of permutations of a set with distinct elements is fairly simple. Consider a set that has a total of different elements, or choices. To pick the first element out of this set, there are choices to choose from. To pick the second element, there are remaining ways to pick the second element because we have already picked one of the choices out of the set. And so on until we have picked out the number of elements that we want for our sample size.
Thus the number of permutations can be expressed as: which is n! (n factorial) because of the product rule. If you want to select a number of elements to order that is less than the number of elements in the set, the math is very similar, and is written as P(n,r) or _{n}P_{r}.
For example if there are 6 colors, and you want to know how many orderings there are of any three of them. There are , or 120 ways of ordering any 3 of the six colors. This is because there are 6 ways to choose the first color, 5 ways of choosing the second, and 4 ways of choosing the third color. The rest of the colors are unused. To calculate the r-permutation, we multiplied . This is because there are n-r elements left out of the ordering. The formula for r-permutations is:
Proofs
Repeated Elements
What if in P(n,r) you are allowed to repeat an element any number of times, up to r (it is possible for everything to be the same element)? In other words, we are sampling with replacement. A good example of this is a bit string of a fixed length. The amount of each number is only limited by the size of the string. Each spot can either be a 0 or a 1, and the places do not depend upon each other. For every spot in the string, there are two possible digits to go there, which doubles the number of orderings there can be. For this reason there are 2^{n} different possible n-length bit strings. This can be extended to any number of elements. If there are n elements that can be repeated an infinite number of times, P(n,r) = n^{r}^{[1]}.
Non-Distinct Elements
Finding the number of permutations for a set of elements is different if some of the elements in the set are exactly the same. We call these items indistinguishable. This applies, for example, if you have a word with a repeated letter. The formula for number of permutations counts the repeated letter as two (or more) separate letters, and will count multiple permutations of the same sequence of letters. So if you have one double letter in a word, how many double sequences does it create?
If you only have one double letter, you count twice as many orderings with the formula for permutations because each ordering is counted with both placings of the double letter. If there is a triple letter, 6 times as many orderings will be counted. This is because there are six ways to order the triple letter. All six orderings will be counted for the tripled letter for each ordering of all of the other letters with the repeated letters all in the same places as the other repeated letters. Following this pattern, we see that there are exactly k! duplicate permutations, where k is the number copies of the same letter there are. Thus, the formula for the number of permutations of a set with a repeated element is:
What if there are multiple repeated elements? We can view this as separate problems: remove the duplication due to one repeated element, remove the duplication from the next, and so on. Using the formula above for the removal of one set of duplicates and assuming we have r sets of k_{r} duplicates, we have:
Repeated Elements
What if in P(n,r) you are allowed to repeat an element any number of times, up to r (it is possible for everything to be the same element)? A good example of this is a bit string of a fixed length. The amount of each number is only limited by the size of the string. Each spot can either be a 0 or a 1, and the places do not depend upon each other. For every spot in the string, there are two possible digits to go there, which doubles the number of orderings there can be. For this reason there are 2^{n} different possible n-length bit strings. This can be extended to any number of elements. If there are n elements that can be repeated an infinite number of times, P(n,r) = n^{r}^{[1]}.
Generating All Permutations
It is easy to generate a single permutation, because it can be in any order. But what if you want to generate all of the permutations of a set? How to you keep track of which ones you have done, and which ones you still need to do? It isn't so hard for small sets, like in the picture at the top of this page, but if the set is very large, we need a systematic way to make sure that there are no repeat orderings.
One effective way to do this is to arbitrarily assign a number, 1 through n, to each element in the set. Then generate the permutations in such an order that each one has a higher numeric value than the last. But how can we find a permutation that is guaranteed to have the next highest number? If we skip any permutations, having them in order is pointless. For example, say there are 6 elements in the set. The first permutation is 123456. We know this because a number is the smallest when its most significant digits are smallest. Keeping with this same idea, we know that the next smallest number will be the same with the last two digits switched. Now that we have all possible permutations with just changing the last two integers, we need to loot at the last three. If the third to last number is smaller than the second to last, the last three numbers can be rearranged to get the next number in sequence. The number that is the smallest of the two least significant digits that is also greater (we must end up with a larger number) than the third least significant is put in the place of the third least significant. If there are no numbers that are larger than the third most significant to its right, we must look at the last four numbers. This extends through the the rest of the digits as well.^{[1]}.
Why It's Interesting
Permutations are often necessary in counting problems.
If you have a program that can find all possible permutations of a string an check them against a dictionary, it can be used to unscramble words. If you need to label a group of objects, permutations can help determine how many symbols are needed to label each object distinctly.
Anagrams!
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
Related Links
Additional Resources
References
- ↑ ^{1.0} ^{1.1} ^{1.2} ^{1.3} Rosen, K. (2007). Discrete Mathematics and Its Applications. New York, New York: The McGraw-Hill Companies, Inc..
- 2. J.A. Rice, Mathematical Statistics and Data Analysis, Thomson Brooks/Cole, Belmont, CA, 2007
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.