Distinct Elements

The math behind finding the number of permutations of a set is fairly simple. If the set is of size n, there are n ways to pick the first element. For each element that could be chosen first, there are n-1 ways to pick the second element (since the first one cannot be chosen again), and so on. Thus the number of permutations is: 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 , 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:

^[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].

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