5 Permutations and what they have to do with horse racing.

Slide 0

Hello and welcome to a new episode in which we talk about math. Today’s topic is permutations. They are an important concept not only in combinatorics and probability theory, but also in algebra. We’re thus talking about a fundamental mathematical concept. However, this concept also has important applications. In particular, we will see what links permutations with horse racing.

Slide 1

What is a permutation? This is a key concept of combinatorics and one of its principles. Let’s begin with an example to understand the concept and its content.

Here is a whiteboard and here are the children Ann, Esi, Ayi, and Ben. They want to solve a math problem together. How many possibilities do they have for standing next to each other at the whiteboard?

To determine this number, we need a new mathematical tool. But don’t worry; it’s a very simple tool.

Slide 2

There are four children, and so there are initially four places for them. We number them and you can see the numbers above the photo at the right.

For the position numbered 1 there are four possibilities.       

For the position numbered 2 there are three possibilities.     

For the position numbered 3 there are two possibilities.        

For the position numbered 4 there is just one option left.      

The result is thus 4 times 3 times 2 times 1 equals 24. Thus there are 24 different possibilities.

Slide 3

Let’s look at another situation that follows the same basic idea. Hedwig was in San Francisco and took a lot of photos. She would like to hang three photos in the hallway, but she isn’t sure what order she should hang them in.

How many possibilities does she have for arranging the photos?

Slide 4

Here are all possibilities. You see that this exercise is also based on the principle of permutation.

Slide 5

Clearly, again there are ...

            … three possibilities for the place numbered 1

            … two possibilities for the place numbered 2

            … and only one possibility for the place numbered 3

Thus, there are 3 • 2 • 1 = 6 possibilities for arranging three photos next to one other.

Slide 6

How many possibilities exist for a group photo with these people? Once again we recognize the same principle. There are five people, and so there are 5 • 4 • 3 • 2 • 1 = 120 different possibilities for arranging them. Yes, I know. You don’t actually have to add the “times 1”, because the result doesn’t change anymore. But that’s how it’s done in mathematics.

Slide 7

We have already mentioned above that the principle is called permutation. This is the general form:

If a set has n elements, then there are n • (n-1) • (n-2) • ... •1 different possibilities for arranging these elements. Each possible arrangement is called a permutation.

We write n • (n-1) • (n-2) • ... • 1 =: n! for short. 

n! is spoken as “n factorial.”

Slide 8

Sometimes, for example, in algebra, you see it as follows:

If K is a finite set, then each bijective mapping of set K onto itself is called a permutation.

What is the connection between these two views? It’s quite simple. K is a finite set, thus has n elements for a natural number n.

A bijective function pairs one element of K exactly and invertibly to each element of K.

Each of these functions thus determines one permutation since all elements occur exactly once as image and inverse image under the function (one-to-one).

Slide 9

So this is how we solve Hedwig’s problem:

We label the photos with 1, 2, and 3 and the locations on the wall also with 1, 2, and 3. Each possibility is thus a bijective mapping of the set K = {1, 2, 3} onto itself.

In this example, the photo numbered 1 remains in location 1 and photos 2 and 3 exchange locations.

Slide 10

Let’s calculate: How many mappings of this type are there? Even after a low n, there are very many. You see in this list that the number n! becomes very large very quickly.

Slide 11

And here’s the same situation again: Twenty horses are running in a horse race. How many different race results are possible if all horses cross the finish line? A whole lot and precisely 2.432902 •10¹⁸, a number with 19 places, which is already in the quintillions.

But regardless of the exact numerical result, what is important is that the same basic idea underlies this example as the previous example.

Slide 12

Do you remember? In the course of this “Sparking conversations about math” series, we have worked with dice and coins, with clothing and food, with photos and horses. Are there other suitable materials for representing the exercises in combinatorics? Yes, there is a very important tool, and that’s an urn filled with suitable balls.

In an urn (or in a small bag, by all means opaque) there are balls that differ only in their color or their numbering (in any case, not in their shape). The advantage of the urn model is that many of the random experiments usually considered go back to this model.

This urn has 20 balls and is therefore suitable, for example, for simulating a race with 20 horses. You need only to take out the balls in succession without looking and obtain a possible race result. Well, one and perhaps two or three. For practical reasons certainly not quintillions.

Slide 13

Especially at school, it is therefore better to work with lower numbers. What easily understandable problems can you simulate using such an urn? Take a moment to think. 

On the left side you see an urn with three different-colored balls. You can use it, for example, to simulate Hedwig’s problem of the three photos. In the middle there is an urn with six balls, numbered from 1 to 6. Clearly you can simulate a roll of the die using this urn. On the right is a box with four balls labeled A, B, C, and D. You can use this box, again, only as an example, to simulate the positioning of the four children at the whiteboard. But there are still more possibilities. If A and B are interpreted as heads and C and D as tails, then we can also use this urn to simulate flipping a coin.

The method is always the same: We draw balls from this urn without looking inside.

Slide 14

Let’s go back to the permutation because at this point, we’re still missing a method for representing the results. Here it is: Once more, a tree diagram is very suitable for the representation.

There is however one characteristic: Let’s assume that we’re working with n elements and, as always, n is a natural number. Then there are always multiple possibilities for the selection of the first n-1 elements. By contrast, for the last element, the nth element, there is only one option left.

Slide 15

That’s all for today. Thank you for listening to me, for being here and for your interest.