4 The general counting principle: An à la carte menu.

Slide 0

Hello everyone. Welcome to this excursion into combinatorics. Today we will discuss the general counting principle, a procedure that plays a key role in – as I just said – combinatorics. We will consider situations in which systematic counting is helpful.

Combinatorics has gained significance in recent years – especially in school. The reason is simple: There are many everyday situations in which it makes sense to apply knowledge of combinatorics. And this subject fits well in mathematics lessons. Many activities lend themselves well for motivating students in particular to grapple with mathematical content.

Slide 1

Educational standards for mathematics lessons in many countries emphasize the handling of data and random events.

One basis is combinatorics. It is part of mathematics in which counting procedures that address the structure and the presence of certain properties of configurations are covered and that is a key foundation for developing the theory of probability.

A key aspect is counting procedures for combinations with and without repetition as well as with and without replacement. We will very quickly see what this specifically means.

In particular, we will learn about an important counting procedure in detail, the previously mentioned “general counting principle.”

Slide 2

Let’s take a look at the educational standards for the General Certificate of Secondary Education in Germany, where combinatoric considerations are explicitly mentioned under the main idea of “number”: The students should make combinatoric observations in specific situations to determine the number of possibilities in each case.

Slide 3

Here is an example of this. Let’s assume that we roll two dice 100 times, add up the number of spots, and determine the absolute frequencies.

6 and 1 are 7, 1 and 1 are 2, 1 and 2 are 3, 4 and 6 are 10, 4 and 5 are 9, 3 and 6 are 9, 5 and 1 are 6, 5 and 6 are 11.

One hundred times is a lot; I think you trust that I did this correctly. We note the results in a table. Clearly, the sums 5, 6, and 7 occurred much more frequently than the sums 2, 3, 11, and 12.

Slide 4

This is how it looks when we transfer the results to a bar chart. You can read the results faster this way and you quickly see which results were obtained more or less frequently.

Is there a system behind this? Perhaps, but you can’t conclude that from just a couple of experiments. However, if you have each student in an entire class roll dice 100 times, then the results may be more reliable. Try it out. Doing something yourself is a wonderful basis for good mathematics.

Slide 5

Let’s roll two dice again, but this time from a combinatoric perspective. What are the possibilities for the sum of the spots from a theoretical perspective?

We obtain a perfect bar chart when we consider the results systematically and can easily calculate the relative frequencies – as you can see at the right.

In other words: Of course, the theoretical perspective is meaningful and appropriate for the experiment. In particular, it helps explain why some sums of spots occur much more frequently than others.

Slide 6

Let’s move on and this time we will flip a coin five times in a row. This is the result: tails – tails – tails – tails – tails.

What do you say about this result? Can you really obtain this result purely by chance? By all means. Unquestionably, tails can occur five times when a coin is flipped five times.

Would your students also see it this way? They could see it differently and declare the result unlikely. And not all of them can accurately distinguish between unlikely and impossible.

Slide 7

Let’s flip the coin again. How do you like this result? Might your students like this result better than the first result?

Slide 8

Now imagine that you had bet 100 euros that heads would come up at least once when you flip a coin five times. What do you think when tails comes up for the first three flips? And what do you say in the end about a comparison of the three rounds shown here? Is something there more random? It’s hard to say just like that. We probably need a perspective that is better supported by a suitable theory.

Slide 9

Here are all the possibilities, sorted neatly taking the order into account. There are 32 different results, specifically two possibilities for each flip and thus 2 times 2 times 2 times 2 times 2 equals 2⁵ equals 32 results that differ – as I said, taking the order into account.

Slide 10

This type of systematic approach is the focus of combinatorics. You can use combinatorics to determine quantities. And for something like the example just shown, where simple multiplication of the respective possibilities is sufficient, we refer to this as the “general counting principle.”

Let’s look at another typical example related to this. Here you see a combination lock with five digits. Each of these digits can be set to one of the numbers between 0 and 9.

Consequently, there are ten possibilities for the first digit, ten possibilities for the second digit, ten possibilities for the third digit, ten possibilities for the fourth digit, and ten possibilities for the fifth digit. So we clearly come up with 10 • 10 • 10 • 10 • 10 = 10⁵ = 100,000 different configurations. Of course, that’s all numbers between 0 and 99,999.

No problem, right?

Slide 11

Another example: We roll four dice with different colors. How many different possibilities are there?

This exercise is also easy and follows the same principle: For each die there are six possibilities, and so you can distinguish a total of 6 • 6 • 6 • 6 • = 6⁴ = 1,296 cases.

Slide 12

And the next example also follows the principle (and is also ideally suited for lessons). We select different outfits to wear (with a limited wardrobe). Max has three shirts, two pairs of pants, and two pairs of shoes. In how many different ways can he get dressed?

Slide 13

I think it is a simple exercise to calculate this number. This is how:

He has three shirts: one, two, three. He has two pairs of pants: one, two, one, two, one, two. And he has two pairs of shoes: one, two, one, two, ... and so on.

Altogether he has 3 times 2 times 2 equals 12 possibilities for dressing differently.

Slide 14

What we just created is a tree diagram, a way of representing data that is very fitting in this context.

Slide 15

There are many examples that are suitable for work in class, such as this three-course menu.

Which three-course meal do you prefer? How many different meals can be combined? What principle underlies this exercise?

Slide 16

Naturally, the same principle, so once again the general counting principle. You can order a total of 2 • 3 • 3 = 18 different meals. In this case as well, you can easily create a tree diagram.

Slide 17

We have thus developed a basic concept of combinatorics, specifically the general counting principle.

Imagine that you must fill n places. If there are

k₁ possibilities for place 1,

k₂ possibilities for place 2,

…

k _n possibilities for place n

then there are a total of k₁ · k₂ · … · k_n different possibilities for filling the n places.

Slide 18

Thank you for your attention and interest, and see you soon.