The strict definition of a permutation is that it is an ordered arrangement, without repetition, of all of the elements of a set, S.

If S has n elements, then there are n! possible unique arrangements of the elements. This follows from the rule of product. Initially S has n elements, so for the event of choosing the first element, there are n choices. Since elements are not repeated in a permutation, the first element is no longer in the pool of possible choices for the second element, leaving (n-1) elements to choose from. The third slot will be chosen from (n-2) elements and so on, until all of the elements have been assigned a position in the permutation. Therefore, by the rule of product, the number of possible permutations for a set with n elements is:

n * (n - 1) * (n-2) * ... * 2 * 1 = n!

A weaker definition of a permutation involves an ordered arrangement, without repetition, of some, but not necessarily all the elements of a set. The convention is to say that we choose k elements from the n total elements of the set. As such these permutations are usual called k-permutations of n, but are sometimes referred to as partial permutations or sequences without repetition.

k-permutations of n are denoted P^n_k\text{, } {}_nP_k\text{, } {}^nP_k\text{, } P_{n,k}\text{, } P(n,k)

The number of possible k-permutations of n follows directly from above:

{}_nP_k = n * (n - 1)  * ... * (n - k + 1)

There is a more elegant way to write this value, however:

n! = n * (n - 1)  * ... * (n - k + 1) * (n - k) * (n - k - 1) * ... * 1

We know that {}_nP_k = n * (n - 1)  * ... * (n - k + 1) and (n - k) * (n - k - 1) * ... * 1 = (n-k)!. Substituting:

n! = {}_nP_k * (n-k)!

And finally rearranging:

{}_nP_k = \dfrac{n!}{(n-k)!}

« Back to Glossary Index

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.