Search This Blog

Calculation of permutations of 'n' objects when 'r' objects are taken at a time

In the previous examples, we calculated the permutations of 'n' number of objects by considering that n objects are to be rearranged among themselves. Now we will also calculate all the different arrangements obtained when there are 'n' number of objects, but only some of those are taken at a time and arranged in different orders.
This means that if there are, say, 10 objects, we will calculate the permutations obtained by taking less than 10 objects at a time. Let us take 3 objects at a time. Thus, we can chose any three objects from the group of 10 objects like this:
  • object 1, object 2, object 3
  • object 4, object 2, object 5
  • object 4, object 3, object 2, and so on.
For each of the group of 3 objects obtained above, we can obtain different arrangements (permutations). For example, for the group of objects object1, object2, and object3, we can obtain the following different arrangements:
  • object1, object2, object3
  • object2, object3, object1
  • object2, object1, object3, and so on.
Thus, it is very difficult to calculate the total number of different arrangements obtained when only some objects are taken from a group of objects at a time. For this, we again apply the fundamental counting principle and make our work simpler. But before that, we will have to reconsider the situation and think about it like this:
  • Consider the situation as if a group of three empty boxes is to be filled in by any three objects from the group of 10 objects:
  • The first box can be filled with any one of the 10 objects. (10 choices)
  • After filling in the first box, we are left with 9 objects. Therefore the second box can be filled in with any one of the 9 objects. (9 choices)
  • After filling the first and second box, 8 objects are left. The third box can be filled with any one of the 8 objects. (8 choices)
Therefore by using the Fundamental counting principle, we conclude that there are 3 events taking place in this example - one is choosing the first object (having 10 choices), second is choosing the second object (having 9 choices), and the third is choosing the third object (having 8 choices).

Since three events can occur in 10, 9 and 8 ways respectively, therefore by the fundamental principle of counting, the total number of different events that can occur are 10 x 9 x 8 = 720.

Therefore, the permutations of 10 objects taken 3 at a time are 720.

Now we will derive the formula for permutations of 'n' objects taken 'r' at a time. In the previous part (Calculation of permutations part 3-A), we calculated that if there are 10 objects and 3 are taken at a time, then the total number of permutations are given by 10 x 9 x 8 = 720.

Generalizing the above obtained result for all numbers:

Let the total number of objects be 'n' and let 'r' objects be taken at a time. Then the total number of permutations obtained when 'r' objects are arranged at a time from a group of n objects will be represented by the symbol P(n, r).
 
Let us look at this situation in the light of the fundamental counting principle (like we did in the previous examples in permutations):

Since 'r' objects are to be arranged at a time this can also be viewed as if there are 'r' number of empty boxes, and from the group of 'n' objects, we can take any object at random and fill in each box with exactly one object. This way, to fill the first of the 'r' empty boxes, there will be 'n' objects to chose from. Therefore the number of choices for the first empty box is 'n'.
 
After filling the first empty box, there are (r - 1) empty boxes left to fill, and (n - 1) number of objects left.There are (n - 1) number of different choices for filling in the second empty box.
 
There are (n - 2) number of different objects to chose from when filling the third empty box, because two of the objects have already been taken and put in the first and second empty box.
 
This way, till the 'r' empty boxes are filled, 'r' number of objects will be taken from the group of 'n' objects. Thus, the number of objects left after filling in the 'r' empty boxes will be (n - r).
 
Therefore, by the fundamental principle of counting, since the first event can occur in 'n' different ways, second event can occur in (n - 1) different ways, third event can occur in (n - 2) different ways, till the r th event, which can take place in (n - r + 1) different ways, the total number of different ways in which all the events can occur together is given by 
P(n, r) = n(n - 1)(n - 2)(n - 3) . . . . (n - r + 1)

The most common questions that students ask after studying this formula is "Where does (n - r + 1) come from?" That is to be explained in detail, otherwise they (and you) will not be able to grasp this concept : 

Where does (n - r + 1) come from?  
Remember that there are 'r' empty boxes to be filled. After filling 1 empty box, (n - 1) objects are left. Similarly, after filling two empty boxes, (n - 2) objects are left. Since we have to fill a total of 'r' empty boxes, after filling the last box, that is, after filling 'r' boxes, the number of objects left will be (n - r). But we have to know the total number of choices for the last box (the r th object). 

So we have to find the total number of objects left after filling in the second last box, because that would be the number of choices present for the last box. 

Since the last box is the r th object, therefore the second last box is (r - 1)th box. After filling in (r - 1) boxes with one object each, (n - (r - 1)) objects are left for the last (the r th) box. Since (n - (r - 1)) = (n - r + 1), thus, there are (n - r + 1) choices for the last empty box to be filled in. Thus the last term in the above formula is (n - r + 1).Final formula we obtained: 

Number of permutations for n objects taken r at a time is
P(n, r) = n(n - 1)(n - 2) . . . (n - r + 1)
By using factorial notation, we get that
P(n, r) = [n(n - 1)(n - 2) . . . (n - r + 1)] * [(n - r) . . . 3 * 2 * 1]/(n - r)!
P(n, r) = n!/(n - r)!

No comments:

Post a Comment