P(12, 3) P(15, 3) P(9, 6)
We define and enumerate permutations.
Permutations
The notation represents the number of permutations of objects taken from a group of objects. Permutations are counted using the fundamental principle of counting.example 1 A fifth grade class consisting of 24 students wishes to elect a class
president, vice-president, secretary and treasurer. Assuming that no student
can hold more than one office, in how many ways can these positions be
filled?
The selection of class officers can be thought of as a permutation because the order of the selection of the 4 students determines which office they will hold. Thus, we seek the number of permutations of 24 objects taken 4 at a time, denoted . By the FPC, we have Thus, there are just over a quarter of a million possible outcomes for the selection of the class officers.
The selection of class officers can be thought of as a permutation because the order of the selection of the 4 students determines which office they will hold. Thus, we seek the number of permutations of 24 objects taken 4 at a time, denoted . By the FPC, we have Thus, there are just over a quarter of a million possible outcomes for the selection of the class officers.
(problem 1) A sports team consisting of 12 players wishes to select a captain, an
inspirational leader and an equipment manager (from among themselves). In how
many ways can this be done?
- Proof
- The number of choices for the first object selected is . The number of choices for the second object selected is . And so on, until the object, for which there are choices remaining. The result then follows directly from the FPC.
Factorials
We now explore the connection between factorials and permutations.
example 4 In how many ways can 5 people line up at an ATM?
The answer is the number of permutations of 5 objects taken 5 at a time, i.e.,
The answer is the number of permutations of 5 objects taken 5 at a time, i.e.,
General permutations can be expressed as a ratio of factorials.
- Proof
- The ratio of factorials lends itself to lots of cancellation. We have Note that the entire denominator cancelled out.
example 5 Express the following as a ratio of factorials: and .
For we have and , so Similarly, In applications, numbers such as and are too unwieldy to write out, so we will prefer the factorial notation as a final form.
For we have and , so Similarly, In applications, numbers such as and are too unwieldy to write out, so we will prefer the factorial notation as a final form.
In the proposition, it was assumed that . But, what if , for we have already seen the expression arise in applications. In fact, . To extend the proposition to cover this case we make the following definition.
With the above definition, we can safely revise the proposition to state that for and natural numbers with , we have for if then the denominator is .
Permutations of Non-distinct Objects
In this subsection, we examine permutations of objects taken at a time in which the objects are not distinct. The idea is that arranging non-distinct objects among themselves does not produce a new permutation. To count such permutations, we will combine the FPC with division.
example 6 How many permutations are there of the word ?
We have 2 non-distinct objects among our 4 objects- namely the two ’s. We begin the counting process by considering the 4 objects as distinct by placing subscripts on the repeated objects. In other words, we consider the word , which has permutations. Among these 24 permutations, consider the following pairs of permutations:
We have 2 non-distinct objects among our 4 objects- namely the two ’s. We begin the counting process by considering the 4 objects as distinct by placing subscripts on the repeated objects. In other words, we consider the word , which has permutations. Among these 24 permutations, consider the following pairs of permutations:
Each of these three pairs of permutations of the 4 distinct objects, correspond to just a single permutation of the non-distinct objects . These pairs correspond to respectively. In fact, the 24 permutations of can be paired in the manner shown above, with each pair yielding a single permutation of . This means that the number of permutations of is twice the number of permutations of . Thus, the number of permutations of is .
example 7 How many permutations are there of the letters in the word ?
Again, we begin by considering the distinct letters , which have permutations. Given any of these 120 permutations, there are ways to rearrange the letters and among themselves, leaving the B and C in the same position. These 6 permutations of all correspond to the same permutation of . Hence, the number of permutations of is 6 times the number of permutations of . Thus the number of permutations of can be obtained by dividing 120 by 6, so there are 20 permutation of the letters in the word .
Again, we begin by considering the distinct letters , which have permutations. Given any of these 120 permutations, there are ways to rearrange the letters and among themselves, leaving the B and C in the same position. These 6 permutations of all correspond to the same permutation of . Hence, the number of permutations of is 6 times the number of permutations of . Thus the number of permutations of can be obtained by dividing 120 by 6, so there are 20 permutation of the letters in the word .
example 8 How many permutations are there of the letters in the word ?
If the letters were all distinct, as in , then there would be permutations. However, the in any such permutation can be permuted among themselves in ways without changing the permutation of the unsubscripted original letters. Furthermore, the ’s can also be permuted among themselves in ways without changing the permutation of the original unsubscripted letters. Thus the total number of permutations of can be found by dividing first by and then dividing that by . This is equivalent to dividing by the product of and . Thus the number of permutations of the letters in the word is
If the letters were all distinct, as in , then there would be permutations. However, the in any such permutation can be permuted among themselves in ways without changing the permutation of the unsubscripted original letters. Furthermore, the ’s can also be permuted among themselves in ways without changing the permutation of the original unsubscripted letters. Thus the total number of permutations of can be found by dividing first by and then dividing that by . This is equivalent to dividing by the product of and . Thus the number of permutations of the letters in the word is