The Concept of Permutation Theory
What is Permutation?
The simplest way to define permutation is: the possible ways you can arrange a group of things.
For example, you have three different playing cards (say, A, B and C). How many ways can you arrange them? Let’s see the solutions:
[A B C], [A C B], [B C A], [B A C], [C A B], [C B A]
There are six possible ways to arrange three different cards.
In the example above we have actually made the all possible arrangements and then counted the number of arrangements (six). However, if we had five hundred or five thousand cards it will be very difficult to determine all the possible arrangements. Don't worry, there is a formula for that! Using Permutation theory we can use formulas to directly find out the number of all possible arrangements.
What About Repetition?
In the previous playing card example you might have noticed that no cards have been used more than once in the arrangements, i.e. no repetition of cards. But if repetitions are allowed then what would have been the number of arrangements? Let’s see.
- You have to select three cards out of three; the first card can be selected by three possible ways.
- Again for each selection of first card second card could be selected by three possible ways.
- So for all the selections of first card second card could be selected by 3 X 3 = 9 ways.
- Similarly the total number of possible selections of all the three cards should be
3 X 3 X 3 = 27
In line to the above discussions, if you have n items and you have to make sets of r items then total number of possible arrangements (where repetitions of the items are possible) will be:
n X n X ……r times = nr
Permutation where Repetitions are not Allowed
Let’s again go to the previous example of cards (card A, B, C) to see how permutations need to be calculated when repetitions are not allowed.
- The first card could be selected 3 possible ways.
- For each selection of the first card second card could be selected 2 possible ways (since repetitions are not allowed).
- Similarly, for each selections of first and second card third card could be selected 1 possible way.
- So the total number of permutations in the case of no repetitions is:
3 X 2 X 1 = 6.
If we try to generalize the above discussion for n number of elements, the number of possible permutations for all the n items will be:
n x (n-1) x (n-2)……..3x2x1= n!
Now, let’s take the case of selecting only two cards out of three from the already discussed playing card example. Here it goes.
- The first card could be selected again by 3 possible ways.
- For each selections of the first card second card could be selected by 2 ways. So, total numbers of possible permutation for selecting two cards out of three will be:
If we generalize this discussion in terms of n and r (where, n is the total numbers of items and r is the number of items to be selected for each set), we can derive the formula of permutation as:
n P r = n x (n-1) x (n-2) x (n-3) x (n-r+1)
= n! / (n-r)!
I hope this has made the concept more clear to you. Practice the formulas until you have it down.