Permutation And Combination Concept And Shortcut Methods
What Are Permutations and Combinations?
The theories of combination and permutation were proposed by French mathematicians Pierre de Fermat and Blaise Pascal.
Combinations and permutations describe the various ways of selecting objects from a given set to create different subsets without replacements.
- Permutation describes subset selection in which the order of the selection is important.
- Combination is the selection of subsets in which the order of the selection is not important.
It’s not unusual for a student to confuse combination and permutation. Here an easy trick for remembering which is which:
Permutation sounds complicated. Hence, with permutations, even the little detail matter. [Nicki, Taylor, and Perry] is therefore different from [Perry, Nicki and Taylor.]
Combination sounds simple and easy going. With combination, details don’t matter. [Nicki, Taylor, and Perry] is therefore similar to [Perry, Nicki and Taylor.]
Permutation is used for lists where order is crucial. Combination is used for groups where order doesn’t matter.
Permutations Explained
Permutations fall into two categories:
- Permutations where repetition is allowed
- Permutations where repetition isn’t allowed
Permutation with Repetition
Example:
The code that opens a certain lock could, for instance, be 333.
This is a permutation with repetition.
Permutation with repetition occurs when a set has r different objects, and there are n choices every time.
The permutation for selecting the 3 objects in such a case will be n multiplied 3 times.
n x n x n
Therefore, for permutation with repetition, selecting r number of objects for which there are n different choices, the permutations will be calculated by:
n x n x … (r times)
(the first object has n possibilities, the second object has n possibilities, and so on)
n x n x …. (r times) can be written as nr
Hence for permutations with repetition:
p = nr
Where:
P is the permutation
n is the number of choices for an object
r is the number of objects
Example:
A padlock has a 4-digit locking code with digits between 0-9. How many different permutations are there if repetition is allowed.
The code could be 0000 or 1234 or 2548 or 1122 or 1002 and so on. Since there are 10 digits to choose from the permutation will be:
10 x 10 x … (4 times) = 104 = 10000 permutations
From the formula:
p = nr
We see that:
n is the amount of choices from which a selection is made (in our example, we had 10 digits (0-9) to choose from)
r is the number of objects (in our example, we had a 4-digit code so, four objects are there)
Permutation Without Repetition
Let’s imagine that we are awarding trophies to the first three winners of a competition where there are 8 competitors. The first winner gets gold, the runners-up gets silver, and the third person gets bronze.
When awarding the first prize (gold), we’ll have 8 contestants to choose from
When awarding the second prize (silver), we’ll have 7 contestants to choose from because the first contestant has already won the first prize (gold) and thus not eligible for the second prize (silver).
When awarding the third prize (bronze), we’ll have 6 contestants to choose from because the first contestant has already won the first prize (gold). The second contestant has won the second prize (silver). Therefore, the first two contestants are not eligible for the third prize (bronze).
We picked three people to win; nobody could be picked twice. Therefore, the total number of options was 8 x 7 x 6 = 336
Therefore:
Without repetition, the number of choices to choose from gets reduced every time a selection is made.
Permutation may be expressed in various ways.
- Using multiplication sign e.g. 8 x 7 x 6 = 336
- Using dots e.g. 8.7.6 = 336
- Using the factorial function !
The Factorial Function (!)
The symbol '!' is used when we are multiplying a series of natural descending numbers e.g.
8! = 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320
5! = 5 x 4 x 3 x 2 x 1 = 120
Note 0! = 1
Therefore, if all the contestants in the competition above were being considered for a prize (let’s say a participation prize,), the permutation would be
8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 (which is the same as 8!)
However, when we are only interested in giving prizes to the first three winners, the permutation should be 8.7.6. So, how do we use the factorial but stop at 5?
We simply divide 8! By 5!
Note that 5 is what was left after we had picked our top 3 winners from the 8 contestants. (i.e. 8-3=5). The permutations could, therefore, be calculated as
What Have We Done So Far?
We had 8 contestants (n objects) we wanted to picked 3 winners (k items) therefore the permutation could be calculated as:
If we have n objects and wanted to find out the different permutations through which k items could be ordered, we use the formula
How many ways can 3 pool balls be picked in order from a collection of 16 pool balls without picking the same ball more than once?
We’re picking 3 balls in order without repetition. Therefore, we are dealing with permutation without repetition.
We already know that:
n = 16
k = 3
Therefore:
=3,360
The answer is 3,360 permutations
How many permutations of 2 different digits can you get between 0 and 9 if each digit is picked only once? (such a picking 2 marbles from a bag with 10 marbles numbered from 0 – 9 if each marble is picked only once)
Once selected, a digit can’t be picked again. We are dealing with permutations without repetition.
Hence:
n = 10 digits (from 0-9)
k = 2 different digits
The answer is 90 permutations
How many sets of 6 letters can be chosen from the alphabet if repeats are allowed?
Any letter can be picked and repeated. We are dealing with permutation with repetition.
Hence
p=nr
n= the 26 letters of the alphabet
r= the 6 random numbers
Therefore,
p = 266 = 308,915,776
The answer is 308,915,776 sets.
Click here for Combination Concept And Shortcut Methods
