Your cart is empty
Permutations, variations
Let us see a few typical problems in connection with counting cases, which are similar to those we have already seen in year 10.
Example 1
Let us add \latex{12} \latex{345} and all the five-digit numbers that can be created by rearranging the digits of \latex{12} \latex{345}. What do we get?
Solution I
We have to add those distinct five-digit numbers that use all the digits \latex{1}, \latex{2}, \latex{3}, \latex{4}, \latex{5} once. The order of the digits is different in these numbers.
Let us first determine the number of five-digit numbers that can be created by using the digits \latex{1}, \latex{2}, \latex{3}, \latex{4}, \latex{5} once.
\latex{5}\latex{4}\latex{3}\latex{2}\latex{1}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\times}\latex{\times}\latex{\times}\latex{\times}Let us realise that we could get to any point in as many different ways as we could get to the previous two points together, thus by listing the number of the routes leading to the
We can choose from \latex{5} different digits for the first place. For the second place, we can only choose from \latex{4} different digits, thus we can choose \latex{5 \times 4} different digits for the first two places, because we can choose from \latex{4} different digits for the second place for every choice of the first digit. For the third place we can only choose from \latex{3} digits, thus for the first three places we can choose \latex{3} digits in \latex{5 \times 4 \times 3} different ways. For the fourth place we can choose a digit in \latex{2} different ways, thus there are \latex{5 \times 4 \times 3 \times 2} possibilities for the first four places. We can write the remaining digit in the fifth place in \latex{1} different way, thus a total of \latex{5 \times 4 \times 3 \times 2 \times 1 = 120} five-digit numbers can be created by using the five different digits once.
In the ones' place the digit \latex{5} appears as many times as the digits \latex{1}, \latex{2}, \latex{3}, \latex{4} can be ordered in the first four place values; similarly to the previous these are \latex{4 \times 3 \times 2 \times 1 = 24} cases. In the same way the other digits appear at the ones' place \latex{24} times, thus the sum of the ones is: \latex{24 \times \left(1 + 2 + 3 + 4 + 5\right) = 360}. Every digit appears at the other place values \latex{24} times in the same way, therefore the sum of the digits is \latex{360} at every place value. Based on this the sum is:
\latex{360} ones \latex{+ 360} tens \latex{+ 360} hundreds \latex{+ 360} thousands \latex{+}
\latex{+ 360} ten thousands \latex{= 3} \latex{999} \latex{960}.
\latex{+ 360} ten thousands \latex{= 3} \latex{999} \latex{960}.
So by adding the number \latex{12} \latex{345} and the five-digit numbers generated by swapping its digits the sum is \latex{3} \latex{999} \latex{960}.
Solution II
Let us list the \latex{120} five-digit numbers generated by swapping the digits of the number \latex{12 \space 345} based on the previous solution in ascending order and then in descending order below:
\latex{\begin{array}{r}12\space345 +12\space354 +12\space435 +12\space453 +...+54\space312 + 54\space321 +\\+54\space321 +54\space312 +54\space231 +45\space213 + ... + 12\space354 +12\space345.\enspace\\\hline66\space666+66\space666+66\space666+66\space666+...+66\space666+66\space666.\enspace\end{array}}
One can notice that the sum of the numbers below each other is always \latex{66\space666}.
Indeed, by subtracting the numbers consisting of the digits \latex{1}, \latex{2}, \latex{3}, \latex{4} and \latex{5} listed in ascending order from \latex{66\space666} the differences will be listed in descending order, and these will also consist of the digits \latex{1}, \latex{2}, \latex{3}, \latex{4} and \latex{5}.
The sum of the numbers listed in ascending order and in descending order together is \latex{120 \times 66\space666}. It is twice the sum in question.
Based on this the sum of the numbers that can be created from the digits of the number \latex{12\space345} is:
\latex{\left(120 \times 66 \space 666\right):2 = 3\space999\space960}.
◆ ◆ ◆
For the sake of a shorter form we introduce separate notation for the products using during the solution of the example:
The product of the positive whole numbers not greater than \latex{5} is called \latex{5} factorial. Notation: \latex{5! = 5 \times 4 \times 3 \times 2 \times 1}.
DEFINITION: If \latex{n} is a positive whole numbers, where \latex{n} is given, the product of the positive whole numbers not greater than \latex{n} is called n factorial. The \latex{0} factorial and the \latex{1} factorial are defined as \latex{1}.
Notation: \latex{n! = n \times \left(n-1\right) \times \left(n-2\right)\times ... \times 3 \times 2 \times 1}.
DEFINITION: A permutation without repetition of the elements of a set with n elements is an arrangement of the \latex{n} distinct elements. The elements are arranged, if we appoint the first, the second, … and so on the \latex{n^{th}} element. Two arrangements are the same if the same elements are at the corresponding places.
permutation without repetition
\latex{n! = n \times \left( n-1 \right)\times \left( n-2 \right)\times ... 2 \times 1}.\latex{0! = 1},\latex{1! = 1},\latex{2! = 2\times 1 = 2},\latex{3! = 3 \times 2 \times 1 = 6},\latex{4! = 4 \times 3 \times 2 \times 1 = 24},\latex{5! = 5 \times 4 \times 3 \times 2 \times 1 = 120},\latex{\vdots}\latex{n! = n \times \left( n-1\right)!}THEOREM: The number of permutations of a given set with latex{n} elements is \latex{n!}
Proof
Let us choose the elements in succession, starting with the first one.
We can choose \latex{n} different elements for the first place. For the second place we can only choose \latex{\left(n-1\right)} different elements, so we can choose \latex{n \times \left(n-1\right)} different elements for the first two places, because we can choose \latex{\left(n-1\right)} different elements for the second place for every choice of the first element. For the third place there are only \latex{\left(n-2\right)} possibilities, so we can choose \latex{3} elements in \latex{n \times \left(n-1\right) \times \left(n-2\right)} different ways for the first three places. And so on: we always have one fewer possibility to choose an element for the next place.
For the \latex{\left(n-1\right)^{\text{th}}} place we can choose an element in \latex{2} different ways, thus there are \latex{n \times\left(n-1\right)\times \left(n-2\right) \times ... \times 2} possibilities for the first \latex{\left(n-1\right)} places.
The remaining element can be written in \latex{1} different way for the \latex{n^{\text{th}}} place, thus the \latex{n} different elements can be written in a total of \latex{n \times \left(n-1\right)\times\left(n-2\right)\times ... \times 2 \times 1 = n!} different orders.
Example 2
Let us write down next to \latex{22\space233} all the distinct five-digit numbers that are generated by swapping the digits of \latex{22\space233}. What is the sum of all the digits written down?
Solution
First we try to find the number of five-digit numbers that can be created using the three digits 2 and the two digits 3. If we distinguish the three digits \latex{2} and the two digits \latex{3}, then \latex{2_1}; \latex{2_2}; \latex{2_3}; \latex{3_1}; \latex{3_2} are five distinct signs, which – based on the previous exercise – can be ordered in \latex{5!} different ways. In half of these arrangements \latex{3_1} lies somewhere before \latex{3_2} in the other half it is the other way round. The two digits \latex{3} lie in the same two places in two cases, however after ignoring the distinction these do not mean distinct cases.
In the same way all the cases, which differ only in the order of the digits \latex{2}, will count as one. The three distinguished digits \latex{2} can be ordered in \latex{3! = 6} different ways, therefore the three digits \latex{2} lie in the same three places in one sixth of the cases. Thus the number of the five-digit numbers that can be created using the three digits \latex{2} and the two digits \latex{3} is:
\latex{\frac{5!}{2! \times 3!}=10}.
The sum of the digits in such a five-digit number is: \latex{2 + 2 + 2 + 3 + 3 = 12}, thus the sum of all the digits written down is: \latex{12 \times10 = 120}.
DEFINITION: If there is an element occurring more than once, an arrangement of the elements is called a permutation with repetition.
By following the method of the solution of example \latex{2} the following theorem can be proven (the proof is not given here):
THEOREM: If there are \latex{p_1}; \latex{p_2}; \latex{…} ; \latex{p_k} identical elements among \latex{n} elements, \latex{p_1+ p_2+ …+ p_n= n}, then these elements can be ordered in
\latex{\frac{n!}{p_1! \times p_2 \times ... \times p_k!}}
different ways.
◆ ◆ ◆
Example 3
How many non-negative whole numbers are there in the base-\latex{3} number system that have at most five digits?
Solution
The number of numbers with at most five digits can be obtained if we choose five places from the digits \latex{0}, \latex{1} and \latex{2}. (If we write \latex{0} in the first place, the number will have at most four digits and so on; \latex{0} can be written in all the places.) We can choose from \latex{3} different digits for both the first and the second places. As we can write any of the three digits for the second place after any of the \latex{3} digits written for the first place, thus we can choose digits for the first two places in \latex{3 \times 3} different ways. Continuing like this there are also \latex{3} possibilities for the third place, thus there are a total of \latex{3 \times 3 \times 3} possibilities for the first three places, there are a total of \latex{3 \times 3 \times 3 \times 3} possibilities for the first four places, and digits can be written to the five place values in \latex{3\times3\times3\times3\times3 = 35 = 243} different ways.
Note: The greatest five-digit base-\latex{3} number is \latex{22222_3}, thus together with \latex{0} there are \latex{22222_3 + 1 = 100000_3} non-negative whole numbers with at most five digits in the base-\latex{3} number system, which is \latex{3^5} in the decimal number system.
\latex{3}\latex{3}\latex{3}\latex{3}\latex{3}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\times}\latex{\times}\latex{\times}\latex{\times}In the example we had to choose \latex{5} out of the \latex{3} different digits so that we were allowed to choose one digit several times, and the number of possibilities was \latex{3^5} with respect to the order of choices. In general:
DEFINITION: If we choose \latex{k} elements out of \latex{n} elements with respect to the order (one type of element can be chosen several times), the \latex{k}-element variation with repetition of \latex{n} elements is obtained.
THEOREM: The number of the \latex{k}-element variations with repetition of \latex{n} elements is \latex{n^k}.
Proof
The \latex{k}-element variation with repetition of \latex{n} elements is obtained, if we choose out of \latex{n} elements to \latex{k} places in succession so that one element can occur several times. We can choose an element for every place in \latex{n} different ways, so for the first two places in \latex{n \times n} different ways, for the first three places in \latex{n \times n \times n} different ways, and so on for the \latex{k} places in \latex{n^k} different ways.
Example 4
How many positive whole numbers with exactly five digits are there in the base-\latex{3} number system?
Solution
In the case of a number with exactly five digits there cannot be \latex{0} in the first place value from the left. So only \latex{2} different digits can be written for this place value in the base-\latex{3} number system. The digit \latex{0} can be written for the other four place values, thus there are \latex{3} possibilities for these, therefore there can be \latex{2 \times 3^4 = 162} different five-digit numbers.
\latex{2}\latex{3}\latex{3}\latex{3}\latex{3}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\times}\latex{\times}\latex{\times}\latex{\times}Example 5
How many four-digit positive whole numbers are there in the decimal number system, which contain distinct digits and there is no \latex{0} in them?
Solution
The number of four-digit numbers consisting of different digits can be obtained if we choose four different digits from the digits \latex{1, 2, 3, 4, 5, 6, 7, 8, 9} to four place values.
We can choose a digit in \latex{9} different ways for the first place and in \latex{8} different ways for the second place. As we can write any of the remaining \latex{8} digits for the second place after any of the \latex{9} digits written for the first place, thus we can choose digits to the first two places in \latex{9 \times 8} different ways. Continuing like this there are only \latex{7} possibilities for the third place, thus there are \latex{9 \times 8 \times 7} possibilities for the first three places, and we can write digits for the first four places in
\latex{9}\latex{8}\latex{7}\latex{6}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\times}\latex{\times}\latex{\times}\latex{9 \times 8 \times 7 \times 6 =\frac{9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2\times 1}{5\times4\times3\times2\times1}=\frac{9!}{5!}=\frac{9!}{\left(9-4\right)!}=3024}
different ways.
In the example we had to choose \latex{4} digits from \latex{9} different digits with respect to the order so that we were allowed to choose every element at most once. We can generalise it:
DEFINITION: If we choose \latex{k} elements out of \latex{n} different elements with respect to the order (arrangement), we obtain a \latex{k}-element variation without repetition of \latex{n} different elements (\latex{0 \leq k \leq n} integers).
THEOREM: The number of the \latex{k}-element variations without repetition of \latex{n} different elements is:
\latex{n \times \left( n-1 \right) \times \left( n-2 \right) \times ... \times \left( n-k+1 \right)=\frac{n!}{\left( n-k \right)!}}.
Proof
The \latex{k}-element variation without repetition of n different elements is obtained, if we choose from \latex{n} different elements to \latex{k} places in succession. We can choose an element for the first place in n different ways, can choose elements to the second place in \latex{(n-1)} different ways, thus for the first two places in \latex{n \times \left( n-1 \right)} different ways, for the first three places in \latex{n \times \left(n-1\right)\times \left(n-2\right)} different ways, and so on we can choose elements for the first \latex{k} places in
\latex{n \times \left( n-1 \right)\times \left( n-2 \right)\times ... \times \left( n-\left(k-1 \right) \right)}
different ways.
By multiplying through by \latex{\left(k -1\right)!} the result appearing in the statement of the theorem is obtained:
\latex{n \times\left(n-1\right)\times\left(n-2\right)\times...\times\left(n-k+1\right)=}
\latex{=\frac{n \times\left(n-1\right)\times\left(n-2\right)\times...\times\left(n-k+1\right) \times \left(n-k \right)\times\left(n-k-1\right)\times ... \times2 \times1}{\left(n-k\right)\times\left(n-k-1\right)\times...\times2\times1}=}
\latex{=\frac{n!}{\left(n-k\right)!}}.
Example 5
- How many positive whole numbers with exactly four digits are there in the decimal number system, which contain distinct digits?
- How many positive whole numbers with exactly four digits are there in the decimal number system, which contain distinct digits and the digits are in ascending order when reading from left to right?
Solution (a)
We can obtain the number of numbers with exactly four digits and consisting of different digits, if we choose four different digits from the digits \latex{0, 1, 2, 3, 4, 5, 6, 7, 8, 9} to four place values so that \latex{0} cannot be in the first place value from left.
We can choose a digit in 9 different ways for the first place, as 0 cannot appear here. We cannot choose the digit already chosen for the first place to the second place, but 0 can be chosen here, thus we can choose a digit in 9 different ways again.
\latex{9}\latex{9}\latex{8}\latex{7}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\uarr}\latex{\times}\latex{\times}\latex{\times}As we can write any of the remaining \latex{9} digits for the second place after any of the \latex{9} digits written to the first place, therefore we can choose digits for the first two places in \latex{9 \times 9} different ways.
There are only \latex{8} possibilities for the \latex{3}rd place, only \latex{7} possibilities for the fourth place, thus we can write digits for the four places in \latex{9 \times 9 \times 8 \times 7 = 4536} different ways.
Solution (b)
By writing the digits in ascending order the number can have four digits only if there is no digit \latex{0} in it (otherwise it should start with it).
We can choose four different digits out of the digits \latex{1, 2, 3, 4, 5, 6, 7, 8, 9} in \latex{9 \times 8 \times 7 \times 6} different ways. We chose the same four digits \latex{4!} times, since the order of the digits also mattered.
These can be written in ascending order in one way, thus the number of four-digit numbers consisting of different digits in which the order of the digits is ascending from left to right is:
\latex{\frac{9 \times 8 \times 7 \times 6}{4!}=126}.
Exercises
{{exercise_number}}. Ann, Beatrice, Cissy and Dana went to the cinema together. They bought tickets next to each other. On the way to the cinema Beatrice and Cissy had a quarrel.
- In how many different ways could the girls sit on the four seats next to each other?
- In how many different ways could the girls sit on the four seats next to each other, if Beatrice and Cissy did not sit next to each other?
- After the cinema they sat down to a round table in a pizza restaurant. In how many different ways could they sit down, if Beatrice and Cissy made up in the meantime?
- In how many different ways could they sit down to the round table, if Beatrice and Cissy still did not want to sit next to each other?
{{exercise_number}}. We roll a die four times in succession and we write down the results next to each other. Thus a four-digit number is obtained. How many different four-digit numbers can we get? Give the sum of all the four-digit numbers obtained this way.
{{exercise_number}}. How many three-digit natural numbers divisible by three can be created from the digits \latex{0}, \latex{1}, \latex{3}, \latex{5}, \latex{7}, if there are no repeating digits in the numbers?
{{exercise_number}}. How many positive divisors do the following numbers have: \latex{360}, \latex{4800}, \latex{5484}?
{{exercise_number}}. In how many different ways can we choose the places of \latex{8} castles on the chessboard so that no two capture each other? (A castle can capture the chess figures in the same row or column.)
{{exercise_number}}. Create all the four-digit positive whole numbers that contain one \latex{1}, one \latex{2} and two \latex{0}s. What will be the sum of these numbers?
{{exercise_number}}. Let us call a number a lucky number, if it is true for all its digits that a digit is greater than the preceding one (the one to the left). How many lucky numbers are there between \latex{4000} and \latex{5000}?
{{exercise_number}}. Sophie gave a phone number to Bridget. Bridget heard the following: seven hundred and fourteen, two hundred and ninety. She called the number \latex{714}-\latex{290}, but there was no answer. She became uncertain: fourteen and forty sound quite similar, just like ninety and nineteen; it is possible that she misunderstood these. If she heard the other numbers correctly, at most how many numbers does she need to call until she finds the correct number?
{{exercise_number}}.
a) How many five-digit positive whole numbers divisible by \latex{25} are there in the decimal number system?
b) How many five-digit positive whole numbers are there in the decimal number system that contain the digit \latex{3}?
Puzzle
\latex{100} prisoners are transported on a ship to a prison island from where it is impossible to escape. They are sentenced to life imprisonment, but they have one chance to be released. The prisoners are taken out for a walk into a small garden of the prison. The prisoners are chosen for the walk at random, only one prisoner at once. If at some point a prisoner can tell for sure that everyone has already been out for a walk, then all of them will be released. There is a lamp in the garden which can be switched on or off by the prisoners when they are walking. The prisoners are allowed to talk on the ship heading to the island, they can come up with a strategy, however they are not allowed to keep in touch in any way once on the island, and they cannot see the lamp from their cells.
Is there a way that they can be released?