✖

Variations

Kapitoly: Combinatorics, Variations, Permutation, Combination, Variations with repetition, Combination with repetition, How many different PINs are there, Calculator.

We use variations when we select a certain number of objects from a set of objects, and the order in which we select these objects matters.

Deriving a formula

Let's start with a typical variation problem: the village has an annual plum dumpling eating contest. A total of seven greasy contestants advance to the final round. Calculate how many total possibilities there are for these seven participants to take the top three places.

It is important to note that in this example, the order matters. For example, if we know that Tonda, Matěj, and Koloděj will take the first three places, then this trio will generate a total of six different placements:

  • Tonda, Matěj, Koloděj;
  • Tonda, Kolodej, Matěj;
  • Matěj, Tonda, Koloděj;
  • Matěj, Koloděj, Tonda;
  • Koloděj, Tonda, Matěj;
  • Koloděj, Matěj, Tonda.

These are all different placements, and we want to calculate how many different placements we can put together when there are 7 competitors.

We use the combinatorial product rule to do this. Let's say we pick triples of the form [x1, x2, x3], where x1 is the racer who finished first, etc. Which racers can we put after x1? All of them, so we can put 7 racers after x1. Which ones can we put after x2? All of them, except the one we already put in first place, so we can put 7 − 1 = 6 after x2. Then we can put the competitors who are not in first or second place behind x3, so we have 7 − 2 = 5 options. We apply the combinatorial product rule and get the total number of possibilities: 7 · 6 · 5 = 210.

We can observe that if we want to know the number of all possibilities in the first 4 places, we can put 7 − 3 = 4 racers after x4, so the total number of possibilities is 7 · 6 · 5 · 4 = 840. What can we deduce from this?

If we have a set of n elements (7 eaters in the example here) and we select 3 elements, depending on the order, the result is equal to n · (n − 1) · (n − 2). All of them can be in the first place, one less in the next place, and so on. From this we can derive a general formula for when we select k elements from a set of n elements: the number of possibilities will be equal to n · (n − 1) · (n − 2) · … · (n − k + 1).

We modify this formula even further by using a factorial. When we look at what the factorial of seven looks like: 7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 and how we counted the number of all medal placements 7 · 6 · 5, we see some similarity. We just need to get rid of the end, i.e. we need to divide 7! by 4 · 3 · 2 · 1, which leaves us with only 7 · 6 · 5. And what is the expression 4 · 3 · 2 · 1 equal to ? It is equal to 4!.

So we can write that if we have a set of n elements, and we select a total of k elements, depending on the order, we have a total of

$$ V(k, n) = \frac{n!}{(n-k)!} $$

possibilities. If we plug the numbers from the plum race into that formula:

$$ V(3, 7) = \frac{7!}{(7-3)!}=\frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{4 \cdot 3 \cdot 2 \cdot 1} = 7 \cdot 6 \cdot 5 = 210. $$

Computer

The following calculator will calculate the number of variations for a given n and k, including the procedure.

k:n:

Solved examples

  1. Let's stay with the dumpling-eating race. How would the number of possible medal placements change if we knew that Ludva Schnitzell, who is a macho guy and always wins, came to the race? I.e. how many different medal placements are there if we have 7 competitors and Ludva is sure to win?

Again, this is a simple variation, first place is certain and of the remaining 6 competitors we are left to determine how they can fill the second and third spots. So we pick 2 elements from the 6 element set, which leads to a variation

$$ V(2, 6) = \frac{6!}{(6-2)!}=30 $$

  1. Once upon a time, when Ludva Schnitzell wasn't such a big shot, he regularly placed in the top three. How many different medal placements are there if we have 7 competitors and Ludva is sure to get a medal?

    This example differs from the previous one in that we don't know where Ludva placed; he could have placed as high as second or even third, which he is still ashamed of. Therefore, we have to calculate a total of three different variations: if Ludva had won, then if Ludva had achieved a silver medal and finally a bronze medal. Of course, each time there are only two places left where someone else can place. For example, if Ludva was second, the other participants could have placed either first or third. Thus, we count again the two-person variation of six, only we have to count it three times, for three different placements of Ludva. The number of all placements is thus equal:

    $$ 3 \cdot V(2, 6) = 3 \cdot \frac{6!}{(6-2)!} = 3 \cdot 30 = 90 $$

    Note that we can write the three before the variation as V(1, 3), because we are actually selecting one element (one particular placement) from a three-element set (three medal positions).

  2. There are a total of 20 teachers in the school. The graduation is coming up soon and we need to form a committee with the following composition: one chairman, one good chairman and one bad chairman. How many options are there in total?

    The first question we have to answer is whether the order matters - yes it does, we can throw the three teachers around again in six different ways. Now it's easy - we choose a 3-person variation from 20 elements:

    $$ V(3, 20) = \frac{20!}{17!}=6840. $$

  3. How many 3-digit numbers can we put together from the digits {0, 1, 2, 3, 4, 5}, if no digit can repeat?

    Does the order matter? Yes, it depends, 123 is a different number than 321. How many different triplets are there? That's a simple 3-digit variation of 6:

    $$ V(3, 6) = \frac{6!}{3!}=120. $$

    But we still have to subtract the variations that have a zero in the first place, because 012 is not a 3-digit number. So the question now is - how many different triples are there that start with zero? In this case, only the digits in the remaining two places are alternating (the triples are in the form [0, x2, x3]), so we are looking to see how many different pairs we can create using the numbers {1, 2, 3, 4, 5}. Again, this is easy: V(2, 5) = 5!/3! = 20. There are thus 20 triples that start with zero.

    So the total number of three-digit numbers that are made up of the digits {0, 1, 2, 3, 4, 5}, is 120 − 20 = 100.

  4. How many different three-digit numbers can we construct from the digits {1, 2, 3, 4, 5}, if no digit is allowed to repeat and the resulting number is supposed to be odd?

    The order matters because 123 is a different number than 321. We are composing a three-digit number that is odd, which means that the first two positions can have any digit, but the last position must have one of the digits {1, 3, 5}. First, we count the number of all the triplets we can put together from five digits: V(3, 5) = 5! / 2! = 60.

    Each digit will appear in the last position equally often, so if we have 5 digits, each digit will appear in the last position 60 / 5 = 12times. We have three digits {1, 3, 5} that can appear in the last place, so we have 12 different numbers that end in 1, 12 numbers that end in 3 to 12 numbers that end in 5. We apply the combinatorial sum rule and get a total of 12 + 12 + 12 = 36 possibilities.

  5. Compute x, if you know that V(2, x) = 72. In other words: we pick pairs from a set of size x and we know that we are able to pick a total of 72 different pairs. How large was the set from which we selected the pairs? Let's break it down:

    $$ V(2, x) = \frac{x!}{(x-2)!} = 72 $$

    Next, we modify:

    $$\begin{eqnarray} \frac{x!}{(x-2)!} &=& 72\\ \frac{x \cdot (x-1)\cdot(x-2)!}{(x-2)!} &=& 72 \\ x \cdot (x-1) &=&72\\ x^2-x&=&72\\ x^2-x-72&=&0 \end{eqnarray}$$

    This is already a classical quadratic equation, so we solve it using a discriminant or we can rewrite the equation in the form

    $$ (x+8)\cdot(x-9)=0 $$

    from which we can already read the solution: x1 = −8 and x2 = 9. We don't care about the negative solution because the set can't be negative in size, so the solution to the original equation is x = 9, the set had nine elements.

Sources and further reading