Temp Directory?: /var/www/html/mathimages/imgUpload/tmpTemp Directory?: /var/www/html/mathimages/imgUpload/tmp Permutations - Math Images

Permutations

From Math Images

Jump to: navigation, search
Image:inprogress.png

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: 4 \times 3 \times 2 \times 1, 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 n different elements, or choices. To pick the first element out of this set, there are n choices to choose from. To pick the second element, there are n-1 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 rsample size.

Thus the number of permutations can be expressed as:  (n) \centerdot (n-1) \centerdot (n-2) ... 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 nPr.

For example if there are 6 colors, and you want to know how many orderings there are for any three of them. There are  6 \centerdot 5 \centerdot 4 , 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  (n) \centerdot (n-1) \centerdot ... \text{down to }(n-r+1) . This is because there are n-r elements left out of the ordering. The formula for r-permutations is:

 P(n,r) = \frac{n!}{(n-r)!} [1]

Using the formula to solve the example problem, we get that:


P(6,3)= \frac {6!} {(6-3)!}


=\frac {6!} {3!}


=\frac {6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times1}


=6 \times 5 \times 4


We get 120 ways as we had intuitively calculated.


Proofs

1.) Proof that P(n)= n! [Number of permutations proof]

This is a proof that can be easily done using mathematical induction. We want to show that we can arrange n things in n! different ways.

For the basis case, we have n=1 objects. The number of permutations for an object is 1 because there is only 1 way to arrange a single object. Although this is trivial, we have shown the basis case.

For the inductive step, we want to show the number of permutations possible for n+1 objects from n objects. Assuming that P(n)=n! is true for the arrangement of n objects, we can arrange n+1 like so:

n+1,\ n_1,\ n_2,\ n_3\, \ldots\,n_k


n_1,\ n+1 ,\ n_2,\ n_3\, \ldots, n_k


n_1,\ n_2,\ n+1,\ n_3\, \ldots, n_k


n_1,\ n_2,\ n_3,\ n+1\, \ldots, n_k


n_1, \,  n_2, \, n_3, \,  \ldots \, n_k, \, n+1


Note that these are distinct permutations. There is no repetition in the specific placement of n+1 objects. Furthermore, the n+1 objects have been arranged in a distinct number of n! ways… So to calculate the number of permutations for n+1 objects, we can take the product like so:  (n+1) \times (n!)= To get (n+1)! Permutations.

2.) Proof that P(n,r)=\frac {n!} {(n-r)!} [Number of permutations in r times proof]

Consider the following scenario: We have no replacement or repetition when placing n distinct objects in r places. In other words, each of the r places must hold a different object from the set of n. To indicate the specific position of the n objects among the r places, we can express n in terms of its specific place, denoted by its position among the rth places. We also equivalently obtain the number of different ways to pick from the remaining n objects as we move down to the rth place.


1st place: n ways= n-(1-1)


2nd place: n-1 ways= n-(2-1)


3rd place: n-2 ways= n-(3-1)


rth place: n-(r-1)=n-r+1 ways. In the case that n=r this is to prevent the possibility that there could be 0 ways, which is impossible.


Thus we obtain the definition of permutation for n objects taken r times, mathematically expressed as: Failed to parse (lexing error): P(n,r)=(n) \centerdot (n-1) \centerdot (n-2)…\centerdot (n-r+1)


Now, assuming knowledge of factorial, which is the product of descending natural numbers, consider that \frac {(n-r)!} {(n-r)!}. This expression is equal to 1.

Expanding \frac {(n-r)!} {(n-r)!} and multiplying it by the definition of P(n,r), we obtain the following expansion:

Failed to parse (lexing error): P(n,r)* \frac{(n-r)!} {(n-r)}= {n\times(n-1)\times(n-2)…\times (n-r+1)} \times [ \frac {(n-r)(n-r-1)…(3)(2)(1)} {(n-r)(n-r-1)…(3)(2)(1)}]


What follows from the above expression is that both the numerator and denominator express the products of descending natural numbers starting from some initial number. For the numerator, that initial number is n. For the denominator, it is n-r. As such, the numerator simplifies to n! and the denominator simplifies to (n-r)!

Thus, we have obtained the expression for P(n,r)= \frac {n!} {(n-r)!}

Repeated Elements

What if in P(n,r) you are allowed to repeat an element any number of times, up to sample size r? 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 n elements that can be repeated an r number of times, P(n,r) = n^r[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?

Figure 1  A possible license plate arrangement, with repetition of single letter G.
Figure 1
A possible license plate arrangement, with repetition of single letter G.


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: 26^3 \times 10^4=175,760,000 ways


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:

 \frac{n!}{k!} .


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 kr duplicates, we have:

 \frac{n!}{k_1 ! \centerdot k_2 ! \centerdot ... k_r !} .


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 \frac{10!} {2! 2! 3!}= 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.

Figure 2 This example from the Harry Potter series is only 1 permutation of the words: Tom Marvolo Riddle. The phrase, 'I am Lord Voldemort' is its anagram.
Figure 2
This example from the Harry Potter series is only 1 permutation of the words: Tom Marvolo Riddle. The phrase, 'I am Lord Voldemort' is its anagram.



Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.



Related Links

Additional Resources

References

  1. 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





If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Personal tools