Permutation
Kapitoly: Combinatorics, Variations, Permutation, Combination, Variations with repetition, Combination with repetition, How many different PINs are there, Calculator.
Permutation is a special case of variation, where we have a set of size n and we want to find the number of all different n-tic.
The formula
Let's review the variations themselves. Given a set of digits {1, 2, 3, 4, 5}, how many three-digit numbers can we construct from them if no digit is allowed to repeat? This is a typical example of a variation that can be solved with the familiar formula
$$ V(k, n) = \frac{n!}{(n-k)!}=\frac{5!}{(5-3)!}=60. $$
How many five-digit numbers could we put together?
$$ V(k, n) = \frac{5!}{(5-5)!}=\frac{5!}{0!}=5!=120. $$
We can notice that if we have a set of five elements and we are looking for the number of all different fives, the result is equal to 5!. We can generalize this and say that if we have a set of n elements, there are a total of n! different n-tics. This brings us to the notion of permutation.
What is a permutation
If we have a set M of size n, then a permutation is an arbitrary n-tice consisting of elements from the set M, and no element may be repeated. Example: if we have a set M = {a, b, c, d}, then the permutation is for example [a, b, d, c] or [d, b, a, c]. The number of all different permutations is equal to
$$ P(n) = V(n, n) = n! $$
Solved examples
-
You have a total of six books and you want to put them on a shelf in some order. How many different orders are there in total? We have six books, permuting all the books each time, so the result is equal to P(6) = 6! = 720.
-
In addition to your 6 Czech books from the previous example, there are 4 books written in Latin. How many different ways are there to shelve these 10 books if you want to keep all the Czech books with you and all the Latin books with you?
What options do we have for how to store the books? We can put the six Czech books first and then the four Latin books, or vice versa - first the four Latin books and then the six Czech books. However, there are 6! ways to store Czech books and 4! ways to store Latin books. We use the combinatorial product rule and add these results: 6! · 4! = 17 280. Since there are two ways to store books (Czech, then Latin, and vice versa), we multiply this number by two. The total result is 17 280 · 2 = 34 560.