Permutations
Permutations |
---|
Permutations
- 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.
To describe the image in mathematical terms, we say that there are 4! permutations. By 4!, we mean 4 factorial, which is the product of natural numbers descending from a starting number. In this case, we start from 4 and take its product of descending natural numbers: , which gives us 24 orderings.
This makes mathematically sense because for permutations, the way elements are arranged in order depends upon the remaining options left to be arranged. For instance, choosing red first among the four colors, leaves 3 colors (blue, green, yellow) left to be chosen next. Once one of those 3 colors is chosen, then we have two left to choose from. And so on, until we only have one last color to choose for the arrangement. Our choices dispose us to the taking the product of the remaining options.
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 as 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 for 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:
Using the formula to solve the example problem, we get that:
We get 120 ways as we had intuitively calculated.
Proofs
Repeated Elements
What if in you are allowed to repeat an element any number of times, up to sample size ? A classic example of this scenario is picking balls out of an urn. You pick a ball out, but then place it back into the urn again. This is also known as sampling with replacement, because you have replaced the ball into the selection choice again. Repeated elements can be extended to any number of elements. If there are elements that can be repeated an number of times, ^{[1]}.
Let’s try a real-world example problem about license plates. Suppose that license plates come in the format: XXX-0000 where X could be any letter (A-Z) and 0 could be any single digit number (0-9). How many possible license plate arrangements are there?
To solve this problem, consider that possible license plates could include repetitions of letters or numbers. We could have repetitions of any single alphabet letter up to three times or we could have repetitions of any single digit up to four times. We need to account for both possibilities. So, we use the formula for permutations of repeated elements.
We get that the total possible permutations of license plates is:
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:
Let’s try out an example problem. How many ways can the word BOOKKEEPER be arranged?
We look at the number of letters the word bookkeeper has. There are a total of 10 letters. So there are a total of 10! letter arrangements. However, out of the 10 letters, there are 2 O’s, 2 K’s, and 3 E’s. We count the O’s, K’s, and E’s as duplicates and of their individual letter repetitions, there is a corresponding number of permutations for each of them.
So there are = 151, 200 ways.
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 are a play on words in which letters of a word can be rearranged to form new words or phrases. However, the rearrangement of letters into other valid words and phrases is distinct; only so many permutations on a word can exist.
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} 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.