Permutation

Permutation
Field: Algebra
Image Created By: Photoshop

Permutation

The image is a tree of permutations which shows all possible orderings for four colors.

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

[Click to view A More Mathematical Explanation]

Distinct Elements

When we are taking permutations of distinct elements, we are sampling withou [...]

[Click to hide A More Mathematical Explanation]

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 $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 $r$sample 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 _nP_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 $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)!}$

Proofs

[show more][hide]

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)*(n!)=$ To get (n+1)! Permutations.

2.) Proof that $P(n,r)=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 (Missing <code>texvc</code> executable. Please see math/README to configure.): P(n,r)=n*(n-1)*(n-2)…*(n-r+1)

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

Expanding $(n-r)!/(n-r)!$ and multiplying it by the definition of P(n,r), we obtain the following expansion:

Failed to parse (Missing <code>texvc</code> executable. Please see math/README to configure.): P(n,r)* (n-r)!/(n-r)!= n(n-1)(n-2)…(n-r+1)*[(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)= n!/(n-r)!$

 

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

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

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

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

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

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

• http://en.wikipedia.org/wiki/Permutation
• http://www.rpi.edu/~schmid/DISCRETE/perils.pdf

References

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.