permutation

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

If has elements, then there are possible unique arrangements of the elements. This follows from the rule of product. Initially has elements, so for the event of choosing the first element, there are 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 elements to choose from. The third slot will be chosen from 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 elements is:

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 elements from the 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

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

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

We know that  and . Substituting:

And finally rearranging:

« Back to Glossary Index

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