# Lesson Introduction to Permutations

Algebra ->  Permutations -> Lesson Introduction to Permutations      Log On

 Ad: Mathway solves algebra homework problems with step-by-step help! Ad: Algebrator™ solves your algebra problems and provides step-by-step explanations!

 Algebra: Combinatorics and Permutations Solvers Lessons Answers archive Quiz In Depth

### Source code of 'Introduction to Permutations'

This Lesson (Introduction to Permutations) was created by by ikleyn(4)  : View Source, Show



Introduction to Permutations

This lesson introduces  Permutations,  one of the subjects of  Combinatorics. Before giving the general definitions, let us consider simple examples.

Example 1

If you have three distinct digits,  how many  3-digit  numbers  can you write using all these digits? For instance, if you have the digits  2,  3  and  4,  you can write 3-digit numbers     234,  243,  324,  342,  423,  432, i.e.  6  different  3-digit  numbers.

Example 2

There are four boys:  Andrew,  Bill,  Christopher, and  Daniel.  In how many ways can they form a line?     - There are  24  ways to form a line.  Possible arrangements are presented below using the boys' initials (first letters of their names):         ABCD, ABDC, ACBD, ACDB, ADBC, ADCB     - all possible combinations with the letter 'A' in the first position,         BACD, BADC, BCAD, BCDA, BDAC, BDCA     - all possible combinations with the letter 'B' in the first position,         CABD, CADB, CBAD, CBDA, CDAB, CDBA     - all possible combinations with the letter 'C' in the first position,         DABC, DACB, DBAC, DBCA, DCAB, DCBA     - all possible combinations with the letter 'D' in the first position.

Example 3

You have  5  different books.  How many ways are there to put them on a shelf?        You can put any book on the first position, any of the remaining books on the second position, and so on.        More exactly,             - First, you can put any of 5 books on the first position of the shelf.  This gives 5 possibilities.             - Second, you can put any of the remaining four books on the second position of the shelf.  This gives 4 independent possibilities.             - Third, you can put any of the remaining three books on the third position of the shelf.  This gives 3 independent possibilities.             - Fourth, you can put any of the remaining two books on the fourth position of the shelf.  This gives 2 independent possibilities.             - Finally, you have only one book remained, and there is only one possibility to put it on the fifth position.     It is clear that         - any of considered combinations is allowed;         - all these combinations are different;         - any possible placement of the books on the shelf falls into one of the considered arrangements.     Now you can calculate the number of all possible placements.     There are  5  independent possibilities for the first position,  4  independent possibilities for the second position,  3  independent possibilities for the third position,     2  independent possibilities in the fourth position,  and only one possibility for the fifth position. Therefore, the total number of all possible combinations is equal to     the product  5*4*3*2*1 = 120.     Thus, there are  120  ways to place  5  different books on the shelf. Now you are ready for the general definition.
Assume there is a set of  n  objects that you can distinct by their names or properties (like colors) or other features. For simplicity, imagine that the objects (elements of a set) are numbered by integer numbers  1, 2, . . . , n  that are their unique names in this case. You can arrange objects of the set in different ways. Each arrangement is the ordered list of objects without repetition,  where the objects are presented by their names. Two arrangements are the same if the respective lists are identical.  Two arrangements are different if the respective lists are different. Such arrangement of  n  elements of the set is called  permutation. In other words,  permutation  is ordering of the given set of distinguishable objects.  When we talk about permutations we assume that there is a standard ordering in this set declared by some way.  Then the permutation is re-ordering of the standard order.  You can think that the permutation is the list saying in which position is the item that originally was in the i-th position of the standard ordering,  for each i = 1, . . . , n. In this way, a permutation can be presented as a sequence of non-repeating integer numbers from  1  to  n,  for a given number  n. Such interpretation of permutation as a sequence of non-repeating integer numbers is universal.
For example, if you consider permutations of the set of four elements, then the sequence  {1, 2, 3, 4}  describes the standard  (original)  order of the elements in the set. The sequence  {2, 1, 3, 4}  describes interchanging of elements  1  and  2:  the former first element is on the second position, while the former second element is on the first position after interchanging. The sequence  {3, 1, 4, 2}  describes permutation which put the element  1  on the second position, the element  2  on the fourth position, the element  3  on the first position, and the element  4  on the third position. Note that the  Example 1  above dealt with permutations of the set of three different digits.  The  Example 2  dealt with permutations of four boys in a line. In the  Example 3  we considered permutations of the set of five different books. Again, a permutation is an arrangement of the set of  n  distinct elements, for some integer  n.  All permutations of the set of  n  elements contain the same set of elements. Two permutations of a given set of  n  elements differentiate from each other only in the order of the elements in their lists.

Theorem

The total number of permutations of a set of  n  distinct objects is equal to n! = n*(n-1)*(n-2)* . . . *2*1.
For the proof of this Theorem see the lesson  PROOF of the formula on the number of Permutations  under the current topic in this site. The examples below show you how to apply this theorem to solve some word problems on permutations.

Problem 1

A secretary has to make a schedule for tomorrow classes in Algebra, Science, Spanish and Physical Exercises. How many ways does she have to arrange these classes in the schedule? Solution You have the set of four non-repeating subjects. Use the formula above for the number of permutations with  n=4. Thus,  4! = 3*3*2*1 = 24 arrangements are possible.

Problem 2

A hotel front desk clerk has three rooms available today.  He has to place three guests in these rooms,  one person to each room. How many ways does he have to arrange accommodation for these people? Solution 3! = 3*2*1 = 6 arrangements are possible,  according to the formula on the number of permutations of the set of three distinct objects.

Problem 3

A chemist has to place seven different liquid chemicals into seven differently colored caps, one chemical into each cap.  How many ways does the chemist have to arrange these chemicals? Solution 7! = 7*6*5*4*3*2*1 = 5040 arrangements are possible,  according to the formula on the number of permutations of the set of seven distinct objects.

Summary

Permutation is an arrangement of the given set of  n  distinct elements. Two permutations of a given set of  n  elements differentiate from each other only in the order of the elements/items in their lists. Presentation of permutations of a set of  n  objects as the sequences of non-repeating integer numbers from  1  to  n  is universal, conventional and generally accepted. The number of permutations of a set of  n  elements is equal to n! = n*(n-1)*(n-2)* . . . *2*1.