This type of exercise is quite easy, and probably you won’t find it commonly on a test, exam, or in real life.
However, there are some places you might find it. So, it is worth looking into it.
As usual, let’s start with relevant definitions and theorems.
“A permutation of a set of distinct objects is an ordered arrangement of these objects.”
Theorem: “If n is a positive integer and r is an integer with 1 ≤ r ≤ n, then there are P (n, r ) = n(n − 1)(n − 2) · · · (n − r + 1) r-permutations of a set with n distinct elements.”
Corollary: “If n and r are integers with 0 ≤ r ≤ n, then P(n,r) = n! / (n−r)!”
The previous definition, theorem, and corollary are from the textbook Discrete Mathematics and its Applications by Rosen.
As per the corollary, the number of permutations is a function of the number of total objects and the number of objects we must choose for each permutation. In this case, both numbers are 7.
P(7,7) = 7!/(7-7)!=7!/1!=7!=5040.
Answer:
There are 5040 different permutations of the set {a,b,c,d,e,f,g}.
Another use of this type of calculation is to find out how secure can be a combination lock.
For you to be able to open this type of lock without knowing the combination, you need to try every possible combination.
So, the one in the picture above has a four-digit combination and each digit can be a number from 0 to 9.
So, how many possible combinations of 4 digits you must try, in the worst-case scenario, to open this lock without knowing the right combination?
In this case, we will first assume that you don’t repeat digits in any of the combinations. For instance, the combination 1312 is not allowed because it repeats the 1 twice.
First, you need to notice that even though the name is a combination lock, it is actually not a combination. It is a permutation of 4 digits from the set {0,1,2,3,4,5,6,7,8,9} (assuming that no digits are repeated).
So, let’s apply the formula.
P(10, 4) = 10!/(10-4)!=10*9*8*7*6!/6!= 5040.
So, someone who doesn’t know the right combination for the lock has to try, in the worst-case scenario, 5040 combinations to open the lock.
If we allowed digits to be repeated, as usually actually happens, then we apply the product rule.
In how many ways you can choose the first digit? 10 ways.
For each of the ways you choose the first digit, you can choose the second digit in 10 ways, and so on.
So, the total number of possible combinations for a combination lock with a 4-digits combination is 104=10000.
Related exercises:
- List all the permutations of {a, b, c}.
- A professor writes 40 discrete mathematics true/false questions. Of the statements in these questions, 17 are true. If the questions can be positioned in any order, how many different answer keys are possible?
- Let S = {1,2,3,4,5}. List all the 3-permutations of S. List all the 3-combinations of S.
- How many permutations of the letters ABCDEFG contain
- In how many ways can a set of five letters be selected from the English alphabet?
- How many bit strings of length 10 contain
- How many possibilities are there for the win, place, and show (first, second, and third) positions in a horse race with 12 horses if all orders of finish are possible?
